chapt線性表二PPT課件

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

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

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

4、由頭指針唯一確定。可以借助高級語言中的“指針”數(shù)據(jù)類型來描述線性鏈表。 鏈式結(jié)構(gòu)的存儲效率： 存儲密度=結(jié)點數(shù)據(jù)信息所占存儲空間 / / 結(jié)點結(jié)構(gòu)所占全部空間第5頁/共46頁帶頭結(jié)點單鏈表示意圖帶頭結(jié)點單鏈表示意圖 在線性表的鏈式存儲中，為了便于插入和刪除算法的實現(xiàn)，可以使用帶頭結(jié)點的鏈表結(jié)構(gòu)，每個鏈表帶有一個頭結(jié)點，并通過頭結(jié)點的指針惟一標識該鏈表。頭結(jié)點數(shù)據(jù)域不需要賦值，指針指向鏈表的首個含有實質(zhì)信息的結(jié)點。第6頁/共46頁1、單鏈表內(nèi)結(jié)點的配置鏈表的內(nèi)存空間動態(tài)配置，在程序運行過程中才向系統(tǒng)配置所需空間。使用鏈表之前，先要定義出每一個結(jié)點的數(shù)據(jù)結(jié)構(gòu)。 C語言中，結(jié)點的格式聲明如下： 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é)點類型 typedef Node *link； /定義指向Node結(jié)點的指針類型定義了上述結(jié)點，在程序中使用結(jié)點結(jié)構(gòu)之前，需要聲明新結(jié)點： Link 變量名稱; （一個具備Node類型的結(jié)點）第7頁/共46頁程序運行中用到所聲明結(jié)點時，還需要配置結(jié)點： 向系統(tǒng)申請結(jié)點所需內(nèi)存空間； 為結(jié)點數(shù)據(jù)域賦值，并標記指針域。 例如，已定義一個名稱為Student的結(jié)點，使用到這個結(jié)點時，還需利用malloc函數(shù)向系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、*rb始終指向始終指向hb的末尾結(jié)點的末尾結(jié)點*/ 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; /*兩個尾結(jié)點的兩個尾結(jié)點的next域置空域置空*/第28頁/共46頁 【例】 有一個帶頭結(jié)點的單鏈表head,其ElemType類型為char,設計一個算法使其元素遞增有序。 解:若原單鏈表中有一個或以上的數(shù)據(jù)結(jié)點,先構(gòu)造只含一個數(shù)據(jù)結(jié)點

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

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

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

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

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

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

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

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

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

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