數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 3(合肥工大)

第三章

鏈表華電計算機系NorthChinaElectricPowerUniversity3.1線性鏈表3.2鏈棧、鏈隊3.3循環(huán)鏈表3.4多重鏈表華電計算機系

3.1線性鏈表華電計算機系

假定上圖為當(dāng)前內(nèi)存的使用情況，陰影部分為已用內(nèi)存，現(xiàn)有一線性表L=(A,B,C,D,E,F,G,H),假若采用順序存儲的話，則在當(dāng)前內(nèi)存中不能分配一塊長度為8的連續(xù)的存儲空間。但實際上，系統(tǒng)的可用內(nèi)存遠(yuǎn)大于該線性表所要求的內(nèi)存空間，應(yīng)采用其它的存儲結(jié)構(gòu)—鏈?zhǔn)酱鎯ΑorthChinaElectricPowerUniversity

可以采用上面的存儲結(jié)構(gòu)，每一個數(shù)據(jù)元素占用兩個存儲單元，其中一個用來存放數(shù)據(jù)元素的值，另外一個存放下一個數(shù)據(jù)元素存儲單元的地址，這種結(jié)構(gòu)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。在這種結(jié)構(gòu)中，數(shù)據(jù)元素存放是不連續(xù)的。

G

F

B

C

E

D

H

^AHead華電計算機系鏈表：以“結(jié)點的序列”表示的線性表。數(shù)據(jù)域指針域鏈表結(jié)點頭指針：指向鏈表中第一個結(jié)點的指針。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素,為表示元素間的邏輯關(guān)系，除了存儲元素本身的信息外，還需存儲一個指示其直接后繼元素存儲位置的信息，這兩部分信息組成一個元素的存儲映像，稱為結(jié)點。

華電計算機系頭結(jié)點首元結(jié)點ABCD

E

F

G^

H表結(jié)點頭指針HeadNorthChinaElectricPowerUniversity鏈表基本概念頭結(jié)點：單鏈表的第一個結(jié)點之前附設(shè)的一個結(jié)點，它的數(shù)據(jù)域不存放信息、或存放如線性的長度等附加信息。首元結(jié)點：單鏈表中存放第一個元素的結(jié)點。表結(jié)點：存放線性表中數(shù)據(jù)元素的結(jié)點。單鏈表中設(shè)置頭結(jié)點的好處：1)其頭指針是指向頭結(jié)點的非空指針，無論鏈表是否為空，頭指針始終保持值不變，因此頭指針的處理方法對空表和非空表的操作是一致的，這與不帶頭結(jié)點的單鏈表為空時頭指針為空不同。華電計算機系2)首元結(jié)點的地址存放在頭結(jié)點的指針域中，對該結(jié)點的操作與其它結(jié)點的操作一致，無需進行特殊處理(如刪除首元結(jié)點時，對不帶頭結(jié)點的單鏈表要修改頭指針)。ProcedureInit_Link(VarHead:Link_list);Beginnew(Head);Head↑.Next:=Nil;End;單鏈表的類型定義如下（Pascal語言）

TypePointer=↑Node;Node=Recorddata:ElemType;next:Pointer;End;Link_list=Pointer;

二、單鏈表基本運算的實現(xiàn)1)Init_Link(Head):初始化一個單鏈表華電計算機系單鏈表的類型定義如下（C語言）

typedef

structNode{

ElemTypedata;

structNode*next;}*Pointer;

voidInitial(Pointer&head)

{

head=newNode;

if(!head)exit(1);

//存儲空間分配失敗

head->next=NULL;}

FunctionLength_Link(Head:Link_list):Integer;Beginp:=Head;j:=0;whilep↑.Next<>NilDo[p:=p↑.Next;j:=j+1;]Return(j);End;intLength(Pointer&head){p=Head;j=0;2)Length_Link(Head):返回單鏈表中所含表結(jié)點的個數(shù)。Pascal實現(xiàn)Length(Pointer&head)

:返回單鏈表中所含表結(jié)點的個數(shù)。C實現(xiàn)華電計算機系

while(p->next!=NULL)//繼續(xù)點數(shù){p=p->next;j++;}

return(j);//回傳表長

}FunctionFind_Link(Head:Link_list;i:Integer):Link_list;Beginp:=Head;j:=0;

3)返回指向線性表第i個結(jié)點的指針。(Pascal實現(xiàn))返回指向線性表第i個結(jié)點的指針。(C語言實現(xiàn))華電計算機系

