第 3章 线性链表线性结构 特点,在数据元素的非空有限集中
存在 唯一 的一个被称作,第一个,的数据元素
存在 唯一 的一个被称作,最后一个,的数据元素
除第一个外，集合中的每个数据元素均 只有一个前驱
除最后一个外，集合中的每个数据元素均 只有一个后继
顺序存储结构的优缺点
优点
逻辑相邻，物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分
表容量难以扩充
§ 线性表的链式存储结构特点：
用一组 任意 的存储单元存储线性表的数据元素
利用 指针 实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素 ai,除存储本身信息外，还需存储其直接后继的信息
结点
数据域：元素本身信息
指针域：指示直接后继的存储位置 数据域 指针域结点
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
LI
QIAN
SUN
WANG
WU
ZHAO
ZHENG
ZHOU
存储地址
1
7
13
19
25
31
37
43
31
H
头指针
实现 typedef struct node {
datatype data;
struct node *link;
}JD;
JD *h,*p;
data link
p 结点（ *p）
(*p)表示 p所指向的结点
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域生成一个 JD型 新结点,p=(JD *)malloc(sizeof(JD));
系统回收 p结点,free(p)
线性链表
定义：结点中只含一个指针域的链表叫 ~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫 ~
头结点指针域为空表示线性表为空
h a1 a2
头结点
an ^…...
h 空表^
单链表的基本运算
查找：查找单链表中是否存在结点 X，若有则返回指向 X结点的指针；否则返回 NULL
算法描述
While循环中语句频度为若找到结点 X,为结点 X在表中的序号否则，为 n
nOnT
p a b
xs
算法评价
插入：在线性表两个数据元素 a和 b间插入 x,已知 p指向 a
s->link=p->link;p->link=s;
1OnT?
算法描述
算法评价
算法描述
p a b c
1OnT?
算法评价
删除：单链表中删除 b,设 p指向 a
p->link=p->link->link;
nOnT?
动态建立单链表算法,设线性表 n个元素已存放在数组 a中，
建立一个单链表,h为头指针
算法描述
算法评价
h
头结点
an ^0
头结点
an-1 an ^a2 …...
头结点
an-1 an ^a1 a2
头结点
an ^…...0
Ch2_3.c
头结点
^
单链表特点
它是一种 动态结构,整个存储空间为多个链表共用
不需预先分配 空间
指针占用 额外 存储空间
不能随机存取,查找速度慢
循环链表 (circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，
提高查找效率
操作与单链表基本一致,循环条件不同
单链表 p或 p->link=NULL
循环链表 p或 p->link=H
h
h 空表
双向链表（ double linked list）
单链表具有单向性的缺点
结点定义
typedef struct node {
datatype element;
struct node *prior,*next;
}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A Bb ca
p
p->prior->next= p= p->next->proir;
b ca
P
void del_dulist(JD *p)
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
删除
算法描述
算法评价,T(n)=O(1)
p->prior->next=p->next;
p->next->prior=p->prior;
void ins_dulist(JD* p,int x)
{JD *s;
s=(JD*)malloc(sizeof(JD));
s->element=x;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
}
算法描述
算法评价,T(n)=O(1)
xS
ba
P?插入
§ 线性表的应用举例一元多项式的表示及相加
一元多项式的表示：
nnn xPxPxPPxP2210)(
),,,,( 210 nPPPPP可用线性表 P表示
2 0 0 0 01 0 0 0 231)( xxxS但对 S(x)这样的多项式浪费空间一般
emmn xPxPxPxP ee21 21)(
其中 为非零系数）（
iPemee210
用数据域含两个数据项的线性表表示
emPePeP m,，，，,21 21
其存储结构可以用顺序存储结构，也可以用单链表
单链表的结点定义
typedef struct node
{ int coef,exp;
struct node *next;
}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
一元多项式相加设 p,q分别指向 A,B中某一结点,p,q初值是第一结点比较
p->exp与 q->exp
p->exp < q->exp,p结点是和多项式中的一项
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项将 q插在 p之前,q后移,p不动
p->exp = q->exp,系数相加 0：从 A表中删去 p,释放 p,q,p,q后移
0：修改 p系数域,
释放 q,p,q后移直到 p或 q为 NULL 若 q==NULL,结束若 p==NULL,将 B中剩余部分连到 A上即可
运算规则
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
Ch2_7.c
算法描述
链栈栈顶
^…...top data link
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *link;
}JD;
^…...
栈底
toptop
xp
top
^…...
栈底
top
q
链队列
结点定义 typedef struct node
{ int data;
struct node *link;
}JD;
头结点
^…...front
队头 队尾
rear
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
入队算法
出队算法
存在 唯一 的一个被称作,第一个,的数据元素
存在 唯一 的一个被称作,最后一个,的数据元素
除第一个外，集合中的每个数据元素均 只有一个前驱
除最后一个外，集合中的每个数据元素均 只有一个后继
顺序存储结构的优缺点
优点
逻辑相邻，物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分
表容量难以扩充
§ 线性表的链式存储结构特点：
用一组 任意 的存储单元存储线性表的数据元素
利用 指针 实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素 ai,除存储本身信息外，还需存储其直接后继的信息
结点
数据域：元素本身信息
指针域：指示直接后继的存储位置 数据域 指针域结点
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
LI
QIAN
SUN
WANG
WU
ZHAO
ZHENG
ZHOU
存储地址
1
7
13
19
25
31
37
43
31
H
头指针
实现 typedef struct node {
datatype data;
struct node *link;
}JD;
JD *h,*p;
data link
p 结点（ *p）
(*p)表示 p所指向的结点
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域生成一个 JD型 新结点,p=(JD *)malloc(sizeof(JD));
系统回收 p结点,free(p)
线性链表
定义：结点中只含一个指针域的链表叫 ~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫 ~
头结点指针域为空表示线性表为空
h a1 a2
头结点
an ^…...
h 空表^
单链表的基本运算
查找：查找单链表中是否存在结点 X，若有则返回指向 X结点的指针；否则返回 NULL
算法描述
While循环中语句频度为若找到结点 X,为结点 X在表中的序号否则，为 n
nOnT
p a b
xs
算法评价
插入：在线性表两个数据元素 a和 b间插入 x,已知 p指向 a
s->link=p->link;p->link=s;
1OnT?
算法描述
算法评价
算法描述
p a b c
1OnT?
算法评价
删除：单链表中删除 b,设 p指向 a
p->link=p->link->link;
nOnT?
动态建立单链表算法,设线性表 n个元素已存放在数组 a中，
建立一个单链表,h为头指针
算法描述
算法评价
h
头结点
an ^0
头结点
an-1 an ^a2 …...
头结点
an-1 an ^a1 a2
头结点
an ^…...0
Ch2_3.c
头结点
^
单链表特点
它是一种 动态结构,整个存储空间为多个链表共用
不需预先分配 空间
指针占用 额外 存储空间
不能随机存取,查找速度慢
循环链表 (circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，
提高查找效率
操作与单链表基本一致,循环条件不同
单链表 p或 p->link=NULL
循环链表 p或 p->link=H
h
h 空表
双向链表（ double linked list）
单链表具有单向性的缺点
结点定义
typedef struct node {
datatype element;
struct node *prior,*next;
}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A Bb ca
p
p->prior->next= p= p->next->proir;
b ca
P
void del_dulist(JD *p)
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
删除
算法描述
算法评价,T(n)=O(1)
p->prior->next=p->next;
p->next->prior=p->prior;
void ins_dulist(JD* p,int x)
{JD *s;
s=(JD*)malloc(sizeof(JD));
s->element=x;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
}
算法描述
算法评价,T(n)=O(1)
xS
ba
P?插入
§ 线性表的应用举例一元多项式的表示及相加
一元多项式的表示：
nnn xPxPxPPxP2210)(
),,,,( 210 nPPPPP可用线性表 P表示
2 0 0 0 01 0 0 0 231)( xxxS但对 S(x)这样的多项式浪费空间一般
emmn xPxPxPxP ee21 21)(
其中 为非零系数）（
iPemee210
用数据域含两个数据项的线性表表示
emPePeP m,，，，,21 21
其存储结构可以用顺序存储结构，也可以用单链表
单链表的结点定义
typedef struct node
{ int coef,exp;
struct node *next;
}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
一元多项式相加设 p,q分别指向 A,B中某一结点,p,q初值是第一结点比较
p->exp与 q->exp
p->exp < q->exp,p结点是和多项式中的一项
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项将 q插在 p之前,q后移,p不动
p->exp = q->exp,系数相加 0：从 A表中删去 p,释放 p,q,p,q后移
0：修改 p系数域,
释放 q,p,q后移直到 p或 q为 NULL 若 q==NULL,结束若 p==NULL,将 B中剩余部分连到 A上即可
运算规则
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
Ch2_7.c
算法描述
链栈栈顶
^…...top data link
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *link;
}JD;
^…...
栈底
toptop
xp
top
^…...
栈底
top
q
链队列
结点定义 typedef struct node
{ int data;
struct node *link;
}JD;
头结点
^…...front
队头 队尾
rear
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
入队算法
出队算法
