chapt線性表二PPT課件

1、第二章第二章 線性表線性表o 線性表概念及其邏輯結(jié)構(gòu)o 線性表的存儲(chǔ)結(jié)構(gòu)o 順序存儲(chǔ)o 鏈?zhǔn)酱鎯?chǔ)o 數(shù)組o 一維數(shù)組o 結(jié)構(gòu)數(shù)組o 二維數(shù)組o 鏈表o 單鏈表o 雙鏈表o 循環(huán)鏈表o 靜態(tài)鏈表o 線性表應(yīng)用實(shí)例o 有序線性表第1頁(yè)/共46頁(yè)線性表（二）線性表（二）o 鏈表o 單鏈表o 雙鏈表o 循環(huán)鏈表o 靜態(tài)鏈表o 線性表應(yīng)用實(shí)例o 有序線性表第2頁(yè)/共46頁(yè)4 4 鏈表具備鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表也可稱之為鏈表。鏈表串聯(lián)的方式通常有兩種：一種是利用數(shù)組結(jié)構(gòu)串聯(lián)的有序列表：利用兩個(gè)數(shù)組，一個(gè)存放數(shù)據(jù)，另一個(gè)存放鏈接關(guān)系。 另一種是以結(jié)點(diǎn)形式串接的鏈表，通常我們所指的鏈表就是這種動(dòng)態(tài)內(nèi)存配置的鏈表

2、。 結(jié)點(diǎn)（node）：數(shù)據(jù)元素的存儲(chǔ)映像,包含數(shù)據(jù)域和指針域信息。數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素的域稱作數(shù)據(jù)域，指針域（鏈域）：存儲(chǔ)直接后繼元素存儲(chǔ)位置的域稱作指針域。指針域中存儲(chǔ)的信息稱作指針或鏈。 n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表（a1 , a2 , a3 , , an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第3頁(yè)/共46頁(yè)一、單鏈表31頭指針Head存儲(chǔ)地址數(shù)據(jù)域指針域 1LI43 7QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25ZHAOQIANSUNLIZHOUWUZHENGWANG NULL鏈表中若每個(gè)結(jié)點(diǎn)指針域中只包含一個(gè)鏈，稱為單鏈表或線性鏈表。單鏈表

3、存儲(chǔ)示意圖：內(nèi)存空間的分配表示?！纠烤€性表（zhao, qian, sun, li, zhou, wu, zheng, wang） 單鏈表邏輯狀態(tài)示意圖 ： Head第4頁(yè)/共46頁(yè)整個(gè)鏈表的存取必須從頭指針開(kāi)始進(jìn)行，頭指針指示鏈表中的首結(jié)點(diǎn)（第一個(gè)元素的存儲(chǔ)映像）的存儲(chǔ)位置，這里用Head表示；由于最后一個(gè)元素沒(méi)有直接后繼，最后一個(gè)結(jié)點(diǎn)的指針是NULL（指針為空），表示這是鏈表的結(jié)尾。由于取得任意一個(gè)數(shù)據(jù)元素都必須從頭指針出發(fā)尋找，所以單鏈表是非隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)。這種單鏈表數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的，只要確定頭指針的位置，就可以確定鏈表中所有元素的位置。換句話說(shuō)，單鏈表

4、由頭指針唯一確定?？梢越柚呒?jí)語(yǔ)言中的“指針”數(shù)據(jù)類型來(lái)描述線性鏈表。 鏈?zhǔn)浇Y(jié)構(gòu)的存儲(chǔ)效率： 存儲(chǔ)密度=結(jié)點(diǎn)數(shù)據(jù)信息所占存儲(chǔ)空間 / / 結(jié)點(diǎn)結(jié)構(gòu)所占全部空間第5頁(yè)/共46頁(yè)帶頭結(jié)點(diǎn)單鏈表示意圖帶頭結(jié)點(diǎn)單鏈表示意圖 在線性表的鏈?zhǔn)酱鎯?chǔ)中，為了便于插入和刪除算法的實(shí)現(xiàn)，可以使用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，每個(gè)鏈表帶有一個(gè)頭結(jié)點(diǎn)，并通過(guò)頭結(jié)點(diǎn)的指針惟一標(biāo)識(shí)該鏈表。頭結(jié)點(diǎn)數(shù)據(jù)域不需要賦值，指針指向鏈表的首個(gè)含有實(shí)質(zhì)信息的結(jié)點(diǎn)。第6頁(yè)/共46頁(yè)1、單鏈表內(nèi)結(jié)點(diǎn)的配置鏈表的內(nèi)存空間動(dòng)態(tài)配置，在程序運(yùn)行過(guò)程中才向系統(tǒng)配置所需空間。使用鏈表之前，先要定義出每一個(gè)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。 C語(yǔ)言中，結(jié)點(diǎn)的格式聲明如下： st