while(p↑.Next<>Nil)and(j<i)Do[p:=p↑.Next;j:=j+1;]

ifi=jthenReturn(p)elseReturn(Nil);End;PointerFind(Pointerhead,inti){p=head;j=0;while((p->next)&&(j<i)){p=p->next;j++;}if(i==j)return(p);Elsereturn(NULL);}//FindFunctionLocate_Link(Head;x:ElemType):Link_list;Beginp:=Head;ABCD

^x=‘C’Headp4)Locate_Link(Head,x):在單鏈表中查找值等于x的結(jié)點，返回指向該結(jié)點的指針。(Pascal實現(xiàn))華電計算機系while(p↑.Next<>Nil)and(p↑.data<>x)Dop:=p↑.Next;ifp↑.data=xthenReturn(p)elseReturn(Nil);End;intLocate(Pointerhead,ElemTypex){p=head;j=0;

intLocate(Pointerhead,ElemTypex)：在單鏈表中查找值等于x的結(jié)點，返回該結(jié)點的序號。(C語言實現(xiàn))華電計算機系

while((p->next)&&(p->data!=x)){p=p->next;j++;}

if(p->data==x)return(j);elsereturn(0);

}ProcedureInsert_Link(VarHead;x:ElemType;i:Integer);Beginp:=Find_Link(Head,i-1);5)Insert_Link(Head,x,i):在單鏈表的第i個結(jié)點之前插入值等于x的結(jié)點。(Pascal實現(xiàn))ABCD^x=‘F’i=3HeadpF①

②

S華電計算機系ifp=NilthenError(‘Without’)else[new(s);s↑.data:=x;s↑.next:=p↑.next;p↑.next:=s;]End;voidInsert(Pointer&head,inti,ElemTypex)

{//在表head的第i個結(jié)點之前插入一個以x為值的新結(jié)點

p=Find(head,i-1);voidInsert(Pointer&head,inti,ElemTypex)在單鏈表的第i個結(jié)點之前插入值等于x的結(jié)點。(C語言實現(xiàn))ABCD^x=‘F’i=3HeadpF①

②

S華電計算機系

if(!p)error(“without”);

Else{s=newNode;if(!s)exit(1);//存儲空間分配失敗

s->data=x;//創(chuàng)建新元素的結(jié)點

s->next=p->next;p->next=s;//修改指針}}ProcedureDelete_Link(VarHead;i:Integer);Beginp:=Find_Link(Head,i-1);ABCD^i=3Headp6)Delete_Link(Head,i):刪除單鏈表的第i個結(jié)點。(Pascal實現(xiàn))華電計算機系if(p<>Nil)and(p↑.next<>Nil)then[q:=p↑.next;p↑.next:=q↑.next;dispose(q);]elseError(‘Without’);End;voidDelete(Pointer&head,intpos,ElemType&x){p=Find(head,i-1);//p指向第i-1個結(jié)點

ABCD^i=3HeadpDelete(Pointer&head,intpos,ElemType&x)：刪除單鏈表的第i個結(jié)點。(C實現(xiàn))華電計算機系if((p!=NULL)&&(p->next!=NULL))

{q=p->next;p->next=q->next;//修改指針

x=q->data;delete(q);}//釋放結(jié)點空間elseError(‘Without’);}ProcedureCreate_Link_1(VarHead:Link_list);Begin7)Create_Link(Head):建立一個單鏈表。華電計算機系Init_Link(Head);Read(x);i:=1;while(x<>‘*’)Do[Insert_Link(head,x,i);i:=i+1;Read(x);]End;voidCreateList(Pointer&head){7)Create_Link(Head):建立一個單鏈表。C語言實現(xiàn)華電計算機系

head=newNode;//生成頭結(jié)點

p=head;//尾指針指向頭結(jié)點

getchar(x);

while(x!=’*’){q=newNode;if(!q)exit(1);//存儲空間分配失敗

q->data=x;p->next=q;p=q;

getchar(x);}p->next=NULL;

}NorthChinaElectricPowerUniversityProcedureCreate_Link_2(VarHead:Link_list);BeginProcedureCreate_Link_3(VarHead:Link_list);Begin華電計算機系Init_Link(Head);p:=Head;Read(x);while(x<>‘*’)Do[new(q);q↑.data:=x;p↑.next:=q;p:=q;Read(x);]p↑.next:=Nil;End;p:=Nil;Read(x);while(x<>‘*’)Do[new(q);q↑.data:=x;q↑.next:=p;p:=q;Read(x);]new(Head);Head↑.next:=p;End;NorthChinaElectricPowerUniversity優(yōu)點線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點：1)存儲空間動態(tài)分配，可以按需要使用；2)插入/刪除結(jié)點操作時，只需要修改指針，不必移動數(shù)據(jù)元素缺點1)每個結(jié)點需要添加指針域，存儲密度降低；2)非隨機存儲結(jié)構(gòu)，查找定位操作需要從頭指針出發(fā)順鏈表掃描。華電計算機系ProcedureInvert_Link_1(VarHead:Link_list);{不帶頭結(jié)點}BeginProcedureInvert_Link_2(VarHead:Link_list);{帶頭結(jié)點}Begin單鏈表的應(yīng)用示例：例1.將一個單鏈表逆置。pascal實現(xiàn)華電計算機系p:=Head;Head:=Nil;while(p<>Nil)Do[s:=p;p:=p↑.next;s↑.next:=Head;Head:=s;]End;p:=Head↑.next;h:=Nil;while(p<>Nil)Do[s:=p;p:=p↑.next;s↑.next:=h;h:=s;]head↑.next:=h;End;voidInvert_Link_1(Link_list&Head){不帶頭結(jié)點}{voidInvert_Link_2(Link_list&Head){帶頭結(jié)點,其中s指向前一個結(jié)點指針，h指向后一個結(jié)點指針，p是跟蹤指針}{單鏈表的應(yīng)用示例：例1.將一個單鏈表逆置。C語言實現(xiàn)華電計算機系p=Head;Head=Null;while(p!=Null){s=p;p=p->next;s->next=Head;Head=s;}}p=Head->next;h=Null;while(p!=Null){s=p;p=p->next;s->next=h;h=s;}head->next:=h;}在數(shù)學(xué)上，一個一元n次多項式Pm(X)可按降冪寫成：

