【正文】 儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的，即前驅(qū)元素一定存儲(chǔ)在后繼元素的前面。熟悉順序線性表（順序存儲(chǔ)的線性表）的存儲(chǔ)方式及其表單元（簡(jiǎn)單數(shù)據(jù)類(lèi)型和記錄數(shù)據(jù)類(lèi)型）的定位和計(jì)算。第二章 線性表了解并掌握線性表的定義及性質(zhì)線性表是線性結(jié)構(gòu)的一種表現(xiàn)形式，即是具有相同屬性數(shù)據(jù)元素的一個(gè)有限序列，序列中的元素是一個(gè)接一個(gè)在邏輯上是有序的，序列中元素的個(gè)數(shù)就是該線性表的長(zhǎng)度.v 存在唯一的一個(gè)被稱(chēng)作“第一個(gè)”的數(shù)據(jù)元素v 存在唯一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素v 除起點(diǎn)元素之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)v 除終點(diǎn)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼v 起點(diǎn)元素只有后繼沒(méi)有前驅(qū)，終點(diǎn)元素只有前驅(qū)沒(méi)有后繼 v 對(duì)于線性表中的數(shù)據(jù)元素ai1和ai來(lái)說(shuō)，ai1是ai的直接前驅(qū)，ai是ai1的直接后繼。算法的時(shí)間復(fù)雜度是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。存儲(chǔ)指算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和總的數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系v 邏輯結(jié)構(gòu)相同，但存儲(chǔ)結(jié)構(gòu)不同，則認(rèn)為是不同的數(shù)據(jù)結(jié)構(gòu)。（1）順序的方法: 將邏輯上相鄰的元素存儲(chǔ)到物理上相鄰的存儲(chǔ)位置. 常用于線性的數(shù)據(jù)結(jié)構(gòu).（2）鏈?zhǔn)浇Y(jié)構(gòu)：給結(jié)點(diǎn)附加一個(gè)指針字段, 指出其后繼節(jié)點(diǎn)的位置, 即存放結(jié)點(diǎn)的存儲(chǔ)單元分為兩部分:數(shù)據(jù)項(xiàng)指針項(xiàng)（3）散列（hashing) 結(jié)構(gòu)：散列的方法是用結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出結(jié)點(diǎn)的存儲(chǔ)地址。數(shù)據(jù)結(jié)構(gòu)的二元組定義，能根據(jù)給出的二元組來(lái)判斷數(shù)據(jù)的邏輯結(jié)構(gòu)類(lèi)型。 v 樹(shù)結(jié)構(gòu)是圖結(jié)構(gòu)的特例，線性結(jié)構(gòu)是樹(shù)結(jié)構(gòu)的特例。第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容①數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)關(guān)系之間的邏輯關(guān)系 ②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 數(shù)據(jù)邏輯結(jié)構(gòu)的種類(lèi)：集合、線性表、樹(shù)和圖的性質(zhì)和特點(diǎn)。v 集合結(jié)構(gòu)中的元素是各自獨(dú)立的，元素之間沒(méi)有聯(lián)系v 線性結(jié)構(gòu)中的元素是一個(gè)接一個(gè)串聯(lián)起來(lái)的，它有一個(gè)頭元素和一個(gè)尾元素，其余為中間元素；每個(gè)中間元素既有前驅(qū)元素，又有后繼元素v 在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)只有后繼結(jié)點(diǎn)，而沒(méi)有前驅(qū)結(jié)點(diǎn)；除樹(shù)根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)結(jié)點(diǎn)，又稱(chēng)為是父結(jié)點(diǎn)或雙親結(jié)點(diǎn)v 在圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)或稱(chēng)頂點(diǎn)都可以有任意多個(gè)前驅(qū)結(jié)點(diǎn)和任意多個(gè)后繼結(jié)點(diǎn)。為了區(qū)別于線性結(jié)構(gòu)，時(shí)常把樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)稱(chēng)為非線性結(jié)構(gòu)。v 集合結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={ }v 線性結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，B,C，C,D，D,E，E,F，F(xiàn),G}v 樹(shù)結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,D，C,E，C,F，D,G}v 圖結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,G，D,G，D,F，C,E，C,F，G,F}了解數(shù)據(jù)的幾種存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）及它們各自的性質(zhì)和特點(diǎn)。這個(gè)取值函數(shù)也稱(chēng)為散列函數(shù)。 如順序表和鏈表具有相同的邏輯結(jié)構(gòu)，但存儲(chǔ)結(jié)構(gòu)分別為順序結(jié)構(gòu)和鏈表結(jié)構(gòu)算法的設(shè)計(jì)要求有那些，會(huì)結(jié)合實(shí)際的語(yǔ)言設(shè)計(jì)來(lái)說(shuō)明這些要求1）正確性：對(duì)于合法的輸入產(chǎn)生符合要求的輸出；2）可讀性：算法應(yīng)該易讀、便于交流， 這也是保證算法正確性的前提；添加注釋也是一種增加可讀性的辦法；3）健壯性：當(dāng)輸入非法時(shí)， 算法還能做出適當(dāng)?shù)姆磻?yīng)而不會(huì)崩潰， 如輸出錯(cuò)誤信息；算法中應(yīng)該考慮適當(dāng)?shù)腻e(cuò)誤處理；4）效率高且內(nèi)存消耗小：效率高指運(yùn)行時(shí)間短。了解時(shí)間復(fù)雜度的概念、時(shí)間復(fù)雜度的度量、時(shí)間復(fù)雜度的類(lèi)型，能對(duì)實(shí)際的程序分析它的時(shí)間復(fù)雜度。把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做該算法的時(shí)間復(fù)雜度，或者叫做時(shí)間復(fù)雜性，用它來(lái)衡量一個(gè)算法的運(yùn)行時(shí)間性能或稱(chēng)計(jì)算性能v 平均復(fù)雜度(The Average Case)：．v 最壞情況復(fù)雜度 (The Worst Case)：估算最壞情況下時(shí)間復(fù)雜度的一個(gè)上界．這也是通常所指的復(fù)雜度．v 最好復(fù)雜度 (The Best Case):在最理想輸入情況下的時(shí)間復(fù)雜度。v 所有數(shù)據(jù)元素ai在同一個(gè)線性表中必須是相同的數(shù)據(jù)類(lèi)型。 線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。熟悉順序線性表的插入、刪除和查找的算法思想和程序了解線性表鏈接存儲(chǔ)的結(jié)構(gòu)和特點(diǎn)v 假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)，從而可以表示數(shù)據(jù)元素之間的邏輯關(guān)系。v 插入、刪除運(yùn)算靈活方便，不需移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可了解單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)和特點(diǎn)通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的結(jié)點(diǎn)序列我們就稱(chēng)為鏈表。雙向鏈表是指線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱(chēng)為左指針，用以指向其直接前驅(qū)；另一個(gè)稱(chēng)為右指針，用以指向其直接后繼。循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為“NULL”，而是指向頭一個(gè)結(jié)點(diǎn)，成為一個(gè)由鏈指針鏈結(jié)的環(huán)。 了解單鏈表的結(jié)點(diǎn)的類(lèi)型定義在程序中，L為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。除了線性表第一個(gè)數(shù)據(jù)元素作為該鏈表的頭結(jié)點(diǎn)外，在某些線性鏈表存儲(chǔ)結(jié)構(gòu)中，還可在單鏈表第一個(gè)結(jié)點(diǎn)之前附加一個(gè)同結(jié)構(gòu)結(jié)點(diǎn)，稱(chēng)為附加頭結(jié)點(diǎn)。那么，指向頭結(jié)點(diǎn)