数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
North China Electric Power University
第三章 链 表
★ 线性链表
★ 链栈、链队
★ 循环链表
★ 多重链表
★ 线性链表假定上图为当前内存的使用情况，阴影部分为已用内存，
现有一线性表 L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为 7的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构 — 链式存储。
North China Electric Power University
North China Electric Power University
G
F
B
C
E
D
H ^
A
可以采用上面的存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。
Head
North China Electric Power University
线性表的链式存储结构：
用一组 地址任意 的存储单元存放线性表中的数据元素结点 (表示数据元素 )=元素 (数据元素的映象 ) + 指针 (
指示后继元素存储位置 )
链表,以,结点的序列,表示的线性表 。
A B C D
EFG^ H
头结点数据 域 指针域链表结点头指针,指向链表中第一个结点的指针。
首元结点表结点头指针
Head
头结点,单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。
North China Electric Power University
首元结点,单链表中存放第一个元素的结点。
表结点,存放线性表中所有数据元素的结点。
单链表中设置头结点的好处：
1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。
2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理 (如删除首元结点时，对不带头结点的单链表要修改头指针 )。
单链表上基本运算的实现
North China Electric Power University
1)Init_Link(Head):初始化一个单链表
Procedure Init_Link(Var Head:Link_list);
Begin
new(Head);
Head↑.Next:=Nil;
End;
单链表的类型定义如下：
Type Pointer=↑ Node;
Node=Record
data:ElemType;
next:Pointer;
End;
Link_list=Pointer;
North China Electric Power University
2)Length_Link (Head):返回单链表中所含表结点的个数。
Function Length_Link(Head:Link_list):Integer;
Begin
p:=Head;j:=0;
while p↑.Next< >Nil Do [ p:=p↑.Next; j:=j+1;]
Return(j);
End;
3)Length_Link (Head):返回指向线性表第 i个结点的指针。
Function Find_Link(Head:Link_list;i:Integer):Link_list;
Begin
p:=Head;j:=0;
while (p↑.Next< >Nil) and (j<i) Do
[ p:=p↑.Next; j:=j+1;]
if i=j then Return(p) else Return(Nil);
End;
North China Electric Power University
4)Locate_Link (Head,x):在单链表中查找值等于 x的结点，
返回指向该结点的指针。
Function Locate_Link(Head;x:ElemType):Link_list;
Begin
p:=Head;
while (p↑.Next< >Nil) and (p↑.data< > x) Do
p:=p↑.Next;
if p↑.data=x then Return(p) else Return(Nil);
End;
A B C D ^
x=‘C’
Head
p
North China Electric Power University
5)Insert_Link (Head,x,i):在单链表的第 i个结点之前插入值等于 x的结点。
Procedure Insert_Link(Var Head;x:ElemType;i:Integer);
Begin
p:=Find_Link(Head,i-1);
if p=Nil then Error(‘Without’)
else [ new(s);s↑.data:=x;s↑.next:=p↑.next;
p↑.next:=s;
]
End;
A B C D ^
x=‘F’ i=3
Head
p
F ①②S
North China Electric Power University
6)Delete_Link (Head,i):删除单链表的第 i个结点。
Procedure Delete_Link(Var Head;i:Integer);
Begin
p:=Find_Link(Head,i-1);
if (p< >Nil) and (p↑.next< >Nil)
then [ q:=p↑.next; p↑.next:=q;
dispose(q);
]
else Error(‘Without’);
End;
A B C D ^
i=3
Head
p
North China Electric Power University
7)Create_Link (Head):建立一个单链表。
Procedure Create_Link_1(Var Head:Link_list);
Begin
Init_Link(Head);
Read(x);i:=1;
while (x< > ‘*’ ) Do
[ Insert_Link(head,x,i);
i:=i+1;
Read(x);
]
End;
North China Electric Power University
Procedure Create_Link_2(Var Head: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;
Procedure Create_Link_3(Var Head:Link_list);
Begin
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;
North China Electric Power University
线性表的链式存储结构的优缺点：
优点,1)存储空间动态分配，可以按需要使用；
2)插入 /删除结点操作时，只需要修改指针，
不必移动数据元素缺点,1)每个结点序加一指针域，存储密度降低；
2)非随机存储结构，查找定位操作需要从头指针出发顺着链表扫描
North China Electric Power University
单链表的应用示例：
例 1.将一个单链表逆置
Procedure Invert_Link_1(Var Head:Link_list);
{不带头结点 }
Begin
p:=Head;Head:=Nil;
while (p < > Nil) Do
[ s:=p; p:=p↑.next;s↑.next:=Head;Head:=s;]
End;
Procedure Invert_Link_2(Var Head:Link_list);
{带头结点 }
Begin
p:=Head↑.next;h:=Nil;
while (p < > Nil) Do
[s:=p; p:=p↑.next; s↑.next:=h;h:=s;] head↑.next:=h;
End;
North China Electric Power University
例 2.设有带头结点的链表，每个结点有三个域,data，
Next,Sort，其中,data为整型值域,next和 sort
均为指针，现所有结点已由 next域链接起来，构成单链表，试编写利用 sort域把所有结点按照值的大小链接起来的算法。
算法的思想,1)先构造以 sort域为链表的空表；
2)依次扫描以 next域链接的单链表上的每个结点，并根据其值将其插入到以 sort域链接的链表的合适位置。
数据类型定义如下：
Slist=↑Snode;
Snode=Record
data:Integer;
next,sort:Slist;
End;
North China Electric Power University
Procedure LinkList_sort(Var Head:Slist);
Begin
h↑.sort:=nil;
q:=head↑.next;
while q< > Nil Do
[ pre:=head; p:=pre↑.sort;
while (p!=Nil) and (q↑data>p↑.data) Do
[ pre:=p;
p:=p↑.sort;]
q↑.sort:=p;
pre↑.sort:=q;
q:=q.next;
]
End;
North China Electric Power University
例 2：一元多项式的表示及相加。
在数学上，一个一元 n次多项式 Pn(X)可按升幂写成：
Pn(x)=P1xe1+P2xe2+… +Pmxem
其中,Pi是指数为 ei的项的非零系数，且满足
0≤e1<e2< … <em=n
若用一个长度为 m且每个元素有两个数据项（系数项和指数项）的线性表 ((p1,e1),(p2,e2),…,(pm,em))便可唯一确定多项式 Pn(x)。
可以采用链式存储结构来表示线性表：
TYPE link=↑node
node=RECORD
cnef:real; exp:integer; next:link
END;
Polyn=link;
North China Electric Power University
算法描述如下：
Procedure Polyadd(pa,pb:Polyn;var pc:Polyn);
{pa,pb和 pc分别表示多项式 A,B及它们的和 C的带表头的头指针 }
Begin
p:=pa↑.next;q:=pb↑.next;s:=pa;pc:=pa;{s指向 p的直接前驱 }
while (p< >Nil) and (q< >Nil) Do
Case
p↑.exp<q↑.exp:[s:=p;p:=p↑.next;]
p↑.exp=q↑.exp:[x:=p↑.coef+q↑.coef;
If x< > 0 then [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;]
EndCase
If q< >Nil then s↑.next:=q;dispose(pb);
End;
North China Electric Power University
例：求多项式的微商问题
Procedure Differential_coefficient(var L:Polyn);
Var q:Polyn;
Begin
q:=L↑.next;
while q< >Nil Do
[ if q↑.exp>0 then
[ q↑.coef:=q.↑coef*q↑.exp;
q↑.exp:=q↑.exp-1;
]
else
[ p:=q;q↑.next,=q↑,next↑,next;dispose(p);]
q:=q↑.next;
]
End;
练习 1
若已知非空线性链表第一个结点的指针为 list，
请 写一个算法,将该链表中数据域值最小的那个结点移到链表的最前端。
North China Electric Power University
lis
t
35 67 18 65827152 10 14… … ^
lis
t
35 67 18 65827152 10 14… … ^
q p
qs
华电 计算机系
North China Electric Power University
procedure Remove( list );
begin
q:=list;
p:=list↑.next;
r:=list;
while (p?nil) do
[ if (p↑.data <q↑.data) then
[ s:=r;
q:=p; ]
r:=p
p:=p↑.next;
] // 找到值最小的那个结点,地址由 q记录 //
if (q?list) then // 若值最小的结点不是链表最前面那个结点 //
[ s↑.next:=q↑.next;
q↑.next:=list;
list:=q; ]
end;
算法
North China Electric Power University
★ 链栈和链队堆栈的链式存储结构一,构造原理链接堆栈就是用一个线性链表来实现一个堆栈结构,同时设置一个指针变量 ( 这里不妨仍用 top
表示 )指出当前栈顶元素所在链结点的位置。当栈为空时，有 top=nil。
North China Electric Power University
在一个初始为空的链接堆栈中依次插入数据元素
A,B,C,D
以后,堆栈的状态为
D C B A ^
top
栈顶元素
North China Electric Power University
item
p
^
top
......
二,插入 (进栈 )算法
procedure Push_link_stack( top,item );
begin
new(p); //申请一个新结点 //
p↑.data:=item; //将 item送新结点数据域 //
p↑.next:=top; //将新结点插在链表最前面 //
top:=p; //修改栈顶指针的指向 //
End;
算法
North China Electric Power University
top
^item,.....
p
三,删除 (退栈 )算法
procedure Pop_link_stack( top,item );
Begin
if (top = nil) then
call STACK_EMPTY( ‘Stack is empty!’ )
else
[ p:=top; //暂时保存栈顶结点的地址 //
item:=top↑.data; //保存被删栈顶的数据信息 //
top:=top↑.next; //删去栈顶结点 //
dispose(p); ] //释放被删结点 //
End;
算法
North China Electric Power University
队列的链式存储结构一,构造原理队列的链式存储结构是用一个线性链表表示一个队列,指针 front 与 rear 分别指示队头和队尾的位置。
约 定,
rear 指出实际队尾元素所在的位置,
front 指出实际队头元素所在位置的前一个位置,
North China Electric Power University
在一个初始为空的链接队列中依次插入数据元素
A,B,C,D
以后,队列的状态为
A B C D ^
front rear
North China Electric Power University
front
rear
空队
front=rear=nil
p
item ^
front rear
…
front rear
二,插入算法
p
^item
North China Electric Power University
procedure addlinkqueue( front,rear,item );
begin
new(p); // 申请一个链结点 //
p↑.data:=item;
p↑.next:=nil;
rear↑.next:=p;
rear:=p;
End;
算 法
North China Electric Power University
…
front rear
^
procedure Del_link_queue( front,rear,item );
Begin
// 删除队头元素,并将数据域信息保存在变元 item中 //
if (front = nil) then
call Queue_empty( ‘Queue is empty!’ )
else
[ q:=front↑.next; front↑.next:=q↑.next;
item:=q↑.data; if q↑.next=nil then rear:=front;
dispose(q); ]
End;
三,删除算法算 法
North China Electric Power University
循环链表 是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表形成一个环。
★ 循环链表
North China Electric Power University
… ^
list
…
list
线性链表带头结点的循环链表
North China Electric Power University
循环链表的特点
1,只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。
2,对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。
3,当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。
… ^ … ^H
av av
… … ^H
av
av
单链表循环链表
North China Electric Power University
★ 多重链表
2.5 双向链表及其操作
1.双向链表的构造
2.双向链表的插入与删除
North China Electric Power University
一,双向链表的构造所谓 双向链表 是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。
链结点的实际构造可以形象地描述如下：
llink data rlink
其中,data 为数据域
llink,rlink 分别为指向该结点的直接前驱结点与直接后继结点的指针域华电计算机系
North China Electric Power University
双向链表的几种形式
list
^^
不带头结点的双向链表
list
不带头结点的双向循环链表
list
带头结点的双向循环链表
North China Electric Power University
二,双向链表的插入功能,在带有头结点的非空双向循环链表中第一个数据域的内容为 x 的链结点右边插入一个数据信息为 item 的新结点。
list
1,找到满足条件的结点。
2,若找到，申请一个新的链结点。
3,将新结点插到满足条件的结点后面。
需要做的工作
North China Electric Power University
itemitem
p
插入前
x
q
插入后插入
p↑.llink:=q p↑.rlink,=q↑.rlink
q↑.rlink:=p q↑.rlink↑.llink,=p
North China Electric Power University
Begin
q:=list↑.rlink; // q 初值时指向头结点的下一个结点 //
while (q≠list and q↑.data≠x) do
q:=q↑.rlink; // 寻找满足条件的链结点 //
if (q=list) then
[ write( ‘There is no this node !’ );
return; ] // 没有找到满足条件的结点 //
procedure insert( list,x,item );
End;
new(p) ; // 申请一个新的结点 //
p↑.data:=item;
q↑,rlink:=p;
q↑,rlink↑.llink:=p;
p↑.rlink:=q↑.rlink;
p↑.llink:=q;
算法
… …x
item
q
North China Electric Power University
三,双向链表的删除
1,找到满足条件的结点。
2,若找到，删除并释放该结点。
list
功能,删除带有头结点的非空双向循环链表中第一个数据域的内容为 x 的链结点。
需要做的工作
North China Electric Power University
删除前删除后删除 q↑.llink↑.rlink:=q↑,rlink
q↑.rlink↑.llink:=q↑,llink
North China Electric Power University
q
begin
q:=list↑.rlink; // q初值时指向头结点的下一个结点 //
while (q≠list) and (q↑.data≠x ) do
q:=q↑.rlink; // 找满足条件的链结点 //
if (q=list) then
[ write( ‘There is no this node’);
return; ] // 没有找到满足条件的结点 //
procedure delete( list,x );
end;
dispose(q); // 释放被删除的结点的存储空间 //
q↑.rlink↑.llink:=q↑.llink;
q↑.llink ↑ rlink:=q↑.rlink;
华电计算机系算法
… …x
q
North China Electric Power University
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
North China Electric Power University
第三章 链 表
★ 线性链表
★ 链栈、链队
★ 循环链表
★ 多重链表
★ 线性链表假定上图为当前内存的使用情况，阴影部分为已用内存，
现有一线性表 L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为 7的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构 — 链式存储。
North China Electric Power University
North China Electric Power University
G
F
B
C
E
D
H ^
A
可以采用上面的存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。
Head
North China Electric Power University
线性表的链式存储结构：
用一组 地址任意 的存储单元存放线性表中的数据元素结点 (表示数据元素 )=元素 (数据元素的映象 ) + 指针 (
指示后继元素存储位置 )
链表,以,结点的序列,表示的线性表 。
A B C D
EFG^ H
头结点数据 域 指针域链表结点头指针,指向链表中第一个结点的指针。
首元结点表结点头指针
Head
头结点,单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长度等附加信息。
North China Electric Power University
首元结点,单链表中存放第一个元素的结点。
表结点,存放线性表中所有数据元素的结点。
单链表中设置头结点的好处：
1)其头指针是指向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。
2)首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理 (如删除首元结点时，对不带头结点的单链表要修改头指针 )。
单链表上基本运算的实现
North China Electric Power University
1)Init_Link(Head):初始化一个单链表
Procedure Init_Link(Var Head:Link_list);
Begin
new(Head);
Head↑.Next:=Nil;
End;
单链表的类型定义如下：
Type Pointer=↑ Node;
Node=Record
data:ElemType;
next:Pointer;
End;
Link_list=Pointer;
North China Electric Power University
2)Length_Link (Head):返回单链表中所含表结点的个数。
Function Length_Link(Head:Link_list):Integer;
Begin
p:=Head;j:=0;
while p↑.Next< >Nil Do [ p:=p↑.Next; j:=j+1;]
Return(j);
End;
3)Length_Link (Head):返回指向线性表第 i个结点的指针。
Function Find_Link(Head:Link_list;i:Integer):Link_list;
Begin
p:=Head;j:=0;
while (p↑.Next< >Nil) and (j<i) Do
[ p:=p↑.Next; j:=j+1;]
if i=j then Return(p) else Return(Nil);
End;
North China Electric Power University
4)Locate_Link (Head,x):在单链表中查找值等于 x的结点，
返回指向该结点的指针。
Function Locate_Link(Head;x:ElemType):Link_list;
Begin
p:=Head;
while (p↑.Next< >Nil) and (p↑.data< > x) Do
p:=p↑.Next;
if p↑.data=x then Return(p) else Return(Nil);
End;
A B C D ^
x=‘C’
Head
p
North China Electric Power University
5)Insert_Link (Head,x,i):在单链表的第 i个结点之前插入值等于 x的结点。
Procedure Insert_Link(Var Head;x:ElemType;i:Integer);
Begin
p:=Find_Link(Head,i-1);
if p=Nil then Error(‘Without’)
else [ new(s);s↑.data:=x;s↑.next:=p↑.next;
p↑.next:=s;
]
End;
A B C D ^
x=‘F’ i=3
Head
p
F ①②S
North China Electric Power University
6)Delete_Link (Head,i):删除单链表的第 i个结点。
Procedure Delete_Link(Var Head;i:Integer);
Begin
p:=Find_Link(Head,i-1);
if (p< >Nil) and (p↑.next< >Nil)
then [ q:=p↑.next; p↑.next:=q;
dispose(q);
]
else Error(‘Without’);
End;
A B C D ^
i=3
Head
p
North China Electric Power University
7)Create_Link (Head):建立一个单链表。
Procedure Create_Link_1(Var Head:Link_list);
Begin
Init_Link(Head);
Read(x);i:=1;
while (x< > ‘*’ ) Do
[ Insert_Link(head,x,i);
i:=i+1;
Read(x);
]
End;
North China Electric Power University
Procedure Create_Link_2(Var Head: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;
Procedure Create_Link_3(Var Head:Link_list);
Begin
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;
North China Electric Power University
线性表的链式存储结构的优缺点：
优点,1)存储空间动态分配，可以按需要使用；
2)插入 /删除结点操作时，只需要修改指针，
不必移动数据元素缺点,1)每个结点序加一指针域，存储密度降低；
2)非随机存储结构，查找定位操作需要从头指针出发顺着链表扫描
North China Electric Power University
单链表的应用示例：
例 1.将一个单链表逆置
Procedure Invert_Link_1(Var Head:Link_list);
{不带头结点 }
Begin
p:=Head;Head:=Nil;
while (p < > Nil) Do
[ s:=p; p:=p↑.next;s↑.next:=Head;Head:=s;]
End;
Procedure Invert_Link_2(Var Head:Link_list);
{带头结点 }
Begin
p:=Head↑.next;h:=Nil;
while (p < > Nil) Do
[s:=p; p:=p↑.next; s↑.next:=h;h:=s;] head↑.next:=h;
End;
North China Electric Power University
例 2.设有带头结点的链表，每个结点有三个域,data，
Next,Sort，其中,data为整型值域,next和 sort
均为指针，现所有结点已由 next域链接起来，构成单链表，试编写利用 sort域把所有结点按照值的大小链接起来的算法。
算法的思想,1)先构造以 sort域为链表的空表；
2)依次扫描以 next域链接的单链表上的每个结点，并根据其值将其插入到以 sort域链接的链表的合适位置。
数据类型定义如下：
Slist=↑Snode;
Snode=Record
data:Integer;
next,sort:Slist;
End;
North China Electric Power University
Procedure LinkList_sort(Var Head:Slist);
Begin
h↑.sort:=nil;
q:=head↑.next;
while q< > Nil Do
[ pre:=head; p:=pre↑.sort;
while (p!=Nil) and (q↑data>p↑.data) Do
[ pre:=p;
p:=p↑.sort;]
q↑.sort:=p;
pre↑.sort:=q;
q:=q.next;
]
End;
North China Electric Power University
例 2：一元多项式的表示及相加。
在数学上，一个一元 n次多项式 Pn(X)可按升幂写成：
Pn(x)=P1xe1+P2xe2+… +Pmxem
其中,Pi是指数为 ei的项的非零系数，且满足
0≤e1<e2< … <em=n
若用一个长度为 m且每个元素有两个数据项（系数项和指数项）的线性表 ((p1,e1),(p2,e2),…,(pm,em))便可唯一确定多项式 Pn(x)。
可以采用链式存储结构来表示线性表：
TYPE link=↑node
node=RECORD
cnef:real; exp:integer; next:link
END;
Polyn=link;
North China Electric Power University
算法描述如下：
Procedure Polyadd(pa,pb:Polyn;var pc:Polyn);
{pa,pb和 pc分别表示多项式 A,B及它们的和 C的带表头的头指针 }
Begin
p:=pa↑.next;q:=pb↑.next;s:=pa;pc:=pa;{s指向 p的直接前驱 }
while (p< >Nil) and (q< >Nil) Do
Case
p↑.exp<q↑.exp:[s:=p;p:=p↑.next;]
p↑.exp=q↑.exp:[x:=p↑.coef+q↑.coef;
If x< > 0 then [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;]
EndCase
If q< >Nil then s↑.next:=q;dispose(pb);
End;
North China Electric Power University
例：求多项式的微商问题
Procedure Differential_coefficient(var L:Polyn);
Var q:Polyn;
Begin
q:=L↑.next;
while q< >Nil Do
[ if q↑.exp>0 then
[ q↑.coef:=q.↑coef*q↑.exp;
q↑.exp:=q↑.exp-1;
]
else
[ p:=q;q↑.next,=q↑,next↑,next;dispose(p);]
q:=q↑.next;
]
End;
练习 1
若已知非空线性链表第一个结点的指针为 list，
请 写一个算法,将该链表中数据域值最小的那个结点移到链表的最前端。
North China Electric Power University
lis
t
35 67 18 65827152 10 14… … ^
lis
t
35 67 18 65827152 10 14… … ^
q p
qs
华电 计算机系
North China Electric Power University
procedure Remove( list );
begin
q:=list;
p:=list↑.next;
r:=list;
while (p?nil) do
[ if (p↑.data <q↑.data) then
[ s:=r;
q:=p; ]
r:=p
p:=p↑.next;
] // 找到值最小的那个结点,地址由 q记录 //
if (q?list) then // 若值最小的结点不是链表最前面那个结点 //
[ s↑.next:=q↑.next;
q↑.next:=list;
list:=q; ]
end;
算法
North China Electric Power University
★ 链栈和链队堆栈的链式存储结构一,构造原理链接堆栈就是用一个线性链表来实现一个堆栈结构,同时设置一个指针变量 ( 这里不妨仍用 top
表示 )指出当前栈顶元素所在链结点的位置。当栈为空时，有 top=nil。
North China Electric Power University
在一个初始为空的链接堆栈中依次插入数据元素
A,B,C,D
以后,堆栈的状态为
D C B A ^
top
栈顶元素
North China Electric Power University
item
p
^
top
......
二,插入 (进栈 )算法
procedure Push_link_stack( top,item );
begin
new(p); //申请一个新结点 //
p↑.data:=item; //将 item送新结点数据域 //
p↑.next:=top; //将新结点插在链表最前面 //
top:=p; //修改栈顶指针的指向 //
End;
算法
North China Electric Power University
top
^item,.....
p
三,删除 (退栈 )算法
procedure Pop_link_stack( top,item );
Begin
if (top = nil) then
call STACK_EMPTY( ‘Stack is empty!’ )
else
[ p:=top; //暂时保存栈顶结点的地址 //
item:=top↑.data; //保存被删栈顶的数据信息 //
top:=top↑.next; //删去栈顶结点 //
dispose(p); ] //释放被删结点 //
End;
算法
North China Electric Power University
队列的链式存储结构一,构造原理队列的链式存储结构是用一个线性链表表示一个队列,指针 front 与 rear 分别指示队头和队尾的位置。
约 定,
rear 指出实际队尾元素所在的位置,
front 指出实际队头元素所在位置的前一个位置,
North China Electric Power University
在一个初始为空的链接队列中依次插入数据元素
A,B,C,D
以后,队列的状态为
A B C D ^
front rear
North China Electric Power University
front
rear
空队
front=rear=nil
p
item ^
front rear
…
front rear
二,插入算法
p
^item
North China Electric Power University
procedure addlinkqueue( front,rear,item );
begin
new(p); // 申请一个链结点 //
p↑.data:=item;
p↑.next:=nil;
rear↑.next:=p;
rear:=p;
End;
算 法
North China Electric Power University
…
front rear
^
procedure Del_link_queue( front,rear,item );
Begin
// 删除队头元素,并将数据域信息保存在变元 item中 //
if (front = nil) then
call Queue_empty( ‘Queue is empty!’ )
else
[ q:=front↑.next; front↑.next:=q↑.next;
item:=q↑.data; if q↑.next=nil then rear:=front;
dispose(q); ]
End;
三,删除算法算 法
North China Electric Power University
循环链表 是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表形成一个环。
★ 循环链表
North China Electric Power University
… ^
list
…
list
线性链表带头结点的循环链表
North China Electric Power University
循环链表的特点
1,只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。
2,对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。
3,当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。
… ^ … ^H
av av
… … ^H
av
av
单链表循环链表
North China Electric Power University
★ 多重链表
2.5 双向链表及其操作
1.双向链表的构造
2.双向链表的插入与删除
North China Electric Power University
一,双向链表的构造所谓 双向链表 是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。
链结点的实际构造可以形象地描述如下：
llink data rlink
其中,data 为数据域
llink,rlink 分别为指向该结点的直接前驱结点与直接后继结点的指针域华电计算机系
North China Electric Power University
双向链表的几种形式
list
^^
不带头结点的双向链表
list
不带头结点的双向循环链表
list
带头结点的双向循环链表
North China Electric Power University
二,双向链表的插入功能,在带有头结点的非空双向循环链表中第一个数据域的内容为 x 的链结点右边插入一个数据信息为 item 的新结点。
list
1,找到满足条件的结点。
2,若找到，申请一个新的链结点。
3,将新结点插到满足条件的结点后面。
需要做的工作
North China Electric Power University
itemitem
p
插入前
x
q
插入后插入
p↑.llink:=q p↑.rlink,=q↑.rlink
q↑.rlink:=p q↑.rlink↑.llink,=p
North China Electric Power University
Begin
q:=list↑.rlink; // q 初值时指向头结点的下一个结点 //
while (q≠list and q↑.data≠x) do
q:=q↑.rlink; // 寻找满足条件的链结点 //
if (q=list) then
[ write( ‘There is no this node !’ );
return; ] // 没有找到满足条件的结点 //
procedure insert( list,x,item );
End;
new(p) ; // 申请一个新的结点 //
p↑.data:=item;
q↑,rlink:=p;
q↑,rlink↑.llink:=p;
p↑.rlink:=q↑.rlink;
p↑.llink:=q;
算法
… …x
item
q
North China Electric Power University
三,双向链表的删除
1,找到满足条件的结点。
2,若找到，删除并释放该结点。
list
功能,删除带有头结点的非空双向循环链表中第一个数据域的内容为 x 的链结点。
需要做的工作
North China Electric Power University
删除前删除后删除 q↑.llink↑.rlink:=q↑,rlink
q↑.rlink↑.llink:=q↑,llink
North China Electric Power University
q
begin
q:=list↑.rlink; // q初值时指向头结点的下一个结点 //
while (q≠list) and (q↑.data≠x ) do
q:=q↑.rlink; // 找满足条件的链结点 //
if (q=list) then
[ write( ‘There is no this node’);
return; ] // 没有找到满足条件的结点 //
procedure delete( list,x );
end;
dispose(q); // 释放被删除的结点的存储空间 //
q↑.rlink↑.llink:=q↑.llink;
q↑.llink ↑ rlink:=q↑.rlink;
华电计算机系算法
… …x
q
North China Electric Power University
North China Electric Power University
