大學計算機基礎讀書筆記

1、計算機計算機的應用 :數(shù)值計算，數(shù)據(jù)處理，自動控制，計算機輔助系統(tǒng)(CAD,CAM,CBE,CAT,CAI)，人工智能，通信和電子商務（數(shù)值計算又稱科學計算；數(shù)據(jù)處理又稱信息處理；自動控制又稱過程控制，包括檢測過程和控制過程;計算機輔助設計 CAD(Computer Aided Design)，降低了設計人員的工作質(zhì)量，提高了設計的效率和質(zhì)量，節(jié)約了設計成本；計算機輔助制造 CAM(Computer Aided Manufacturing)提高產(chǎn)品質(zhì)量，降低生產(chǎn)成本和勞動強度，縮短生產(chǎn)周期 ;計算機輔助教育 CBE(Computer Based Education)包括計算機輔助測試 CAT(

2、Computer Aided Test) 和計算機輔助教學 CAI(Computer Assisted Instruction) ，提高了教學質(zhì)量；人工智能 AI(Artificial Intelligence), 如專家系統(tǒng)等，可以對原始數(shù)據(jù)進行分析決策；計算機網(wǎng)絡是計算機技術(shù)與通訊技術(shù)相結(jié)合的產(chǎn)物，提高了通信的速度與效率，降低了軟件與硬件的使用費用，提高了計算機系統(tǒng)的可靠性）計算機的特點：運算速度快，計算精度高，記憶力強，具有邏輯判斷能力，自動化程度高1946 年 2 月，世界上第一臺電子計算機 ENIAC誕生于美國賓州大學。計算機代別劃分依據(jù)： 邏輯元器件。第一代計算機： 1946195

3、8 電子管。第二代計算機： 19581964 晶體管。第三代計算機： 19651971 中，小規(guī)模集成電路。 第四代計算機： 1972至今 大規(guī)模和超大規(guī)模集成電路。英國科學家： 阿倫·圖靈：圖靈機，建立計算機理論模型。匈牙利科學家：馮·諾依曼：計算機之父。根據(jù)計算機的應用范圍分類：專用計算機和通用計算機。根據(jù)數(shù)據(jù)的處理方式分類：數(shù)字計算機，模擬計算機，數(shù)字模擬混合計算機。 根據(jù)計算機的規(guī)模和功能強弱分類：巨型機，小巨型機，大型主機，小型機，工作站，個人計算機計算機系統(tǒng)：硬件系統(tǒng)和軟件系統(tǒng)。硬件系統(tǒng)：運算器，控制器，存儲器，輸入設備，輸出設備。軟件系統(tǒng)：系統(tǒng)軟件，應用軟件。

4、計算機系統(tǒng)層次結(jié)構(gòu)：應用軟件層實用軟件層操作系統(tǒng)層硬件層數(shù)制：按進位的原則進行計數(shù)，進位計數(shù)制位權(quán)：一種進制中某個位置上的單位值十進制： 0，1， ,9,逢十進一 ,基數(shù)為 10。二進制： 0，1，逢二進一，基數(shù)為2。二進制的優(yōu)點：便于實現(xiàn)、運算簡單、工作可靠、方便邏輯運算、物理元器件容易制造、運算規(guī)則少。八進制： 0，1，2， ,7,逢八進一，基數(shù)為 8。 十六進制： 0，1， ,9,A,B,C,D,E,F,逢十六進一，基數(shù)為 16。二進制八進制十進制十 六 進二進制八進制十進制十 六 進制制000000010001088000111110011199001022210101210A0011

5、33310111311B010044411001412C010155511011513D011066611101614E011177711111715FN 進制轉(zhuǎn)換為十進制：展開多項式，各項相加。 （注意位權(quán)比位數(shù)少一） 。十進制轉(zhuǎn)換為 N 進制：整數(shù)：將十進制整數(shù)連續(xù)的除以N，記下每次的余數(shù)，直到商為 0，倒排余數(shù)。 小數(shù)：將十進制小數(shù)連續(xù)的乘以N，記下每次的整數(shù)，直到十進制小數(shù)為0 或滿足進度為止，正排整數(shù)。二進制轉(zhuǎn)換為八進制的方法：從小數(shù)點開始，每3 位一組，不足3 位的用 0 補齊，每一組用一個八進制數(shù)表示。二進制轉(zhuǎn)換為十六進制方法：從小數(shù)點開始，每4 位一組，不足4 位的用 0 補齊

