1、第二章 線(xiàn)性表,2.1 線(xiàn)性表的定義,2.1.1 線(xiàn)性表的邏輯結(jié)構(gòu) 線(xiàn)性表是有限元素（e0,e1, .,ei,.,en-1）的有序序列的集合。其中n是有窮自然數(shù)，表中的每個(gè)元素ei具有相同的特性，表中元素占用空間大小相同,記為：size，n是表的長(zhǎng)度。當(dāng)n=0時(shí)，表為空；當(dāng)n0時(shí)，e0是第一個(gè)元素，en-1 是最后一個(gè)元素。 “有序”是指線(xiàn)性元素間的相互位置關(guān)系。ei-1是 ei的直接前驅(qū)元素，而元素ei一定在元素ei+1之前，稱(chēng)ei+1是ei的直接后繼元素。而且，每個(gè)元素只有一個(gè)直接前驅(qū)元素（除第一個(gè)元素），也僅有一個(gè)直接后繼元素（除最后一個(gè)元素）。,2.1 線(xiàn)性表的定義,2.1 線(xiàn)性表的定

2、義,2.1.2 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型,2.1 線(xiàn)性表的定義,. 線(xiàn)性表的順序存儲(chǔ)及操作 2.2.1 線(xiàn)性表順序存儲(chǔ) 1. 線(xiàn)性表順序存儲(chǔ)概念 線(xiàn)性表順序存儲(chǔ)方式，是將線(xiàn)性表中的數(shù)據(jù)元素連續(xù)順序地存放于存儲(chǔ)器中相鄰的單元 。 線(xiàn)性表占用的第一個(gè)存儲(chǔ)單元的地址，就是線(xiàn)性表的首地址，也是線(xiàn)性表中第一個(gè)數(shù)據(jù)元素（e0）的首地址。 “首地址”有兩種理解： 一是相對(duì)于線(xiàn)性表本身，是線(xiàn)性表的始點(diǎn)，即“0號(hào)地址”，這就是通常所說(shuō)的“相對(duì)地址”； 二是相對(duì)于計(jì)算機(jī)的物理存儲(chǔ)空間，線(xiàn)性表的始點(diǎn)相對(duì)于計(jì)算機(jī)物理存儲(chǔ)空間則是一個(gè)“物理地址”，一般記為：location(e0)，通常稱(chēng)為“絕對(duì)地址”或“基地址”。,2.

3、2線(xiàn)性表的順序存儲(chǔ)及操作,線(xiàn)性表中每個(gè)數(shù)據(jù)元素占用size字節(jié)空間，length（length=n）表示線(xiàn)性表中元素的個(gè)數(shù),MaxSize表示線(xiàn)性表可以存儲(chǔ)元素的最大空間。,元素ei的地址則可以立即由下面公式求出。 location(ei)=location(e0)+isize 請(qǐng)注意：這個(gè)公式是元素序號(hào)由0到n-1安排，若元素序號(hào)是由j開(kāi)始安排，則上面公式應(yīng)改為： location(ei)=location(ej)+(i-j)size,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2. 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)定義 線(xiàn)性表結(jié)構(gòu)： typedef struct EType *element; intlength;

4、intMaxSize; LinearList； LinearListL，L1，L2；,2.2線(xiàn)性表的順序存儲(chǔ)及操作,學(xué)生信息的情況數(shù)據(jù)元素結(jié)構(gòu)類(lèi)型（EType）及線(xiàn)性表 typedef struct unsignednumber10; charname8; charsex2; intage; charplace20; student; typedef struct student *element; intlength; intMaxSize; LinearList； LinearListstud1, stud2;,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.2.2 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)下的操作 1. 構(gòu)

