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

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

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

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

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

typedef

struct

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

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

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

typedef

Snode

SlinkList[MaxSize];

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

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

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

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

s[i].data

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

s[i].cur

指示第i個元素的直接后繼,即第i+1個元素的存儲位置

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

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

/*將數(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;/*獲取空白鏈表第一個結(jié)點(diǎn)的下標(biāo)*/

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

space[0].cur=space[i].cur;/*從表中摘下第一個結(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)酱鎯Y(jié)構(gòu)。它將單鏈表中最后一個結(jié)點(diǎn)的指針指向鏈表的頭結(jié)點(diǎn)，使整個鏈表頭尾相接形成一個環(huán)形。這樣，從鏈表中任一結(jié)點(diǎn)出發(fā)，順著指針鏈都可找到表中其它結(jié)點(diǎn)。循環(huán)鏈表的最大特點(diǎn)是不增加存儲量，只是簡單地改變一下最后一個結(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

例：求線性表長度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)，沿最后一個結(jié)點(diǎn)的指針又可立即找到鏈表的第一個結(jié)點(diǎn)。在實(shí)際應(yīng)用中，使用尾指針來代替頭指針進(jìn)行某些操作往往會更簡單?！纠?】將兩個循環(huán)鏈表首尾相接進(jìn)行合并，

La、Lb分別為兩個循環(huán)鏈表的尾指針，對兩個單循環(huán)鏈表La，Lb進(jìn)行的連接操作，是將Lb的第一個數(shù)據(jù)結(jié)點(diǎn)接到La的尾部。head指向合并后的鏈表的頭結(jié)點(diǎn)?！窘狻克惴ㄋ悸罚涸谘h(huán)鏈表中若采用尾指針La，Lb來標(biāo)識，則時間性能將變?yōu)镺(1)。其連接過程如圖所示。圖2-14兩個循環(huán)鏈表首尾相接進(jìn)行合并

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

listMerge(LinkList

La,LinkListLb){

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

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

/*q指向第二個鏈表的頭結(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;雙向鏈表是用兩個指針表示結(jié)點(diǎn)間的邏輯關(guān)系。即增加了一個指向其直接前驅(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指向了一個結(jié)點(diǎn)，則通過p->next可以直接訪問該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，也可以由指針p->prior直接訪問它的前驅(qū)結(jié)點(diǎn)。這種結(jié)構(gòu)極大地簡化了某些操作。

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

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

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

雙向鏈表的刪除過程：

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

——

一元多項(xiàng)式表示及計算2.4.1一元多項(xiàng)式表示鏈?zhǔn)酱鎯Y(jié)構(gòu)的典型應(yīng)用之一是在高等數(shù)學(xué)的多項(xiàng)式方面。本節(jié)主要討論采用鏈表結(jié)構(gòu)表示的一元多項(xiàng)式的操作處理。在數(shù)學(xué)上，一個一元多項(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個系數(shù)，而且是線性排列。一個多項(xiàng)式由多個aixi(1≤i≤m)項(xiàng)組成，每個多項(xiàng)式項(xiàng)采用以下結(jié)點(diǎn)存儲：

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

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

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

typedef

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

int

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

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

在順序存儲結(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ù)會為0。如多項(xiàng)式A(x)=a0+a1x+a2x2+a6x6+a9x9+a15x15

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

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

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

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

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

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

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