第4課-循環(huán)鏈表及應(yīng)用

本課內(nèi)容一、鏈表的其它幾種形式：靜態(tài)鏈表（理解）循環(huán)鏈表（掌握）雙向鏈表（掌握插入/刪除算法）二、鏈表的應(yīng)用（了解）一元高次多項(xiàng)式的存儲(chǔ)集合類型的實(shí)現(xiàn)

有些高級(jí)程序設(shè)計(jì)語(yǔ)言中沒(méi)有指針類型，但為了實(shí)現(xiàn)鏈表結(jié)構(gòu)，應(yīng)用其優(yōu)點(diǎn)，可以通過(guò)定義一個(gè)結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)類似于“鏈表”的存儲(chǔ)結(jié)構(gòu)。該數(shù)組中的每個(gè)元素類似與線性表的“結(jié)點(diǎn)”，只是將結(jié)點(diǎn)中的指針改為下標(biāo)，用于指出后繼在數(shù)組中的序號(hào)（相對(duì)位置），從而形成靜態(tài)鏈表結(jié)構(gòu)。由于它是利用數(shù)組定義的，數(shù)組的長(zhǎng)度在編譯時(shí)就確定，因此在整個(gè)運(yùn)算過(guò)程中鏈表存儲(chǔ)空間的大小不會(huì)發(fā)生變化，故稱這種結(jié)構(gòu)為靜態(tài)鏈表。

2.3.1靜態(tài)鏈表靜態(tài)鏈表的類型定義

#defineMaxSize1000/*鏈表的最大長(zhǎng)度*//*定義存儲(chǔ)數(shù)據(jù)元素的“結(jié)點(diǎn)”類型——Snode*/

typedef

struct

{ElemTypedata;/*存儲(chǔ)數(shù)據(jù)元素的值*/

intcur;/*存儲(chǔ)元素直接后繼的下標(biāo)*/}Snode;

/*定義靜態(tài)鏈表類型SlinkList—結(jié)構(gòu)體數(shù)組類型*/

typedef

Snode

SlinkList[MaxSize];

理解：靜態(tài)鏈表中的用于存儲(chǔ)每個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)也有數(shù)據(jù)域data和指向下個(gè)元素存儲(chǔ)位置的域cur，不過(guò)這里的cur是個(gè)下標(biāo),是相對(duì)數(shù)組第一個(gè)元素的偏移,屬于相對(duì)地址.但是所起的作用與線性鏈表中的指針next相同，因此稱為靜態(tài)指針。為了簡(jiǎn)化鏈表操作算法,靜態(tài)鏈表也可以設(shè)表頭結(jié)點(diǎn).

設(shè)有變量s定義:

Slinklists;/*s為一個(gè)靜態(tài)鏈表*/

則s[0]表示頭結(jié)點(diǎn),s[0].cur指示第一個(gè)元素結(jié)點(diǎn)的位置

s[i].data

表示第i個(gè)數(shù)據(jù)元素的值

s[i].cur

指示第i個(gè)元素的直接后繼,即第i+1個(gè)元素的存儲(chǔ)位置

如圖（a)在鏈表沒(méi)有使用前，各個(gè)結(jié)點(diǎn)已經(jīng)形成一個(gè)鏈，變量AV指示鏈表的首地址(頭結(jié)點(diǎn))。由AV指向的鏈表稱為可利用空間表，可用于管理結(jié)點(diǎn)的分配和回收?！摹摹摹摹摹膸ь^結(jié)點(diǎn)的靜態(tài)鏈表操作的算法邏輯與線性鏈表相似,不過(guò)有以下區(qū)別:1.需要用戶自己實(shí)現(xiàn)類似于malloc和free函數(shù)的操作.2.線性表中向后移動(dòng)指針的操作:p=p->next