6、，每一組用一個十六進制數(shù)表示。八進制（十六進制）數(shù)轉(zhuǎn)換為二進制數(shù)方法：每位八進制數(shù)（十六進制數(shù)）用3（ 4）位二進制數(shù)表示，刪除兩端無意義的 0。機器數(shù)：正負號用數(shù)字表示的數(shù)。 0 為正， 1 為負。真值：與機器數(shù)對應的數(shù)學中的數(shù)。定點整數(shù)：將小數(shù)點的位置約定在機器數(shù)的末端。補0 為符號位后面。定點小數(shù)：將小數(shù)點的位置約定在符號位的右側(cè)。補0 為數(shù)值后面。浮點數(shù)：將一個數(shù)表示為尾數(shù)和階碼。階碼用定點整數(shù)，尾數(shù)用定點小數(shù)。與科學計數(shù)法類似。原碼：整數(shù)含 0 的符號位為 0，負數(shù)含 0 的符號位為 1.數(shù)值部分為對應數(shù)的絕對值。 0 的原碼有兩種編碼，00000000（0.0000000），100

7、00000（ 1.0000000）。優(yōu)點：與真值轉(zhuǎn)換簡單。缺點：運算不方便且有錯誤。 8 位定點整數(shù)原碼的表示范圍： -127-+127反碼：正數(shù)含 0 的反碼與原碼一樣； 將負數(shù)含 0 原碼除符號位外， 每位變反。 0 的反碼有兩種編碼00000000（ 0.0000000）， 11111111（1.1111111） 反碼的反碼為原碼。補碼：正數(shù)含 0 的補碼與原碼一樣；將負數(shù)的反碼末位加 1，注意進位。0 的補碼只有 1 種。00000000（ 0.0000000）正數(shù)的原碼、反碼、補碼均相同。補碼的補碼為原碼。先原碼再反碼后補碼。求補：包括符號位在內(nèi)，每位變反，末位加1。對某個數(shù)的補碼求

8、補即可得到該數(shù)相反數(shù)的補碼。規(guī)格化浮點數(shù)：提高了存儲的精度。階碼采用定點整數(shù)補碼，尾數(shù)采用定點小數(shù)補碼。對于整數(shù)，規(guī)格化就是將小數(shù)點移到數(shù)值部分第一個1 的左側(cè)，對于負數(shù)而言就是將小數(shù)點移到第一個0 的右側(cè)。ASCII美國國家標準信息交換碼。7 位 ASCII碼又稱基本 ASCII碼，用 7 位二進制表示128 個字符編碼，包括33 個控制字符。常用字符代碼由小到大：空格（32）、數(shù)字（ 0 的代碼為 48）、大寫字母（ A 的代碼為 65）、小寫字母（ a 的代碼為 97）。小寫字母的代碼比對應大寫字母的代碼大32。8 位 ASCII碼又稱擴展 ASCII碼，用 8 位二進制表示 256 種

9、，其中 0-127 即為前面的 128 個基本 ASCII碼，特點是最高位為0； 128255 是擴展部分，特點是最高位為 1。漢字編碼：國標碼：中國制定的用于計算機系統(tǒng)間交換漢字信息時使用的編碼。輸入碼：利用鍵盤輸入漢字的編碼。機內(nèi)碼：計算機內(nèi)部存儲、處理和傳輸漢字的編碼。字型碼：表示漢字形狀的編碼。 （點陣字型：將一個漢字均勻的分成若干行、若干列，形成一個點陣。）CPU 與內(nèi)存構(gòu)成主機。主機與外部設備股票擬共同構(gòu)成了計算機硬件系統(tǒng)。外存既是輸入設備又是輸出設備。存儲器包括內(nèi)存與外存?？刂破髋c運算器構(gòu)成了中央處理器CPU。計算機的主機和外部設備之間通過接口電路（簡稱接口）連接。運算器：算數(shù)運

