1
三,顺序表操作的效率分析
时间效率分析,
算法时间主要耗费在 移动元素 的操作上，因此计算时
间复杂度的基本操作（最深层语句频度）
T(n)= O (移动 元素次数 )
而移动元素的个数取决于插入或删除元素的位臵,
注意,若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部要后移（特别慢）；
应当考虑在各种位臵插入（共 n+1种可能）的 平均 移动次数
才合理。
2
推导：
假定在每个元素位臵上插入 x的可能性都一样（即概
率 P相同），则应当这样来计算平均执行时间：
将所有位臵的执行时间相加，然后取平均。
若在首结点前插入，需要移动的元素最多，后移 n次；
若在 a1后面插入，要后移 n-1个元素，后移次数为 n-1;
……
若在 an-1后面插入，要后移 1个元素；
若在尾结点 an之后插入，则后移 0个元素；
所有可能的元素移动次数合计,
0+1+… +n = n(n+1)/2
共有多少种插入形式?—— 连头带尾有 n+1种 !
故插入时的平均移动次数为：
n(n+1)/2÷ （ n+1）＝ n/2≈ O(n)
3
同理可证：
顺序表删除一元素的时间效率为,
T(n)=(n-1)/2 ≈ O(n)
即 插入、删除算法的平均时间复杂度为
O(n)
4
简单回顾
线性表 顺序存储结构特点,逻辑关系上相邻的两个元
素在物理存储位臵上也相邻；
优点,可以随机存取表中任一元素，方便快捷；
缺点,在插入或删除某一元素时，需要移动大量元素 ;
需要预先确定数据元素的最大个数。
解决问题的思路,改用另一种线性存储方式：
链式存储结构
5
2.3 线性表的链式表示和实现
一、单链表的存储结构
二,单 链表的操作实现
三、链表的运算效率分析
6
１, 单链式及表示方法
(1)单链表,构成链表的结点只有一个指向直接后继结点
的指针 。 其结构特点,逻辑上相邻的数据元素在物理上
不一定相邻 。
如何实现？ 通过 指针 来实现！
让每个存储结点都包含两部分,数据域 和 指针域
指针域数据域 nextdata或样式：
数据域,存储
元素数值数据
指针域,存储直接后继的
存储位臵
设计思想：牺牲空间效率换取时间效率
一,单链表的存储结构
7
定义单链表结点的结构体如下,
typedef struct Node
{
DataType data;
struct Node *next;
}SLNode;
其中,data域 用来存放数据元素,next域 用来存放指向下
一个结点的指针。
8
例：请画出 26个英文字母表的链式存储结构。
该字母表在内存中链式存放的样式举例如下：
解,该字母表的逻辑结构为,（ a,b,…,y,z）
链表存放示意图如下：
a1head a2 /\an……
讨论 1,每个存储结点都包含两部分：数据域和 。
讨论 2,在单链表中，除了首元结点外，任一结点的存储位置
由 指示。其直接前驱结点的链域的值
指针域 (链域 )
9
1）结点,数据元素的存储映像。由数据域和指针域两部分组成；
2）链表,n 个结点由 指针链 组成一个链表。它是线性表的链
式存储映像, 称为线性表的链式存储结构 。
3）单链表、双链表、多链表、循环链表,
? 结点只有一个指针域的链表，称为 单链表 或 线性链表 ；
? 有两个指针域的链表，称为 双链表 （但未必是双向链表） ；
? 有多个指针域的链表，称为 多链表 ；
? 首尾相接的链表称为 循环链表 。
a1head a2 an……
循环链表 示意图：
head
(2) 与链式存储有关的术语：
10
4）头指针、头结点和首元结点的区别
头指针 头结点 首元结点
a1head a2 …info an ^
头指针 是指向链表中第一个结点（或为头结点、或为首元
结点）的指针；
头结点 是在链表的首元结点之前 附设 的一个结点；数据域
内只放空表标志和表长等信息，它不计入表长度。
首元结点 是指链表中存储线性表第一个数据元素 a０ 的结点。
示意图如下：
11
答：
讨论 1,在链表中设臵 头结点 有什么好处？
讨论 2,如何表示 空表？
头结点 即在链表的首元结点之前附设的一个结点，该结
点的 数据域可以为空，也可存放 表长度 等附加信息，其作用是
为了对链表进行操作时，可以对 空表、非空表 的情况以及对 首
元结点 进行 统一 处理，编程更方便。
答：
无头结点时，当头 指针 的值为 空 时表示空表；
^
头指针
无头结点
^
头指针 头结点
有头结点
有头结点时，当头 结点 的 指针域为空 时表示空表。
头结点不计入链
表长度！
12
一个线性表的逻辑结构为：
（ ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用
单链表 表示如下,请问其 头指针 的 值 是多少？
存储地址 数据域 指针域
1 LI 43
7 QIAN 13
13 SUN 1
19 WANG NULL
25 WU 37
31 ZHAO 7
37 ZHENG 19
43 ZHOU 25
答,头指针 是指向链
表中 第一个 结点的指
针，因此关键是要寻
找 第一个结点 的 地址 。
7ZHAO
H
31
称：头指针 H的值是 31
２、带头结点单链表和不带头结点单链表的比较
例：
13
上例链表的逻辑结构示意图有以下 两种形式,
①
ZHAO QIAN LISUN
ZHOU WU ZHENG /\WANG
H
②
ZHAO QIAN LISUN
ZHOU WU ZHENG /\WANG
H
区别,① 无头结点 ② 有头结点 头结点不计入 链表长度！
14
见课本 P38，对比带头结点的单链表的插入、
删除过程和不带带头结点的单链表的插入、删除
过程，可以得知：若设计的单链表 带头结点,则
无论是在第一个数据元素结点前插入还是在其他
数据元素结点前 插入都不会改变头指针的数值 。
若设计的单链表 不带头结点,则在第一个数据元
素结点前插入与在其他数据元素结点前 插入其算
法的处理方法不同 。在单链表中删除一个结点时
类似。因此,单链表一般构造成 带头结点 的单链
表 。
15
讨论, 链表的数据元素有 两个域,不再是简单数据
类型,编程 时该如何表示？
因每个结点至少有两个分量，且数据类型通常不一致，所
以要采用 结构 数据类型。
答：
以 26个字母的链表为例，每个结点都有两个分量：
字符型 指针型
设每个结点用变量 node表示，其指
针用 p表示，两个分量分别用 data和
*next表示，这两个分量如何赋值？
p *nextdata
node
方式 1,直接表示为 node.data＝ 'a'； node.next=q
方式 2,p指向结点首地址，然后 p->data='a'; p->next=q;
方式 3,p指向结点首地址，然后 (*p).data='a'； (*p).next＝ q
‘a’ ‘b’qp
16
设 p为指向链表的第 i个元素的指针,则第 i个元素的
数据域写为,指针域写为 。
练习：
p->data
ai的值
p->next
ai+1的地址
附 1,介绍 C的三个有用的库函数 /算符（都在 <stdlib.h> 中）：
sizeof(x)—— 计算变量 x的长度（字节数）；
malloc(m) — 开辟 m字节长度的地址空间，并返回这段空间
的首地址；
free(p) —— 释放指针 p所指变量的存储空间，即彻底删除
一个变量。
17
sizeof(x)—— 计算 x的长度
malloc(m) — 开 m字节 空间
free(p) —— 删除一个变量
问 1,自定义结构类型变量 node的长度 m是多少？
问 2,结构变量 node的首地址 (指针 p）是多少？
问 3,怎样删除结构变量 node？
*nextdata
node,长度为 m字节
p
m＝ sizeof(node) //单位是字节
p＝ (node*)malloc(m)
free(p) //只能借助 node的指针删除！
P->data=‘a’; p->next=q
18
② 对于指向结构类型的指针变量，可说明为：
SLNode *p,*q;
//或用 struct SLNode *p,*q;
//注：上面已经定义了 SLNode为用户自定义的 Node类型。
① 类型定义和变量说明可以合写为：
typedef struct Node //Node是自定义结构类型名称
{ DataType data; //定义数据域的变量名及其类型
struct Node *next; //定义指针域的变量名及其类型
}SLNode,*p; //SLNode是 Node结构类型的类型替代,
*p是指针型的 Node结构类型的替代
附 2,补充结构数据类型的 C表示法
19
编程训练建议：
简单,先建立一个整型数的单链表，然后统计单
链表中数据元素为 0的个数。
稍难,先建立一个字母单链表并输出到屏幕上，
再试着插入一个字母（例如将 I插入到 L之后）。
作业：
课本 P35 2-4,2-5,2-6,2-12
三,顺序表操作的效率分析
时间效率分析,
算法时间主要耗费在 移动元素 的操作上，因此计算时
间复杂度的基本操作（最深层语句频度）
T(n)= O (移动 元素次数 )
而移动元素的个数取决于插入或删除元素的位臵,
注意,若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部要后移（特别慢）；
应当考虑在各种位臵插入（共 n+1种可能）的 平均 移动次数
才合理。
2
推导：
假定在每个元素位臵上插入 x的可能性都一样（即概
率 P相同），则应当这样来计算平均执行时间：
将所有位臵的执行时间相加，然后取平均。
若在首结点前插入，需要移动的元素最多，后移 n次；
若在 a1后面插入，要后移 n-1个元素，后移次数为 n-1;
……
若在 an-1后面插入，要后移 1个元素；
若在尾结点 an之后插入，则后移 0个元素；
所有可能的元素移动次数合计,
0+1+… +n = n(n+1)/2
共有多少种插入形式?—— 连头带尾有 n+1种 !
故插入时的平均移动次数为：
n(n+1)/2÷ （ n+1）＝ n/2≈ O(n)
3
同理可证：
顺序表删除一元素的时间效率为,
T(n)=(n-1)/2 ≈ O(n)
即 插入、删除算法的平均时间复杂度为
O(n)
4
简单回顾
线性表 顺序存储结构特点,逻辑关系上相邻的两个元
素在物理存储位臵上也相邻；
优点,可以随机存取表中任一元素，方便快捷；
缺点,在插入或删除某一元素时，需要移动大量元素 ;
需要预先确定数据元素的最大个数。
解决问题的思路,改用另一种线性存储方式：
链式存储结构
5
2.3 线性表的链式表示和实现
一、单链表的存储结构
二,单 链表的操作实现
三、链表的运算效率分析
6
１, 单链式及表示方法
(1)单链表,构成链表的结点只有一个指向直接后继结点
的指针 。 其结构特点,逻辑上相邻的数据元素在物理上
不一定相邻 。
如何实现？ 通过 指针 来实现！
让每个存储结点都包含两部分,数据域 和 指针域
指针域数据域 nextdata或样式：
数据域,存储
元素数值数据
指针域,存储直接后继的
存储位臵
设计思想：牺牲空间效率换取时间效率
一,单链表的存储结构
7
定义单链表结点的结构体如下,
typedef struct Node
{
DataType data;
struct Node *next;
}SLNode;
其中,data域 用来存放数据元素,next域 用来存放指向下
一个结点的指针。
8
例：请画出 26个英文字母表的链式存储结构。
该字母表在内存中链式存放的样式举例如下：
解,该字母表的逻辑结构为,（ a,b,…,y,z）
链表存放示意图如下：
a1head a2 /\an……
讨论 1,每个存储结点都包含两部分：数据域和 。
讨论 2,在单链表中，除了首元结点外，任一结点的存储位置
由 指示。其直接前驱结点的链域的值
指针域 (链域 )
9
1）结点,数据元素的存储映像。由数据域和指针域两部分组成；
2）链表,n 个结点由 指针链 组成一个链表。它是线性表的链
式存储映像, 称为线性表的链式存储结构 。
3）单链表、双链表、多链表、循环链表,
? 结点只有一个指针域的链表，称为 单链表 或 线性链表 ；
? 有两个指针域的链表，称为 双链表 （但未必是双向链表） ；
? 有多个指针域的链表，称为 多链表 ；
? 首尾相接的链表称为 循环链表 。
a1head a2 an……
循环链表 示意图：
head
(2) 与链式存储有关的术语：
10
4）头指针、头结点和首元结点的区别
头指针 头结点 首元结点
a1head a2 …info an ^
头指针 是指向链表中第一个结点（或为头结点、或为首元
结点）的指针；
头结点 是在链表的首元结点之前 附设 的一个结点；数据域
内只放空表标志和表长等信息，它不计入表长度。
首元结点 是指链表中存储线性表第一个数据元素 a０ 的结点。
示意图如下：
11
答：
讨论 1,在链表中设臵 头结点 有什么好处？
讨论 2,如何表示 空表？
头结点 即在链表的首元结点之前附设的一个结点，该结
点的 数据域可以为空，也可存放 表长度 等附加信息，其作用是
为了对链表进行操作时，可以对 空表、非空表 的情况以及对 首
元结点 进行 统一 处理，编程更方便。
答：
无头结点时，当头 指针 的值为 空 时表示空表；
^
头指针
无头结点
^
头指针 头结点
有头结点
有头结点时，当头 结点 的 指针域为空 时表示空表。
头结点不计入链
表长度！
12
一个线性表的逻辑结构为：
（ ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用
单链表 表示如下,请问其 头指针 的 值 是多少？
存储地址 数据域 指针域
1 LI 43
7 QIAN 13
13 SUN 1
19 WANG NULL
25 WU 37
31 ZHAO 7
37 ZHENG 19
43 ZHOU 25
答,头指针 是指向链
表中 第一个 结点的指
针，因此关键是要寻
找 第一个结点 的 地址 。
7ZHAO
H
31
称：头指针 H的值是 31
２、带头结点单链表和不带头结点单链表的比较
例：
13
上例链表的逻辑结构示意图有以下 两种形式,
①
ZHAO QIAN LISUN
ZHOU WU ZHENG /\WANG
H
②
ZHAO QIAN LISUN
ZHOU WU ZHENG /\WANG
H
区别,① 无头结点 ② 有头结点 头结点不计入 链表长度！
14
见课本 P38，对比带头结点的单链表的插入、
删除过程和不带带头结点的单链表的插入、删除
过程，可以得知：若设计的单链表 带头结点,则
无论是在第一个数据元素结点前插入还是在其他
数据元素结点前 插入都不会改变头指针的数值 。
若设计的单链表 不带头结点,则在第一个数据元
素结点前插入与在其他数据元素结点前 插入其算
法的处理方法不同 。在单链表中删除一个结点时
类似。因此,单链表一般构造成 带头结点 的单链
表 。
15
讨论, 链表的数据元素有 两个域,不再是简单数据
类型,编程 时该如何表示？
因每个结点至少有两个分量，且数据类型通常不一致，所
以要采用 结构 数据类型。
答：
以 26个字母的链表为例，每个结点都有两个分量：
字符型 指针型
设每个结点用变量 node表示，其指
针用 p表示，两个分量分别用 data和
*next表示，这两个分量如何赋值？
p *nextdata
node
方式 1,直接表示为 node.data＝ 'a'； node.next=q
方式 2,p指向结点首地址，然后 p->data='a'; p->next=q;
方式 3,p指向结点首地址，然后 (*p).data='a'； (*p).next＝ q
‘a’ ‘b’qp
16
设 p为指向链表的第 i个元素的指针,则第 i个元素的
数据域写为,指针域写为 。
练习：
p->data
ai的值
p->next
ai+1的地址
附 1,介绍 C的三个有用的库函数 /算符（都在 <stdlib.h> 中）：
sizeof(x)—— 计算变量 x的长度（字节数）；
malloc(m) — 开辟 m字节长度的地址空间，并返回这段空间
的首地址；
free(p) —— 释放指针 p所指变量的存储空间，即彻底删除
一个变量。
17
sizeof(x)—— 计算 x的长度
malloc(m) — 开 m字节 空间
free(p) —— 删除一个变量
问 1,自定义结构类型变量 node的长度 m是多少？
问 2,结构变量 node的首地址 (指针 p）是多少？
问 3,怎样删除结构变量 node？
*nextdata
node,长度为 m字节
p
m＝ sizeof(node) //单位是字节
p＝ (node*)malloc(m)
free(p) //只能借助 node的指针删除！
P->data=‘a’; p->next=q
18
② 对于指向结构类型的指针变量，可说明为：
SLNode *p,*q;
//或用 struct SLNode *p,*q;
//注：上面已经定义了 SLNode为用户自定义的 Node类型。
① 类型定义和变量说明可以合写为：
typedef struct Node //Node是自定义结构类型名称
{ DataType data; //定义数据域的变量名及其类型
struct Node *next; //定义指针域的变量名及其类型
}SLNode,*p; //SLNode是 Node结构类型的类型替代,
*p是指针型的 Node结构类型的替代
附 2,补充结构数据类型的 C表示法
19
编程训练建议：
简单,先建立一个整型数的单链表，然后统计单
链表中数据元素为 0的个数。
稍难,先建立一个字母单链表并输出到屏幕上，
再试着插入一个字母（例如将 I插入到 L之后）。
作业：
课本 P35 2-4,2-5,2-6,2-12