改為k=s[i].cur算法2.14:管理分配給鏈表的空閑結(jié)點(diǎn)算法2.15:實(shí)現(xiàn)結(jié)點(diǎn)的分配，即從空白表獲取一個(gè)結(jié)點(diǎn)算法2.16:實(shí)現(xiàn)結(jié)點(diǎn)的回收，即將刪除的結(jié)點(diǎn)鏈接到空白表靜態(tài)鏈表的操作實(shí)現(xiàn)算法2.14將鏈表空間初始化為一個(gè)空白鏈表

/*將數(shù)組space的各分量鏈成一空白鏈表，space[0].cur為頭指針*/

voidInitSpaceSL(SLinkListspace)

{

inti;

for(inti=0;i<MAXSIZE-1;++i)

space[i].cur=i+1;

/*置鏈表結(jié)束標(biāo)志,cur為0表示尾結(jié)點(diǎn)*/

space[MAXSIZE-1].cur=0;

}

算法2.15——malloc函數(shù)

/*若備用空間鏈表非空，則返回分配的結(jié)點(diǎn)下標(biāo)，否則返回0

int

Malloc_SL(SLinkListspace)

{

inti=space[0].cur;/*獲取空白鏈表第一個(gè)結(jié)點(diǎn)的下標(biāo)*/

if(i>0)/*備用空間不為空*/

space[0].cur=space[i].cur;/*從表中摘下第一個(gè)結(jié)點(diǎn)*/

returni;

}

算法2.16——將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表

voidFree_SL(SLinkListspace,intk)

{

space[k].cur=space[0].cur;/*鏈接到頭結(jié)點(diǎn)后*/

space[0].cur=k;

}

循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的頭結(jié)點(diǎn)，使整個(gè)鏈表頭尾相接形成一個(gè)環(huán)形。這樣，從鏈表中任一結(jié)點(diǎn)出發(fā)，順著指針鏈都可找到表中其它結(jié)點(diǎn)。循環(huán)鏈表的最大特點(diǎn)是不增加存儲(chǔ)量，只是簡(jiǎn)單地改變一下最后一個(gè)結(jié)點(diǎn)的指針指向，就可以使操作更加方便靈活。2.3.2循環(huán)單鏈表循環(huán)鏈表結(jié)構(gòu)示意圖帶頭結(jié)點(diǎn)的單循環(huán)鏈表的操作算法和帶頭結(jié)點(diǎn)的單鏈表的操作算法相似，差別僅在于算法中的判斷循環(huán)終止的條件不同。循環(huán)鏈表中：

指針p指向表尾的條件：p->next=head

表空條件：head->next=head

例：求線性表長(zhǎng)度Getlen(L)函數(shù)、查找運(yùn)算locate(L,x)函數(shù)、鏈表元素輸出運(yùn)算displist(L)函數(shù)中，循環(huán)是否進(jìn)行的條件由p!=NULL改為p!=L;

此外，還可用尾指針表示循環(huán)鏈表。尾指針tail指向最后一結(jié)點(diǎn)，沿最后一個(gè)結(jié)點(diǎn)的指針又可立即找到鏈表的第一個(gè)結(jié)點(diǎn)。在實(shí)際應(yīng)用中，使用尾指針來(lái)代替頭指針進(jìn)行某些操作往往會(huì)更簡(jiǎn)單?！纠?】將兩個(gè)循環(huán)鏈表首尾相接進(jìn)行合并，

La、Lb分別為兩個(gè)循環(huán)鏈表的尾指針，對(duì)兩個(gè)單循環(huán)鏈表La，Lb進(jìn)行的連接操作，是將Lb的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)接到La的尾部。head指向合并后的鏈表的頭結(jié)點(diǎn)。【解】算法思路：在循環(huán)鏈表中若采用尾指針La，Lb來(lái)標(biāo)識(shí)，則時(shí)間性能將變?yōu)镺(1)。其連接過(guò)程如圖所示。圖2-14兩個(gè)循環(huán)鏈表首尾相接進(jìn)行合并

操作如下：/*La,Lb為帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針*/LinkList