10、算、邏輯運算?？刂破鳎嚎刂聘鞑考f(xié)調(diào)工作。存儲器：保存程序和數(shù)據(jù)，分為內(nèi)存和外存。內(nèi)存：可以與 CPU（運算器 +控制器）直接交換信息，保存正在處理的數(shù)據(jù)和正在執(zhí)行的程序。內(nèi)存主要包括隨機存儲器RAM(Random Access Memory)和只讀存儲器 ROM（Read Only Memory）兩類。 RAM 可以進行讀取和寫保存兩種操作，但斷電時信息丟失。ROM 只能進行讀操作，不能執(zhí)行寫操作，但是斷電時信息不丟失。ROM 主要保存最基本的固定不變的程序和數(shù)據(jù)。ROM 容量 RAM。通常所說的內(nèi)存容量指RAM。RAM 分為動態(tài)隨機存儲器DRAM 和靜態(tài)隨機存儲器SRAM。DRAM 存儲密

11、度高、存取速度慢、需要定期刷新。 SRAM存儲密度低、存取速度快、不需要刷新。存儲單位有：位（bit）、字節(jié)（ Byte）、字（ Word）。位是存儲設備的最小存儲單位存儲一位二進制的存儲設備。字節(jié)是內(nèi)存的最小編址單位，即每個字節(jié)都有唯一的一個地址，一般由連續(xù)的 8 位構(gòu)成。CPU一次能夠處理的連續(xù)字節(jié)稱為字。 字長有 8 位，16 位，32 位， 64 位。字長越長， CPU的處理速度越快。存儲容量：單位：，。，外存的功能：保存需要長期存儲的內(nèi)容和擴充內(nèi)存容量。斷電時，外存中內(nèi)容不丟失。 CPU 不能直接訪問外存。常用外存：軟盤存儲器、硬盤存儲器、光盤存儲器、移動存儲器（U 盤）、Cache

12、高速緩存 L1，L2、指令存儲器、寄存器等。軟盤存儲器：磁道：每個同心圓。扇區(qū)：每個磁道被分成相同數(shù)目的區(qū)段，每個區(qū)段就是扇區(qū)。一個扇區(qū)的容量為512B，即 0.5KB 。面數(shù) * 每面磁道數(shù) * 每磁道扇區(qū)數(shù) *512B。硬盤存儲器：分為固定式和可移動式兩種。容量=柱面數(shù) * 每柱面容量 =柱面數(shù)* 盤面數(shù) * 每磁道容量 =柱面數(shù) * 盤面數(shù) * 每磁道扇區(qū)數(shù) *512B。光盤存儲器：光盤主要包括 CD和 DVD兩種，CD的容量通常為 600MB 左右，而 DVD 的容量通常都在 4.7GB 以上。 CD緊湊光盤， CD有 CDROM、CDR、CDRW。DVD 是數(shù)字多功能光盤或數(shù)字激光視

13、盤的簡稱，包括 DVDROM、DVDR、DVDRW 等。 U盤存儲器特點：不使用驅(qū)動器，節(jié)省開支；使用的是 USB 接口，無需外接電源，支持即插即用和熱插拔；存取速度比軟盤快得多； 體積非常小且很輕， 便于攜帶；防震性能好。 為了滿足用戶對存儲系統(tǒng)速度快、價格低和容量大的需求，存儲系統(tǒng)采用了層次結(jié)構(gòu)。Cache 是與 CPU 和內(nèi)存直接交換信息的高速緩沖存儲器（簡稱高速緩存），其讀寫速度遠高于內(nèi)存。 Cache存儲系統(tǒng)由 Cache和內(nèi)存構(gòu)成，目的：提高CPU訪問內(nèi)存的速度。虛擬存儲系統(tǒng)由內(nèi)存和外存（通常使用硬盤存儲器）構(gòu)成，目的：擴大內(nèi)存的容量。輸入設備：負責將計算機外部的信息轉(zhuǎn)換為計算機能

