大學(xué)計(jì)算機(jī)基礎(chǔ)讀書筆記

計(jì)算機(jī)計(jì)算機(jī)的應(yīng)用:數(shù)值計(jì)算，數(shù)據(jù)處理，自動(dòng)控制，計(jì)算機(jī)輔助系統(tǒng)(CAD,CAM,CBE,CAT,CAI)，人工智能，通信和電子商務(wù)（數(shù)值計(jì)算又稱科學(xué)計(jì)算；數(shù)據(jù)處理又稱信息處理；自動(dòng)控制又稱過程控制，包括檢測(cè)過程和控制過程;計(jì)算機(jī)輔助設(shè)計(jì)CAD(ComputerAidedDesign)，降低了設(shè)計(jì)人員的工作質(zhì)量，提高了設(shè)計(jì)的效率和質(zhì)量，節(jié)約了設(shè)計(jì)成本；計(jì)算機(jī)輔助制造CAM(ComputerAidedManufacturing)提高產(chǎn)品質(zhì)量，降低生產(chǎn)成本和勞動(dòng)強(qiáng)度，縮短生產(chǎn)周期;計(jì)算機(jī)輔助教育CBE(ComputerBasedEducation)包括計(jì)算機(jī)輔助測(cè)試CAT(ComputerAidedTest)和計(jì)算機(jī)輔助教學(xué)CAI(ComputerAssistedInstruction)，提高了教學(xué)質(zhì)量；人工智能AI(ArtificialIntelligence),如專家系統(tǒng)等，可以對(duì)原始數(shù)據(jù)進(jìn)行分析決策；計(jì)算機(jī)網(wǎng)絡(luò)是計(jì)算機(jī)技術(shù)與通訊技術(shù)相結(jié)合的產(chǎn)物，提高了通信的速度與效率，降低了軟件與硬件的使用費(fèi)用，提高了計(jì)算機(jī)系統(tǒng)的可靠性）計(jì)算機(jī)的特點(diǎn)：運(yùn)算速度快，計(jì)算精度高，記憶力強(qiáng)，具有邏輯判斷能力，自動(dòng)化程度高1946年2月，世界上第一臺(tái)電子計(jì)算機(jī)ENIAC誕生于美國(guó)賓州大學(xué)。計(jì)算機(jī)代別劃分依據(jù)：邏輯元器件。第一代計(jì)算機(jī)：1946—1958電子管。第二代計(jì)算機(jī)：1958—1964晶體管。第三代計(jì)算機(jī)：1965—1971中，小規(guī)模集成電路。第四代計(jì)算機(jī)：1972—至今大規(guī)模和超大規(guī)模集成電路。英國(guó)科學(xué)家：阿倫·圖靈：圖靈機(jī)，建立計(jì)算機(jī)理論模型。匈牙利科學(xué)家：馮·諾依曼：計(jì)算機(jī)之父。根據(jù)計(jì)算機(jī)的應(yīng)用范圍分類：專用計(jì)算機(jī)和通用計(jì)算機(jī)。根據(jù)數(shù)據(jù)的處理方式分類：數(shù)字計(jì)算機(jī)，模擬計(jì)算機(jī)，數(shù)字模擬混合計(jì)算機(jī)。根據(jù)計(jì)算機(jī)的規(guī)模和功能強(qiáng)弱分類：巨型機(jī)，小巨型機(jī)，大型主機(jī)，小型機(jī)，工作站，個(gè)人計(jì)算機(jī)計(jì)算機(jī)系統(tǒng)：硬件系統(tǒng)和軟件系統(tǒng)。硬件系統(tǒng)：運(yùn)算器，控制器，存儲(chǔ)器，輸入設(shè)備，輸出設(shè)備。軟件系統(tǒng)：系統(tǒng)軟件，應(yīng)用軟件。計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)：應(yīng)用軟件層》實(shí)用軟件層》操作系統(tǒng)層》硬件層數(shù)制：按進(jìn)位的原則進(jìn)行計(jì)數(shù)，進(jìn)位計(jì)數(shù)制位權(quán)：一種進(jìn)制中某個(gè)位置上的單位值十進(jìn)制：0，1，…,9,逢十進(jìn)一,基數(shù)為10。二進(jìn)制：0，1，逢二進(jìn)一，基數(shù)為2。二進(jìn)制的優(yōu)點(diǎn)：便于實(shí)現(xiàn)、運(yùn)算簡(jiǎn)單、工作可靠、方便邏輯運(yùn)算、物理元器件容易制造、運(yùn)算規(guī)則少。八進(jìn)制：0，1，2，…,7,逢八進(jìn)一，基數(shù)為8。十六進(jìn)制：0，1，…,9,A,B,C,D,E,F,逢十六進(jìn)一，基數(shù)為16。二進(jìn)制八進(jìn)制十進(jìn)制十六進(jìn)制二進(jìn)制八進(jìn)制十進(jìn)制十六進(jìn)制000000010001088000111110011199001022210101210A001133310111311B010044411001412C010155511011513D011066611101614E011177711111715FN進(jìn)制轉(zhuǎn)換為十進(jìn)制：展開多項(xiàng)式，各項(xiàng)相加。（注意位權(quán)比位數(shù)少一）。十進(jìn)制轉(zhuǎn)換為N進(jìn)制：整數(shù)：將十進(jìn)制整數(shù)連續(xù)的除以N，記下每次的余數(shù)，直到商為0，倒排余數(shù)。小數(shù)：將十進(jìn)制小數(shù)連續(xù)的乘以N，記下每次的整數(shù)，直到十進(jìn)制小數(shù)為0或滿足進(jìn)度為止，正排整數(shù)。二進(jìn)制轉(zhuǎn)換為八進(jìn)制的方法：從小數(shù)點(diǎn)開始，每3位一組，不足3位的用0補(bǔ)齊，每一組用一個(gè)八進(jìn)制數(shù)表示。二進(jìn)制轉(zhuǎn)換為十六進(jìn)制方法：從小數(shù)點(diǎn)開始，每4位一組，不足4位的用0補(bǔ)齊，每一組用一個(gè)十六進(jìn)制數(shù)表示。八進(jìn)制（十六進(jìn)制）數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)方法：每位八進(jìn)制數(shù)（十六進(jìn)制數(shù)）用3（4）位二進(jìn)制數(shù)表示，刪除兩端無意義的0。機(jī)器數(shù)：正負(fù)號(hào)用數(shù)字表示的數(shù)。0為正，1為負(fù)。真值：與機(jī)器數(shù)對(duì)應(yīng)的數(shù)學(xué)中的數(shù)。定點(diǎn)整數(shù)：將小數(shù)點(diǎn)的位置約定在機(jī)器數(shù)的末端。補(bǔ)0為符號(hào)位后面。定點(diǎn)小數(shù)：將小數(shù)點(diǎn)的位置約定在符號(hào)位的右側(cè)。補(bǔ)0為數(shù)值后面。浮點(diǎn)數(shù)：將一個(gè)數(shù)表示為尾數(shù)和階碼。階碼用定點(diǎn)整數(shù)，尾數(shù)用定點(diǎn)小數(shù)。與科學(xué)計(jì)數(shù)法類似。原碼：整數(shù)含0的符號(hào)位為0，負(fù)數(shù)含0的符號(hào)位為1.數(shù)值部分為對(duì)應(yīng)數(shù)的絕對(duì)值。0的原碼有兩種編碼，00000000（0.0000000），10000000（1.0000000）。優(yōu)點(diǎn)：與真值轉(zhuǎn)換簡(jiǎn)單。缺點(diǎn)：運(yùn)算不方便且有錯(cuò)誤。8位定點(diǎn)整數(shù)原碼的表示范圍：--127--+127反碼：正數(shù)含0的反碼與原碼一樣；將負(fù)數(shù)含0原碼除符號(hào)位外，每位變反。0的反碼有兩種編碼00000000（0.0000000），11111111（1.1111111）反碼的反碼為原碼。補(bǔ)碼：正數(shù)含0的補(bǔ)碼與原碼一樣；將負(fù)數(shù)的反碼末位加1，注意進(jìn)位。0的補(bǔ)碼只有1種。00000000（0.0000000）正數(shù)的原碼、反碼、補(bǔ)碼均相同。補(bǔ)碼的補(bǔ)碼為原碼。先原碼再反碼后補(bǔ)碼。求補(bǔ)：包括符號(hào)位在內(nèi)，每位變反，末位加1。對(duì)某個(gè)數(shù)的補(bǔ)碼求補(bǔ)即可得到該數(shù)相反數(shù)的補(bǔ)碼。規(guī)格化浮點(diǎn)數(shù)：提高了存儲(chǔ)的精度。階碼采用定點(diǎn)整數(shù)補(bǔ)碼，尾數(shù)采用定點(diǎn)小數(shù)補(bǔ)碼。對(duì)于整數(shù)，規(guī)格化就是將小數(shù)點(diǎn)移到數(shù)值部分第一個(gè)1的左側(cè)，對(duì)于負(fù)數(shù)而言就是將小數(shù)點(diǎn)移到第一個(gè)0的右側(cè)。ASCII美國(guó)國(guó)家標(biāo)準(zhǔn)信息交換碼。7位ASCII碼又稱基本ASCII碼，用7位二進(jìn)制表示128個(gè)字符編碼，包括33個(gè)控制字符。常用字符代碼由小到大：空格（32）、數(shù)字（0的代碼為48）、大寫字母（A的代碼為65）、小寫字母（a的代碼為97）。小寫字母的代碼比對(duì)應(yīng)大寫字母的代碼大32。8位ASCII碼又稱擴(kuò)展ASCII碼，用8位二進(jìn)制表示256種，其中0---127即為前面的128個(gè)基本ASCII碼，特點(diǎn)是最高位為0；128—255是擴(kuò)展部分，特點(diǎn)是最高位為1。漢字編碼：國(guó)標(biāo)碼：中國(guó)制定的用于計(jì)算機(jī)系統(tǒng)間交換漢字信息時(shí)使用的編碼。輸入碼：利用鍵盤輸入漢字的編碼。機(jī)內(nèi)碼：計(jì)算機(jī)內(nèi)部存儲(chǔ)、處理和傳輸漢字的編碼。字型碼：表示漢字形狀的編碼。（點(diǎn)陣字型：將一個(gè)漢字均勻的分成若干行、若干列，形成一個(gè)點(diǎn)陣。）CPU與內(nèi)存構(gòu)成主機(jī)。主機(jī)與外部設(shè)備股票擬共同構(gòu)成了計(jì)算機(jī)硬件系統(tǒng)。外存既是輸入設(shè)備又是輸出設(shè)備。存儲(chǔ)器包括內(nèi)存與外存。控制器與運(yùn)算器構(gòu)成了中央處理器CPU。計(jì)算機(jī)的主機(jī)和外部設(shè)備之間通過接口電路（簡(jiǎn)稱接口）連接。運(yùn)算器：算數(shù)運(yùn)算、邏輯運(yùn)算?？刂破鳎嚎刂聘鞑考f(xié)調(diào)工作。存儲(chǔ)器：保存程序和數(shù)據(jù)，分為內(nèi)存和外存。內(nèi)存：可以與CPU（運(yùn)算器+控制器）直接交換信息，保存正在處理的數(shù)據(jù)和正在執(zhí)行的程序。內(nèi)存主要包括隨機(jī)存儲(chǔ)器RAM(RandomAccessMemory)和只讀存儲(chǔ)器ROM（ReadOnlyMemory）兩類。RAM可以進(jìn)行讀取和寫保存兩種操作，但斷電時(shí)信息丟失。ROM只能進(jìn)行讀操作，不能執(zhí)行寫操作，但是斷電時(shí)信息不丟失。ROM主要保存最基本的固定不變的程序和數(shù)據(jù)。ROM容量＜RAM。通常所說的內(nèi)存容量指RAM。RAM分為動(dòng)態(tài)隨機(jī)存儲(chǔ)器DRAM和靜態(tài)隨機(jī)存儲(chǔ)器SRAM。DRAM存儲(chǔ)密度高、存取速度慢、需要定期刷新。SRAM存儲(chǔ)密度低、存取速度快、不需要刷新。存儲(chǔ)單位有：位（bit）、字節(jié)（Byte）、字（Word）。位是存儲(chǔ)設(shè)備的最小存儲(chǔ)單位存儲(chǔ)一位二進(jìn)制的存儲(chǔ)設(shè)備。字節(jié)是內(nèi)存的最小編址單位，即每個(gè)字節(jié)都有唯一的一個(gè)地址，一般由連續(xù)的8位構(gòu)成。CPU一次能夠處理的連續(xù)字節(jié)稱為字。字長(zhǎng)有8位，16位，32位，64位。字長(zhǎng)越長(zhǎng)，CPU的處理速度越快。存儲(chǔ)容量：?jiǎn)挝唬海耍?，ＭＢ，ＧＢ，ＴＢ。１ＫＢ＝１０２４Ｂ，１ＭＢ＝１０２４ＫＢ，１ＧＢ＝１０２４ＭＢ，１ＴＢ＝１０２４ＧＢ外存的功能：保存需要長(zhǎng)期存儲(chǔ)的內(nèi)容和擴(kuò)充內(nèi)存容量。斷電時(shí)，外存中內(nèi)容不丟失。CPU不能直接訪問外存。常用外存：軟盤存儲(chǔ)器、硬盤存儲(chǔ)器、光盤存儲(chǔ)器、移動(dòng)存儲(chǔ)器（U盤）、Cache高速緩存L1，L2、指令存儲(chǔ)器、寄存器等。軟盤存儲(chǔ)器：磁道：每個(gè)同心圓。扇區(qū)：每個(gè)磁道被分成相同數(shù)目的區(qū)段，每個(gè)區(qū)段就是扇區(qū)。一個(gè)扇區(qū)的容量為512B，即0.5KB。面數(shù)*每面磁道數(shù)*每磁道扇區(qū)數(shù)*512B。硬盤存儲(chǔ)器：分為固定式和可移動(dòng)式兩種。容量=柱面數(shù)*每柱面容量=柱面數(shù)*盤面數(shù)*每磁道容量=柱面數(shù)*盤面數(shù)*每磁道扇區(qū)數(shù)*512B。光盤存儲(chǔ)器：光盤主要包括CD和DVD兩種，CD的容量通常為600MB左右，而DVD的容量通常都在4.7GB以上。CD緊湊光盤，CD有CD—ROM、CD—R、CD—RW。DVD是數(shù)字多功能光盤或數(shù)字激光視盤的簡(jiǎn)稱，包括DVD—ROM、DVD—R、DVD—RW等。U盤存儲(chǔ)器特點(diǎn)：不使用驅(qū)動(dòng)器，節(jié)省開支；使用的是USB接口，無需外接電源，支持即插即用和熱插拔；存取速度比軟盤快得多；體積非常小且很輕，便于攜帶；防震性能好。為了滿足用戶對(duì)存儲(chǔ)系統(tǒng)速度快、價(jià)格低和容量大的需求，存儲(chǔ)系統(tǒng)采用了層次結(jié)構(gòu)。Cache是與CPU和內(nèi)存直接交換信息的高速緩沖存儲(chǔ)器（簡(jiǎn)稱高速緩存），其讀寫速度遠(yuǎn)高于內(nèi)存。Cache存儲(chǔ)系統(tǒng)由Cache和內(nèi)存構(gòu)成，目的：提高CPU訪問內(nèi)存的速度。虛擬存儲(chǔ)系統(tǒng)由內(nèi)存和外存（通常使用硬盤存儲(chǔ)器）構(gòu)成，目的：擴(kuò)大內(nèi)存的容量。輸入設(shè)備：負(fù)責(zé)將計(jì)算機(jī)外部的信息轉(zhuǎn)換為計(jì)算機(jī)能夠識(shí)別的二進(jìn)制形式并保存到計(jì)算機(jī)的內(nèi)存中。常見的輸入設(shè)備：鍵盤、鼠標(biāo)器、掃描儀、數(shù)碼相機(jī)（DC）、數(shù)碼攝像機(jī)（DV）、麥克、光筆、條形碼閱讀機(jī)和觸摸屏等。鍵盤：字符輸入設(shè)備。輸出設(shè)備：負(fù)責(zé)將計(jì)算機(jī)內(nèi)部的二進(jìn)制信息轉(zhuǎn)換為人或其他設(shè)備能夠識(shí)別的形式并輸出。常見的輸出設(shè)備：顯示器、打印機(jī)、音箱、繪圖儀等。外存既是輸入設(shè)備又是輸出設(shè)備。計(jì)算機(jī)硬件的各部分之間通年5月Windows3.0版，1995年8月24日Windows95逐步取代了DOS系統(tǒng)，2000年Windows2000，2001年WindowsXP。Windows操作系統(tǒng)成功的特點(diǎn)：易學(xué)易用的面向?qū)ο蟮膱D形用戶界面；支持多任務(wù)多窗口；即插即用功能；支持多媒體技術(shù)；內(nèi)置網(wǎng)絡(luò)和通信功能。UNIX操作系統(tǒng)：UNIX系統(tǒng)正式發(fā)布于1974年，1975年發(fā)布的第6版中引入了多道程序技術(shù)，這時(shí)UNIX系統(tǒng)才成為真正的多用戶分時(shí)系統(tǒng)。Linux操作系統(tǒng)：免費(fèi)使用、自由傳播。MacOS操作系統(tǒng)：美國(guó)Apple公司推出，運(yùn)行在Macintosh計(jì)算機(jī)上。Netware操作系統(tǒng)：Novell公司，Netware是其開發(fā)的網(wǎng)絡(luò)操作系統(tǒng)NOS。文件：具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。每個(gè)文件都要用一個(gè)名字來標(biāo)識(shí)，稱為文件名?！拔募?擴(kuò)展名”。通配符“？”：文件名中的一個(gè)可用字符。通配符“*”：文件名中的一個(gè)可用字符串。Windows系統(tǒng)中文件名最多包含256個(gè)字符，可以包含字母、漢字、數(shù)字和部分符號(hào)。文件的命名：“文件名.[擴(kuò)展名]”“*.*”任何文件都包括。操作系統(tǒng)中負(fù)責(zé)存取和管理文件信息的部分稱為文件系統(tǒng)。文件系統(tǒng)的功能：文件讀/寫管理；文件目錄管理；文件存儲(chǔ)空間管理；文件保護(hù)與共享；提供方便的用戶接口；文件系統(tǒng)的可靠性與一致性。從文件管理的角度看，文件由文件說明和文件體2部分組成。文件體即文件本身，而文件說明（又稱文件控制塊FCB）是保存文件屬性信息的數(shù)據(jù)結(jié)構(gòu)，它通常包含以下內(nèi)容：文件名稱、文件的結(jié)構(gòu)、文件在外存中的物理存放位置、建立和修改的日期、保護(hù)信息等。文件說明的集合稱為文件目錄。目錄的功能：實(shí)現(xiàn)“按名存取”；提高檢索速度；允許文件同名；允許文件共享。目錄結(jié)構(gòu)：?jiǎn)渭?jí)目錄結(jié)構(gòu)、二級(jí)目錄結(jié)構(gòu)、多級(jí)目錄結(jié)構(gòu)。路徑名有2種表示形式：絕對(duì)路徑名和相對(duì)路徑名。絕對(duì)路徑名：從根目錄“\”開始直至指定文件所在位置的目錄名序列。表示方法：\一級(jí)子目錄名\二級(jí)子目錄名\...\n級(jí)子目錄名。相對(duì)路徑：從當(dāng)前目錄出發(fā)到指定文件所在位置的目錄名序列。第3章軟件技術(shù)基礎(chǔ)程序是人們?yōu)榱私鉀Q實(shí)際問題要求計(jì)算機(jī)執(zhí)行的動(dòng)作和操作，程序表達(dá)了程序設(shè)計(jì)者的思想；對(duì)于計(jì)算機(jī)來說，程序是一組計(jì)算機(jī)能操作的命令。程序包括：數(shù)據(jù)的描述（即數(shù)據(jù)結(jié)構(gòu)）、對(duì)操作的描述。程序=數(shù)據(jù)結(jié)構(gòu)+算法。程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計(jì)方法+語言工具和環(huán)境。算法：完成一個(gè)問題的有限執(zhí)行步驟的有序集合。算法的基本特征（5個(gè)重要特征）：輸入：一個(gè)算法有0個(gè)或多個(gè)輸入；輸出：一個(gè)算法有1個(gè)或多個(gè)輸出；確定性：算法的每一步驟都必須有確切的含義，不存在二義性；有窮性：一個(gè)算法必須在執(zhí)行有限步驟之后結(jié)束，而不能是無限的；可行性：算法的每一步驟都必須能有效的執(zhí)行，得到確定的結(jié)果。算法的表示：自然語言、流程圖、程序設(shè)計(jì)語言、偽代碼（一種介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。數(shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)實(shí)體，是數(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)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)；對(duì)數(shù)據(jù)元素的操作，即數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)主要有2種，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)（數(shù)據(jù)元素）之間存在一對(duì)一關(guān)系。特點(diǎn)：開始結(jié)點(diǎn)和終端結(jié)點(diǎn)是唯一的，除了它們以外，其余結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。順序表就是典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)（數(shù)據(jù)元素）之間存在一對(duì)多或多對(duì)一的關(guān)系。分為樹型結(jié)構(gòu)、圖形結(jié)構(gòu)。樹型結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多的關(guān)系。特點(diǎn)：僅有一個(gè)前驅(qū)結(jié)點(diǎn)，可以有多個(gè)后續(xù)結(jié)點(diǎn)，可以有多個(gè)終端結(jié)點(diǎn)。圖形結(jié)構(gòu)：在數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)之間存在多對(duì)多的關(guān)系。特點(diǎn)：每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的個(gè)數(shù)是任意的。因此，可能沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，也可以有多個(gè)開始結(jié)點(diǎn)和終端結(jié)點(diǎn)。數(shù)據(jù)元素之間的關(guān)系是指它們的邏輯關(guān)系，與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無關(guān)。通常采用二元組表示：DS=（D，S）DS是一個(gè)數(shù)據(jù)結(jié)構(gòu)，D是在一個(gè)數(shù)據(jù)結(jié)構(gòu)（DS）中數(shù)據(jù)元素的集合，S是定義在D上的關(guān)系的集合，可以稱S為邏輯結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可分為：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列（或哈希）存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。優(yōu)點(diǎn)：節(jié)省存儲(chǔ)空間，因?yàn)榉峙浣o數(shù)據(jù)的存儲(chǔ)單元全用于存放結(jié)點(diǎn)的數(shù)據(jù)，結(jié)點(diǎn)之間的邏輯關(guān)系沒有占用額外的存儲(chǔ)空間?？梢詫?shí)現(xiàn)對(duì)結(jié)點(diǎn)的隨機(jī)訪問，即每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有一個(gè)序號(hào)，由該序號(hào)可直接計(jì)算出結(jié)點(diǎn)的存儲(chǔ)地址。缺點(diǎn)：不便于修改（對(duì)結(jié)點(diǎn)的插入、刪除運(yùn)算可能涉及移動(dòng)一系列的結(jié)點(diǎn)）；要求有連續(xù)的空間。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每個(gè)結(jié)點(diǎn)中至少包含一個(gè)指針域，用來指出數(shù)據(jù)元素之間的邏輯關(guān)系，不要求在邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰。優(yōu)點(diǎn)：便于修改（在進(jìn)行插入、刪除運(yùn)算時(shí)，僅需修改結(jié)點(diǎn)的指針域值，不必移動(dòng)結(jié)點(diǎn)）；可運(yùn)用零散的空間。缺點(diǎn)：存儲(chǔ)空間的利用率低，因?yàn)榉峙浣o數(shù)據(jù)的存儲(chǔ)單元有一部分要用來存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系。另外，由于邏輯上相鄰的結(jié)點(diǎn)在存儲(chǔ)器中不一定相鄰，所以不能對(duì)結(jié)點(diǎn)隨機(jī)訪問。索引存儲(chǔ)結(jié)構(gòu)：在存儲(chǔ)信息的同時(shí)，還建立附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是關(guān)鍵字與地址。關(guān)鍵字唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)，地址作為指向結(jié)點(diǎn)的指針，可以大大提高數(shù)據(jù)查找的速度。散列（或哈希）存儲(chǔ)結(jié)構(gòu)：根據(jù)結(jié)點(diǎn)的關(guān)鍵字通過散列（或哈希）函數(shù)直接計(jì)算出一個(gè)值，并將這個(gè)值作為該結(jié)點(diǎn)的存儲(chǔ)地址。優(yōu)點(diǎn)：查找速度快，只要給出帶查結(jié)點(diǎn)的關(guān)鍵字，就可立即算出該結(jié)點(diǎn)的存儲(chǔ)地址。散列存儲(chǔ)方法只存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)，不存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系。一般只適合要求對(duì)數(shù)據(jù)進(jìn)行快速查找和插入。線性表：具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。用n表示，n≥0.當(dāng)n=0時(shí)空表，即不包含任何數(shù)據(jù)元素。非空線性表特點(diǎn)：有且只有一個(gè)根結(jié)點(diǎn)，無前驅(qū)；有且僅有一個(gè)終端結(jié)點(diǎn)，無后繼；除根結(jié)點(diǎn)和終結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)和一個(gè)后繼。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。線性表的順序存儲(chǔ)結(jié)構(gòu)是把線性表中的所有元素按照其邏輯順序，依次存儲(chǔ)到連續(xù)的計(jì)算機(jī)存儲(chǔ)空間中。每一個(gè)數(shù)據(jù)元素占k個(gè)字節(jié)。順序存儲(chǔ)結(jié)構(gòu)有2個(gè)基本特點(diǎn)：線性表中所有數(shù)據(jù)元素所占的存儲(chǔ)空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有2個(gè)基本特點(diǎn)：線性表中所有數(shù)據(jù)所占空間不一定是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間的邏輯關(guān)系是由各結(jié)點(diǎn)的指針域來表