数据结构-合肥工业大学 3(合肥工大)

第三章

链表华电计算机系NorthChinaElectricPowerUniversity3.1线性链表3.2链栈、链队3.3循环链表3.4多重链表华电计算机系

3.1线性链表华电计算机系

假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为8的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构—链式存储。NorthChinaElectricPowerUniversity

可以采用上面的存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。

G

F

B

C

E

D

H

^AHead华电计算机系链表：以“结点的序列”表示的线性表。数据域指针域链表结点头指针：指向链表中第一个结点的指针。线性表的链式存储结构：用一组地址任意的存储单元存放线性表中的数据元素,为表示元素间的逻辑关系，除了存储元素本身的信息外，还需存储一个指示其直接后继元素存储位置的信息，这两部分信息组成一个元素的存储映像，称为结点。

华电计算机系头结点首元结点ABCD

E

F

G^

H表结点头指针HeadNorthChinaElectricPowerUniversity链表基本概念头结点：单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。首元结点：单链表中存放第一个元素的结点。表结点：存放线性表中数据元素的结点。单链表中设置头结点的好处：1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。华电计算机系2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理(如删除首元结点时，对不带头结点的单链表要修改头指针)。ProcedureInit_Link(VarHead:Link_list);Beginnew(Head);Head↑.Next:=Nil;End;单链表的类型定义如下（Pascal语言）

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

二、单链表基本运算的实现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):返回单链表中所含表结点的个数。Pascal实现Length(Pointer&head)

:返回单链表中所含表结点的个数。C实现华电计算机系

while(p->next!=NULL)//继续点数{p=p->next;j++;}

return(j);//回传表长

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

3)返回指向线性表第i个结点的指针。(Pascal实现)返回指向线性表第i个结点的指针。(C语言实现)华电计算机系

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的结点，返回指向该结点的指针。(Pascal实现)华电计算机系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的结点，返回该结点的序号。(C语言实现)华电计算机系

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个结点之前插入值等于x的结点。(Pascal实现)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个结点之前插入一个以x为值的新结点

p=Find(head,i-1);voidInsert(Pointer&head,inti,ElemTypex)在单链表的第i个结点之前插入值等于x的结点。(C语言实现)ABCD^x=‘F’i=3HeadpF①

②

S华电计算机系

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

Else{s=newNode;if(!s)exit(1);//存储空间分配失败

s->data=x;//创建新元素的结点

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个结点。(Pascal实现)华电计算机系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个结点

ABCD^i=3HeadpDelete(Pointer&head,intpos,ElemType&x)：删除单链表的第i个结点。(C实现)华电计算机系if((p!=NULL)&&(p->next!=NULL))

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

x=q->data;delete(q);}//释放结点空间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语言实现华电计算机系

head=newNode;//生成头结点

p=head;//尾指针指向头结点

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优点线性表的链式存储结构的优缺点：1)存储空间动态分配，可以按需要使用；2)插入/删除结点操作时，只需要修改指针，不必移动数据元素缺点1)每个结点需要添加指针域，存储密度降低；2)非随机存储结构，查找定位操作需要从头指针出发顺链表扫描。华电计算机系ProcedureInvert_Link_1(VarHead:Link_list);{不带头结点}BeginProcedureInvert_Link_2(VarHead:Link_list);{带头结点}Begin单链表的应用示例：例1.将一个单链表逆置。pascal实现华电计算机系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){不带头结点}{voidInvert_Link_2(Link_list&Head){带头结点,其中s指向前一个结点指针，h指向后一个结点指针，p是跟踪指针}{单链表的应用示例：例1.将一个单链表逆置。C语言实现华电计算机系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;}在数学上，一个一元n次多项式Pm(X)可按降幂写成：

Pm(x)=Pmxem+Pm-1xem-1+…+P1xe1其中,Pi是指数为ei的项的非零系数，且满足

em>em-1>…>e1>=0若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表((p1,e1),(p2,e2),…,(pm,em))便可唯一确定多项式Pm(x)。例2：一元多项式的表示及相加。可以采用链式存储结构来表示线性表：PascalTYPElink=↑nodenode=RECORD

coef:real;exp:integer;next:linkEND;polynom=link;华电计算机系可以采用链式存储结构来表示线性表：

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的直接前驱}

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的直接前驱}

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结点

else{s->next=p->next;delete(p);}//删除p结点

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结点插入在p结点之前,q指针后移

}

if(q!=NULL)s->next=q;delete(pb);}华电计算机系练习1

若已知非空线性链表第一个结点的指针为list，

请写一个算法，将该链表中数据域值最小的那个结点移到链表的最前端。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;]{找到值最小的那个结点，地址由q记录}if(qlist)then//若值最小的结点不是链表最前面那个结点//[

s↑.next:=q↑.next;q↑.next:=list;list:=q;]end;华电计算机系算法voidRemove(linklist&list)//类C语言实现{

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