listMerge(LinkList

La,LinkListLb){

LNode*p,*q;p=La->next;

/*p指向第一個(gè)鏈表的頭結(jié)點(diǎn)*/q=Lb->next;

/*q指向第二個(gè)鏈表的頭結(jié)點(diǎn)*/La->next=q->next;

/*將鏈表Lb鏈接到La的尾部*/Lb->next=p;

/*設(shè)置鏈表的尾指針*/free(q);/*釋放多余的頭結(jié)點(diǎn)*/returnLb;

/*返回新鏈表的尾指針*/}2.3.3雙向鏈表

雙向鏈表結(jié)點(diǎn)的定義如下：

typedef

struct

Dnode{

ElemTypedata;

struct

DNode*prior;

struct

DNode*next;}Dnode,*DuLinkList;雙向鏈表是用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。即增加了一個(gè)指向其直接前驅(qū)的指針域，這樣形成的鏈表有兩條不同方向的鏈，前驅(qū)和后繼，因此稱為雙鏈表。在雙鏈表中，根據(jù)已知結(jié)點(diǎn)查找其直接前驅(qū)結(jié)點(diǎn)可以和查找其直接后繼結(jié)點(diǎn)一樣方便。這里也僅討論帶頭結(jié)點(diǎn)的雙鏈表。仍假設(shè)數(shù)據(jù)元素的類型為ElemType。雙向鏈表結(jié)點(diǎn)示意圖帶頭結(jié)點(diǎn)的雙向鏈表如果指針變量p指向了一個(gè)結(jié)點(diǎn)，則通過(guò)p->next可以直接訪問(wèn)該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，也可以由指針p->prior直接訪問(wèn)它的前驅(qū)結(jié)點(diǎn)。這種結(jié)構(gòu)極大地簡(jiǎn)化了某些操作。

在雙向鏈表中也可采用與單鏈表類似的方法，設(shè)置頭結(jié)點(diǎn)。用頭指針標(biāo)識(shí)鏈表的存在。雙向鏈表的插入過(guò)程如圖表示：

注意：指針操作序列，操作①必須在操作③之前完成。在雙向鏈表中找到刪除位置的前一個(gè)結(jié)點(diǎn)，由p指向它，q指向要?jiǎng)h除的結(jié)點(diǎn)。刪除操作如下：①將*p的next域改為指向待刪結(jié)點(diǎn)*q的后繼結(jié)點(diǎn)；②若*q不是指向最后的結(jié)點(diǎn)，則將*q之后結(jié)點(diǎn)的prior域指向*p。

注意：在雙向鏈表中進(jìn)行插入和刪除時(shí)，對(duì)指針的修改需要同時(shí)修改結(jié)點(diǎn)的前驅(qū)指針和后繼指針的指向。

雙向鏈表的刪除過(guò)程：

2.4線性表的應(yīng)用

——

一元多項(xiàng)式表示及計(jì)算2.4.1一元多項(xiàng)式表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的典型應(yīng)用之一是在高等數(shù)學(xué)的多項(xiàng)式方面。本節(jié)主要討論采用鏈表結(jié)構(gòu)表示的一元多項(xiàng)式的操作處理。在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可以表示為：

Pn(x)=a0+a1x+a2x2+…+anxn

(最多有n+1項(xiàng))

aixi是多項(xiàng)式的第i項(xiàng)（0≤i≤n）。其中ai為系數(shù)，x為自變量，i為指數(shù)。多項(xiàng)式中有n+1個(gè)系數(shù)，而且是線性排列。一個(gè)多項(xiàng)式由多個(gè)aixi(1≤i≤m)項(xiàng)組成，每個(gè)多項(xiàng)式項(xiàng)采用以下結(jié)點(diǎn)存儲(chǔ)：

其中，coef數(shù)據(jù)域存放系數(shù)ci；

expn數(shù)據(jù)域存放指數(shù)ei；

next域是一個(gè)鏈域，指向下一個(gè)結(jié)點(diǎn)。由此，一個(gè)多項(xiàng)式可以表示成由這些結(jié)點(diǎn)鏈接而成的單鏈表(假設(shè)該單鏈表是帶頭結(jié)點(diǎn)的單鏈表)。

typedef