5、ruct 結(jié)構(gòu)名稱 數(shù)據(jù)類型 數(shù)據(jù)變量； 數(shù)據(jù)類型 數(shù)據(jù)變量； . struct 結(jié)構(gòu)名稱 *next； ； typedef struct 結(jié)構(gòu)名稱 Node；/定義Node為使用上述結(jié)構(gòu)的結(jié)點(diǎn)類型 typedef Node *link； /定義指向Node結(jié)點(diǎn)的指針類型定義了上述結(jié)點(diǎn)，在程序中使用結(jié)點(diǎn)結(jié)構(gòu)之前，需要聲明新結(jié)點(diǎn)： Link 變量名稱; （一個(gè)具備Node類型的結(jié)點(diǎn)）第7頁(yè)/共46頁(yè)程序運(yùn)行中用到所聲明結(jié)點(diǎn)時(shí)，還需要配置結(jié)點(diǎn)： 向系統(tǒng)申請(qǐng)結(jié)點(diǎn)所需內(nèi)存空間； 為結(jié)點(diǎn)數(shù)據(jù)域賦值，并標(biāo)記指針域。 例如，已定義一個(gè)名稱為Student的結(jié)點(diǎn)，使用到這個(gè)結(jié)點(diǎn)時(shí)，還需利用malloc函數(shù)向系

6、統(tǒng)要求配置內(nèi)存空間。 Student = （Link）malloc（sizeof（Node）； 內(nèi)存配置成功，則為該結(jié)點(diǎn)返回一個(gè)指針；內(nèi)存配置不成功時(shí)，返回NULL指針。 另外，調(diào)用malloc函數(shù)，還需在程序開(kāi)頭使用包含命令注明其頭文件：#include 第8頁(yè)/共46頁(yè)結(jié)點(diǎn)空間配置成功則賦值： 為結(jié)點(diǎn)的數(shù)據(jù)域賦值： New-Data(結(jié)點(diǎn)結(jié)構(gòu)中數(shù)據(jù)變量名) = 23; 若結(jié)點(diǎn)結(jié)構(gòu)中定義了多個(gè)變量，則可逐一賦值。 如：New-Number = 23; New-Namei = Datanamei; 為結(jié)點(diǎn)的指針域賦值： New-Next = NULL; 內(nèi)存配置成功，且為結(jié)點(diǎn)賦值之后結(jié)構(gòu)如下：

