链式存储结构
假定上图为当前内存的使用情况，阴影部分为已用内存，假定上图为当前内存的使用情况，阴影部分为已用内存，
现有一线性表现有一线性表LL==((AA,,BB,,CC,,DD,,EE,,FF,,GG,,HH)),,假假若若采采用用顺顺序序存存储储的的，，
则则在在当当前前内内存存中中不不能能分分配配一一块块长长度度为为77的的连连续续的的存存储储空空间间。。
但实际上，系统的可用内存远大于该线性表所但实际上，系统的可用内存远大于该线性表所
1
要求的内存空间，应采用其它的存储结构要求的内存空间，应采用其它的存储结构——链式存储。链式存储。
2
Head
A B
C
G
F D
E
H ^
可以采用上面的存储结构，每一个数据元素占用两个存
储单元，其中一个用来存放数据元素的值，另外一个存
放下一个数据元素存储单元的地址，这种结构称为链式
存储结构。在这种结构中，数据元素存放是不连续的。
3
A
1.线性表的链式存储结构：
用一组地址任意的存储单元存放线性表中的数据元素
结点(表示数据元素)=元素(数据元素的映象) + 指针(
指示后继元素存储位置)
链表结点
链表：以“结点的序列”表示的线性表。
头指针
Head
头结点 首元结点
表结点
指针域数据域
B C D
EFGH^
A
头指针
Head
头结点 首元结点
表结点
头指针头指针：指向链表中第一个结点的指针。
头结点：头结点：单链表的第一个结点之前附设的一个结点，它单链表的第一个结点之前附设的一个结点，它的的
数数据据域域不不存存放放信信息息、、或或存存放放如如线线性性的的长长度度等等附附加加信信息息。。
首元结点：首元结点：单链表中存放第一个元素的结点。单链表中存放第一个元素的结点。
表结点：表结点：存放线性表中所有数据元素的结点。存放线性表中所有数据元素的结点。 4
B C D
EFGH^
5
Head
A B C D
^ H G F E
不带头结点的链表不带头结点的链表
6
链表中设置头结点的好处：链表中设置头结点的好处：
1)其头指针是指向头结点的非空指针，无论链表是否为
空，头指针始终保持值不变，因此头指针的处理方法
对空表和非空表的操作是一致的，这与不带头结点的
单链表为空时头指针为空不同。
2)首元结点的地址存放在头结点的指针域中，对该结点
的操作与其它结点的操作一致，无需进行特殊处理(如
删除首元结点时，对不带头结点的单链表要修改头指
针)。
7
Head
a1 a2 ^an
2.链表的描述
链表由头指针唯一确定，因此单链表可以用头指针
的名字来命名。
例如：若头指针为head,则可把链表称为“表head”。
8
typedef struct link {
ElEM element;
link * next;
}Link;
element next
（1） 结点的描述：
结点 数据域 指针域
（（22）结点的访问）结点的访问：
• 指针p与指向的结点关系示意图：
P
结点 (*p)
说明：
p---指向链表中某一结点的指针。
*p---表示 由指针p所指向的结点。
(*p).element或p->element -----------------表示由
p所指向结点的数据域。
(*p).next或p->next -------------表示由p所指向
结点的指针域。 9
nextelement
申请空间：
new type
例 ：LNode *p; p=new
Lnode;
回收空间
delete p；
10
11
typedef struct list {
link * head;
link * tail; link
*curr;
}
（（33）链表的类定义）链表的类定义
12
（（44）） 链表的成员函数定义链表的成员函数定义
13
14
链表的插入操作函数链表的插入操作函数
curr
S ①
s=new link;
① ①
item
①
s->element = Item;
s->next=curr->next;
curr->next=s;
curr->next= new link(item, curr->next);
15
16
b
b
链表的删除操作函数链表的删除操作函数
curr
a c
ltemp
link *itemp= curr->next
curr->next =ltemp->next;
delete ltemp；
存储池
17
18
链表的清空操作函数链表的清空操作函数
19
链表的其他操作函数链表的其他操作函数
20
21
22
curr
curr
23
curr
24
两种实现方法的比较：
（1） 顺序是用数组实现的，而链表是用
指针来实现的。
（2） 当线性表的长度变化较大，难以估
计其存储规模时， 益采用动态链表作为
存储结构为佳；当线性表的长度变化不
大，易于事先确定其大小时，为了节约
存储空间，宜采用顺序表作为存储结构。
（基于空间的考虑）
25
• （3）顺序表是一种随机存取结构，对表中任一
结点都可在O(1)时间内直接存取。而链表中
的结点则需用从头指针开始顺链扫描。
因此：
若线性表的操作主要是查找，很少涉及到插
入、删除操作时，可采用顺序表结构。
若要频繁地进行插入和删除操作，宜采用链
表作为存储结构。
若表的插入、删除操作主要发生在表的两
端，则宜采用有尾指针的单循环链表。
26
可利用空间表可利用空间表
• 可利用空间表的作用是管理可用于链表插
人和删除的节点，当链表插人需要一个新
节点时，就从可利用空间表中删除第一个
节点，用这个节点去做链表插人；当从链
表中删除一个节点时，就把这个节点插人
到可利用空间表的第一个节点前面。 这样
可以减少调用系统级的空间管理
27
Class link
{ public:
Elem element;
List* next;
static Link<Elem>* freelist;//静态类成员
Link(const Elem &elemval,List* nextval=NULL)//构函数
同时进行类的初始化。
{ element=dataval; next=nextval; }
Link(List* nextval=NULL)
{ next=nextval; }
~List(){};
void* operator new(size_t);//new重载函数的声明。void
operator delete(void*);//delete重载函数的声明。
};
Link*link::freelist=NULL;// 静态类数据成员的初始化。
28
newnew重载函数的实现重载函数的实现
• void*link::operator
new(size_t){ if(
freelist==Null)
• return ::new link ；
link* temp=freelist;
freelist=freelist->next; return
temp;
29
}
30
• delete重载函数的实现。
void operator delete(void *ptr)
{
((Link*)ptr)->next=freelist; //因为
void* ptr是不指向任何类型的指针。所以
要记得强制link*型的指针。
freelist=(Link*)ptr; }
31
链表的其他形式链表的其他形式
• 循环链表
• 双向链表
32
……..
循环链表
整个链表形成一个环，从表中任一结点出发均可找到表
中其它结点。
特点特点：（1）表中最后一个结点的指针指向第一个结点
或表头结点（如有表头结点的话）。
Head
a1 an
(非空表）
head (空表）
33
• （2）循环链表的运算与线性链表基本一致。
但两者判断是否到表尾的条件不同：
线性表：判断某结点的链域是否为空。
head->next=NULL
循环链表：判断某结点的链域值是否等于头
指针。
Head->next=head
head head
33
• （3）用头指针表示的单循环链表查找结点：
找a1(开始结点) O(1)
找an 需要遍历表 O(n)
由于在实际问题中，对表的操作常在表的首尾位
置进行，因此可增加一个尾指针(rear)，则：
找a1(开始结点) ：rear->next->next O(1)
找an rear O(1)
实用中多用尾指针表示单循环链表。
34
head
非空表 rear
空循环链表
head
空表 rear
35
双向链表（Double linked list
回顾单链表查找特点的：
只能顺链向前（顺着直接后继指针）查
找。若要找某一结点的前趋，则：
单链表：从头顺链找。O(n)
36
• 双向链表（Double linked list)----
单链表的每个结点再增加一个指向其前趋的指针域
prev，这样形成的链表有两条不同方向的链，称之
为双（向）链表。
特点：
双链表一般也由头指针head唯一确定。
每一结点均有：
数据域（element)
左链域 （prev)指向前趋结点.
右链域 （next)指向后继。
是一种对称结构（既有前趋势，又有后继）。
37
双向链表双向链表((DoubleDouble LinkedLinked ListList)_)_表示表示
prev element next
L
L
38
双向链表双向链表_C_C表示表示
39
40
41
curr->next =new link(item, curr-next, curr);
Curr->next->next->prev =curr->next;
双向链表双向链表__插入插入
curr
s
s=new link(item, curr-next, curr);
curr->next = s;
Curr->next->next->prev = s;
a b
item
42
双向链表双向链表__删除删除
curr ltemp
a b c
Temp=curr->next->element;
Link*ltemp=curr->next;
Ltemp->next->prev=curr;
Curr->next=ltemp->next; delete
ltemp;
Return temp;
43
线性表的应用线性表的应用
例1 一元多项式相加
P2000(x)= 1+ 3x1000 +
5x2000
. 一元多项式的数学通式？一元多项式的数学通式？
A ( x )
①
a m 1 x
e m 1 a m 2 x
e m 2 . . . a 0 x
一般用顺序存储—— 只存系数项（但零系数项也不能遗漏）
但当多项式的次数很高且零系数项很多时，更适于用链表存储。
通常设计两个数据域（系数项和指数项）和一个指针域
链式存储 …
或 …
头结点 44
linkexponcoef
e 0
a0 a1 a2 … am-2 am-1
am-1 em-1 am-2 em-2 a0 e0 ^
-1 a0 e0 am-1 em-1 ^
45
P ( x) ① p x e1 p x e2 ... p x em
n 1 2 m
(( p1, e1), ( p2, e2 ),①,( pm , em ))
A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8
polya
polyb
07 913 8
2218 7－1
－1 5 17
－9 8
46
例222：如如何何编编程程实实现现两两个个一一元元多多项项式式相相加加？？
A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8
polya
polyb －1
－1 7 0 913 8
2218 7
5 17
－9 8
－1 7
因3x＋8x＝11x而得
90
8 1－1 8－9
polya
polyb
因9x8＋(－9)x8＝0而被删除
并释放
polya 8 5 17
合并后释放
polyb 的头结点
因3x＋8x＝11x被并到
polya 中,该结点被删除并释放
多项式相加得到的多项式和 47
722 8－918
175891307
－1
－1
11 1
22 7
48
49
p
50
51
La
pa
Lc = La
pc = Lc
例例22 有序线性链表合并有序线性链表合并
把有序表把有序表a=(2,6,7,9)a=(2,6,7,9) 和和 b=(1,4,7,8,10)b=(1,4,7,8,10)合合
并并
合并后合并后c=(1,2,4,6,7,8,9,10c=(1,2,4,6,7,8,9,10 ))
Lb
pb 52
pa = pa->next;
}
53
有序线性链表合并有序线性链表合并((pa->datapa->data << pb->datapb->data))
La
Lc = La pa
pc
if ( pa->data < pb->data )
{
pc->next = pa; pc
= pa;
L
b
pb
pc->next = pb;
pc = pb;
pb = pb->next;
}
54
La
pa
Lc = La
b
pc
pb
有序线性链表合并有序线性链表合并((pa->datapa->data >> pb->datapb->data))
L
if ( pa->data > pb->data )
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
55
La
pa
Lc = La
b
pc
pb
有序线性链表合并有序线性链表合并((pa->datapa->data >> pb->datapb->data))
L
if ( pa->data > pb->data )
{
有序线性链表合并有序线性链表合并((pa->datapa->data ==== pb->datapb->data))
La
Lc = La
pc
pa
Lb
if ( pa->data == pb->data )
{
pc->next = pa;
pc = pa;
pa = pa->next; q
= pb;
pb = pb->next;
delete( q );
q pb
56
}
57
La
Lc = La
b
pc pa
pb
有序线性链表合并有序线性链表合并((papa ==== NULLNULL))
L
58
有序线性链表合并有序线性链表合并((papa ==== NULLNULL))
La
Lc = La
Lb
pc pa=NULL
若La（Lb）线性链表全部加入到Lc中， pb
只需要把另一个链表的剩余部分完整地
加入Lc中即可。
Pc->next = pa ? pa : pb;
59
有序线性链表合并有序线性链表合并
La
Lc = La
Lb
delete( Lb );
pc pa
pb
60
La
pc
Lc = La
b
pb
有序线性链表合并有序线性链表合并
pa
L
61
本章小结本章小结
本章主要介绍了如下一些基本概念：
线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，
an-1的有限序列。
线性表的顺序存储结构：在计算机中用一组地址连续的存
储单元依次存储线性表的各个数据元素，称作线性表的顺序
存储结构。
线性表的链式存储结构：线性表的链式存储结构就是用一
组任意的存储单元——结点（可以是不连续的）存储线性表
的数据元素。表中每一个数据元素，都由存放数据元素值的
数据域和存放直接前驱或直接后继结点的地址（指针）的指
针域组成。
循环链表：循环链表(Circular Linked List)是将单链表的表
中最后一个结点指针指向链表的表头结点，整个链表形成一
个环，从表中任一结点出发都可找到表中其他的结点。
62
双向链表：双向链表中，在每一个结点除了数据域外，
还包含两个指针域，一个指针（next）指向该结点的后
继结点，另一个指针（left）指向它的前驱结点。
除上述基本概念以外，学生还应该了解：线性表的基本
操作（初始化、插入、删除、存取、复制、合并）、顺
序存储结构的表示、线性表的链式存储结构的表示、一
元多项式Pn(x)，掌握顺序存储结构（初始化、插入操作
、删除操作）、单链表（单链表的初始化、单链表的插
入、单链表的删除）。