Pm(x)=Pmxem+Pm-1xem-1+…+P1xe1其中,Pi是指數(shù)為ei的項的非零系數(shù)，且滿足

em>em-1>…>e1>=0若用一個長度為m且每個元素有兩個數(shù)據(jù)項（系數(shù)項和指數(shù)項）的線性表((p1,e1),(p2,e2),…,(pm,em))便可唯一確定多項式Pm(x)。例2：一元多項式的表示及相加?？梢圆捎面?zhǔn)酱鎯Y(jié)構(gòu)來表示線性表：PascalTYPElink=↑nodenode=RECORD

coef:real;exp:integer;next:linkEND;polynom=link;華電計算機系可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示線性表：

typedef

structNode{doublecoef;

intexp;

structNode*next;}*polynom;算法ProcedurePolyadd(pa,pb:polynom;varpc:polynom);{pa,pb和pc分別表示多項式A,B及它們的和C的帶表頭單鏈表的頭指針}Beginp:=pa↑.next;q:=pb↑.next;s:=pa;pc:=pa;{s指向p的直接前驅(qū)}

while(p<>Nil)and(q<>Nil)DoCasep↑.exp>q↑.exp:[s:=p;p:=p↑.next;]p↑.exp=q↑.exp:[x:=p↑.coef+q↑.coef;Ifx<>0then[p↑.coef:=x;s:=p;]else[s↑.next:=p↑.next;dispose(p);]p:=s↑.next;u:=q;q:=q↑.next;dispose(u);]p↑.exp<q↑.exp:[u:=q↑.next;q↑.next:=p;s↑.next:=q;s:=q;q:=u]

EndCaseIfq<>Nilthens↑.next:=q;dispose(pb);End;華電計算機系算法voidPolyadd(polynom&pa,&pb,&pc)//pa,pb和pc分別為表示多項式A和B及它們的和C的帶表頭的單鏈表的頭指針

{

p=pa->next;q=pb->next;s=pa;pc=pa;{s指向p的直接前驅(qū)}

while((p!=NULL)&&(q!=NULL))

{if(p->exp>q->exp){s=p;p=p->next;}//p指針后移

if(p->exp==q->exp){x=p->coef+q->coef;if(x!=0){p->coef=x;s=p}//修改p結(jié)點

else{s->next=p->next;delete(p);}//刪除p結(jié)點

p=s->next;u=q;q=q->next;delete(u);}if(p->exp<q->exp){u=q->next;q->next=p;s->next=q;s=q;q=u;}//q結(jié)點插入在p結(jié)點之前,q指針后移

}

if(q!=NULL)s->next=q;delete(pb);}華電計算機系練習(xí)1