7、（若新結(jié)點(diǎn)為New） NewData Next 23第9頁(yè)/共46頁(yè) 單鏈表類型定義也可如下表示( (本教材定義方法) )： 在單鏈表中，假定每個(gè)結(jié)點(diǎn)類型用LinkList表示，它應(yīng)包括存儲(chǔ)元素的數(shù)據(jù)域，這里用 data 表示，其類型使用通用類型標(biāo)識(shí)符ElemType 表示；還包括存儲(chǔ)后繼元素位置的指針域，這里用 next表示。則LinkList類型的定義如下類型的定義如下: typedef struct LNode /*定義單鏈表結(jié)點(diǎn)類型定義單鏈表結(jié)點(diǎn)類型*/ ElemType data; struct LNode *next; /*指向后繼結(jié)點(diǎn)指向后繼結(jié)點(diǎn)*/ LinkList; /*定義

8、單鏈表*/ 定義了上述結(jié)點(diǎn)，在程序中使用結(jié)點(diǎn)結(jié)構(gòu)之前，聲明新結(jié)點(diǎn)： LinkList *結(jié)點(diǎn)名稱；第10頁(yè)/共46頁(yè) 如，定義結(jié)點(diǎn)s： LinkList *s ； 則配置（建立）新結(jié)點(diǎn)s的過(guò)程為： s=(LinkList * *)malloc(sizeof(LinkList); s- -data=ai i; s- -next=NULL;第11頁(yè)/共46頁(yè)2 2、單鏈表的建立單鏈表的建立就是從首結(jié)點(diǎn)開(kāi)始，將每個(gè)結(jié)點(diǎn)單向串聯(lián)起來(lái)。建立步驟：為每一個(gè)結(jié)點(diǎn)配置空間；為結(jié)點(diǎn)賦值；掛接結(jié)點(diǎn)。（1）頭插法先聲明一個(gè)頭結(jié)點(diǎn)Head，為其配置空間；令Head-Next =NULL。 （空頭結(jié)點(diǎn)，便于鏈表的插入和

9、刪除操作。）每輸入一筆數(shù)據(jù)就聲明一個(gè)新結(jié)點(diǎn)New，為其配置空間；為新結(jié)點(diǎn)數(shù)據(jù)域賦值，令New-Next = Head -Next （即將新結(jié)點(diǎn)鏈接到鏈表頭結(jié)點(diǎn)之后）；令頭結(jié)點(diǎn)指針指向New 。教材p39p39、p40p40第12頁(yè)/共46頁(yè)adc bi=0 i=1 i=2 i=3head采用頭插法建立單鏈表的過(guò)程采用頭插法建立單鏈表的過(guò)程headaheaddaheadcdaheadbcda第第1 1步步: :建頭結(jié)點(diǎn)建頭結(jié)點(diǎn)第第2 2步步:i:i0,0,新建新建a a結(jié)點(diǎn)結(jié)點(diǎn), ,插入到頭結(jié)點(diǎn)之后插入到頭結(jié)點(diǎn)之后第第3 3步步:i:i1,1,新建新建d d結(jié)點(diǎn)結(jié)點(diǎn), ,插入到頭結(jié)點(diǎn)之后插入到頭

10、結(jié)點(diǎn)之后第第4 4步步:i:i2,2,新建新建c c結(jié)點(diǎn)結(jié)點(diǎn), ,插入到頭結(jié)點(diǎn)之后插入到頭結(jié)點(diǎn)之后第第5 5步步:i:i3,3,新建新建b b結(jié)點(diǎn)結(jié)點(diǎn), ,插入到頭結(jié)點(diǎn)之后插入到頭結(jié)點(diǎn)之后第13頁(yè)/共46頁(yè)（2）尾插法先聲明一個(gè)頭結(jié)點(diǎn)Head，為其配置空間；令Head-Next =NULL。 （空頭結(jié)點(diǎn)，便于鏈表的插入和刪除操作。）每輸入一筆數(shù)據(jù)就聲明一個(gè)新結(jié)點(diǎn)New，為其配置空間；為新結(jié)點(diǎn)數(shù)據(jù)域賦值，令New-Next = NULL； 將新結(jié)點(diǎn)鏈接到鏈表尾結(jié)點(diǎn)之后；令尾結(jié)點(diǎn)為New 。教材p39p39、p40p40第14頁(yè)/共46頁(yè)bcdai=0 i=1 i=2 i=3head頭結(jié)點(diǎn)頭結(jié)點(diǎn)a

11、dcbb采用尾插法建立單鏈表的過(guò)程采用尾插法建立單鏈表的過(guò)程第15頁(yè)/共46頁(yè)3 3、單鏈表的釋放鏈?zhǔn)浇Y(jié)構(gòu)使用結(jié)束須向系統(tǒng)釋放使用的空間，以節(jié)省內(nèi)存空間，保持內(nèi)存配置的動(dòng)態(tài)特性。單鏈表的釋放就是將結(jié)點(diǎn)逐個(gè)釋放。 釋放內(nèi)存空間需調(diào)用free函數(shù)，聲明格式如下： free(變量名稱) 如上例 free(New) 單鏈表釋放步驟：先將工作指針指向第一個(gè)結(jié)點(diǎn)，將當(dāng)前結(jié)點(diǎn)釋放后，再將工作指針指向其下一個(gè)結(jié)點(diǎn)。重復(fù)該步驟直至工作指針指向NULL。 教材p41 DestroyList(L) 【例】Void ClearList(LinkList &L) / 初始條件：線性表L已存在。操作結(jié)果：將L重置

