1
六、双向链表
１、双向链表的存储结构
双向链表,链表中每个结点除后继指针域和数
据域外还有一个前驱指针域。
其 结点的结构 为：
双向链表结点的结构体定义如下：
typedef struct Node
{ DataType data;
struct Node *next;
struct Node *prior; }DLNode;
prior data next
2
s a0 a1 an
带头结点的双向循环链表的结构示意图。
head
…
与单链表类同，双向链表分带头结点和不带头结
点两种，也分有循环和非循环两种结构。下面仅讨论
带头结点的双向循环链表。
3
2、双向链表的操作实现
(1)前插 设 p已指向第 i 元素，请在第 i 元素 前 插入元素 x
xs
ai-1 ai
p
指针域的变化,
① ai-1的后继从 ai ( 指针是 p)变为 x（指针是 s),
s->next = p ; p->prior->next = s ;
② ai 的前驱从 ai-1 ( 指针是 p->prior)变为 x ( 指针是 s);
s->prior = p ->prior ; p->prior = s ;
4
p
指针域的变化,
后继方向,ai-1的后继由 ai ( 指针 p)变为 ai+1(指针 p ->next );
p ->prior->next = p->next ;
前驱方向,ai+1 的前驱由 ai ( 指针 p)变为 ai-1 (指针 p -> prior );
p->next->prior = p ->prior ;
(2)双向链表的删除操作
设 p指向第 i 个元素，删除第 i 个 元素
ai-1 ai ai+1
5
例,已知 P结点是双向链表的中间结点, 试从下列
提 供 的 答 案 中 选 择 合 适 的 语 句 序 列 。
a,在 P结点后插入 S结点的语句序列是 -----------。
b,在 P结点前插入 S结点的语句序列是 -----------。
c,删除 P结点的直接后继结点的语句序列是 - -----。
d,删除 P结点的直接前驱结点的语句序列是 -------。
e,删除 P结点的语句序列是 ------------。
6
(1)P->next=P->next->next; (10) P->prior->next=P;
(2)P->prior=P->prior->prior; (11) P->next->prior =P;
(3) P->next=S; (12)P->next->prior=S;
(4) P->prior=S; (13) P->prior->next=S;
(5)S->next=P; (14) P->next->prior=P->prior
(6)S->prior=P; (15)Q=P->next;
(7) S->next= P->next; (16)Q= P->prior;
(8) S->prior= P->prior; (17)free(P);
(9) P->prior->next=p->next; (18)free(Q);
解答：
a.(12)(7)(3)(6) 3必须在 12和 7的后面，其余的顺序可变
b.(13)(8)(4)(5) 同上
c.(15)(1)(11)(18) 不可变
d.(16)(2)(10)(18) 不可变
e.(9)(14)(17)
7
2.4 静态链表
静态链表,在数组中增加一个（或两个）指针
域，这些指针域用来存放下一个（或上一个）
数据元素在数组中的下标，从而构成用数组
构造的单链表（或双链表）。静态链表中的
指针又称仿真指针。
8
静态单链表的类型定义如下：
#define MAXSIZE 1000 //预分配最大的元素个数（连续空间
typedef struct {
DataType data ; //数据域
int next ; //指示域
}component,SLinkList[MAXSIZE] ; //这是一维结构型数组
例 1,软考题,L={ 23,17,47,05,31 }
若此分量定义为 指针型,属于 动态链表（题目中是指针） ；
若此分量定义为 整型 （通常存放下标），则属于 静态链表 。
Z47Y31V23X17U05
100 119104 108 116112
9
例 2：一 线性表 S = ( ZHAO,QIAN,SUN,LI,ZHOU,
WU )，用静态链表如何表示？
data
1
ZHAO 3
LI 5
QIAN 6
WU 0
ZHOU 4
SUN 2
…… ……
0
1
2
3
4
5
6
…
1000
cur 说明 1,假设 S为 SLinkList型变量，则
S[MAXSIZE] 为一个静态链表；
S[0].next则表示第 1个结点在数组中的
位置。
说明 2,如果数组的第 i个分量表示链表
的第 k个结点，则：
S[i].data表示第 k个结点的数据；
S[i].next 表示第 k+1个结点 (即 k的直
接后继 )的位置。
i
头结点
10
说明 3,静态链表的插入与删除操作与普通链表一样，不需要
移动元素，只需修改指示器就可以了。
例如：在线性表 S = ( ZHAO,QIAN,SUN,LI,ZHOU,WU )的
QIAN,SUN之间 插入新元素 LIU，可以这样实现：
S[7].next = S[3].next；
Step2:将 QIAN的游标换为新元素 LIU的
下标：
S[3].next = 7
Step1:将 QIAN的游标值存入 next的游
标中：
data
……
2SUN
4ZHOU
0WU
6QIAN
5LI
3ZHAO
10
1
2
3
4
5
6
1000
curi
头结点
LIU 67
7
11
例 3,试用 C或类 C语言编写一 高效 算法，将一顺
序存储的线性表（设元素均为整型量）中所有零
元素向表尾集中，其他元素则 顺序 向表头方向集
中。
（ a1,a2,… ai-1,ai,ai+1, …,a n）
常见做法：
①从前往后扫描，见到 0元素则与尾部非 0元素互换；
② 从后往前扫描，见到 0元素则后面元素统统前移；
③ 从前往后扫描，见到 0元素先计数，再将后续的一
个非 0元素前移，全部扫完后再把后续部分（长度为 0
元素的个数）清 0。
×
×
√
深圳华为公司
去年来校招聘
面试题
12
解,void SortA(SeqList *L)
{ int i=0,zerosum =0;
if(L->size= =0) return(0); //空表则结束
else { for( i=0; i<L.->size; i++)
{if (L->list[i]<>0) L->list[i- zerosum]= L->list[i];
else zerosum++; }
}
for( i= L->size-zerosum; i<=L.->size; i++)
L->list[i]=0; //表的后部补 0
}
若表完全不空，也要
移动 n次？
13
若考虑表完全非空的情况，则程序要变长很多。
解,void SortA(SeqList *L)
{ int i=0,zerosum =0;
if(L->size= =0) return(0); //空表则不执行
for( i; i<=L->size; i++)
{if (L->list[i]<>0&zerosum!=0)L->list[i- zerosum]= L-
>list[i];
else zerosum++ }; //适当移动非零元素,是零则增加计数
for( i= L->size-zerosum+1; i<=L->size; i++)
L->list[i]=0; //表的后部补 0
return( )；
}
14
本章小结
1,线性结构 (包括表、栈、队、数组）的定义和特点,
仅一个首、尾结点，其余元素仅一个直接前驱和一个
直接后继。
2,线性表
逻辑结构,, 一对一, 或, 1:1”
存储结构,顺序、链式
运 算,修改、插入、删除 [查找和排序另述 ]
3.顺序存储
特征,逻辑上相邻，物理上也相邻；
优点,随机查找修改快 O(1)
缺点,插入、删除慢 O(n)
改进方案,链表存储结构
15
循环链表的特点,从任一结点出发均可找到表中其他结点
双向链表的特点,可方便 找到任一结点的前驱
静态链表的特点,不用指针也能实现链式存储和运算
4.链式存储
特征,逻辑上相邻，物理上未必相邻；
优点,插入、删除快 O(1)
缺点,随机查找修改慢 O(n)
5.几种特殊链表的特点：
16
讨论 1,顺序存储和链式存储的区别和优缺点？
顺序存储时,逻辑上相邻的数据元素，其物理存放地址
也相邻。顺序存储的优点是存储密度大，存储空间利用率高；
缺点是插入或删除元素时不方便。
链式存储时,相邻数据元素可随意存放，但所占存储空
间分两部分，一部分存放结点值，另一部分存放表示结点间
关系的指针。链式存储的优点是插入或删除元素时很方便，
使用灵活。缺点是存储密度小，存储空间利用率低。
顺序表 适宜于做 查找 这样的静态操作； 链表 宜于做 插
入、删除 这样的动态操作。若 线性表的长度变化不大,且
其主要操作是查找，则采用顺序表；若 线性表的长度变化
较大,且其主要操作是插入、删除操作，则采用链表。
17
讨论 2,什么是指针？指针的作用？
指针 — 即变量的内存地址。 指针主要功能 有二：
①提供了一种快速访问数组单元的途径；
②使 C语言函数可以修改其调用的参数。
六、双向链表
１、双向链表的存储结构
双向链表,链表中每个结点除后继指针域和数
据域外还有一个前驱指针域。
其 结点的结构 为：
双向链表结点的结构体定义如下：
typedef struct Node
{ DataType data;
struct Node *next;
struct Node *prior; }DLNode;
prior data next
2
s a0 a1 an
带头结点的双向循环链表的结构示意图。
head
…
与单链表类同，双向链表分带头结点和不带头结
点两种，也分有循环和非循环两种结构。下面仅讨论
带头结点的双向循环链表。
3
2、双向链表的操作实现
(1)前插 设 p已指向第 i 元素，请在第 i 元素 前 插入元素 x
xs
ai-1 ai
p
指针域的变化,
① ai-1的后继从 ai ( 指针是 p)变为 x（指针是 s),
s->next = p ; p->prior->next = s ;
② ai 的前驱从 ai-1 ( 指针是 p->prior)变为 x ( 指针是 s);
s->prior = p ->prior ; p->prior = s ;
4
p
指针域的变化,
后继方向,ai-1的后继由 ai ( 指针 p)变为 ai+1(指针 p ->next );
p ->prior->next = p->next ;
前驱方向,ai+1 的前驱由 ai ( 指针 p)变为 ai-1 (指针 p -> prior );
p->next->prior = p ->prior ;
(2)双向链表的删除操作
设 p指向第 i 个元素，删除第 i 个 元素
ai-1 ai ai+1
5
例,已知 P结点是双向链表的中间结点, 试从下列
提 供 的 答 案 中 选 择 合 适 的 语 句 序 列 。
a,在 P结点后插入 S结点的语句序列是 -----------。
b,在 P结点前插入 S结点的语句序列是 -----------。
c,删除 P结点的直接后继结点的语句序列是 - -----。
d,删除 P结点的直接前驱结点的语句序列是 -------。
e,删除 P结点的语句序列是 ------------。
6
(1)P->next=P->next->next; (10) P->prior->next=P;
(2)P->prior=P->prior->prior; (11) P->next->prior =P;
(3) P->next=S; (12)P->next->prior=S;
(4) P->prior=S; (13) P->prior->next=S;
(5)S->next=P; (14) P->next->prior=P->prior
(6)S->prior=P; (15)Q=P->next;
(7) S->next= P->next; (16)Q= P->prior;
(8) S->prior= P->prior; (17)free(P);
(9) P->prior->next=p->next; (18)free(Q);
解答：
a.(12)(7)(3)(6) 3必须在 12和 7的后面，其余的顺序可变
b.(13)(8)(4)(5) 同上
c.(15)(1)(11)(18) 不可变
d.(16)(2)(10)(18) 不可变
e.(9)(14)(17)
7
2.4 静态链表
静态链表,在数组中增加一个（或两个）指针
域，这些指针域用来存放下一个（或上一个）
数据元素在数组中的下标，从而构成用数组
构造的单链表（或双链表）。静态链表中的
指针又称仿真指针。
8
静态单链表的类型定义如下：
#define MAXSIZE 1000 //预分配最大的元素个数（连续空间
typedef struct {
DataType data ; //数据域
int next ; //指示域
}component,SLinkList[MAXSIZE] ; //这是一维结构型数组
例 1,软考题,L={ 23,17,47,05,31 }
若此分量定义为 指针型,属于 动态链表（题目中是指针） ；
若此分量定义为 整型 （通常存放下标），则属于 静态链表 。
Z47Y31V23X17U05
100 119104 108 116112
9
例 2：一 线性表 S = ( ZHAO,QIAN,SUN,LI,ZHOU,
WU )，用静态链表如何表示？
data
1
ZHAO 3
LI 5
QIAN 6
WU 0
ZHOU 4
SUN 2
…… ……
0
1
2
3
4
5
6
…
1000
cur 说明 1,假设 S为 SLinkList型变量，则
S[MAXSIZE] 为一个静态链表；
S[0].next则表示第 1个结点在数组中的
位置。
说明 2,如果数组的第 i个分量表示链表
的第 k个结点，则：
S[i].data表示第 k个结点的数据；
S[i].next 表示第 k+1个结点 (即 k的直
接后继 )的位置。
i
头结点
10
说明 3,静态链表的插入与删除操作与普通链表一样，不需要
移动元素，只需修改指示器就可以了。
例如：在线性表 S = ( ZHAO,QIAN,SUN,LI,ZHOU,WU )的
QIAN,SUN之间 插入新元素 LIU，可以这样实现：
S[7].next = S[3].next；
Step2:将 QIAN的游标换为新元素 LIU的
下标：
S[3].next = 7
Step1:将 QIAN的游标值存入 next的游
标中：
data
……
2SUN
4ZHOU
0WU
6QIAN
5LI
3ZHAO
10
1
2
3
4
5
6
1000
curi
头结点
LIU 67
7
11
例 3,试用 C或类 C语言编写一 高效 算法，将一顺
序存储的线性表（设元素均为整型量）中所有零
元素向表尾集中，其他元素则 顺序 向表头方向集
中。
（ a1,a2,… ai-1,ai,ai+1, …,a n）
常见做法：
①从前往后扫描，见到 0元素则与尾部非 0元素互换；
② 从后往前扫描，见到 0元素则后面元素统统前移；
③ 从前往后扫描，见到 0元素先计数，再将后续的一
个非 0元素前移，全部扫完后再把后续部分（长度为 0
元素的个数）清 0。
×
×
√
深圳华为公司
去年来校招聘
面试题
12
解,void SortA(SeqList *L)
{ int i=0,zerosum =0;
if(L->size= =0) return(0); //空表则结束
else { for( i=0; i<L.->size; i++)
{if (L->list[i]<>0) L->list[i- zerosum]= L->list[i];
else zerosum++; }
}
for( i= L->size-zerosum; i<=L.->size; i++)
L->list[i]=0; //表的后部补 0
}
若表完全不空，也要
移动 n次？
13
若考虑表完全非空的情况，则程序要变长很多。
解,void SortA(SeqList *L)
{ int i=0,zerosum =0;
if(L->size= =0) return(0); //空表则不执行
for( i; i<=L->size; i++)
{if (L->list[i]<>0&zerosum!=0)L->list[i- zerosum]= L-
>list[i];
else zerosum++ }; //适当移动非零元素,是零则增加计数
for( i= L->size-zerosum+1; i<=L->size; i++)
L->list[i]=0; //表的后部补 0
return( )；
}
14
本章小结
1,线性结构 (包括表、栈、队、数组）的定义和特点,
仅一个首、尾结点，其余元素仅一个直接前驱和一个
直接后继。
2,线性表
逻辑结构,, 一对一, 或, 1:1”
存储结构,顺序、链式
运 算,修改、插入、删除 [查找和排序另述 ]
3.顺序存储
特征,逻辑上相邻，物理上也相邻；
优点,随机查找修改快 O(1)
缺点,插入、删除慢 O(n)
改进方案,链表存储结构
15
循环链表的特点,从任一结点出发均可找到表中其他结点
双向链表的特点,可方便 找到任一结点的前驱
静态链表的特点,不用指针也能实现链式存储和运算
4.链式存储
特征,逻辑上相邻，物理上未必相邻；
优点,插入、删除快 O(1)
缺点,随机查找修改慢 O(n)
5.几种特殊链表的特点：
16
讨论 1,顺序存储和链式存储的区别和优缺点？
顺序存储时,逻辑上相邻的数据元素，其物理存放地址
也相邻。顺序存储的优点是存储密度大，存储空间利用率高；
缺点是插入或删除元素时不方便。
链式存储时,相邻数据元素可随意存放，但所占存储空
间分两部分，一部分存放结点值，另一部分存放表示结点间
关系的指针。链式存储的优点是插入或删除元素时很方便，
使用灵活。缺点是存储密度小，存储空间利用率低。
顺序表 适宜于做 查找 这样的静态操作； 链表 宜于做 插
入、删除 这样的动态操作。若 线性表的长度变化不大,且
其主要操作是查找，则采用顺序表；若 线性表的长度变化
较大,且其主要操作是插入、删除操作，则采用链表。
17
讨论 2,什么是指针？指针的作用？
指针 — 即变量的内存地址。 指针主要功能 有二：
①提供了一种快速访问数组单元的途径；
②使 C语言函数可以修改其调用的参数。