若已知非空線性鏈表第一個結(jié)點的指針為list，

請寫一個算法，將該鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前端。NorthChinaElectricPowerUniversity華電計算機系list356718658271521014……^list356718658271521014……^qpqsNorthChinaElectricPowerUniversity華電計算機系算法procedureRemove(list);beginq:=list;p:=list↑.next;r:=list;while(pnil)do[if(p↑.data<q↑.data)then[s:=r;q:=p;]r:=pp:=p↑.next;]{找到值最小的那個結(jié)點，地址由q記錄}if(qlist)then//若值最小的結(jié)點不是鏈表最前面那個結(jié)點//[

s↑.next:=q↑.next;q↑.next:=list;list:=q;]end;華電計算機系算法voidRemove(linklist&list)//類C語言實現(xiàn){

q=list;p=list->next;r=list;while(p!=null){if(p->data<q->data)

{s=r;//s總是指向q的前一個結(jié)點

q=p;}r=p;//r總是指向p的前一個結(jié)點

p=p->next;}//找到值最小的那個結(jié)點，地址由q記錄if(q!=list)//若值最小的結(jié)點不是鏈表最前面那個結(jié)點//

{s->next=q->next;q->next=list;list=q;}}華電計算機系3.2

鏈棧和鏈隊堆棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)一.構(gòu)造原理

鏈接堆棧就是用一個線性鏈表來實現(xiàn)一個堆棧結(jié)構(gòu),同時設(shè)置一個指針變量(這里不妨仍用top表示)指出當(dāng)前棧頂元素所在鏈結(jié)點的位置。當(dāng)棧為空時，有top=null。NorthChinaElectricPowerUniversity華電計算機系

在一個初始為空的鏈接堆棧中依次插入數(shù)據(jù)元素

A,B,C,D以后,堆棧的狀態(tài)為DCBA^top棧頂元素NorthChinaElectricPowerUniversity華電計算機系itemp^top

......

二.插入(進棧)算法voidPushStack(Stack&S,ElemTypex){//將元素x壓入棧s中

p=newNode;//生成新結(jié)點

p->data=x;p->next=S;//鏈入棧中

S=p;//修改棧頂指針}

算法NorthChinaElectricPowerUniversity華電計算機系top^item......py三.刪除(退棧)算法void

PopStack(Stack&S)

{算法NorthChinaElectricPowerUniversity華電計算機系if(S==Null)error(“?？铡?;{p=S;S=S->next;delete(p);}}隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)一.構(gòu)造原理

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一個線性鏈表表示一個隊列，指針front與rear分別指向隊頭與隊尾元素所在的結(jié)點。約定：rear指出實際隊尾元素所在的位置,NorthChinaElectricPowerUniversity華電計算機系

在一個初始為空的鏈隊列中依次插入數(shù)據(jù)元素

A,B,C,D以后,隊列的狀態(tài)為ABCD^frontrear空隊對應(yīng)的鏈表為空鏈表，空隊的標(biāo)志是

front=nullNorthChinaElectricPowerUniversity華電計算機系front=rear=nullpx^front

rear…frontrear二.插入算法p^itemNorthChinaElectricPowerUniversity華電計算機系procedureaddlinkqueue(front,rear,x);//Pascal實現(xiàn)begin

算法NorthChinaElectricPowerUniversitynew(p);//申請一個鏈結(jié)點//p↑.data:=x;p↑.next:=nil;if(front=nil)thenfront:=p//插入空隊的情況//Elserear↑.next:=p;

rear:=p;//插入非空隊的情況//End;華電計算機系voidaddlinkqueue(front,rear,x)//C語言實現(xiàn){

算法NorthChinaElectricPowerUniversityp=newNode;

//申請一個鏈結(jié)點//P->data=x;p->next=null;if(front==null)front=p//插入空隊的情況//Elserear->next=p;

rear=p;//插入非空隊的情況//}華電計算機系…frontrear^三.刪除算法算法NorthChinaElectricPowerUniversity華電計算機系voidDellinkqueue(front,rear,y)//類C語言{//在不帶頭結(jié)點的鏈隊中，刪除隊頭元素,并將數(shù)據(jù)域信息保存在變元y中//

if(front==null)return(“Queueisempty!”)else{x=front;front=front->next;

y=x->data;if(x->next==null)rear=front;delete(x);}}…frontrear^三.刪除算法算法NorthChinaElectricPowerUniversity華電計算機系procedureDellinkqueue1(front,rear,y);{//在帶頭結(jié)點的鏈隊中，刪除隊頭元素,并將數(shù)據(jù)域信息保存在變元y中//

if(front->next==null)return(‘Queueisempty!’)else{x=front->next;front->next=x->next;

y=x->data;if(x->next==NULL)rear=front;delete(x);}}