structnode{doublecoef;//系數(shù)為雙精度型

int

expn;//指數(shù)為正整型

structnode*next;//指針域}polynode;

在順序存儲(chǔ)結(jié)構(gòu)中，采用基類型為polynode的數(shù)組表示多項(xiàng)式中的各項(xiàng)。如p[i].coef和p[i].expn分別表示多項(xiàng)式中第i項(xiàng)的系數(shù)和指數(shù)。但多項(xiàng)式中，其中一些項(xiàng)的系數(shù)會(huì)為0。如多項(xiàng)式A(x)=a0+a1x+a2x2+a6x6+a9x9+a15x15

中包括16項(xiàng)，其中只有6項(xiàng)系數(shù)不為0。順序存儲(chǔ)結(jié)構(gòu)可以使多項(xiàng)式相加算法變得簡(jiǎn)單。但是，當(dāng)多項(xiàng)式中存在大量的零系數(shù)時(shí)，這種方式就會(huì)浪費(fèi)大量的存儲(chǔ)空間。為了有效利用存儲(chǔ)空間，可用有序鏈表存儲(chǔ)結(jié)構(gòu)表示多項(xiàng)式。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，多項(xiàng)式中每一個(gè)非零項(xiàng)構(gòu)成鏈表中的一個(gè)結(jié)點(diǎn)，而對(duì)于系數(shù)為零的項(xiàng)則不需要表示，因此可以節(jié)省存儲(chǔ)空間。

2.4.2一元多項(xiàng)式相加

假設(shè)用單鏈表表示多項(xiàng)式：A(x)=12+7x+8x10+5x17，B(x)=8x+15x7-6x10，頭指針Ah與Bh分別指向這兩個(gè)鏈表，如圖2-21所示：對(duì)兩個(gè)多項(xiàng)式進(jìn)行相加運(yùn)算，其結(jié)果為C(x)=12+15x+15x7+2x10+5x17。如圖2-22所示。合并以前的鏈表合并以后的鏈表對(duì)兩個(gè)一元多項(xiàng)式進(jìn)行相加操作的運(yùn)算規(guī)則是：假設(shè)指針qa和qb分別指向多項(xiàng)式A(x)和B(x)中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn)，則需比較兩個(gè)結(jié)點(diǎn)數(shù)據(jù)域的指數(shù)項(xiàng)，有三種情況：(1)指針qa所指結(jié)點(diǎn)的指數(shù)值＜指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，則保留qa指針?biāo)赶虻慕Y(jié)點(diǎn)，qa指針后移；(2)指針qa所指結(jié)點(diǎn)的指數(shù)值＞指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，則將qb指針?biāo)赶虻慕Y(jié)點(diǎn)插入到qa所指結(jié)點(diǎn)前，qb指針后移；(3)指針qa所指結(jié)點(diǎn)的指數(shù)值＝指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加。若和不為零，則修改qa所指結(jié)點(diǎn)的系數(shù)值，同時(shí)釋放qb所指結(jié)點(diǎn)；反之，從多項(xiàng)式A(x)的鏈表中刪除相應(yīng)結(jié)點(diǎn)，并釋放指針qa和qb所指結(jié)點(diǎn)。多項(xiàng)式相加算法——用有序表的合并算法實(shí)現(xiàn)：struct

