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

第三章

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

3.1線性鏈表華電計(jì)算機(jī)系

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

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

G

F

B

C

E

D

H

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

華電計(jì)算機(jī)系頭結(jié)點(diǎn)首元結(jié)點(diǎn)ABCD

E

F

G^

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

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

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

typedef

structNode{

ElemTypedata;

structNode*next;}*Pointer;

voidInitial(Pointer&head)

{

head=newNode;

if(!head)exit(1);

//存儲(chǔ)空間分配失敗

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é)點(diǎn)的個(gè)數(shù)。Pascal實(shí)現(xiàn)Length(Pointer&head)

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

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

return(j);//回傳表長

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

3)返回指向線性表第i個(gè)結(jié)點(diǎn)的指針。(Pascal實(shí)現(xiàn))返回指向線性表第i個(gè)結(jié)點(diǎn)的指針。(C語言實(shí)現(xiàn))華電計(jì)算機(jī)系

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é)點(diǎn)，返回指向該結(jié)點(diǎn)的指針。(Pascal實(shí)現(xiàn))華電計(jì)算機(jī)系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é)點(diǎn)，返回該結(jié)點(diǎn)的序號(hào)。(C語言實(shí)現(xiàn))華電計(jì)算機(jī)系

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個(gè)結(jié)點(diǎn)之前插入值等于x的結(jié)點(diǎn)。(Pascal實(shí)現(xiàn))ABCD^x=‘F’i=3HeadpF①

②

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

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

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

②

S華電計(jì)算機(jī)系

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

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

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

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個(gè)結(jié)點(diǎn)。(Pascal實(shí)現(xiàn))華電計(jì)算機(jī)系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個(gè)結(jié)點(diǎn)

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

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

x=q->data;delete(q);}//釋放結(jié)點(diǎn)空間elseError(‘Without’);}ProcedureCreate_Link_1(VarHead:Link_list);Begin7)Create_Link(Head):建立一個(gè)單鏈表。華電計(jì)算機(jī)系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):建立一個(gè)單鏈表。C語言實(shí)現(xiàn)華電計(jì)算機(jī)系

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

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

getchar(x);

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

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華電計(jì)算機(jī)系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)點(diǎn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：1)存儲(chǔ)空間動(dòng)態(tài)分配，可以按需要使用；2)插入/刪除結(jié)點(diǎn)操作時(shí)，只需要修改指針，不必移動(dòng)數(shù)據(jù)元素缺點(diǎn)1)每個(gè)結(jié)點(diǎn)需要添加指針域，存儲(chǔ)密度降低；2)非隨機(jī)存儲(chǔ)結(jié)構(gòu)，查找定位操作需要從頭指針出發(fā)順鏈表掃描。華電計(jì)算機(jī)系ProcedureInvert_Link_1(VarHead:Link_list);{不帶頭結(jié)點(diǎn)}BeginProcedureInvert_Link_2(VarHead:Link_list);{帶頭結(jié)點(diǎn)}Begin單鏈表的應(yīng)用示例：例1.將一個(gè)單鏈表逆置。pascal實(shí)現(xiàn)華電計(jì)算機(jī)系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é)點(diǎn)}{voidInvert_Link_2(Link_list&Head){帶頭結(jié)點(diǎn),其中s指向前一個(gè)結(jié)點(diǎn)指針，h指向后一個(gè)結(jié)點(diǎn)指針，p是跟蹤指針}{單鏈表的應(yīng)用示例：例1.將一個(gè)單鏈表逆置。C語言實(shí)現(xiàn)華電計(jì)算機(jī)系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é)上，一個(gè)一元n次多項(xiàng)式Pm(X)可按降冪寫成：

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

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

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

typedef

structNode{doublecoef;

intexp;

structNode*next;}*polynom;算法ProcedurePolyadd(pa,pb:polynom;varpc:polynom);{pa,pb和pc分別表示多項(xiàng)式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;華電計(jì)算機(jī)系算法voidPolyadd(polynom&pa,&pb,&pc)//pa,pb和pc分別為表示多項(xiàng)式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é)點(diǎn)

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

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é)點(diǎn)插入在p結(jié)點(diǎn)之前,q指針后移

}

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

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

請(qǐng)寫一個(gè)算法，將該鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前端。NorthChinaElectricPowerUniversity華電計(jì)算機(jī)系list356718658271521014……^list356718658271521014……^qpqsNorthChinaElectricPowerUniversity華電計(jì)算機(jī)系算法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;]{找到值最小的那個(gè)結(jié)點(diǎn)，地址由q記錄}if(qlist)then//若值最小的結(jié)點(diǎn)不是鏈表最前面那個(gè)結(jié)點(diǎn)//[

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

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

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

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

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

{s->next=q->next;q->next=list;list=q;}}華電計(jì)算機(jī)系3.2

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

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

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

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

......

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

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

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

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

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

PopStack(Stack&S)

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

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

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

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

front=nullNorthChinaElectricPowerUniversity華電計(jì)算機(jī)系front=rear=nullpx^front

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

算法NorthChinaElectricPowerUniversitynew(p);//申請(qǐng)一個(gè)鏈結(jié)點(diǎn)//p↑.data:=x;p↑.next:=nil;if(front=nil)thenfront:=p//插入空隊(duì)的情況//Elserear↑.next:=p;

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

算法NorthChinaElectricPowerUniversityp=newNode;

//申請(qǐng)一個(gè)鏈結(jié)點(diǎn)//P->data=x;p->next=null;if(front==null)front=p//插入空隊(duì)的情況//Elserear->next=p;

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

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

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

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)鏈表

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

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

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

llink

,rlink

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

二.雙向鏈表的插入

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

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

=q->rlinkq->rlink=pq->rlink->llink=p華電計(jì)算機(jī)系Begin

q:=list↑.rlink;//q初值時(shí)指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)

//

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

//

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

//

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

new(p);//申請(qǐng)一個(gè)新的結(jié)點(diǎn)

//

p↑.data:=x;q↑.

rlink:=p;

q↑.

rlink↑.llink:=p;p↑.rlink:=q↑.rlink;p↑.llink:=q;算法……xitemqNorthChinaElectricPowerUniversity華電計(jì)算機(jī)系Begin

q=list->rlink;//q初值時(shí)指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)

//

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

//

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

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

p=newNode;