循環(huán)鏈表

是指鏈表中最后那個鏈結(jié)點的指針域存放指向鏈表最前面那個結(jié)點的指針，整個鏈表形成一個環(huán)。3.3循環(huán)鏈表華電計算機系…^list…list線性鏈表帶頭結(jié)點的循環(huán)鏈表NorthChinaElectricPowerUniversity華電計算機系循環(huán)鏈表的特點只要給出表中任何一個結(jié)點的位置，則由此出發(fā)就可以訪問表中其他所有結(jié)點。2.對循環(huán)鏈表，若在它的第一個結(jié)點之前設(shè)立一個特殊的稱為表頭的結(jié)點，它的數(shù)據(jù)域可以按需要設(shè)定。使這樣的鏈表中任何時候都至少有一個結(jié)點存在，這樣就可以把對空表和非空表的處理統(tǒng)一起來。3.當(dāng)需要將整個鏈表中所有結(jié)點歸還給可用空間棧時，用循環(huán)鏈表比用普通鏈表要方便的多。華電計算機系…^…^Havav……^Havav單鏈表循環(huán)鏈表3.4多重鏈表雙向鏈表及其操作1.雙向鏈表的構(gòu)造2.雙向鏈表的插入與刪除NorthChinaElectricPowerUniversity華電計算機系一.雙向鏈表的構(gòu)造

所謂雙向鏈表是指鏈表的每一個結(jié)點中除了數(shù)據(jù)域以外設(shè)置兩個指針域，其中之一指向結(jié)點的直接前驅(qū)結(jié)點，另外一個指向結(jié)點的直接后繼結(jié)點。鏈結(jié)點的實際構(gòu)造可以形象地描述如下：llinkdatarlink其中，data

為數(shù)據(jù)域

llink

,rlink

分別為指向該結(jié)點的直接前驅(qū)結(jié)點與直接后繼結(jié)點的指針域NorthChinaElectricPowerUniversity華電計算機系雙向鏈表的幾種形式list^^不帶頭結(jié)點的雙向鏈表list不帶頭結(jié)點的雙向循環(huán)鏈表list帶頭結(jié)點的雙向循環(huán)鏈表華電計算機系

二.雙向鏈表的插入

功能：在帶有頭結(jié)點的非空雙向循環(huán)鏈表中第一個數(shù)據(jù)域的內(nèi)容為x的鏈結(jié)點右邊插入一個數(shù)據(jù)信息為item的新結(jié)點。list1.找到滿足條件的結(jié)點。2.若找到，申請一個新的鏈結(jié)點。3.

將新結(jié)點插到滿足條件的結(jié)點后面。需要做的工作NorthChinaElectricPowerUniversity華電計算機系itemitemitemp插入前xq插入后插入p->llink=qp->rlink

=q->rlinkq->rlink=pq->rlink->llink=p華電計算機系Begin

q:=list↑.rlink;//q初值時指向頭結(jié)點的下一個結(jié)點

//

while(q≠listandq↑.data≠x)doq:=q↑.rlink;//尋找滿足條件的鏈結(jié)點

//

if(q=list)then[print(‘Thereisnothisnode!’);return;]//沒有找到滿足條件的結(jié)點

//

procedureinsert(list,x);//pascal實現(xiàn)End;

new(p);//申請一個新的結(jié)點

//

p↑.data:=x;q↑.

rlink:=p;

q↑.

rlink↑.llink:=p;p↑.rlink:=q↑.rlink;p↑.llink:=q;算法……xitemqNorthChinaElectricPowerUniversity華電計算機系Begin

q=list->rlink;//q初值時指向頭結(jié)點的下一個結(jié)點

//

while(q!=listandq->data!=x)q=q->rlink;//尋找滿足條件的鏈結(jié)點

//

if(q==list){printf(‘Thereisnothisnode!’);return;}//沒有找到滿足條件的結(jié)點

//voidinsert(list,x)//類C語言實現(xiàn)}

p=newNode;