{s=r;//s总是指向q的前一个结点

q=p;}r=p;//r总是指向p的前一个结点

p=p->next;}//找到值最小的那个结点，地址由q记录if(q!=list)//若值最小的结点不是链表最前面那个结点//

{s->next=q->next;q->next=list;list=q;}}华电计算机系3.2

链栈和链队堆栈的链式存储结构一.构造原理

链接堆栈就是用一个线性链表来实现一个堆栈结构,同时设置一个指针变量(这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。当栈为空时，有top=null。NorthChinaElectricPowerUniversity华电计算机系

在一个初始为空的链接堆栈中依次插入数据元素

A,B,C,D以后,堆栈的状态为DCBA^top栈顶元素NorthChinaElectricPowerUniversity华电计算机系itemp^top

......

二.插入(进栈)算法voidPushStack(Stack&S,ElemTypex){//将元素x压入栈s中

p=newNode;//生成新结点

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);}}队列的链式存储结构一.构造原理

队列的链式存储结构是用一个线性链表表示一个队列，指针front与rear分别指向队头与队尾元素所在的结点。约定：rear指出实际队尾元素所在的位置,NorthChinaElectricPowerUniversity华电计算机系

在一个初始为空的链队列中依次插入数据元素

A,B,C,D以后,队列的状态为ABCD^frontrear空队对应的链表为空链表，空队的标志是

front=nullNorthChinaElectricPowerUniversity华电计算机系front=rear=nullpx^front

rear…frontrear二.插入算法p^itemNorthChinaElectricPowerUniversity华电计算机系procedureaddlinkqueue(front,rear,x);//Pascal实现begin

算法NorthChinaElectricPowerUniversitynew(p);//申请一个链结点//p↑.data:=x;p↑.next:=nil;if(front=nil)thenfront:=p//插入空队的情况//Elserear↑.next:=p;

rear:=p;//插入非空队的情况//End;华电计算机系voidaddlinkqueue(front,rear,x)//C语言实现{

算法NorthChinaElectricPowerUniversityp=newNode;

//申请一个链结点//P->data=x;p->next=null;if(front==null)front=p//插入空队的情况//Elserear->next=p;

rear=p;//插入非空队的情况//}华电计算机系…frontrear^三.删除算法算法NorthChinaElectricPowerUniversity华电计算机系voidDellinkqueue(front,rear,y)//类C语言{//在不带头结点的链队中，删除队头元素,并将数据域信息保存在变元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);{//在带头结点的链队中，删除队头元素,并将数据域信息保存在变元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);}}

循环链表

是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表形成一个环。3.3循环链表华电计算机系…^list…list线性链表带头结点的循环链表NorthChinaElectricPowerUniversity华电计算机系循环链表的特点只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。2.对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。3.当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。华电计算机系…^…^Havav……^Havav单链表循环链表3.4多重链表双向链表及其操作1.双向链表的构造2.双向链表的插入与删除NorthChinaElectricPowerUniversity华电计算机系一.双向链表的构造

所谓双向链表是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。链结点的实际构造可以形象地描述如下：llinkdatarlink其中，data

为数据域

llink

,rlink

分别为指向该结点的直接前驱结点与直接后继结点的指针域NorthChinaElectricPowerUniversity华电计算机系双向链表的几种形式list^^不带头结点的双向链表list不带头结点的双向循环链表list带头结点的双向循环链表华电计算机系

二.双向链表的插入

功能：在带有头结点的非空双向循环链表中第一个数据域的内容为x的链结点右边插入一个数据信息为item的新结点。list1.找到满足条件的结点。2.若找到，申请一个新的链结点。3.

将新结点插到满足条件的结点后面。需要做的工作NorthChinaElectricPowerUniversity华电计算机系itemitemitemp插入前xq插入后插入p->llink=qp->rlink

=q->rlinkq->rlink=pq->rlink->llink=p华电计算机系Begin

q:=list↑.rlink;//q初值时指向头结点的下一个结点

//

while(q≠listandq↑.data≠x)doq:=q↑.rlink;//寻找满足条件的链结点

//

if(q=list)then[print(‘Thereisnothisnode!’);return;]//没有找到满足条件的结点

//

procedureinsert(list,x);//pascal实现End;

new(p);//申请一个新的结点

//

p↑.data:=x;q↑.

rlink:=p;

q↑.

rlink↑.llink:=p;p↑.rlink:=q↑.rlink;p↑.llink:=q;算法……xitemqNorthChinaElectricPowerUniversity华电计算机系Begin

q=list->rlink;//q初值时指向头结点的下一个结点

//

while(q!=listandq->data!=x)q=q->rlink;//寻找满足条件的链结点

//

if(q==list){printf(‘Thereisnothisnode!’);return;}//没有找到满足条件的结点

//voidinsert(list,x)//类C语言实现}

p=newNode;