5、造空線(xiàn)性表L 空線(xiàn)性表是指表中沒(méi)有一個(gè)數(shù)據(jù)元素，但數(shù)據(jù)元素的空間和線(xiàn)性表結(jié)構(gòu)存在 構(gòu)造空線(xiàn)性表L算法（Creat） viod Creat(LinearList 算法的時(shí)間復(fù)雜性是O(1)。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2. 輸出線(xiàn)性表L中的所有數(shù)據(jù)元素 輸出線(xiàn)性表L中所有數(shù)據(jù)元素（Output） viod Output(LinearList 算法的時(shí)間復(fù)雜性是O(length )。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,3. 線(xiàn)性表L中取第k個(gè)元素 線(xiàn)性表L中將第k個(gè)元素取至x中算法（GetElem） bool GetElem(LinearList 算法的時(shí)間復(fù)雜性是O

6、(1 )。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.2線(xiàn)性表的順序存儲(chǔ)及操作,4. 線(xiàn)性表L中查找元素x 線(xiàn)性表L中查找元素x（Search） int Search(LinearList 算法的時(shí)間復(fù)雜性是O(length)。 一般是已知某個(gè)查找關(guān)鍵字（Searchkey），通過(guò)查找關(guān)鍵字與線(xiàn)性表中的數(shù)據(jù)元素的關(guān)鍵字的比較完成查找過(guò)程的，因此，算法查找的比較條件也可以表達(dá)為： if (L.elementi.key = Searchkey),2.2線(xiàn)性表的順序存儲(chǔ)及操作,5. 線(xiàn)性表L中第k個(gè)數(shù)據(jù)元素之后插入元素x 線(xiàn)性表L中第k個(gè)數(shù)據(jù)元素之后插入元素x運(yùn)算（Insert） Status Insert

7、(LinearList 算法的時(shí)間復(fù)雜性是O(length)。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.2線(xiàn)性表的順序存儲(chǔ)及操作,6. 線(xiàn)性表L中刪除第k個(gè)數(shù)據(jù)元素 線(xiàn)性表L中刪除第k個(gè)數(shù)據(jù)元素算法（Delete） Status Delete(LinearList 算法的時(shí)間復(fù)雜性是O(length-k)。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.2線(xiàn)性表的順序存儲(chǔ)及操作,線(xiàn)性表特征： 優(yōu)點(diǎn)：線(xiàn)性表的順序存儲(chǔ)方式，它有著邏輯關(guān)系上相鄰的兩個(gè)數(shù)據(jù)元素在物理位置上也相鄰的特征。因此，只要知道第一個(gè)元素的位置（即下標(biāo)），則可以利用尋址公式高效地存取一個(gè)元素。 缺點(diǎn)： 其一，在插入或刪除的過(guò)程中有著大量元素的移動(dòng)

8、，運(yùn)算時(shí)間較長(zhǎng)。 其二，在為長(zhǎng)度可變化的線(xiàn)性表預(yù)先分配空間時(shí)，必須按最大表長(zhǎng)MaxSize空間分配，因而造成存儲(chǔ)空間得不到充分利用。 第三，表的空間不容易擴(kuò)充。 為此，在有著頻繁插入、刪除運(yùn)算時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)。,2.2線(xiàn)性表的順序存儲(chǔ)及操作,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3.1 簡(jiǎn)單鏈表的存儲(chǔ) 1. 簡(jiǎn)單鏈表的存儲(chǔ)概念 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，是用物理上不一定相鄰的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表的元素，為了保證線(xiàn)性表之間的邏輯上的連續(xù)性，存儲(chǔ)元素ei時(shí),除了存儲(chǔ)它本身的內(nèi)容以外，還必須附加一個(gè)指針域（也叫鏈接域）來(lái)指出元素ei的直接后繼元素ei+1的存儲(chǔ)地址。,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)

9、及操作,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3.1 簡(jiǎn)單鏈表的存儲(chǔ) 1. 簡(jiǎn)單鏈表的存儲(chǔ)概念 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，是用物理上不一定相鄰的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表的元素，為了保證線(xiàn)性表之間的邏輯上的連續(xù)性，存儲(chǔ)元素ei時(shí),除了存儲(chǔ)它本身的內(nèi)容以外，還必須附加一個(gè)指針域（也叫鏈接域）來(lái)指出元素ei的直接后繼元素ei+1的存儲(chǔ)地址。,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3.1 簡(jiǎn)單鏈表的存儲(chǔ) 1. 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)定義 動(dòng)態(tài)存儲(chǔ)空間分配方式下線(xiàn)性表的數(shù)據(jù)元素的類(lèi)型： typedef struct EType data; ChainNode*link; ChainNode； ChainNode *

10、N, *N1; 表頭結(jié)點(diǎn)結(jié)構(gòu)定義如下： typedef struct HeadEType Hdata; ChainNode*first; ChainList； ChainList *L, *L1, *stud;,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3.2 簡(jiǎn)單鏈表的操作 1. 利用動(dòng)態(tài)存儲(chǔ)分配構(gòu)造簡(jiǎn)單鏈表(空鏈表) 構(gòu)造一個(gè)簡(jiǎn)單鏈表就是構(gòu)造一個(gè)，即只產(chǎn)生一個(gè)僅有表頭結(jié)點(diǎn)的鏈表，表頭結(jié)點(diǎn)的鏈接域first的值首先設(shè)為空（NULL）值，表頭結(jié)點(diǎn)的數(shù)據(jù)域填入表頭的相應(yīng)數(shù)據(jù)。并返回（帶回）表頭結(jié)點(diǎn)的結(jié)點(diǎn)指針。 構(gòu)造帶表頭的簡(jiǎn)單鏈表算法（Creat） viod Creat

11、(ChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2. 將簡(jiǎn)單鏈表數(shù)據(jù)元素進(jìn)行輸出 輸出簡(jiǎn)單鏈表L中的數(shù)據(jù)元素算法（Output） viod Output(ChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,3. 確定簡(jiǎn)單鏈表的長(zhǎng)度 計(jì)算簡(jiǎn)單鏈表L中數(shù)據(jù)元素結(jié)點(diǎn)數(shù)算法（Length） int Length(ChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,4.刪除簡(jiǎn)單鏈表中的所有數(shù)據(jù)元素結(jié)點(diǎn) 刪除后，鏈表只剩鏈表表頭結(jié)點(diǎn)，鏈表表頭的鏈接域被置為空。刪除過(guò)程中，不能簡(jiǎn)單將表頭結(jié)點(diǎn)的鏈接域設(shè)為空，應(yīng)該將鏈表中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)的逐一刪除，并釋放每個(gè)結(jié)點(diǎn)所占用的存儲(chǔ)空間。 刪除簡(jiǎn)單鏈表中的

12、所有數(shù)據(jù)元素結(jié)點(diǎn)（Destroy） viod Destroy(ChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,5.簡(jiǎn)單鏈表L中查找第k個(gè)元素 算法中設(shè)定一個(gè)指針current，用于指向鏈表中的一個(gè)數(shù)據(jù)結(jié)點(diǎn)，另設(shè)一個(gè)計(jì)數(shù)器index，記載指針current已經(jīng)指向鏈表中的第幾個(gè)數(shù)據(jù)結(jié)點(diǎn)。當(dāng)index的值等于k值時(shí)，表示已經(jīng)找到了第k個(gè)數(shù)據(jù)元素。 當(dāng)current為空時(shí)，說(shuō)明指針已經(jīng)指到了鏈表的最后一個(gè)結(jié)點(diǎn)的后面，說(shuō)明不存在第k個(gè)數(shù)據(jù)結(jié)點(diǎn)，查找失敗。,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,簡(jiǎn)單鏈表L中查找第k個(gè)元素取至x中算法（GetElem） bool GetEl

13、em(ChainList / k值太大，不存在第k個(gè)結(jié)點(diǎn) ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,6.簡(jiǎn)單鏈表中查找數(shù)據(jù)元素x 這是已知數(shù)據(jù)元素值的查找。 簡(jiǎn)單鏈表L中查找元素x（Search） ChainNode * Search(ChainList 實(shí)際中，一般是已知某個(gè)查找關(guān)鍵字（Searchkey），通過(guò)查找關(guān)鍵字與線(xiàn)性表中的數(shù)據(jù)元素的關(guān)鍵字的比較完成查找過(guò)程的，因此，算法查找的比較條件也可以表達(dá)為： while (current while （current -link != InsertP ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,7.從簡(jiǎn)單鏈表中刪除一個(gè)數(shù)據(jù)元素 在動(dòng)態(tài)存儲(chǔ)分配方式下，刪除鏈表

14、的某個(gè)結(jié)點(diǎn)（current所指結(jié)點(diǎn)）。只要將current的直接前驅(qū)元素q找到，然后對(duì)q的鏈接域作下述修改，即執(zhí)行： q-link=current-link 的操作就可以刪除結(jié)點(diǎn)current。實(shí)際上，它是將current的直接前驅(qū)結(jié)點(diǎn)q的鏈接指針直指current的直接后繼元素結(jié)點(diǎn)。鏈表中的被刪除結(jié)點(diǎn)從鏈表中斷開(kāi)后，還要將結(jié)點(diǎn)空間釋放。,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,刪除簡(jiǎn)單鏈表L中第k個(gè)數(shù)據(jù)結(jié)點(diǎn)算法（Delete） Status Delete(ChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,2.4 雙向鏈表,2.4.1 雙向鏈表的存儲(chǔ) 雙向鏈表的結(jié)點(diǎn)

15、類(lèi)型： typedef struct EType data; DoubleNode*plink; DoubleNode*nlink; DoubleNode； 其中，nlink指向current的直接后繼結(jié)點(diǎn)，plink指向current的直接前驅(qū)結(jié)點(diǎn)。鏈表中最后一個(gè)結(jié)點(diǎn)的nlink域?yàn)镹ULL，第一個(gè)結(jié)點(diǎn)的plink域?yàn)镹ULL。 表頭結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型定義如下： typedef struct HeadEType Hdata; DoubleNode*first; DoubleChainList；,2.4 雙向鏈表,2.4 雙向鏈表,2.4.2 雙向鏈表的操作 1. 雙向鏈表L中第k個(gè)數(shù)據(jù)元素之后插

16、入元素x 插入過(guò)程是首先從表頭開(kāi)始查找到第k個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)，用current指針指向第k個(gè)結(jié)點(diǎn)，完成插入。,2.4 雙向鏈表,2.4 雙向鏈表,Status Insert(DoubleChainList ,2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,if (k) / 插入在current 之后 q-nlink = current -nlink; q-plink = current; DoubleNode *p = current -nlink ; p-plink = q; current -nlink = q; else / 作為第一個(gè)元素結(jié)點(diǎn)插入 q-nlink = L-first; q-plink

17、= NULL; DoubleNode *p = L-first; p-plink = q; L-first = q; return OK; ,雙向鏈表L中第k個(gè)數(shù)據(jù)元素之后插入元素x算法（Insert）,Status Delete(DoubleChainList index+),2.3 簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作,q = q-nlink; if (!q) return ERROR; current = q; / current 指向第k個(gè)結(jié)點(diǎn) q = current -plink; p = current -nlink; q-nlink = p; p-plink = q; delete curre

18、nt; / 釋放被刪除結(jié)點(diǎn)current的空間 return OK; ,2. 從雙向鏈表中刪除一個(gè)數(shù)據(jù)元素,刪除雙向鏈表L中第k個(gè)數(shù)據(jù)結(jié)點(diǎn)算法（Delete）,2.5 單向循環(huán)鏈表和雙向循環(huán)鏈表 2.5.1 單向循環(huán)鏈表的存儲(chǔ) 簡(jiǎn)單鏈表的最后一個(gè)結(jié)點(diǎn)的鏈接域的值始終為空，若將最后一個(gè)結(jié)點(diǎn)的鏈接域值定義為指向開(kāi)頭（表頭結(jié)點(diǎn)或第一個(gè)數(shù)據(jù)結(jié)點(diǎn)）。則形成一個(gè)環(huán)，稱(chēng)為單向循環(huán)鏈表或稱(chēng)為循環(huán)鏈表。 循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的鏈域指向表頭結(jié)點(diǎn)，而循環(huán)鏈表為空時(shí)表頭結(jié)點(diǎn)指針指向自身。判斷指針指向鏈表的最后一個(gè)結(jié)點(diǎn)的方法是： current-link = L-first; 循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的鏈域指向第一個(gè)數(shù)

19、據(jù)元素結(jié)點(diǎn)，而循環(huán)鏈表為空時(shí)表頭結(jié)點(diǎn)指針為空（與簡(jiǎn)單鏈表的空狀態(tài)沒(méi)有區(qū)別）。判斷指針指向鏈表的第一個(gè)結(jié)點(diǎn)的方法是： current = L-first;,2.5 單向循環(huán)鏈表和雙向循環(huán)鏈表,2.5 單向循環(huán)鏈表和雙向循環(huán)鏈表,2.5.2 雙向循環(huán)鏈表的存儲(chǔ) 雙向循環(huán)鏈表是利用雙向鏈表中最后一個(gè)結(jié)點(diǎn)的直接后繼鏈接域（nlink），使其值為指向表頭結(jié)點(diǎn)或鏈表中的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)。這樣形成一個(gè)雙向環(huán)，稱(chēng)為雙向循環(huán)鏈表。 雙向循環(huán)鏈表的特點(diǎn)是只要已知鏈表中某個(gè)結(jié)點(diǎn)的指針（current），就可以通過(guò)該指針“周游” 雙向循環(huán)鏈表中的所有結(jié)點(diǎn)，這時(shí)不需要知道鏈表表頭結(jié)點(diǎn)的指針。 判斷指針指向鏈表的最后一

20、個(gè)結(jié)點(diǎn)的方法是： current-nlink = L-first; 判斷指針指向鏈表的第一個(gè)結(jié)點(diǎn)的方法是： current = L-first; 另外，如從給定的結(jié)點(diǎn)指針p0處開(kāi)始訪問(wèn)其后的第k個(gè)結(jié)點(diǎn)，則搜尋的過(guò)程為： current = p0 -nlink; int index=1; while (current!=p0 ,2.5 單向循環(huán)鏈表和雙向循環(huán)鏈表,2.5 單向循環(huán)鏈表和雙向循環(huán)鏈表,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表 2.6.1 模擬鏈表的存儲(chǔ)單向循環(huán)鏈表的存儲(chǔ) 模擬指針（Simulated Pointer）方式構(gòu)造簡(jiǎn)單鏈表，也稱(chēng)為利用靜態(tài)存儲(chǔ)分配構(gòu)造簡(jiǎn)單鏈表。在這種結(jié)構(gòu)下，存儲(chǔ)空

21、間是從一個(gè)事先定義的數(shù)組中申請(qǐng)，使用后又將使用過(guò)的空間歸還到數(shù)組中，鏈表中的空間不是由系統(tǒng)分配的，而是由用戶(hù)自己分配的，每個(gè)數(shù)據(jù)元素空間是數(shù)組中的一個(gè)數(shù)組元素，所以，指針的值也不是存儲(chǔ)空間的物理地址，而是數(shù)組的下標(biāo)。因此，也將這種鏈表的指針定義為“模擬指針”。 對(duì)存儲(chǔ)池中的空間，定義使用GetNode過(guò)程從這個(gè)存儲(chǔ)池中每次取一個(gè)結(jié)點(diǎn)空間（一個(gè)數(shù)組元素空間），使用FreeNode過(guò)程將使用過(guò)的空間歸還到存儲(chǔ)池中。這兩個(gè)操作 “等價(jià)于”C+中動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間過(guò)程（new）和釋放存儲(chǔ)空間過(guò)程（delete）。,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,為了實(shí)現(xiàn)指針的模擬，需要設(shè)計(jì)用于釋放和分配結(jié)點(diǎn)空間的過(guò)程

22、。首先，定義一個(gè)足夠大的數(shù)組（node），稱(chēng)為存儲(chǔ)池（storage pool），當(dāng)前未使用的結(jié)點(diǎn)空間將被放入這個(gè)存儲(chǔ)池中。開(kāi)始，這個(gè)存儲(chǔ)池中包含了所有數(shù)組元素空間： node 0 ：MaxSize -1 數(shù)據(jù)元素的結(jié)點(diǎn)仍然是由兩個(gè)部分組成：數(shù)據(jù)域和鏈接域。對(duì)存儲(chǔ)池中的所有空間，是采用鏈表方式將所有的可用空間 “鏈”在一起，由一個(gè)稱(chēng)為avail的指針指向。 初始狀態(tài)時(shí)，可將定義的node數(shù)組中任何一個(gè)數(shù)組元素空間作為起點(diǎn)，圖中是以0下標(biāo)的空間作為起點(diǎn)，每個(gè)數(shù)組元素與其后面的數(shù)組元素“鏈”在一起，即在每個(gè)數(shù)組元素的鏈接域中填入下一個(gè)數(shù)組元素的下標(biāo)，最后一個(gè)數(shù)組元素的鏈接域中填入“空”（約定為-1

23、）。,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,L1: A1,A2,A3,A4,A5,A6,A7 L2: B1,B2 L3: C1,C2,C3,C4,C5,C6,靜態(tài)存儲(chǔ)分配方式下，鏈表中的每個(gè)結(jié)點(diǎn)結(jié)構(gòu)： typedef struct EType data; int link; SimNode； 鏈接域link的類(lèi)型不是指針類(lèi)型，而是整型（因?yàn)閿?shù)組的下標(biāo)是整型）。存儲(chǔ)池的表頭結(jié)點(diǎn)結(jié)構(gòu)的定義： typedef struct SimNode*node; /指向數(shù)組（存儲(chǔ)池）的指針 intMaxSize; /存儲(chǔ)池大小 intavail;/指向存儲(chǔ)池鏈表的第一個(gè)結(jié)點(diǎn) Sim

24、ChainList； 整個(gè)存儲(chǔ)池的核心部分是一個(gè)由node指向的數(shù)組；另外，用MaxSize記載存儲(chǔ)池的大小，即node數(shù)組的大??；用avail指向存儲(chǔ)池鏈表（未用空間）的第一個(gè)結(jié)點(diǎn)，avail在邏輯上被看作指針，但由于靜態(tài)分配的空間，所以空間的地址是整型。,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,2.6.2 模擬鏈表的操作 1. 模擬鏈表的初始化 模擬鏈表的初始化過(guò)程就是定義一個(gè)數(shù)組，并將整個(gè)數(shù)組鏈成一個(gè)存儲(chǔ)池。其基本思想是，將定義的結(jié)點(diǎn)數(shù)組的鏈域從第一個(gè)元素開(kāi)始逐個(gè)地鏈接到下一結(jié)點(diǎn)元素，即結(jié)點(diǎn)link域的值以下一個(gè)元素的下標(biāo)賦值，而最后一個(gè)結(jié)點(diǎn)的link域以-1賦值。 模擬鏈表的初始化算法（Cr

25、eat） void Creat(SimChainList ,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,2.模擬鏈表中結(jié)點(diǎn)空間的分配 分配結(jié)點(diǎn)的思想是：將avail鏈表第一結(jié)點(diǎn)作為一可用結(jié)點(diǎn)空間取走（從avail鏈表中刪除），可用空間鏈表表頭指針指向avail鏈表的下一結(jié)點(diǎn)。 模擬鏈表分配結(jié)點(diǎn)空間算法（GetNode） int GetNode(SimChainList ,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,3.模擬鏈表中結(jié)點(diǎn)空間的釋放 當(dāng)發(fā)生刪除時(shí)，釋放的結(jié)點(diǎn)仍要?dú)w還到可用結(jié)點(diǎn)鏈表中去，歸還（釋放）結(jié)點(diǎn)的基本思想是：將被刪結(jié)點(diǎn)作為一可用結(jié)點(diǎn)插入到可用結(jié)點(diǎn)鏈表avail中，作為第一結(jié)點(diǎn)。 模擬鏈表釋放結(jié)點(diǎn)空

26、間算法（FreeNode） void FreeNode(SimChainList ,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,4.模擬鏈表中插入結(jié)點(diǎn)的運(yùn)算 由于模擬鏈表是一個(gè)數(shù)組空間，所以插入時(shí)要提供某鏈表的第一個(gè)結(jié)點(diǎn)的下標(biāo)地址first參數(shù)。first實(shí)際上是靜態(tài)存儲(chǔ)空間上某個(gè)鏈表的首地址。 first指向的鏈表中第k 個(gè)結(jié)點(diǎn)后面插入結(jié)點(diǎn)算法（Insert） Status Insert(SimChainList ,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,5. 模擬鏈表中刪除結(jié)點(diǎn)的運(yùn)算 first指向的鏈表中刪除第k 個(gè)結(jié)點(diǎn)算法（Delete） Status Delete(SimChainList ,2.6

27、 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,6 . 模擬鏈表的輸出 模擬鏈表輸出算法（FreeNode） void Output(SimChainList ,2.6 模擬指針?lè)绞綐?gòu)造簡(jiǎn)單鏈表,2.7 多重鏈表,2.7 多重鏈表,2.8 鏈表應(yīng)用 2.8.1 結(jié)點(diǎn)移至表首運(yùn)算 簡(jiǎn)單鏈表L中將第k個(gè)數(shù)據(jù)結(jié)點(diǎn)移至表首算法（MoveFirst） Status MoveFirst (ChainList ,2.8 鏈表應(yīng)用,2.8 鏈表應(yīng)用,2.8.2 鏈表的逆向運(yùn)算 簡(jiǎn)單鏈表L的逆向的算法（Invert） Status Invert (ChainList ,2.8 鏈表應(yīng)用,2.8 鏈表應(yīng)用,2.8.3 多項(xiàng)式的相加運(yùn)算 設(shè)多項(xiàng)式為： pn(x)=anxn+an-1x