12、為空表 。 LinkList *p; while(L) / L不空 p=L; / p指向首元結(jié)點(diǎn) L=L-next; / L指向第2個(gè)結(jié)點(diǎn)(新首元結(jié)點(diǎn)) free(p); / 釋放首元結(jié)點(diǎn) 16. 第16頁(yè)/共46頁(yè)4 4、單鏈表的基本操作定義好單鏈表結(jié)構(gòu)，基于該結(jié)構(gòu)通常定義如下一組基本操作：（1）初始化單鏈表InitList(L) 建立一個(gè)空頭結(jié)點(diǎn)。算法時(shí)間復(fù)雜度O(1)。（2）銷毀單鏈表DestoryList(L) 即釋放單鏈表L。算法時(shí)間復(fù)雜度O(n)。（3）判斷單鏈表是否為空ListEmpty(L) 返回值為1或0。算法時(shí)間復(fù)雜度O(1)。（4）求取單鏈表長(zhǎng)度ListLength(L)

13、 即返回單鏈表的結(jié)點(diǎn)個(gè)數(shù)，作為鏈表長(zhǎng)度。算法時(shí)間復(fù)雜度O(n)。（5）輸出單鏈表DispList(L) 從首結(jié)點(diǎn)起，將結(jié)點(diǎn)數(shù)據(jù)域紙打印在標(biāo)準(zhǔn)輸出。算法時(shí)間復(fù)雜度O(n)。（6）從單鏈表中取得指定結(jié)點(diǎn)的數(shù)據(jù)元GetElem(L,i,e) 從首結(jié)點(diǎn)起，找到指定的第i個(gè)結(jié)點(diǎn)，并取出數(shù)據(jù)值賦給變量e。屬于線性查找，算法時(shí)間復(fù)雜度O(n)。第17頁(yè)/共46頁(yè)（7）從單鏈表中查找指定數(shù)據(jù)元的結(jié)點(diǎn)LocateElem(L,e) 從首結(jié)點(diǎn)起，找到關(guān)鍵字值為e的結(jié)點(diǎn)，并返回結(jié)點(diǎn)位置（第i個(gè)）。屬于線性查找，算法時(shí)間復(fù)雜度O(L-length)或O(n)。（8）在單鏈表中插入結(jié)點(diǎn)ListInsert(L,i,e)

14、 令e成為鏈表中第i個(gè)結(jié)點(diǎn)。從首結(jié)點(diǎn)起，找到第i-1個(gè)結(jié)點(diǎn)，并將數(shù)據(jù)元為e的新結(jié)點(diǎn)插入其后。 插入位置i: 1iListLength(L)+1 該算法查找結(jié)點(diǎn)屬于線性查找，算法時(shí)間復(fù)雜度O(n)。（9）從單鏈表中取得指定結(jié)點(diǎn)的數(shù)據(jù)元GetElem(L,i,e) 從首結(jié)點(diǎn)起，找到指定的第i個(gè)結(jié)點(diǎn)，取出數(shù)據(jù)值賦給變量e保留，而后刪除結(jié)點(diǎn)i。屬于線性查找，算法時(shí)間復(fù)雜度O(n)。兩種常規(guī)操作：在單鏈表中插入結(jié)點(diǎn)操作和刪除結(jié)點(diǎn)操作 第18頁(yè)/共46頁(yè) 插入結(jié)點(diǎn)運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)的位置上。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再在其后插入新結(jié)點(diǎn)。 單鏈表插入結(jié)點(diǎn)的過(guò)程如下