14、夠識別的二進制形式并保存到計算機的內(nèi)存中。常見的輸入設備：鍵盤、鼠標器、掃描儀、數(shù)碼相機（DC）、數(shù)碼攝像機（ DV）、麥克、光筆、條形碼閱讀機和觸摸屏等。鍵盤：字符輸入設備。輸出設備：負責將計算機內(nèi)部的二進制信息轉(zhuǎn)換為人或其他設備能夠識別的形式并輸出。常見的輸出設備：顯示器、打印機、音箱、繪圖儀等。外存既是輸入設備又是輸出設備。計算機硬件的各部分之間通過總線相互傳輸信號。 總線：計算機中實現(xiàn)各部分之間通信的公共通道。 根據(jù)傳輸信號功能的不同，總線分為數(shù)據(jù)總線、地址總線和控制總線 3 種。 數(shù)據(jù)總線 DB：傳輸數(shù)據(jù)信息的雙向總線。地址總線 AB：傳輸?shù)刂沸畔⒌膯雾椏偩€。 控制總線 CB：傳輸

15、CPU發(fā)往其他部件的控制信息， 或傳輸其他部件發(fā)給 CPU的狀態(tài)和請求等信息?？刂瓶偩€中某個線是單向的，但總體是雙向的。 根據(jù)層次的不同，常見的：片內(nèi)總線、系統(tǒng)總線和外部總線 3 種。 接口：輸入輸出設備接口的簡稱。也稱為輸入輸出適配器，功能：連接主機和外設并實現(xiàn)兩者之間數(shù)據(jù)的傳輸。用接口的目的：解決主機和外設的差異并使兩者協(xié)調(diào)工作的功能。軟件分為系統(tǒng)軟件和應用軟件。系統(tǒng)軟件：用于管理計算機系統(tǒng)的軟、 硬件資源、控制計算機系統(tǒng)運行、維護計算機系統(tǒng)的軟件的集合。主要包括：操作系統(tǒng)、計算機語言處理程序、數(shù)據(jù)庫管理系統(tǒng)和服務程序4類。操作系統(tǒng)（ OS） 計算機語言處理程序：計算機語言包括：低級語言和

16、高級語言。低級語言：包括機器語言和匯編語言。機器語言：能直接執(zhí)行、執(zhí)行速度快、編程效率低和不通用的特點。匯編語言：執(zhí)行速度快、不能直接執(zhí)行、編程效率低（但比機器語言效率高）和不通用的特點。高級語言：編程效率高、通用、不能直接執(zhí)行和執(zhí)行速度慢的特點。數(shù)據(jù)庫管理系統(tǒng)服務程序計算機犯罪：利用計算機進行的犯罪。特點：智能性、隱蔽性、危害性、廣域性、低齡化、訴訟困難性、司法滯后性。計算機病毒是程序。 黑客是人。防火墻防黑客。 殺毒針對程序。計算機病毒特點： 傳染性、潛伏性、隱蔽性、破壞性、寄生性、針對性、不可預見性。預防計算機病毒應從管理制度和技術(shù)手段入手。在技術(shù)上可以安裝防毒卡和防毒軟件。病毒的檢測有

17、手工檢測和自動檢測。殺毒有手工殺毒和自動殺毒。沒有一種防毒軟件可以查殺所有的病毒。第 2 章操作系統(tǒng)基礎操作系統(tǒng)（ Operating System，OS）：直接控制和管理計算機系統(tǒng)的軟、硬件資源，合理的組織計算機的工作流程，方便用戶充分而有效的使用這些資源的程序集合。操作系統(tǒng)是軟件，而且是系統(tǒng)軟件，由一組程序組成；功能：管理計算機系統(tǒng)內(nèi)的各種資源，組織多道程序運行；是用戶和計算機之間通信的橋梁，為用戶提供良好的界面，以方便用戶使用計算機，并擴充硬件功能。操作系統(tǒng)的史前時代：手工操作。程序設計全部采用機器語言，沒有操作系統(tǒng)，人們采用手工操作方式來控制計算機的基本功能。慢速的手工操作與快速的 C

