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

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

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

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

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

typedef

struct

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

intcur;/*存儲元素直接后繼的下標*/}Snode;

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

typedef

Snode

SlinkList[MaxSize];

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

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

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

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

s[i].data

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

s[i].cur

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

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

改為k=s[i].cur算法2.14:管理分配給鏈表的空閑結(jié)點算法2.15:實現(xiàn)結(jié)點的分配，即從空白表獲取一個結(jié)點算法2.16:實現(xiàn)結(jié)點的回收，即將刪除的結(jié)點鏈接到空白表靜態(tài)鏈表的操作實現(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é)束標志,cur為0表示尾結(jié)點*/

space[MAXSIZE-1].cur=0;

}

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

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

int

Malloc_SL(SLinkListspace)

{

inti=space[0].cur;/*獲取空白鏈表第一個結(jié)點的下標*/

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

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

returni;

}

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

voidFree_SL(SLinkListspace,intk)

{

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

space[0].cur=k;

}

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

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

表空條件：head->next=head

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

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

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

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

listMerge(LinkList

La,LinkListLb){

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

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

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

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

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

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

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

typedef

struct

Dnode{

ElemTypedata;

struct

DNode*prior;

struct

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

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

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

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

雙向鏈表的刪除過程：

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

——

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

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

(最多有n+1項)

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

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

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

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

typedef

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

int

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

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

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

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

2.4.2一元多項式相加

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

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)//多項式Ah的指數(shù)值小

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

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

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

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