15、圖所示。第19頁(yè)/共46頁(yè)插入結(jié)點(diǎn)示意圖第20頁(yè)/共46頁(yè) 刪除結(jié)點(diǎn)運(yùn)算 刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再刪除其后的結(jié)點(diǎn)。 刪除單鏈表結(jié)點(diǎn)的過(guò)程如下圖所示。第21頁(yè)/共46頁(yè)刪除結(jié)點(diǎn)示意圖第22頁(yè)/共46頁(yè)5 5、單鏈表的應(yīng)用單鏈表在系統(tǒng)設(shè)計(jì)中應(yīng)用十分廣泛，是實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。單鏈表的三項(xiàng)基本操作：定位（查找結(jié)點(diǎn)）、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)。定位操作的時(shí)間復(fù)雜度為O（n）；插入與刪除結(jié)點(diǎn)算法的時(shí)間復(fù)雜度均為O（1）。 下面討論幾個(gè)基于單鏈表的典型操作：（1）單鏈表的反轉(zhuǎn) 把單鏈表的指針從頭至尾反轉(zhuǎn)方向，原先的頭結(jié)點(diǎn)作為尾結(jié)點(diǎn)，指針指向NULL，逐個(gè)

16、反轉(zhuǎn)指針?lè)较颍鹊奈步Y(jié)點(diǎn)變?yōu)轭^結(jié)點(diǎn)。 設(shè)計(jì)思路：可分三種情況首結(jié)點(diǎn)的指針?lè)崔D(zhuǎn)；中間結(jié)點(diǎn)的指針?lè)崔D(zhuǎn)；尾結(jié)點(diǎn)的指針?lè)崔D(zhuǎn)。具體方法：需要設(shè)置三個(gè)指針 Back、pointer、Next。以pointer為當(dāng)前結(jié)點(diǎn)（也是行走結(jié)點(diǎn)）。 第23頁(yè)/共46頁(yè)步驟一： 先將Back指向首結(jié)點(diǎn)；Pointer指向第二個(gè)結(jié)點(diǎn)；反轉(zhuǎn)首結(jié)點(diǎn)（Back）的指針，指向NULL。 Back=Head; Pointer=Back-Next Back-Next=NULL 然后定義Next結(jié)點(diǎn)為第三個(gè)結(jié)點(diǎn)；將第二個(gè)結(jié)點(diǎn)Pointer指針?lè)崔D(zhuǎn)；將Back結(jié)點(diǎn)后移一位；將Pointer結(jié)點(diǎn)也后移一位。（紅色） Next= Poin

17、ter- Next; Pointer- Next=Back; Back=Pointer; Pointer=Netx;BackPointerHeadNull Back NextPointer第24頁(yè)/共46頁(yè)步驟二： 經(jīng)過(guò)步驟一后圖示如下： 此時(shí)，Back、Pointer、Next均為中間結(jié)點(diǎn)。 從設(shè)立Next結(jié)點(diǎn)開(kāi)始，重復(fù)第二種情況，逐個(gè)反轉(zhuǎn)Pointer所指向的結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)）指針，直到Pointer結(jié)點(diǎn)的指針指向NULL為止。步驟三： 反轉(zhuǎn)尾結(jié)點(diǎn)的指針，并令尾結(jié)點(diǎn)為首結(jié)點(diǎn)。 Pointer-Next=Back; Head=Pointer; 總結(jié)：1）總是在反轉(zhuǎn)某個(gè)結(jié)點(diǎn)指針之前定義好其下一個(gè)

18、結(jié)點(diǎn)的指針 2）每一步均完成對(duì)Pointer 結(jié)點(diǎn)的反轉(zhuǎn) 3）Next比Back、Pointer滯后一步定義，作為后半截鏈表首節(jié)點(diǎn)NullBackPointerNext第25頁(yè)/共46頁(yè)Link Invert_List (Link Head) Link pointer; Link Back; Link next; Back=Head; Pointer=Back-Next； Back-Next=NULL； /*反轉(zhuǎn)首結(jié)點(diǎn)*/ While(Pointer- Next!=NULL) Next= Pointer- Next; Pointer- Next=Back; Back=Pointer; Poin

19、ter=Netx; /*反轉(zhuǎn)中間結(jié)點(diǎn)*/ Pointer-Next=Back; Head=Pointer; return Head; /*反轉(zhuǎn)尾結(jié)點(diǎn)*/第26頁(yè)/共46頁(yè) 【例】 設(shè)C=a1,b1,a2,b2,an,bn為一線性表,采用帶頭結(jié)點(diǎn)的hchc單鏈表存放,編寫(xiě)一個(gè)算法,將其拆分為兩個(gè)線性表,使得: A=a1,a2,an,B=b1,b2,bn 解: 設(shè)拆分后的兩個(gè)線性表都用帶頭結(jié)點(diǎn)的單鏈表存放。 先建立兩個(gè)頭結(jié)點(diǎn)*ha和*hb,它們用于存放拆分后的線性表A和B。ra和rb分別指向這兩個(gè)單鏈表的表尾,用p指針掃描單鏈表hc,將當(dāng)前結(jié)點(diǎn)*p鏈到ha未尾,p沿next域下移一個(gè)結(jié)點(diǎn),若不為空