18、PU之間出現(xiàn)了矛盾，另一方面 CPU與輸入輸出設備之間速度不匹配。操作系統(tǒng)的雛形：監(jiān)督程序（早期批處理）。單道批處理分為聯(lián)機批處理和脫機批處理。聯(lián)機批處理：由CPU直接控制作業(yè)輸入與輸出。脫機批處理：加設的“衛(wèi)星機”專門處理輸入與輸出?，F(xiàn)代意義上操作系統(tǒng)的出現(xiàn)：多道批處理。通道、中斷和緩沖技術(shù)的使用使得多道程序的并發(fā)執(zhí)行稱為可能。優(yōu)點：在內(nèi)存中總有多道程序等待運行，系統(tǒng)資源得到比較充分的利用。缺點：作業(yè)平均周轉(zhuǎn)時間長，用戶無法干預程序的執(zhí)行，沒有交互能力。操作系統(tǒng)步入實用化：分時操作系統(tǒng)。在分時操作系統(tǒng)中，用戶通過終端設備與計算機交互作用來運行自己的作業(yè)。多用戶分時系統(tǒng)是當今計算機系統(tǒng)中使用最

19、普遍的一類操作系統(tǒng)。為了實時的對特定任務進行可靠處理， 人們又開發(fā)出實時系統(tǒng)。 實時系統(tǒng)具有專用性， 不同的實時系統(tǒng)有不同的應用領(lǐng)域?，F(xiàn)代操作系統(tǒng)的發(fā)展批處理操作系統(tǒng)： “單道”：一次只能有一個作業(yè)裝入計算機系統(tǒng)的內(nèi)存運行?！岸嗟馈保阂淮卧试S多個作業(yè)同時裝入內(nèi)存，使 CPU輪流的執(zhí)行多個作業(yè)。單道批處理系統(tǒng)：大大減少了人工操作的時間，提高了機器的利用率，但是 CPU的利用率很低。多道批處理系統(tǒng)：具有系統(tǒng)資源利用率高和作業(yè)吞吐量大的優(yōu)點，缺點：用戶作業(yè)的等待時間長，沒有交互能力，用戶無法干預自己作業(yè)的運行。分時操作系統(tǒng)：多個用戶分享使用同一臺計算機。將 CPU時間劃分成若干個片段，每個時間段稱為

20、時間片，操作系統(tǒng)以時間片為單位輪流為每個終端用戶服務。 每個用戶輪流使用其中的一個時間片。分時操作系統(tǒng)的特征： 交互性、及時性、獨占性、多路性。多路性提高了系統(tǒng)資源利用率。節(jié)省了開支。分時操作系統(tǒng)和多道批處理系統(tǒng)有 3 個方面的差異：基本目標的不同；提交給系統(tǒng)的作業(yè)性質(zhì)上；對于充分使用系統(tǒng)資源而言。實時操作系統(tǒng)主要特征：高響應性、高可靠性、高安全性。單用戶操作系統(tǒng)根本特征：一個用戶獨占計算機系統(tǒng)資源，系統(tǒng)所有的軟、硬件資源都為一個用戶服務，系統(tǒng)單獨的執(zhí)行該用戶提交的一個任務。網(wǎng)絡操作系統(tǒng)：交換數(shù)據(jù)、實現(xiàn)信息交換、資源共享的系統(tǒng)。網(wǎng)絡操作系統(tǒng)是基于計算機網(wǎng)絡的，它負責網(wǎng)絡管理、網(wǎng)絡通信、資源共享

21、和系統(tǒng)安全等工作。操作系統(tǒng)的主要特征：并發(fā)性：指 2 個或 2 個以上的事件或活動在同一時間間隔內(nèi)發(fā)生，交替進行。共享性：系統(tǒng)中的資源可以被多個用戶共同使用。操作系統(tǒng)的功能： CPU管理（計算機系統(tǒng)中最重要的資源是 CPU，系統(tǒng)以進程為單位對 CPU分配和運行，對 CPU的管理可歸結(jié)為對“進程”的管理，進程指正在執(zhí)行的程序） 存儲管理（管理內(nèi)存資源）設備管理（輸入輸出設備）文件管理（針對系統(tǒng)中的信息資源管理，計算機的程序和數(shù)據(jù)通常以文件的形式存放在外部存儲器上，需要時再將它們載入內(nèi)存）用戶接口（命令接口、程序接口、圖形用戶接口）現(xiàn)代主流操作系統(tǒng)簡介：Windows 操作系統(tǒng)：當前個人微型計算機