polynode*add_poly(struct

polynode*Ah,struct

polynode*Bh){struct

polynode*qa,*qb,*s,*r,*Ch;

qa=Ah->next;qb=Bh->next; //qa和qb分別指向兩個(gè)鏈表的第一結(jié)點(diǎn)

r=qa;Ch=Ah;

//將鏈表Ah作為相加后的結(jié)果鏈表

while(qa!=NULL&&qb!=NULL)//兩鏈表均非空

{if(qa->exp==qb->exp)//兩者指數(shù)值相等

{x=qa->coef+qb->coef;

if(x!=0)//相加后系數(shù)不為零時(shí)

{qa->coef=x;r->next=qa;r=qa;

s=qb++;free(s);qa++;}

else//相加后系數(shù)為零時(shí)

{s=qa++;free(s);s=qb++;free(s);}

}

elseif(qa->exp<qb->exp)//多項(xiàng)式Ah的指數(shù)值小

{r->next=qa;r=qa;qa++;}else//多項(xiàng)式Bh的指數(shù)值小

{r->next=qb;r=qb;qb++;}}if(qa==NULL)r->next=qb;elser->next=qa; //鏈接Ah或Bh中的剩余結(jié)點(diǎn)return(Ch);}

2.5小結(jié)：順序表和鏈表的比較本章介紹了線性表的邏輯結(jié)構(gòu)及它的兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表。這兩種表各有短長(zhǎng)，在實(shí)際應(yīng)用中應(yīng)根據(jù)問(wèn)題的要求和性質(zhì)來(lái)選擇使用。通過(guò)前面的討論可知：順序存儲(chǔ)有三個(gè)優(yōu)點(diǎn)：(1)方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)；(2)不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)開(kāi)銷；(3)具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)。兩大缺點(diǎn)：(1)插入/刪除操作平均移動(dòng)大約表中一半的元素(2)需要預(yù)先分配足夠大的存儲(chǔ)空間。若估計(jì)過(guò)大，容易導(dǎo)致順序表后部大量閑置；預(yù)先分配過(guò)小，又會(huì)造成溢出。1．基于空間的考慮順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行前必須明確規(guī)定它的存儲(chǔ)規(guī)模。若線性表長(zhǎng)度n變化較大，則存儲(chǔ)規(guī)模很難預(yù)先正確估計(jì)。估計(jì)太大將造成空間浪費(fèi)，估計(jì)太小又將使空間溢出機(jī)會(huì)增多。所以當(dāng)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)。順序表的存儲(chǔ)密度為1。鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，是動(dòng)態(tài)分配。只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。因此，當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。但鏈表的存儲(chǔ)密度較低。存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比。顯然鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度是小于1的。2．基于時(shí)間的考慮

隨機(jī)存取結(jié)構(gòu)，就是對(duì)表中任一結(jié)點(diǎn)都可在O(1)時(shí)間內(nèi)直接取得。若對(duì)線性表主要做查找，很少做插入和刪除操作時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)為宜；而在鏈表中按序號(hào)訪問(wèn)的時(shí)間性能為O(n)。所以，如果經(jīng)常做的運(yùn)算是按序號(hào)訪問(wèn)數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表。而在順序表中做插入、刪除操作時(shí)，要平均移動(dòng)表中一半的元素；尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間開(kāi)銷就相當(dāng)可觀，這一點(diǎn)不應(yīng)忽視。在鏈表中的任何位置上進(jìn)行插入和刪除，都只需要修改指針。對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。3．基于環(huán)境的考慮順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類型；鏈表的操作是基于指針的，其使用受語(yǔ)言環(huán)境的限制，這也是用戶應(yīng)該考慮的因素之一。兩種存儲(chǔ)結(jié)構(gòu)各有特點(diǎn)。選擇哪種結(jié)構(gòu)根據(jù)實(shí)際使用的主要因素決定。通常“較穩(wěn)定”的線性表選擇順序存儲(chǔ)結(jié)構(gòu)；而插入/刪除頻繁“動(dòng)態(tài)性“較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。一、基礎(chǔ)知識(shí)題1.請(qǐng)說(shuō)明在線性鏈表中設(shè)置頭結(jié)點(diǎn)的意義。2.順序表有哪些優(yōu)點(diǎn)？請(qǐng)分析在什么情況下使用順序表較好。3.請(qǐng)分析鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)缺點(diǎn)。一、思考與練習(xí)（1）順序結(jié)構(gòu)線性表的特點(diǎn)是__________________________，在順序表中插入一個(gè)元素，平均需要移動(dòng)________個(gè)元素，移動(dòng)個(gè)數(shù)與_______________有關(guān)。但是，在順序表中進(jìn)行查找比較方便，可以實(shí)現(xiàn)________查找。（2）在單鏈表中，邏輯上相鄰的元素物理上____________，在表中插入