20、,則當(dāng)前結(jié)點(diǎn)*p鏈到hb未尾,p沿next域下移一個(gè)結(jié)點(diǎn),如此這樣,直到p為空。最后將兩個(gè)尾結(jié)點(diǎn)的next域置空。 對(duì)應(yīng)算法如下:第27頁(yè)/共46頁(yè) void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的頭結(jié)點(diǎn)利用的頭結(jié)點(diǎn)利用hc的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)*/ ra=ha; /*ra始終指向始終指向ha的末尾結(jié)點(diǎn)的末尾結(jié)點(diǎn)*/ hb=(LinkList *)malloc(sizeof(LinkList); /*創(chuàng)建創(chuàng)建hb頭結(jié)點(diǎn)頭結(jié)點(diǎn)*/ rb=hb; /

21、*rb始終指向始終指向hb的末尾結(jié)點(diǎn)的末尾結(jié)點(diǎn)*/ while (p!=NULL) ra-next=p;ra=p; /*將將*p鏈到鏈到ha單鏈表未尾單鏈表未尾*/ p=p-next; if (p!=NULL) rb-next=p; rb=p; /*將將*p鏈到鏈到hb單鏈表未尾單鏈表未尾*/ p=p-next; ra-next=rb-next=NULL; /*兩個(gè)尾結(jié)點(diǎn)的兩個(gè)尾結(jié)點(diǎn)的next域置空域置空*/第28頁(yè)/共46頁(yè) 【例】 有一個(gè)帶頭結(jié)點(diǎn)的單鏈表head,其ElemType類型為char,設(shè)計(jì)一個(gè)算法使其元素遞增有序。 解:若原單鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn),先構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)

22、的有序表(只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表一定是有序表)。掃描原單鏈表余下的結(jié)點(diǎn)*p(當(dāng)前結(jié)點(diǎn)，行走直到p=NULL為止),在有序表中通過(guò)比較找到插入*p的前驅(qū)結(jié)點(diǎn)*q,然后將*p插入到*q之后(這里實(shí)際上采用的是直接插入排序方法)。第29頁(yè)/共46頁(yè) void Sort(LinkList *&head) LinkList *p=head-next,*q,*r; /p指向首個(gè)數(shù)據(jù)結(jié)點(diǎn)/if (p!=NULL) /head有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn)/ r=p-next; /r保存p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針/ p-next=NULL; /構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表,頭結(jié)點(diǎn)仍為head/ p=r; whil

23、e (p!=NULL) r=p-next; /r保存p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針/ q=head; while (q-next!=NULL & q-next-datadata) q=q-next; /在有序表中尋找插入*p的前驅(qū)結(jié)點(diǎn)*q/ p-next=q-next;/將*p插入到*q之后/ q-next=p; p=r; /掃描原單鏈表余下的結(jié)點(diǎn)/ 第30頁(yè)/共46頁(yè)二、雙鏈表單鏈表的結(jié)點(diǎn)中只有一個(gè)指向其直接后繼的指針。由此，從某個(gè)結(jié)點(diǎn)出發(fā)只能順著指針?lè)较蛳蚝髮ふ移渌慕Y(jié)點(diǎn)。若要尋找某個(gè)結(jié)點(diǎn)的直接前趨，仍需要從首結(jié)點(diǎn)出發(fā)，找到那個(gè)直接后繼為該結(jié)點(diǎn)的結(jié)點(diǎn)。為了克服單鏈表這種單向性的缺點(diǎn)，我們可以