22、中應用最廣泛的一種操作系統(tǒng)。1990年 5 月 Windows3.0 版， 1995 年 8 月 24 日 Windows95 逐步取代了 DOS系統(tǒng)， 2000 年 Windows2000， 20XX年 Windows XP。Windows 操作系統(tǒng)成功的特點： 易學易用的面向?qū)ο蟮膱D形用戶界面； 支持多任務多窗口；即插即用功能；支持多媒體技術(shù)；內(nèi)置網(wǎng)絡和通信功能。UNIX 操作系統(tǒng)： UNIX 系統(tǒng)正式發(fā)布于 1974年，1975 年發(fā)布的第 6 版中引入了多道程序技術(shù)， 這時 UNIX系統(tǒng)才成為真正的多用戶分時系統(tǒng)。Linux操作系統(tǒng)：免費使用、自由傳播。Mac OS 操作系統(tǒng)：美國 A

23、pple 公司推出，運行在 Macintosh 計算機上。Netware 操作系統(tǒng)： Novell 公司， Netware 是其開發(fā)的網(wǎng)絡操作系統(tǒng) NOS?！拔募?.擴展文件：具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。每個文件都要用一個名字來標識，稱為文件名。名”。通配符“？”：文件名中的一個可用字符。通配符“* ”：文件名中的一個可用字符串。Windows 系統(tǒng)中文件名最多包含 256 個字符，可以包含字母、漢字、數(shù)字和部分符號。文件的命名：“文件名 .擴展名 ”“*.* ”任何文件都包括。操作系統(tǒng)中負責存取和管理文件信息的部分稱為文件系統(tǒng)。文件系統(tǒng)的功能：文件讀/ 寫管理；文件目錄管理；文件存儲

24、空間管理；文件保護與共享；提供方便的用戶接口；文件系統(tǒng)的可靠性與一致性。從文件管理的角度看，文件由文件說明和文件體2 部分組成。文件體即文件本身，而文件說明（又稱文件控制塊 FCB）是保存文件屬性信息的數(shù)據(jù)結(jié)構(gòu)，它通常包含以下內(nèi)容：文件名稱、文件的結(jié)構(gòu)、文件在外存中的物理存放位置、建立和修改的日期、 保護信息等。文件說明的集合稱為文件目錄。目錄的功能：實現(xiàn)“按名存取”；提高檢索速度；允許文件同名；允許文件共享。目錄結(jié)構(gòu)：單級目錄結(jié)構(gòu)、二級目錄結(jié)構(gòu)、多級目錄結(jié)構(gòu)。路徑名有 2 種表示形式：絕對路徑名和相對路徑名。絕對路徑名：從根目錄“”開始直至指定文件所在位置的目錄名序列。表示方法：一級子目錄名

25、 二級子目錄名 .n 級子目錄名。相對路徑：從當前目錄出發(fā)到指定文件所在位置的目錄名序列。第 3 章 軟件技術(shù)基礎程序是人們?yōu)榱私鉀Q實際問題要求計算機執(zhí)行的動作和操作，程序表達了程序設計者的思想；對于計算機來說，程序是一組計算機能操作的命令。程序包括：數(shù)據(jù)的描述（即數(shù)據(jù)結(jié)構(gòu)）、對操作的描述。程序 =數(shù)據(jù)結(jié)構(gòu) +算法。程序設計 =數(shù)據(jù)結(jié)構(gòu) +算法 +程序設計方法 +語言工具和環(huán)境。 算法：完成一個問題的有限執(zhí)行步驟的有序集合。算法的基本特征（ 5 個重要特征）：輸入：一個算法有 0 個或多個輸入；輸出：一個算法有 1 個或多個輸出；確定性：算法的每一步驟都必須有確切的含義，不存在二義性；有窮性：

26、一個算法必須在執(zhí)行有限步驟之后結(jié)束，而不能是無限的；可行性：算法的每一步驟都必須能有效的執(zhí)行，得到確定的結(jié)果。算法的表示：自然語言、流程圖、程序設計語言、偽代碼（一種介于自然語言和計算機語言之間的文字和符號來描述算法。 數(shù)據(jù)是對客觀事物的符號表示。數(shù)據(jù)元素是數(shù)據(jù)集合中的一個實體，是數(shù)據(jù)的基本單位。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素和相互之間關(guān)系的集合。數(shù)據(jù)結(jié)構(gòu)包括：數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式，即數(shù)據(jù)的存儲結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)；對數(shù)據(jù)元素的操作，即數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)主要有2 種，即線性結(jié)構(gòu)和非線性

