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

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

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

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

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

typedef

struct

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

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

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

typedef

Snode

SlinkList[MaxSize];

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

設有變量s定義:

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

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

s[i].data

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

s[i].cur

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

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

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

/*置鏈表結束標志,cur為0表示尾結點*/

space[MAXSIZE-1].cur=0;

}

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

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

int

Malloc_SL(SLinkListspace)

{

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

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

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

returni;

}

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

voidFree_SL(SLinkListspace,intk)

{

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

space[0].cur=k;

}

循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈式存儲結構。它將單鏈表中最后一個結點的指針指向鏈表的頭結點，使整個鏈表頭尾相接形成一個環(huán)形。這樣，從鏈表中任一結點出發(fā)，順著指針鏈都可找到表中其它結點。循環(huán)鏈表的最大特點是不增加存儲量，只是簡單地改變一下最后一個結點的指針指向，就可以使操作更加方便靈活。2.3.2循環(huán)單鏈表循環(huán)鏈表結構示意圖帶頭結點的單循環(huán)鏈表的操作算法和帶頭結點的單鏈表的操作算法相似，差別僅在于算法中的判斷循環(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指向最后一結點，沿最后一個結點的指針又可立即找到鏈表的第一個結點。在實際應用中，使用尾指針來代替頭指針進行某些操作往往會更簡單?！纠?】將兩個循環(huán)鏈表首尾相接進行合并，

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

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

listMerge(LinkList

La,LinkListLb){

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

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

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

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

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

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

雙向鏈表結點的定義如下：

typedef

struct

Dnode{

ElemTypedata;

struct

DNode*prior;

struct

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

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

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

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

雙向鏈表的刪除過程：

2.4線性表的應用

——

一元多項式表示及計算2.4.1一元多項式表示鏈式存儲結構的典型應用之一是在高等數(shù)學的多項式方面。本節(jié)主要討論采用鏈表結構表示的一元多項式的操作處理。在數(shù)學上，一個一元多項式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)項組成，每個多項式項采用以下結點存儲：

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

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

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

typedef

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

int

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

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

在順序存儲結構中，采用基類型為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。順序存儲結構可以使多項式相加算法變得簡單。但是，當多項式中存在大量的零系數(shù)時，這種方式就會浪費大量的存儲空間。為了有效利用存儲空間，可用有序鏈表存儲結構表示多項式。在鏈式存儲結構中，多項式中每一個非零項構成鏈表中的一個結點，而對于系數(shù)為零的項則不需要表示，因此可以節(jié)省存儲空間。

2.4.2一元多項式相加

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

r=qa;Ch=Ah;

//將鏈表Ah作為相加后的結果鏈表

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中的剩余結點return(Ch);}

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

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