24、使用雙向鏈表。顧名思義，在雙向鏈表中有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)的直接前趨；另一個(gè)指向結(jié)點(diǎn)的直接后繼。1、雙向鏈表的建立對(duì)于雙鏈表，采用類似于單鏈表的類型定義，其DLinkList類型的定義如下： typedef struct DNode /*定義雙鏈表結(jié)點(diǎn)類型*/ ElemType data; struct DNode *prior; /*指向前驅(qū)結(jié)點(diǎn)*/ struct DNode *next; /*指向后繼結(jié)點(diǎn)*/ DLinkList; /*定義雙鏈表*/第31頁(yè)/共46頁(yè)雙鏈表的內(nèi)存定位，仍可由首結(jié)點(diǎn)或尾結(jié)點(diǎn)確定。我們可根據(jù)通常在哪一端操作確定來(lái)保留定位結(jié)點(diǎn)，當(dāng)然也可以保留首尾兩個(gè)結(jié)點(diǎn)。雙

25、鏈表建立： 如上圖三個(gè)結(jié)點(diǎn) ( node1-back=NULL; ) node1-next=node2; node2-back=node1; node2-next=node3; node3-bake=node2; ( node3-next=NULL; )編制具體算法時(shí) ，仍可如單鏈表一樣采用頭插法和尾插法實(shí)現(xiàn)。教材p44-45 node1 node3 node2第32頁(yè)/共46頁(yè)3、雙鏈表的基本操作在雙鏈表中,有些操作如求長(zhǎng)度、取元素值、查找元素、輸出和釋放鏈表等操作算法與單鏈表中相應(yīng)算法是相同的。雙鏈表插入和刪除與單鏈表有較大差別。單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變

26、化。雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化。（1）在雙鏈表中插入結(jié)點(diǎn) 在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)s結(jié)點(diǎn)，其操作語(yǔ)句描述為: s-next=p-next; /*將s插入到p之后*/ s-prior=p; p-next-prior=s; 仍需注意鏈表斷裂問(wèn)題！ p-next=s; 插入結(jié)點(diǎn)操作算法的時(shí)間復(fù)雜度為O O(n)(n)【例】在雙鏈表中插入元素算法 教材p45第33頁(yè)/共46頁(yè)雙鏈表中插入結(jié)點(diǎn)示意圖第34頁(yè)/共46頁(yè)（1）在雙鏈表中刪除結(jié)點(diǎn) 刪除雙鏈表L中*p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。其操作語(yǔ)句描述為: p-next=q-next; q-next-prior=p; 雙

27、鏈表中刪除結(jié)點(diǎn)操作算法的時(shí)間復(fù)雜度為O(n)第35頁(yè)/共46頁(yè)三、循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。特點(diǎn)是鏈表的尾指針不指向NULL，而是指向Head，整個(gè)鏈表形成一個(gè)環(huán)鏈。由此，從任意一個(gè)結(jié)點(diǎn)出發(fā)均可找到鏈表中的其它結(jié)點(diǎn) 。仍可設(shè)立頭結(jié)點(diǎn)來(lái)確定整條鏈表的位置。因?yàn)槠涫孜蚕嘟拥奶匦?，有時(shí)候只需要設(shè)立一個(gè)尾指針確定鏈表的內(nèi)存位置，并可不再設(shè)立頭指針以簡(jiǎn)化操作。對(duì)當(dāng)前指針在行走一遍的相關(guān)操作中，通常不再判斷其是否為NULL，而是是否為Head（或空頭結(jié)點(diǎn)L）。1、建立循環(huán)單鏈表 如同建立單鏈表算法，可使用尾插法，結(jié)點(diǎn)插入結(jié)束后將尾結(jié)點(diǎn)指針指向頭結(jié)點(diǎn)。 教材P40尾插法算法 修改尾指針：