27、結(jié)構(gòu)。線性結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點 （數(shù)據(jù)元素） 之間存在一對一關(guān)系。 特點：開始結(jié)點和終端結(jié)點是唯一的，除了它們以外，其余結(jié)點都有且僅有一個前驅(qū)結(jié)點和一個后繼結(jié)點。順序表就是典型的線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點 （數(shù)據(jù)元素） 之間存在一對多或多對一的關(guān)系。 分為樹型結(jié)構(gòu)、 圖形結(jié)構(gòu)。樹型結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點之間存在一對多的關(guān)系。 特點：僅有一個前驅(qū)結(jié)點， 可以有多個后續(xù)結(jié)點，可以有多個終端結(jié)點。 圖形結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點之間存在多對多的關(guān)系。特點：每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的個數(shù)是任意的。 因此，可能沒有開始結(jié)點和終端結(jié)點， 也可以有多個開始結(jié)點和終端結(jié)點。數(shù)據(jù)元素之間

28、的關(guān)系是指它們的邏輯關(guān)系， 與它們在計算機中的存儲位置無關(guān)。 通常采用二元組表示： DS = （D，S）DS是一個數(shù)據(jù)結(jié)構(gòu)， D 是在一個數(shù)據(jù)結(jié)構(gòu)（ DS）中數(shù)據(jù)元素的集合， S 是定義在 D 上的關(guān)系的集合，可以稱 S 為邏輯結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式，數(shù)據(jù)的存儲結(jié)構(gòu)又稱為數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)可分為：順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、散列（或哈希）存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu)：把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。優(yōu)點：節(jié)省存儲空間，因為分配給數(shù)據(jù)的存儲單元全用于存放結(jié)點的數(shù)據(jù)，

29、結(jié)點之間的邏輯關(guān)系沒有占用額外的存儲空間?？梢詫崿F(xiàn)對結(jié)點的隨機訪問，即每個結(jié)點對應有一個序號， 由該序號可直接計算出結(jié)點的存儲地址。缺點：不便于修改（對結(jié)點的插入、刪除運算可能涉及移動一系列的結(jié)點） ；要求有連續(xù)的空間。 鏈式存儲結(jié)構(gòu)：在每個結(jié)點中至少包含一個指針域，用來指出數(shù)據(jù)元素之間的邏輯關(guān)系，不要求在邏輯上相鄰的結(jié)點在物理位置上也相鄰。優(yōu)點：便于修改（在進行插入、刪除運算時，僅需修改結(jié)點的指針域值，不必移動結(jié)點） ；可運用零散的空間。缺點：存儲空間的利用率低，因為分配給數(shù)據(jù)的存儲單元有一部分要用來存儲結(jié)點之間的邏輯關(guān)系。另外，由于邏輯上相鄰的結(jié)點在存儲器中不一定相鄰，所以不能對結(jié)點隨機訪問。索引存儲結(jié)構(gòu)：在存儲信息的同時，還建立附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式是關(guān)鍵字與地址。關(guān)鍵字唯一標識一個結(jié)點，地址作為指向結(jié)點的指針，可以大大提高數(shù)據(jù)查找的速度。散列（或哈希）存儲結(jié)構(gòu)：根據(jù)結(jié)點的關(guān)鍵字通過散列（或哈希）函數(shù)直接計算出一個值，并將這個值作為該結(jié)點的存儲地址。優(yōu)點：查找速度快，只要給出帶查結(jié)點的關(guān)鍵字，就可立即算出該結(jié)點的存儲地址。散列存儲方法只存儲結(jié)點的數(shù)據(jù)，不存儲結(jié)點之間的邏輯關(guān)系。一般只適合要求對數(shù)據(jù)進行快速查找和插入。線性表：具有相同特性的數(shù)據(jù)元素的一個有限序列。用n 表示， n0.當 n=