28、r-next=L;第36頁(yè)/共46頁(yè) 帶頭結(jié)點(diǎn)的循環(huán)單鏈表和循環(huán)雙鏈表示意圖第37頁(yè)/共46頁(yè)3、釋放循環(huán)鏈表的結(jié)點(diǎn)方法一：如果確定了頭結(jié)點(diǎn)的位置，則釋放循環(huán)鏈表的結(jié)點(diǎn)時(shí)，通常從第二個(gè)結(jié)點(diǎn)開(kāi)始，這是為了保存整個(gè)環(huán)鏈的完整性。 比如先將頭結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)鏈接，釋放第二個(gè)，再與第四個(gè)鏈接，釋放第三個(gè)如此依序，釋放完尾結(jié)點(diǎn)時(shí)，頭結(jié)點(diǎn)的指針指向自己，直接釋放頭結(jié)點(diǎn)。 如此操作，在整個(gè)釋放過(guò)程中可以不必重新為系統(tǒng)確定整條鏈表的位置，頭結(jié)點(diǎn)一直存在至最后一個(gè)才被釋放。另外環(huán)鏈一直不會(huì)斷裂，不影響其他操作。 算法實(shí)現(xiàn)如下： （使用pointer指針指向當(dāng)前欲釋放的結(jié)點(diǎn)：） next=head-next; /

29、*next先指向第二個(gè)結(jié)點(diǎn)*/ While ( next!=head) pointer=next; /*next做為行走結(jié)點(diǎn)，從第二個(gè)走向尾*/ next=next-next; head-next=next; /*頭結(jié)點(diǎn)不變，并且環(huán)鏈不斷裂*/ free(pointer); free(head);第38頁(yè)/共46頁(yè)方法二：先將循環(huán)鏈表斷為單鏈表，再?gòu)氖捉Y(jié)點(diǎn)一直釋放到尾結(jié)點(diǎn)。 將首結(jié)點(diǎn)做為尾結(jié)點(diǎn)，則第二個(gè)結(jié)點(diǎn)為新的首結(jié)點(diǎn)，然后從新的首結(jié)點(diǎn)一直釋放到尾結(jié)點(diǎn)。（釋放每一個(gè)首結(jié)點(diǎn)，所以需考慮重新定位） 實(shí)際上與上一種釋放方式一樣，都從原循環(huán)鏈表第二個(gè)開(kāi)始，只是首尾指針有所變化，變成了單鏈表。這種方法破

30、壞了環(huán)鏈的特性，適合于單一的釋放結(jié)點(diǎn)操作。 具體算法： Pointer=head-next; head Head-next=NULL; ( head ) While (pointer!=NULL) pointer pointer Head=pointer; pointer=pointer-next; free(head); 第39頁(yè)/共46頁(yè)【例】編寫(xiě)出判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱相等的算法。 p從左向右掃描L，q從右向左掃描L，若對(duì)應(yīng)數(shù)據(jù)結(jié)點(diǎn)的data域不相等，則退出循環(huán)，否則繼續(xù)比較，直到p與q相等或p的下一個(gè)結(jié)點(diǎn)為*q為止。對(duì)應(yīng)算法如下:int Equeal(DLinkList

31、*L) int same=1; DLinkList *p=L-next; /*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ DLinkList *q=L-prior; /*q指向最后數(shù)據(jù)結(jié)點(diǎn)*/ while (same=1) if (p-data!=q-data) same=0; else if (p=q) break;/*數(shù)據(jù)結(jié)點(diǎn)為奇數(shù)的情況*/ q=q-prior; if (p=q) break;/*數(shù)據(jù)結(jié)點(diǎn)為偶數(shù)的情況*/ p=p-next; return same; 第40頁(yè)/共46頁(yè)四、靜態(tài)鏈表 靜態(tài)鏈表借用一維數(shù)組來(lái)描述線性鏈表。通過(guò)定義一個(gè)較大的結(jié)構(gòu)體數(shù)組來(lái)作為備用結(jié)點(diǎn)空間(即存儲(chǔ)池)，每個(gè)結(jié)點(diǎn)應(yīng)至少含有兩個(gè)域：data域和cursor域。 一維數(shù)組中的一個(gè)分量（元素）表示一個(gè)結(jié)點(diǎn)，使用游標(biāo)(指示器cur，即偽指針)代替指針以指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。數(shù)組中的第0個(gè)分量可以看成頭結(jié)點(diǎn)，其指針域指示靜態(tài)鏈表的第一個(gè)結(jié)點(diǎn)。 這種存儲(chǔ)結(jié)構(gòu)仍然需要預(yù)先分配一個(gè)較大空間，但是在進(jìn)行線性表的插入和刪除操作時(shí)不需要移動(dòng)元素，僅需要修改“指針”，因此仍然具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)。 下頁(yè)圖給出了一