目 录
《数据结构》考研分析与指导（１）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第一章 绪论（４）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第二章 线性表（１１）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第三章 限定性线性表———栈和队列（３１）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第四章 串（５０）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第五章 数组和广义表（５９）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第六章 树与二叉树（６８）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第七章 图（９９）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第八章 查找（１２１）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
第九章 内部排序（１４８）G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21 G21
《数据结构》考研考点讲义
《数据结构》考研分析与指导
一、考试特点分析
１．在计算机专业硕士研究生入学全国统考中，作为专业课综合中的一个版块进行考察。在部分
自主命题院校硕士研究生入学考试中有单独作为一个科目进行考察，也有和其他一门或者两门科目
联合出题。
２．出题形式多为选择题和综合应用题
３．侧重于基础知识点及对知识点灵活运用的考核
二、复习方法
１．分清复习的阶段，把握复习进度
２．亲手做题，在练习中总结出题方向和方法，重视真题，透彻分析，揣摩出题人心理。只有做好一
定量的习题，才能帮助理解和牢固掌握考点。
３．讲过的知识点和题彻底掌握并及时回顾，不要学过忘过。
４．注重知识点之间的联系
５．不可忽视基础概念和知识体系。但是同时还要做到重点突出，突破难点，查缺补漏。
三、考试内容及分值分布：
章节重点难点必考点考试题型
１．绪论选择
２．线性表√√√选择、综合分析
３．栈和队列√√√选择、综合分析
４．串√√选择、填空
５．数组和广义表选择、填空
６．树√√√选择、综合分析
７．图√√√选择、综合分析
８．查找√√√选择、综合分析
９．排序√√√选择、综合分析
四、章节知识点及题型分析
章知识点题型题型易考点
１
数据结构的定义、逻辑结构和物理结构
的分类、算法的定义和算法性能的复
杂度
选择题
逻辑结构和物理结构的分类、算法的定义
和算法性能的复杂度
２
１．线性表的概念及运算
２．线性表的顺序存储
３．线性表的链式存储
４．一元多项式的表示及相加
选择题
１．线性表的定义和基本运算
２．线性表的顺序存储
３．线性表的链式存储
综合分析题１．线性表算法的设计
３
１．栈的定义和运算
２．栈的顺序存储和链式存储
３．栈的应用
１．队列的定义和运算
２．队列的顺序存储和链式存储
３．队列的应用
选择题
１．栈和队列的定义和运算
２．栈和队列的顺序存储和链式存储
综合分析题栈和队列的应用算法
４
１．串类型的定义
２．串的顺序存储和链式存储
３．串的模式匹配算法
选择题１．串的定义和存储
综合分析题２．串的模式匹配算法
５
１．数组的定义和运算
２．数组的顺序存储和实现
３．特殊矩阵的压缩存储
４．广义表
选择题
数组和广义表的定义和存储
矩阵的压缩存储
６
１．树的概念与定义
２．二叉树的定义和存储结构
３．二叉树的遍历与线索化
４．树、森林和二叉树的关系
５．哈夫曼树及其应用
选择题
树与二叉树的定义和存储结构
树、森林和二叉树的关系
综合分析题哈夫曼树及其应用
７
１．图的定义与图的存储结构
２．图的遍历
３．最小生成树
４．拓扑排序和关键路径
５．最短路径
选择题图的定义和存储结构
综合分析题
最小生成树
拓扑排序
关键路径
最短路径
续表
章知识点题型题型易考点
８
１．查找的基本概念
２．基于静态查找表的查找算法
３．基于动态查找表的查找算法
４．哈希表的查找
选择题查找的定义
综合分析题
顺序查找
折半查找
索引顺序表查找
二叉排序树
平衡二叉排序树
Ｂ树
哈希冲突的解决
９
①插入排序
②交换排序
③选择排序
④归并排序
⑤基数排序
综合分析题各种排序方法的应用
第一章 绪论
一、考试分析
考点重点与难点考试中常见题型复习思路与方法
数据、数据结构、算法的基
本概念，数据的逻辑结构和
物理结构
数据的四种逻辑结构和四
种物理结构、算法复杂度
选择题、
综合分析题
１．熟记概念；
２．理解并熟练掌握数据的逻辑结构
和物理结构，以及算法复杂度。
二、考点讲解
数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作
等等的学科。
１．基本概念
·数据（Ｄａｔａ）：
对客观事物的符号描述，能输入到计算机中并被计算机程序处理的符号的总称；
能被计算机识别、存储和加工处理的信息的载体。
例，数字：自然数、整数
字母：ａ～ｚ，单词
图像
视频、音频信号等
表格
·数据元素（ＤａｔａＥｌｅｍｅｎｔ）：
数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和
处理。
例，“对弈树”中的一个格局
书目信息中的一条书目
数据项：一个数据元素可由若干个数据项组成。
例，一条书目信息是由书名、作者名、分类等多个数据项组成的数据项是数据的不可分割的最小
单位。
例如：有一个学生表如下所示。这个表中的数据元素是学生记录，每个数据元素由四个数据项
（即学号、姓别、性别和班号）组成。
学号姓名性别班号
１张斌男９９０１
８刘丽女９９０２
３４李英女９９０１
２０陈华男９９０２
１２王奇男９９０１
２６董强男９９０２
５王萍女９９０１
·数据结构（ＤａｔａＳｔｒｕｃｔｕｒｅ）
数据结构是指相互之间存在一种或多种特定关系的数据元素
集合
结构（Ｓｔｒｕｃｔｕｒｅ）：数据元素相互之间的关系。
在形式上可用二元组表示：
Ｄａｔａ＿Ｓｔｒｕｃｔｕｒｅ＝（Ｄ，Ｓ）
Ｄ：数据元素的有限集
Ｓ：Ｄ上关系的有限集
Ｄ＝｛ｋ
ｉ
｜１≤ｉ≤ｎ，ｎ≥０｝
·ｋ
ｉ
表示集合Ｄ中的第ｉ个结点或数据元素
·ｎ为Ｄ中结点的个数
·若ｎ＝０，则Ｄ是一个空集，表示Ｄ无结构可言，有时也可以认为它具有任意的结构
Ｓ＝｛ｒ
ｊ
｜１≤ｊ≤ｍ，ｍ≥０｝
·ｒ
ｊ
表示集合Ｓ中的第ｊ个二元关系（简称关系）
·ｍ为Ｓ中关系的个数
·若ｍ＝０，则Ｓ是一个空集，表明集合Ｄ中的元结点间不存在任何关系，彼此是独立的
Ｄ上的一个关系ｒ是序偶的集合，对于ｒ中的任一序偶＜ｘ，ｙ＞（ｘ，ｙ∈Ｄ），我们称序偶的第一结
点为第二结点的直接前驱结点（通常简称前驱结点），称第二结点为第一结点的直接后继结点（通常简
称后继结点）。如在＜ｘ，ｙ＞的序偶中，ｘ为ｙ的前驱结点，而ｙ为ｘ的后继结点。
若某个结点没有前驱，则称该结点为开始结点；若某个结点没有后继，则称该结点为终端结点；除
此之外的节点称为内部节点。
“尖括号”表示有向关系，“圆括号”表示无向关系。
例如：用二元组表示学生表，学生表中共有７个结点，依次用ｋ
１
～ｋ
７
表示，则对应的二元组表
示为：
Ｄａｔａ＿Ｓｔｒｕｃｔｕｒｅ＝（Ｄ，Ｓ）
其中：
Ｄ＝｛ｋ
１
，ｋ
２
，ｋ
３
，ｋ
４
，ｋ
５
，ｋ
６
，ｋ
７
｝
Ｓ＝｛＜ｋ
１
，ｋ
２
＞，＜ｋ
２
，ｋ
３
＞，＜ｋ
３
，ｋ
４
＞，＜ｋ
４
，ｋ
５
＞，＜ｋ
５
，ｋ
６
＞，＜ｋ
６
，ｋ
７
＞｝
逻辑结构图：可以将数据结构用图形形象地表示出来，图形中的每个结点对应着一个数据元素，
两结点之间的连线对应着关系中的一个序偶。
上述“学生表”数据结构用下图的图形表示。
２．数据结构的内容
·逻辑结构
数据元素之间的关系
逻辑结构可看作是从具体问题抽象出来的数学模型
按照逻辑关系的不同特性分类：
逻辑结构类型的分类
（１）线性结构
所谓线性结构，该结构中的结点之间存在一对一的关系。
其特点是：开始结点和终端结点都是惟一的，除了开始结点和终端结点以外，其余结点都有且仅
有一个前驱结点，有且仅有一个后继结点。
顺序表就是典型的线性结构。
（２）非线性结构
所谓非线性结构，该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构
和图形结构两类。
所谓树形结构，该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱，
—６—
但可以有多个后继，可以有多个终端结点。非线性结构树形结构简称为树。
ＵＮＩＸ文件系统的系统结构图
所谓图形结构，该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个
数都可以是任意的。因此，可能没有开始结点和终端结点，也可能有多个开始结点、多个终端结点。
图形结构简称为图。
·存储结构（物理结构）
逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系
的表示。
顺序存储结构
非顺序存储结构（链式存储结构）
索引存储结构
散列存储结构
例如：用顺序存储法和链式存储法表示下面的学生表。
学号姓名性别班号
１张斌男９９０１
８刘丽女９９０２
３４李英女９９０１
２０陈华男９９０２
１２王奇男９９０１
２６董强男９９０２
５王萍女９９０１
用顺序存储法存放学生表的结构体定义为：
ｓｔｒｕｃｔ Ｓｔｕｄ｛
ｉｎｔｎｏ； ／学号／
ｃｈａｒｎａｍｅ［８］； ／姓名／
ｃｈａｒｓｅｘ［２］； ／性别／
ｃｈａｒｃｌａｓｓ［４］； ／班号／
｝ Ｓｔｕｄｓ［７］＝｛
｛１，“张斌”，“男”，“９９０１”｝，
…，
｛５，＂王萍＂，＂女＂，＂９９０１＂｝
｝；
结构体数组Ｓｔｕｄｓ各元素在内存中按顺序存放，即第ｉ（１≤ｉ≤６）个学生对应的元素Ｓｔｕｄｓ［ｉ］存放
在第ｉ＋１个学生对应的元素Ｓｔｕｄｓ［ｉ＋１］之前，Ｓｔｕｄｓ［ｉ＋１］正好在Ｓｔｕｄｓ［ｉ］之后。
用链式存储法存放学生表的结构体定义为：
ｔｙｐｅｄｅｆｓｔｒｕｃｔｎｏｄｅ
｛
ｉｎｔｎｏ； ／学号／
ｃｈａｒｎａｍｅ［８］； ／姓名／
ｃｈａｒｓｅｘ［２］； ／性别／
ｃｈａｒｃｌａｓｓ［４］； ／班号／
ｓｔｒｕｃｔｎｏｄｅｎｅｘｔ；／指向下个学生的指针／
｝ＳｔｕｄＴｙｐｅ；
学生表构成的链表如下图所示。其中的ｈｅａｄ为第一个数据元素的指针。
链式存储法的缺点：
·存储空间占用大
·无法随机访问
链式存储法的优点：
·便于修改（插入、删除、移动）
３．算法
（１）算法（Ａｌｇｏｒｉｔｈｍ）的定义
Ａｌｇｏｒｉｔｈｍｉｓａｆｉｎｉｔｅｓｅｔｏｆｒｕｌｅｓｗｈｉｃｈｇｉｖｅｓａｓｅｑｕｅｎｃｅｏｆｏｐｅｒａｔｉｏｎｆｏｒｓｏｌｖｉｎｇａｓｐｅｃｉｆｉｃｔｙｐｅｏｆｐｒｏｂ
ｌｅｍ．（算法是规则的有限集合，是为解决特定问题而规定的一系列操作。）
（２）算法的特性
①有穷性：有限步骤之内正常结束，不能形成无穷循环。
②确定性：算法中的每一个步骤必须有确定含义，无二义性。
③可行性：原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成。
④输入：有多个或０个输入。
⑤输出：至少有一个或多个输出。
在算法的五大特性中，最基本的是有限性、确定性和可行性。
４．算法描述的工具
描述算法的方法
·自然语言：优点———简单。缺点———有歧异，表达复杂思想不明晰，不能和实现方式很好结合
·高级程序设计语言，如Ｐａｓｃａｌ，Ｃ／Ｃ＋＋，Ｊａｖａ等。优点———克服了自然语言的缺点，可直接执
行。缺点———对部分问题的描述比较烦杂，嗦
·类语言。和高级程序设计语言类似，但是对其中一些比较烦杂的部分进行和简化（原因：算
法主要目的是为了清晰的表述思想）
举例：两个数据ａ，ｂ交换空间
自然语言：交换ａ，ｂ的存储空间；
高级语言：｛ｘ＝ａ；ａ＝ｂ；ｂ＝ｘ；｝
类语言：ａｂ；／／交换空间
５．对算法作性能评价
衡量算法效率的方法主要有两大类：
·事后统计：利用计算机的时钟；
·事前分析估算：用高级语言编写的程序运行的时间主要取决于如下因素：
算法；
问题规模；
使用语言：级别越高，效率越低；
编译程序；
机器；
通常，从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次
数作为算法执行的时间度量。
基本操作重复执行的次数分别为１，ｎ，ｎ
２
《数据结构》考研考点精讲及复习思路
设算法的问题规模为ｎ；
频度：语句重复执行的次数称为该语句的频度，记ｆ（ｎ）。
对算法各基本操作的频度求和，便可得算法的时间复杂度。但实际中我们所关心的主要是一个
算法所花时间的数量级，即取算法各基本操作的最大频度数量级。
时间复杂度：算法执行时间度量，记Ｔ（ｎ）＝Ｏ（ｍａｘｌｅｖｅｌ（ｆ（ｎ）））。
ｆ（ｎ）＝１＋ｎ＋ｎ
２
＋ｎ
３
Ｔ（ｎ）＝Ｏ（ｎ
３
）
Ｏ的数学定义：
若Ｔ（ｎ）和ｆ（ｎ）是定义在正整数集合上的两个函数，则如果存在正常数Ｃ和ｎ
０
，使得当ｎ≥ｎ
０
时，
总满足０≤Ｔ（ｎ）≤Ｃｆ（ｎ），则记做Ｔ（ｎ）＝Ｏ（ｆ（ｎ））
也就是只求出Ｔ（ｎ）的最高阶（数量级），忽略其低阶项和常系数，这样既可简化Ｔ（ｎ）的计算，又
能比较客观地反映出当ｎ很大时，算法的时间性能。
６．算法的空间复杂度
关于算法的存储空间需求，类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空
间的量度，记作：
Ｓ（ｎ）＝Ｏ（ｆ（ｎ））
三、真题举例
１．从逻辑结构上可以把数据结构分为（ ）两大类．【武汉交通科技大学】
Ａ．动态结构、静态结构
Ｂ．顺序结构、链式结构
Ｃ．线性结构、非线性结构
Ｄ．初等结构、构造型结构
２．在下面的程序段中，对ｘ的赋值语句的频度为（ ）【北京工商大学】
ＦＯＲｉ：＝１ＴＯｎＤＯ
ＦＯＲｊ：＝１ＴＯｎＤＯ
ｘ：＝ｘ＋１；
Ａ．Ｏ（２ｎ） Ｂ．Ｏ（ｎ） Ｃ．Ｏ（ｎ
２
） Ｄ．Ｏ（ｌｏｇ
２
ｎ）
３．以下属于逻辑结构的是（ ）【西安电子科技大学】
Ａ．顺序表Ｂ．哈希表Ｃ．有序表Ｄ．单链表
四、本讲小结
本章讲解了数据、数据结构、算法的基本概念，数据的逻辑结构和物理结构。
重点讲解了数据的４种逻辑结构和４种物理结构，以及算法复杂度。
第二章 线性表
目录分析
２．１ 线性表的概念及运算［一般了解］
２．２ 线性表的顺序存储［熟练掌握］
２．３ 线性表的链式存储［熟练掌握］
第１讲
一、考试分析
考点重点与难点考试中常见题型复习思路与方法
线性表的基本概念和常用
操作、线性表的顺序存储
方式。
线性表在常用操作、线性表
的顺序存储。
选择题、
综合分析题
１．熟记概念；
２．理解并熟练掌握线性表的顺序存
储方式和线性表的基本运算在现行
存储方式下的实现方法。
二、考点讲解
２．１ 线性表的概念及运算
１．线性表的定义
一个线性表是具有ｎ个数据元素的有限序列。记为（ａ
１
，…，ａ
ｉ－１
，ａ
ｉ
，ａ
ｉ＋１
，…，ａ
ｎ
）
２．线性表的长度
线性表中元素的个数ｎ（ｎ＞＝０），ｎ＝０时，称为空表。
３．位序
ａ
ｉ
是第ｉ个元素，称ｉ为数据元素ａ
ｉ
在线性表中的位序。
４．线性表的逻辑结构
例子：
·英文字母表（Ａ，Ｂ，…，Ｚ）；
·车辆登记表。
５．线性表的特点
·同一性：线性表由同类数据元素组成，每一个ａ
ｉ
必须属于同一数据对象。
·有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。
·有序性：线性表中相邻数据元素之间存在着序偶关系＜ａ
ｉ
，ａ
ｉ＋１
＞。
６．线性表的基本运算
·初始化ＩｎｉｔＬｉｓｔ（＆Ｌ）建立一个空表。
·求表长ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回线性表的长度。
·读表元素ＧｅｔＥｌｅｍ（Ｌ，ｉ，＆ｅ）用ｅ返回Ｌ中第ｉ个数据元素的值。
·定位ＬｏｃａｔｅＥｌｅｍ（Ｌ，ｅ，ｃｏｍｐａｒｅ（））返回满足关系的数据元素的位序。
·插入ＬｉｓｔＩｎｓｅｒｔ（＆Ｌ，ｉ，ｅ）在Ｌ中第ｉ个位置之前插入新的数据元素ｅ，线性表的长度增１。
·删除ＬｉｓｔＤｅｌｅｔｅ（＆Ｌ，ｉ，＆ｅ）删除Ｌ的第ｉ个位置上的数据元素ｅ，线性表的长度减１。
·输出ＬｉｓｔＤｉｓｐｌａｙ（Ｌ）按前后次序输出线性表的所有元素。
练习１：两个线性表ＬＡ和ＬＢ分别表示两个集合Ａ和Ｂ，现求一个新的集合Ａ＝Ａ∪Ｂ。
ｖｏｉｄｕｎｉｏｎ（Ｌｉｓｔ＆Ｌａ，ＬｉｓｔＬｂ）
｛
Ｌａ＿ｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）；
Ｌｂ＿ｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）；
ｆｏｒ（ｉ＝１；ｉ＜＝Ｌｂ＿ｌｅｎ；ｉ＋＋）｛
ＧｅｔＥｌｅｍ（Ｌｂ，ｉ，ｅ）；
ｉｆ（！ＬｏｃａｔｅＥｌｅｍ（Ｌａ，ｅ，ｅｑｕａｌ））
ＬｉｓｔＩｎｓｅｒｔ（Ｌａ，＋＋Ｌａ＿ｌｅｎ，ｅ）；
｝
｝
Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）×ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ））
练习２：
两个线性表ＬＡ和ＬＢ中的数据元素按值非递减有序排列，现将ＬＡ和ＬＢ归并为一个新的线性
表，ＬＣ中的数据元素仍按值非递减有序排列。
ＬＡ＝（３，５，８，１１）
ＬＢ＝（２，６，８，９，１１，１５，２０）
ＬＣ＝（２，３，５，６，８，８，９，１１，１１，１５，２０）
ｃ＝
ａ，当ａG21ｂ时
ｂ，当ａ＞ｂ
{
时
ｖｏｉｄＭｅｒｇｅＬｉｓｔ（ＬｉｓｔＬａ，ＬｉｓｔＬｂ，Ｌｉｓｔ＆Ｌｃ）
｛ＩｎｉｔＬｉｓｔ（Ｌｃ）；
Ｌａ＿ｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）； Ｌｂ＿ｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）；
ｉ＝ｊ＝１；ｋ＝０；
ｗｈｉｌｅ（（ｉ＜＝Ｌａ＿ｌｅｎ）＆＆（ｊ＜＝Ｌｂ＿ｌｅｎ））｛
ＧｅｔＥｌｅｍ（Ｌａ，ｉ，ａ）；ＧｅｔＥｌｅｍ（Ｌｂ，ｊ，ｂ）；
ｉｆ（ａ＜＝ｂ）｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；＋＋ｉ；｝
ｅｌｓｅ｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；＋＋ｊ；｝
｝
ｗｈｉｌｅ（ｉ＜＝Ｌａ＿ｌｅｎ）｛
ＧｅｔＥｌｅｍ（Ｌａ，ｉ＋＋，ａ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；｝
ｗｈｉｌｅ（ｊ＜＝Ｌｂ＿ｌｅｎ）｛
ＧｅｔＥｌｅｍ（Ｌｂ，ｊ＋＋，ｂ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；｝
｝
Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）＋ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ））
例，Ｌａ＝（３，５，８），Ｌｂ＝（２，６，８，９，１５）
构造Ｌｃ＝（２，３，５，６，８，８，９，１５）
首先，Ｌａ＿ｌｅｎ＝３；Ｌｂ＿ｌｅｎ＝５；
２．２ 线性表的顺序表示和实现
１．顺序表：
按顺序存储方式构造的线性表。
《数据结构》考研考点精讲及复习思路
假设线性表中有ｎ个元素，每个元素占ｋ个单元，第一个元素的地址为ｌｏｃ（ａ
１
），则可以通过如下
公式计算出第ｉ个元素的地址ｌｏｃ（ａ
ｉ
）：
ｌｏｃ（ａ
ｉ
）＝ｌｏｃ（ａ
１
）＋（ｉ－１）×ｋ
其中ｌｏｃ（ａ
１
）称为基地址。
２．顺序表的特点：
·逻辑结构中相邻的数据元素在存储结构中仍然相邻。
·线性表的顺序存储结构是一种随机存取的存储结构。
３．顺序表的描述：
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ
｛
ＥｌｅｍＴｙｐｅ ｅｌｅｍ；
ｉｎｔ ｌｅｎｇｔｈ； ／／当前长度
ｉｎｔ ｌｉｓｔｓｉｚｅ； ／／分配的存储容量
｝ＳｑＬｉｓｔ；
／／ＥｌｅｍＴｙｐｅｅｌｅｍ［ＭＡＸＳＩＺＥ］；
ｔｙｐｅｄｅｆ ＃ＥｌｅｍＴｙｐｅ； ＃为根据具体问题确定的数据类型
ｔｙｐｅｄｅｆ ｉｎｔ Ｓｔａｔｕｓ；
４．顺序表上基本运算的实现
·初始化ＳｔａｔｕｓＩｎｉｔＬｉｓｔ＿Ｓｑ（ＳｑＬｉｓｔ＆Ｌ）
｛
Ｌ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ｍａｌｌｏｃ（ＬＩＳＴ＿ＩＮＩＴ＿ＳＩＺＥ
ｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））；
ｉｆ（！Ｌ．ｅｌｅｍ）
ｅｘｉｔ（ＯＶＥＲＦＬＯＷ）；
Ｌ．ｌｅｎｇｔｈ＝０；
Ｌ．ｌｉｓｔｓｉｚｅ＝ＬＩＳＴ＿ＩＮＩＴ＿ＳＩＺＥ；
ｒｅｔｕｒｎＯＫ；
｝
Ｌ．ｅｌｅｍ＝ｎｅｗＥｌｅｍＴｙｐｅ［ＬＩＳＴ＿ＩＮＩＴ＿ＳＩＺＥ］；
顺序表的插入：在表中第４个元素之前插入“２１“。
顺序表中插入元素
·插入ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔ＿Ｓｑ（ＳｑＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅｅ）
｛
ｉｆ（（ｉ＜１）｜｜（ｉ＞Ｌ．ｌｅｎｇｔｈ＋１））
ｒｅｔｕｒｎＥＲＲＯＲ；
ｉｆ（Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ）｛
ｒｅａｌｌｏｃ（…）；…．；／／越界处理；
｝
ｑ＝＆（Ｌ．ｅｌｅｍ［ｉ－１］）；
ｆｏｒ（ｐ＝＆（Ｌ．ｅｌｅｍ［Ｌ．ｌｅｎｇｔｈ－１］；ｐ＞＝ｑ；－－ｐ）
（ｐ＋１）＝ｐ；
ｑ＝ｅ；
＋＋Ｌ．ｌｅｎｇｔｈ；
ｒｅｔｕｒｎＯＫ；
｝
／／越界处理
ｉｆ （Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ） ｛
ｎｅｗｂａｓｅ＝（ＥｌｅｍＴｙｐｅ）ｒｅａｌｌｏｃ（Ｌ．ｅｌｅｍ，
（Ｌ．ｌｉｓｔｓｉｚｅ＋ＬＩＳＴＩＮＣＲＥＭＥＮＴ）ｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））；
ｉｆ （！ｎｅｗｂａｓｅ） ｅｘｉｔ（ＯＶＥＲＦＬＯＷ）；
Ｌ．ｅｌｅｍ＝ｎｅｗｂａｓｅ；
Ｌ．ｌｉｓｔｓｉｚｅ＋＝ＬＩＳＴＩＮＣＲＥＭＥＮＴ；
算法时间复杂度：
时间主要花在移动元素上，而移动元素的个数取决于插入元素位置。
ｉ＝１，需移动ｎ个元素；
ｉ＝ｎ＋１，需移动０个元素；
ｉ＝ｉ，需移动ｎ－ｉ＋１个元素；
假设ｐ
ｉ
是在第ｉ个元素之前插入一个新元素的概率
则长度为ｎ的线性表中插入一个元素所需移动元素次数的期望Ｅ
ｉｓ
＝
∑
ｎ＋１
ｉ＝１
ｐ
ｉ
（ｎ－ｉ＋１）。
设在任何位置插入元素等概率，ｐ
ｉ
＝
１
ｎ＋１
。
Ｅ
ｉｓ
＝
１
ｎ＋１
∑
ｎ＋１
ｉ＝１
（ｎ－ｉ＋１）＝
ｎ
２
Ｏ（ｎ）
·顺序表的归并，表中元素非递减排列。
ｖｏｉｄＭｅｒｇｅＬｉｓｔ＿Ｓｑ（ＳｑＬｉｓｔＬａ，ＳｑＬｉｓｔＬｂ，ＳｑＬｉｓｔ＆Ｌｃ）
｛
ｐａ＝Ｌａ．ｅｌｅｍ；ｐｂ＝Ｌｂ．ｅｌｅｍ；
Ｌｃ．ｌｉｓｔｓｉｚｅ＝Ｌｃ．ｌｅｎｇｔｈ＝Ｌａ．ｌｅｎｇｔｈ＋Ｌｂ．ｌｅｎｇｔｈ；
ｐｃ＝Ｌｃ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ｍａｌｌｏｃ（…）；
ｉｆ（！Ｌｃ．ｅｌｅｍ）ｅｘｉｔ（ＯＶＥＲＦＬＯＷ）；
ｐａ＿ｌａｓｔ＝Ｌａ．ｅｌｅｍ＋Ｌａ．ｌｅｎｇｔｈ－１；ｐｂ＿ｌａｓｔ＝Ｌｂ．ｅｌｅｍ＋Ｌｂ．ｌｅｎｇｔｈ－１；
ｗｈｉｌｅ（（ｐａ＜＝ｐａ＿ｌａｓｔ）＆＆ｐｂ＜＝ｐｂ＿ｌａｓｔ））｛
ｉｆ（ｐａ＜＝ｐｂ） ｐｃ＋＋＝ｐａ＋＋；
ｅｌｓｅ ｐｃ＋＋＝ｐｂ＋＋；｝
ｗｈｉｌｅ（ｐａ＜＝ｐａ＿ｌａｓｔ）ｐｃ＋＋＝ｐａ＋＋；
ｗｈｉｌｅ（ｐｂ＜＝ｐｂ＿ｌａｓｔ）ｐｃ＋＋＝ｐｂ＋＋；
｝
顺序表的基础要点：
１．无需为表示元素间的逻辑关系而增加额外的存储空间，存储密度大（１００％）；
２．可随机存取表中的任一元素。
３．插入或删除一个元素时，需平均移动表的一半元素，具体的个数与该元素的位置有关，在等概
率情况下，插入ｎ／２，删除（ｎ－１）／２；Ｏ（ｎ）
４．存储分配只能预先进行分配。
５．将两个各有ｎ个元素的有序表归并为一个有序表，其最少的比较次数是：ｎ
练习２．２９
已知Ａ、Ｂ、Ｃ为三个元素值递增有序的顺序表，现要求对Ａ作如下运算，删去那些既在Ｂ中出现
又在Ｃ中出现的元素，实现上述算法并分析时间复杂度。
Ａ＝Ａ－（Ｂ∩Ｃ）
Ａ＝（１，２，６，６，８，９，１０，１０，１１，１５）
Ｂ＝（１，２，６，６，７，９，１０，１５）
Ｃ＝（３，４，６，７，７，９，９，９，１０，１２）
Ａ＝（１，２，８，１１，１５）
分析：
·先从Ｂ和Ｃ中找出公有元素，记为ｓａｍｅ；
·Ａ中从当前位置开始，凡小于ｓａｍｅ的元素均保留（存到新的位置），等于ｓａｍｅ的跳过；
·大于ｓａｍｅ时就再找下一个ｓａｍｅ．
ｖｏｉｄＳｑＬｉｓｔ＿Ｉｎｔｅｒｓｅｃｔ＿Ｄｅｌｅｔｅ（ＳｑＬｉｓｔ＆Ａ，ＳｑＬｉｓｔＢ，ＳｑＬｉｓｔＣ）
｛ ｐａ＝Ａ．ｅｌｅｍ；ｐａ＿ｌａｓｔ；ｐｂ；ｐｂ＿ｌａｓｔ；ｐｃ；ｐｃ＿ｌａｓｔ；ｐ０；
ｗｈｉｌｅ（（ｐａ＜＝ｐａ＿ｌａｓｔ）＆＆（ｐｂ＜＝ｐｂ＿ｌａｓｔ）＆＆（ｐｃ＜＝ｐｃ＿ｌａｓｔ））｛
ｉｆ（ｐｂ＜ｐｃ） ｐｂ＋＋；
ｅｌｓｅｉｆ（ｐｂ＞ｐｃ） ｐｃ＋＋；
ｅｌｓｅ｛
ｓａｍｅ＝ｐｂ；
ｗｈｉｌｅ（（ｐｂ＜＝ｐｂ＿ｌａｓｔ）＆＆（ｐｂ＝＝ｓａｍｅ）） ｐｂ＋＋；
ｗｈｉｌｅ（（ｐｃ＜＝ｐｃ＿ｌａｓｔ）＆＆（ｐｃ＝＝ｓａｍｅ）） ｐｃ＋＋；
ｗｈｉｌｅ（（ｐａ＜＝ｐａ＿ｌａｓｔ）＆＆（ｐａ＜ｓａｍｅ））
ｐ０＋＋＝ｐａ＋＋；
ｗｈｉｌｅ（（ｐａ＜＝ｐａ＿ｌａｓｔ）＆＆（ｐａ＝＝ｓａｍｅ）） ｐａ＋＋；
｝／／ｅｌｓｅ
｝／／ｗｈｉｌｅ
ｗｈｉｌｅ（ｐａ＜＝ｐａ＿ｌａｓｔ）
ｐ０＋＋＝ｐａ＋＋；
Ａ．ｌｅｎｇｔｈ＝ｐ０G22Ａ．ｅｌｅｍ；
｝
三、真题举例
１．下面关于线性表的叙述中，错误的是哪一个？（ ）【北方交通大学】
Ａ．线性表采用顺序存储，必须占用一片连续的存储单元。
Ｂ．线性表采用顺序存储，便于进行插入和删除操作。
Ｃ．线性表采用链接存储，不必占用一片连续的存储单元。
Ｄ．线性表采用链接存储，便于插入和删除操作。
２．若长度为ｎ的线性表采用顺序存储结构，在其第ｉ个位置插入一个新元素的算法的时间复杂度
为（ ）（１＜＝ｉ＜＝ｎ＋１）。【北京航空航天大学】
Ａ．Ｏ（０）Ｂ．Ｏ（１）Ｃ．Ｏ（ｎ）Ｄ．Ｏ（ｎ
２
）
四、本讲小结
本讲主要讲解了：线性表的基本概念和常用操作、线性表的顺序存储方式。
常考题型：选择题，综合分析题。
—７１—
应试方法：理解并熟练掌握线性表的顺序存储方式和线性表的基本运算在现行存储方式下在实
现方法。
第２讲
一、考试分析
考点重点与难点考试中常见题型复习思路与方法
线性表的链式存储结构。
选择题、
综合分析题
理解并熟练掌握线性表的链式存储
方式和线性表的基本运算在链式存
储方式下的实现方法。
二、考点讲解
２．３ 线性表的链式表示和实现
线性表链式存储结构的特点：
·用一组任意的存储单元存储线性表的元素，不要求逻辑上相邻的元素在物理位置上也相邻；
·插入删除时不需移动大量元素；
·失去顺序表可随机存取的优点。
例，整数数组ａ［３］＝｛３，５，６｝
１．线性链表（单链表）
·结点：数据元素的存储映象。
数据域用来存储结点的值；
指针域用来存储数据元素的直接后继的地址（或位置）。
·头指针
指示链表中第一个结点的存储位置，单链表可由头指针唯一确定。
·单链表的存储映象
·头结点
在链表的第一个结点之前附设一个结点，头指针指向头结点。设置头结点的目的是统一空表与
非空表的操作，简化链表操作的实现。
·首元结点
链表中存储线性表中第一个数据元素的结点。
·链表存储结构描述：
ＴｙｐｅｄｅｆｓｔｒｕｃｔＬＮｏｄｅ
｝ＬＮｏｄｅ， ＬｉｎｋＬｉｓｔ；
单链表基本运算实现
（１）初始化线性表ＩｎｉｔＬｉｓｔ（Ｌ）
该运算建立一个空的单链表，即创建一个头结点。
ｖｏｉｄＩｎｉｔＬｉｓｔ（ＬｉｎｋＬｉｓｔ＆Ｌ
｛
ＥｌｅｍＴｙｐｅｄａｔａ；
ｓｔｒｕｃｔＬＮｏｄｅ ｎｅｘｔ；
）
｛
Ｌ＝（ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
／创建头结点／
Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；
｝
（２）销毁线性表ＤｅｓｔｒｏｙＬｉｓｔ（Ｌ）
释放单链表Ｌ占用的内存空间。即逐一释放全部结点的空间。
ｖｏｉｄＤｅｓｔｒｏｙＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）
｛ＬｉｎｋＬｉｓｔｐ＝Ｌ，ｑ＝ｐ－＞ｎｅｘｔ；
ｗｈｉｌｅ（ｑ！＝ＮＵＬＬ）
｛ ｆｒｅｅ（ｐ）；
ｐ＝ｑ；ｑ＝ｐ－＞ｎｅｘｔ；
｝
ｆｒｅｅ（ｐ）；
｝
（３）判线性表是否为空表ＬｉｓｔＥｍｐｔｙ（Ｌ）
若单链表Ｌ没有数据结点，则返回真，否则返回假。
ｉｎｔＬｉｓｔＥｍｐｔｙ（ＬｉｎｋＬｉｓｔＬ）
｛
ｒｅｔｕｒｎ（Ｌ－＞ｎｅｘｔ＝＝ＮＵＬＬ）；
｝
（４）求线性表的长度ＬｉｓｔＬｅｎｇｔｈ（Ｌ）
返回单链表Ｌ中数据结点的个数。
ｉｎｔＬｉｓｔＬｅｎｇｔｈ（ＬｉｎｋＬｉｓｔＬ）
｛ＬｉｎｋＬｉｓｔｐ＝Ｌ；ｉｎｔｉ＝０；
ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ！＝ＮＵＬＬ）
｛ ｉ＋＋；
ｐ＝ｐ－＞ｎｅｘｔ；
｝
ｒｅｔｕｒｎ（ｉ）；
｝
（５）输出线性表ＤｉｓｐＬｉｓｔ（Ｌ）
逐一扫描单链表Ｌ的每个数据结点，并显示各结点的ｄａｔａ域值。
ｖｏｉｄＤｉｓｐＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）
｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；
ｗｈｉｌｅ（ｐ！＝ＮＵＬＬ）
｛ ｐｒｉｎｔｆ（＂％ｃ＂，ｐ－＞ｄａｔａ）；
ｐ＝ｐ－＞ｎｅｘｔ；
｝
ｐｒｉｎｔｆ（＂＼ｎ＂）；
｝
（６）取表元素
ＳｔａｔｕｓＧｅｔＥｌｅｍ（ＬｉｎｋＬｉｓｔＬ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ＆ｅ）
—０２—
｛
ｐ＝Ｌ－＞ｎｅｘｔ； ｊ＝１；
ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ）｛
ｐ＝ｐ－＞ｎｅｘｔ； ＋＋ｊ；
｝
ｉｆ（！ｐ｜｜ｊ＞ｉ）ｒｅｔｕｒｎＥＲＲＯＲ；
ｅ＝ｐ－＞ｄａｔａ；
ｒｅｔｕｒｎＯＫ；
｝
例，取第ｉ＝３个元素。
ｅ＝ｐ－＞ｄａｔａ＝Ｓｕｎ
时间复杂度：Ｏ（ｎ）
·在单链表第ｉ个结点前插入一个结点的过程
（７）插入
ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅｅ）
｛
ｐ＝Ｌ；ｊ＝０；
ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝
ｉｆ（！ｐ｜｜ｊ＞ｉ－１） ｒｅｔｕｒｎＥＲＲＯＲ；
ｓ＝ （ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
ｓ－＞ｄａｔａ＝ｅ；
ｓ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；①
ｐ－＞ｎｅｘｔ＝ｓ；②
ｒｅｔｕｒｎＯＫ；
｝
·删除单链表的第ｉ个结点的过程
（８）删除
ＳｔａｔｕｓＬｉｓｔＤｅｌｅｔｅ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ＆ｅ）
｛
ｐ＝Ｌ；ｊ＝０；
ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝
ｉｆ（！（ｐ－＞ｎｅｘｔ）｜｜ｊ＞ｉ－１） ｒｅｔｕｒｎＥＲＲＯＲ；
ｒ＝ｐ－＞ｎｅｘｔ；
ｅ＝ｒ－＞ｄａｔａ；
ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－ｎｅｘｔ； ／／（ｐ－＞ｎｅｘｔ＝ｒ－＞ｎｅｘｔ；）①
ｆｒｅｅ（ｒ）；
ｒｅｔｕｒｎＯＫ；
｝
·动态建立单链表的过程
（９）头插法建表
ＣｒｅａｔｅＬｉｓｔ＿Ｈ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｎ）
｛
Ｌ＝（ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；
ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）｛
ｓ＝（ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；
ｓ－＞ｎｅｘｔ＝Ｌ－＞ｎｅｘｔ；①
Ｌ－＞ｎｅｘｔ＝ｓ；②
｝
｝
·尾插法建表
（１０）尾插法建表
ＣｒｅａｔｅＬｉｓｔ＿Ｔ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｎ）
｛
ｔａｉｌ＝Ｌ＝（ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；
ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）｛
ｓ＝（ＬｉｎｋＬｉｓｔ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＬＮｏｄｅ））；
ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；
ｓ－＞ｎｅｘｔ＝ＮＵＬＬ；
ｔａｉｌ－＞ｎｅｘｔ＝ｓ；①
ｔａｉｌ＝ｓ；②
｝
｝
（１１）按元素值查找ＬｏｃａｔｅＥｌｅｍ（Ｌ，ｅ）
思路：在单链表Ｌ中从头开始找第１个值域与ｅ相等的结点，若存在这样的结点，则返回位置，否
则返回０。
ｉｎｔＬｏｃａｔｅＥｌｅｍ（ＬｉｎｋＬｉｓｔＬ，ＥｌｅｍＴｙｐｅｅ）
｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；ｉｎｔｎ＝１；
ｗｈｉｌｅ（ｐ！＝ＮＵＬＬ＆＆ｐ－＞ｄａｔａ！＝ｅ）
｛ ｐ＝ｐ－＞ｎｅｘｔ； ｎ＋＋； ｝
ｉｆ（ｐ＝＝ＮＵＬＬ） ｒｅｔｕｒｎ（０）；
ｅｌｓｅ ｒｅｔｕｒｎ（ｎ）；
｝
练习：已知Ｌ是带头结点的非空单链表，指针ｐ所指的结点既不是第一个结点，也不是最后一个
结点。
·删除ｐ结点的直接后继结点的语句序列
ｑ＝ｐ－＞ｎｅｘｔ；
ｐ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；
ｆｒｅｅ（ｑ）；
·删除ｐ结点的直接前驱结点的语句序列
ｑ＝Ｌ；
ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ－＞ｎｅｘｔ！＝ｐ） ｑ＝ｑ－＞ｎｅｘｔ；
ｓ＝ｑ－＞ｎｅｘｔ；
ｑ－＞ｎｅｘｔ＝ｐ；
ｆｒｅｅ（ｓ）；
·删除ｐ结点的语句序列
ｑ＝Ｌ；
ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ！＝ｐ） ｑ＝ｑ－＞ｎｅｘｔ；
ｑ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；
ｆｒｅｅ（ｐ）；
·删除首元结点的语句序列
ｑ＝Ｌ－＞ｎｅｘｔ；
Ｌ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；
ｆｒｅｅ（ｑ）；
·删除最后一个结点的语句序列
ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ！＝ＮＵＬＬ） ｐ＝ｐ－＞ｎｅｘｔ；
ｑ＝ｐ－＞ｎｅｘｔ；
ｐ－＞ｎｅｘｔ＝ＮＵＬＬ；
ｆｒｅｅ（ｑ）；
链式结构的特点：
·非随机存贮结构，所以取表元素要慢于顺序表。
节约了大块内存
·适合于插入和删除操作
实际上用空间换取了时间，结点中加入了指针，使得这两种操作转换为指针操作；
２．静态链表
有些高级程序设计语言并没有指针类型，如ＦＯＲＴＲＡＮ和ＪＡＶＡ。我们可以用数组来表示和实现
一个链表，称为静态链表。
可定义如下：
＃ｄｅｆｉｎｅ ＭＡＸＳＩＺＥ １０００ ／／最多元素个数
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ｛
ＥｌｅｍＴｙｐｅｄａｔａ；
ｉｎｔ ｃｕｒ；／／游标，指示器
｝ｃｏｍｐｏｎｅｎｔ，ＳＬｉｎｋＬｉｓｔ［ＭＡＸＳＩＺＥ］；
·ｉ＝ｓ［ｉ］．ｃｕｒ；指针后移操作
·Ｍａｌｌｏｃ： ｉ＝ｓ［０］．ｃｕｒ；第一个可用结点位置
ｉｆ（ｓ［０］．ｃｕｒ） ｓ［０］．ｃｕｒ＝ｓ［ｉ］．ｃｕｒ；
·Ｆｒｅｅ： ／／释放ｋ结点
ｓ［ｋ］．ｃｕｒ＝ｓ［０］．ｃｕｒ；
ｓ［０］．ｃｕｒ＝ｋ；
·Ｉｎｓｅｒｔ：／／将ｉ插在ｒ之后
ｓ［ｉ］．ｃｕｒ＝ｓ［ｒ］．ｃｕｒ；
ｓ［ｒ］．ｃｕｒ＝ｉ；
·Ｄｅｌｅｔｅ：；／／ｐ为ｋ的直接前驱，释放ｋ
ｓ［ｐ］．ｃｕｒ＝ｓ［ｋ］．ｃｕｒ
Ｆｒｅｅ（ｋ）；
单链表基础要点：
·在单链表中，不能从当前结点出发访问到任一结点。
·在单链表中，删除某一指定结点时，必须找到该结点的前驱结点。
·线性表的链式存储结构是一种顺序存取的存储结构，不具有随机访问任一元素的特点。
·设置头结点的作用：使在链表的第一个位置上的操作和表中其它位置上的操作一致，无需进行
特殊处理，对空表和非空表的处理统一。
循环链表：
·循环链表是另一种形式的链式存储结构；
·可从当前结点出发，访问到任一结点；
·循环单链表；
·多重循环链表。
单循环链表
设置尾指针ｒｅａｒ，比设头指针更好。
连接两个只设尾指针的单循环链表Ｌ１和Ｌ２
操作如下：
ｐ＝Ｒ１G22＞ｎｅｘｔ； ／／保存Ｌ１的头结点指针
Ｒ１－＞ｎｅｘｔ＝Ｒ２－＞ｎｅｘｔ－＞ｎｅｘｔ；／／头尾连接
ｆｒｅｅ（Ｒ２－＞ｎｅｘｔ）； ／／释放第二个表的头结点
Ｒ２－＞ｎｅｘｔ＝ｐ；
操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是ｐ是否为空，而是ｐ是否
等于头指针。
例：取循环链表第ｉ个元素。
Ｓｔａｔｕｓ ＧｅｔＥｌｅｍ＿Ｌ（ＬｉｎｋＬｉｓｔ Ｌ，ｉｎｔ ｉ，ＥｌｅｍＴｙｐｅ ＆ｅ） ｛
ｐ＝Ｌ－＞ｎｅｘｔ；ｊ＝１；
ｗｈｉｌｅ （ｐ！＝Ｌ＆＆ ｊ＜ｉ） ｛
ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ；
｝
ｉｆ （ｐ＝＝Ｌ｜｜ｊ＞ｉ） ｒｅｔｕｒｎ ＥＲＲＯＲ；
ｅ＝ｐ－＞ｄａｔａ；
ｒｅｔｕｒｎ ＯＫ；
｝
双链表：
希望查找前驱的时间复杂度达到Ｏ（１），我们可以用空间换时间，每个结点再加一个指向前驱的
指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为双向链表。
结点的结构图：
双向链表的逻辑表示：
双向链表（ＤｏｕｂｌｅＬｉｎｋｅｄＬｉｓｔ）
类型描述
ｔｙｐｅｄｅｆｓｔｒｕｃｔＤｕＬＮｏｄｅ｛
ＥｌｅｍＴｙｐｅ ｄａｔａ；
ｓｔｒｕｃｔＤｕＬＮｏｄｅ ｐｒｉｏｒ；
ｓｔｒｕｃｔＤｕＬＮｏｄｅ ｎｅｘｔ；
｝ＤｕＬＮｏｄｅ， ＤｕＬｉｎｋＬｉｓｔ；
双向循环链表
ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ；
·双向链表的前（后）插入操作
①ｓ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ； ②ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｓ；
③ｓ－＞ｎｅｘｔ＝ｐ； ④ｐ－＞ｐｒｉｏｒ＝ｓ；
①ｓ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ； ②ｑ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｓ；
③ｓ－＞ｐｒｉｏｒ＝ｑ； ④ｑ－＞ｎｅｘｔ＝ｓ；
·双向链表的删除操作
①ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；
②ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ；
·删除ｐ的直接后继结点的语句序列
ｑ＝ｐ－＞ｎｅｘｔ；
ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ；
ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ；
ｆｒｅｅ（ｑ）；
·删除ｐ的直接前驱结点的语句序列
ｑ＝ｐ－＞ｐｒｉｏｒ；
ｐ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞ｐｒｉｏｒ；
ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ；
ｆｒｅｅ（ｑ）；
ｒｅｔｕｒｎｐｒｅ；
｝
②找结点的中序后继结点
结点ｐ，无右孩子，右指针指向其后继，否则ｐ的右子树中“最左下”结点。
ＢｉＴｈｒＴｒｅｅＰｏｓｔＮｏｄｅ（ＢｉＴｈｒＴｒｅｅｐ）
｛
ｐｏｓｔ＝ｐ－＞ｒｃｈｉｌｄ；
ｉｆ（ｐ－＞ＲＴａｇ＝＝０）／／有右孩子
ｗｈｉｌｅ（ｐｏｓｔ－＞ＬＴａｇ＝＝０）
ｐｏｓｔ＝ｐｏｓｔ－＞ｌｃｈｉｌｄ；
ｒｅｔｕｒｎｐｏｓｔ；
｝
·带头结点的线索二叉链表
带头结点的中序线索二叉链表
中序遍历线索二叉树／／０：有孩子；１：无孩子
ＶｏｉｄＩｎＯｒｄｅｒＴｒａｖｅｒｓｅ＿Ｔｈｒ（ＢｉＴｈｒＴｒｅｅ Ｔ）／／Ｔ：头结点
｛
ｐ＝Ｔ－＞ｌｃｈｉｌｄ；
ｗｈｉｌｅ（ｐ！＝Ｔ）｛
ｗｈｉｌｅ（ｐ－＞ＬＴａｇ＝＝０）ｐ＝ｐ－＞ｌｃｈｉｌｄ；
ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；
ｗｈｉｌｅ（（ｐ－＞ＲＴａｇ＝＝１）＆＆（ｐ－＞ｒｃｈｉｌｄ！＝Ｔ））
｛ ｐ＝ｐ－＞ｒｃｈｉｌｄ；
ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；
｝
ｐ＝ｐ－＞ｒｃｈｉｌｄ；
｝
｝
·建立线索化链表（以中序为例）
按某种次序将二叉链表线索化，实质是在遍历过程中用线索取代空指针。
对线索树进行遍历，显然其效率要比传统方式高些。如果程序中经常要进行二叉树的遍历或者
需要查找在遍历过程中所的线性序列中前驱和后继，此时应当采用线索链表表示。
６．４ 树和森林
１．树的存储结构（三种方法）
双亲表示法：用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指
示其双亲结点在表中的位置，其结点的结构如下：
ＤａｔａＰａｒｅｎｔ
树的双亲存储结构示意图
＃ｄｅｆｉｎｅＭＡＸ＿ＴＲＥＥ＿ＳＩＺＥ １００
ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛
ＴＥｌｅｍＴｙｐｅ ｄａｔａ；
ｉｎｔ ｐａｒｅｎｔ；
｝ＰＴＮｏｄｅ；
Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛
ＰＴＮｏｄｅ ｎｏｄｅｓ［ＭＡＸ＿ＴＲＥＥ＿ＳＩＺＥ］；
ｉｎｔ ｒ，ｎ； ／／根的位置和结点数
｝ＰＴｒｅｅ；
双亲表示法的类型说明：
·孩子表示法：
①定长结点长度
空链域个数：ｎｋG22（ｎ－１）＝ｎ（ｋ－１）＋１．
②把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。ｎ个结点共有ｎ个孩子链
表（叶子结点的孩子链表为空表），而ｎ个结点的数据和ｎ个孩子链表的头指针又组成一个顺序表。
ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＴＮｏｄｅ｛／孩子结点的定义／
ｉｎｔ Ｃｈｉｌｄ； ／该孩子结点在线性表中的位置／
ｓｔｒｕｃｔＣＴＮｏｄｅ ｎｅｘｔ； ／指向下一个孩子结点的指针／
｝ＣｈｉｌｄＰｔｒ；
ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛／顺序表结点的结构定义／
ＴＥｌｅｍＴｙｐｅｄａｔａ； ／结点的信息／
ＣｈｉｌｄＰｔｒ ＦｉｒｓｔＣｈｉｌｄ；／指向孩子链表的头指针／
｝ＣＴＢｏｘ；
ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛／树的定义／
ＣＴＢｏｘ ｎｏｄｅｓ［ＭＡＸ＿ＴＲＥＥ＿ＳＩＺＥ］；／顺序表／
ｉｎｔｒｏｏｔ，ｎｕｍ；／根结点的位置和树的结点个数／
｝ＣＴｒｅｅ；
·孩子兄弟表示法
ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＳＮｏｄｅ｛
ＥｌｅｍＴｙｐｅｄａｔａ； ／结点信息／
ＳｔｒｕｃｔＣＳＮｏｄｅ ＦｉｒｓｔＣｈｉｌｄ， ＮｅｘｔＳｉｂｌｉｎｇ； ／第一个孩子，下一个兄弟／
｝ＣＳＮｏｄｅ， ＣＳＴｒｅｅ；
这种存储结构便于实现树的各种操作。
树的孩子兄弟链存储结构示意图
２．树、森林与二叉树的相互转换
·树转换为二叉树
（１）在所有相邻兄弟结点之间加一水平连线。
（２）对每个非叶结点ｋ，除了其最左边的孩子结点外，删去ｋ与其他孩子结点的连线。
（３）所有水平线段以左边结点为轴心顺时针旋转４５度，使之结构层次分明。
树做这样的转换所构成的二叉树是唯一的。
树与二叉树的对应
·森林转换为二叉树
森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：
（１）将森林中的每棵树转换成相应的二叉树。
（２）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树
根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
·二叉树还原为树或森林
将一棵二叉树还原为树或森林，具体方法如下：
（１）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲
结点用线连起来。
（２）删掉原二叉树中所有双亲结点与右孩子结点的连线。
（３）整理由（１）、（２）两步所得到的树或森林，使之结构层次分明。
二叉树到森林的转换示例
３．树与森林的遍历
·树的遍历（两种）
１）先根遍历
若树非空，则遍历方法为：
①访问根结点。
②从左到右，依次先根遍历根结点的每一棵子树。
等同于转换的二叉树进行先序遍历
先根遍历序列ＡＢＥＣＦＨＧＤ
２）后根遍历
若树非空，则遍历方法为：
①从左到右，依次后根遍历根结点的每一棵子树。
②访问根结点。
等同于转换的二叉树进行中序遍历
后根遍历序列为ＥＢＨＦＧＣＤＡ
·森林的遍历（２种）
１）中序遍历
若森林非空，则遍历方法为：
①访问森林中第一棵树的根结点。
②先序遍历第一棵树的根结点的子树森林。
③先序遍历除去第一棵树之后剩余的树构成的森林。
先序遍历序列为ＡＢＣＤＥＦＧＨＩＪ
等同于转换的二叉树进行先序遍历
２）先序遍历
若森林非空，则遍历方法为：
①中序遍历森林中第一棵树的根结点的子树森林。
②访问第一棵树的根结点。
③中序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历序列为 ＢＣＤＡＦＥＨＪＩＧ
等同于转换的二叉树进行中序遍历
４．几个问题
①给定树的先根遍历序列和后根遍历序列可唯一画出一棵树。
先根遍历序列：ＡＢＥＣＦＨＧＤ
后根遍历序列：ＥＢＨＦＧＣＤＡ
②给定森林的先序遍历序列和中序遍历序列可唯一确定一森林。
先序遍历序列：ＡＢＣＤＥＦＧＨＩＪ
中序遍历序列：ＢＣＤＡＦＥＨＪＩＧ
③关于二叉树的先序、中序和后序遍历序列确定二叉树的问题。
·任何ｎ（ｎ≥０）个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定。
证明：
先序序列是ａ
１
ａ
２
…ａ
ｎ
中序序列是ｂ
１
ｂ
２
…ｂ
ｎ
根结点：ａ
１
。
在中序序列中与ａ
１
相同的结点为：ｂ
ｊ
。
｛ｂ
１
…ｂ
ｊ－１
｝ｂ
ｊ
｛ｂ
ｊ＋１
…ｂ
ｎ
｝
←→
ａ
１
｛ａ
２
…ａ
ｋ
｝｛ａ
ｋ＋１
…ａ
ｎ
｝
例 已知先序序列为ＡＢＤＧＣＥＦ，中序序列为ＤＧＢＡＥＣＦ
·任何ｎ（ｎ＞０）个不同结点的二叉树，都可由它的中序序列和后序序列唯一地确定。
证明：
后序序列是ａ
１
ａ
２
…ａ
ｎ
中序序列是ｂ
１
ｂ
２
…ｂ
ｎ
根结点：ａ
ｎ
。
在中序序列中与ａ
ｎ
相同的结点为：ｂ
ｊ
。
｛ｂ
１
…ｂ
ｊ－１
｝ｂ
ｊ
｛ｂ
ｊ＋１
…ｂ
ｎ
｝
←→
｛ａ
１
ａ
２
…ａ
ｋ
｝｛ａ
ｋ＋１
…ａ
ｎ－１
｝ａ
ｎ
例 后序序列为ＧＤＢＥＦＣＡ，中序序列为ＤＧＢＡＥＣＦ
６．５ 树与等价问题
离散数学中的定义
·等价关系：若集合Ｓ中的关系Ｒ是自反的、对称的和传递的，则称为等价关系。
·等价类：Ｒ是集合Ｓ的等价关系，由［ｘ］Ｒ＝｛ｙ｜ｙ∈Ｓ∧ｘＲｙ｝给出的集合［ｘ］Ｒ称为由ｘ∈Ｓ生成
的一个Ｒ等价类。
·划分：Ｒ是Ｓ上的等价关系，可以按Ｒ将Ｓ划分为若干不相交的子集Ｓ
１
，Ｓ
２
，……，它们的并即
为Ｓ，则这些子集Ｓ
ｉ
就是Ｓ的Ｒ等价类。
如何划分等价类？
·假设集合Ｓ有ｎ个元素，ｍ个形如（ｘ，ｙ）的等价偶对确定了等价关系Ｒ，求Ｓ的划分。
一种算法：
１）令Ｓ中每个元素各自形成一个只含单个成员的子集，记为Ｓ
１
，Ｓ
２
，…，Ｓ
ｎ
。
２）重复读入ｍ个偶对，对每个偶对（ｘ，ｙ），判断ｘ和ｙ所属的子集，设ｘ∈Ｓ
ｉ
，ｙ∈Ｓ
ｊ
，若Ｓ
ｉ
≠Ｓ
ｊ
，则将
Ｓ
ｊ
并入Ｓ
ｉ
，并置Ｓ
ｊ
为空。
处理完ｍ个偶对后剩下的非空子集就是Ｓ的Ｒ等价类。
划分等价类需要的操作：
１）构造只含单个元素的集合
２）判定某个元素所属集合
３）合并两个互不相交的集合
ＡＤＴＭＦＳｅｔ：若Ｓ是ＭＦＳｅｔ类型的集合，则它由子集Ｓ
ｉ
构成，Ｓ
１
∪Ｓ
２
∪…∪Ｓ
ｎ
＝Ｓ。
基本操作：
Ｉｎｉｔｉａｌ（＆Ｓ，ｎ，ｘ
１
，ｘ
２
，…，ｘ
ｎ
）：构造由ｎ个子集构成的集合Ｓ，每个子集只含单个元素。
Ｆｉｎｄ（Ｓ，ｘ）：查找ｘ所属的子集Ｓ
ｉ
。
Ｍｅｒｇｅ（＆Ｓ，ｉ，ｊ）：合并两个不相交的集合Ｓ
ｉ
和Ｓ
ｊ
。
ＭＦＳｅｔ类型的实现
·根据Ｆｉｎｄ和Ｍｅｒｇｅ两个操作的特点，用树来实现ＭＦＳｅｔ。
·以森林Ｆ＝（Ｔ
１
，Ｔ
２
，…，Ｔ
ｎ
）表示ＭＦＳｅｔ类型的集合Ｓ，每颗树Ｔ
ｉ
表示一个子集Ｓ
ｉ
。
·树中每个结点表示子集中的一个成员ｘ。
·令每个结点中包含一个指向其双亲的指针。
·约定根结点兼作子集的名称。
集合的合并：
将一棵树的根指向另一颗树的根。
＃ｄｅｆｉｎｅＭＡＸ＿ＴＲＥＥ＿ＳＩＺＥ １００
ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛
ＴＥｌｅｍＴｙｐｅ ｄａｔａ；
ｉｎｔ ｐａｒｅｎｔ；
｝ＰＴＮｏｄｅ；
Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛
ＰＴＮｏｄｅ ｎｏｄｅｓ［ＭＡＸ＿ＴＲＥＥ＿ＳＩＺＥ］；
ｉｎｔ ｒ，ｎ； ／／根的位置和结点数
｝ＰＴｒｅｅ；
ＴｙｐｅｄｅｆＰＴｒｅｅ ＭＦＳｅｔ；
ｉｎｔｆｉｎｄ＿ｍｆｓｅｔ（ＭＦＳｅｔＳ，ｉｎｔｉ）
｛
ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－１；
ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］．ｐａｒｅｎｔ） ；
ｒｅｔｕｒｎｊ；
｝
Ｓｔａｔｕｓｍｅｒｇｅ＿ｍｆｓｅｔ（ＭＦＳｅｔ＆Ｓ，ｉｎｔｉ，ｉｎｔｊ）
｛
ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎＥＲＲＯＲ；
Ｓ．ｎｏｄｅ［ｉ］．ｐａｒｅｎｔ＝ｊ；
ｒｅｔｕｒｎＯＫ；
｝
时间复杂度分别为Ｏ（ｄ）和Ｏ（１），ｄ为树的深度
（７）掌握线索二叉树的概念和相关算法的实现。
（８）掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。
（９）灵活运用二叉树这种数据结构解决一些综合应用问题。
二、真题举例
１．已知一棵二叉树的前序遍历结果为ＡＢＣＤＥＦ，中序遍历结果为ＣＢＡＥＤＦ，则后序遍历的结果为
（ ）【浙江大学】
Ａ．ＣＢＥＦＤＡＢ．ＦＥＤＣＢＡＣ．ＣＢＥＤＦＡＤ．不定
２．已知某二叉树的后序遍历序列是ｄａｂｅｃ，中序遍历序列是ｄｅｂａｃ，它的前序遍历是（ ）【山东
大学】
Ａ．ａｃｂｄｅＢ．ｄｅｃａｂＣ．ｄｅａｃｂＤ．ｃｅｄｂａ
３．一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（ ）【合肥工业大学】
Ａ．不确定Ｂ．０Ｃ．１Ｄ．２
４．若Ｘ是二叉中序线索树中一个有左孩子的结点，且Ｘ不为根，则Ｘ的前驱为（ ）【南京理工
大学】
Ａ．Ｘ的双亲Ｂ．Ｘ的右子树中最左的结点
Ｃ．Ｘ的左子树中最右结点Ｄ．Ｘ的左子树中最右叶节点
５．设Ｆ是一个森林，Ｂ是由Ｆ变换得的二叉树。若Ｆ中有ｎ个非终端结点，则Ｂ中右指针域为空
的结点有（ ）个。【西安电子科技大学】
Ａ．ｎ－１Ｂ．ｎＣ．ｎ＋１Ｄ．ｎ＋２
三、本讲小结
线索二叉树的概念和相关算法的实现。
树、森林与二叉树的关系
树的简单应用
第３讲
一、考点讲解
极端情况：
改进方法？
·Ｍｅｒｇｅ时，总是将成员少的子集根结点指向含成员多的子集的根
·修改存储结构，令根结点的ｐａｒｅｎｔ域存储子集中所含成员数目的负值
·可以将ｆｉｎｄ＿ｍｆｓｅｔ的复杂度降到Ｏ（ｌｏｇｎ）
Ｓｔａｔｕｓｍｉｘ＿ｍｆｓｅｔ（ＭＦＳｅｔ＆Ｓ，ｉｎｔｉ，ｉｎｔｊ）
｛
ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎＥＲＲＯＲ；
ｉｆ（Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＞Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ）｛
Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ；
Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＝ｊ；
｝ｅｌｓｅ｛
Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ；
Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＝ｉ；
｝
ｒｅｔｕｒｎＯＫ；
｝
进一步的改进：Ｆｉｎｄ时压缩路径
·当所查元素不在第二层时，将所有从根到该元素路径上的元素都变成根结点的孩子
ｉｎｔｆｉｘ＿ｍｆｓｅｔ（ＭＦＳｅｔ＆Ｓ，ｉｎｔｉ）
｛
ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－１；
ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］．ｐａｒｅｎｔ） ；
ｆｏｒ（ｋ＝ｉ；ｋ！＝ｊ；ｋ＝ｔ）
｛
ｔ＝Ｓ．ｎｏｄｅｓ［ｋ］．ｐａｒｅｎｔ； Ｓ．ｎｏｄｅｓ［ｋ］．ｐａｒｅｎｔ＝ｊ；
｝
ｒｅｔｕｒｎｊ；
｝
６．６ 哈夫曼树及其应用
１．哈夫曼树
①路径长度
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做
路径长度。
②树的路径长度
从树根到每一结点的路径长度之和。
③结点的权和带权路径长度
给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。在树形结
构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。
④树的带权路径长度ＷＰＬ（ＷｅｉｇｈｔｅｄＰａｔｈＬｅｎｇｔｈｏｆＴｒｅｅ）
树中所有叶子结点的带权路径长度之和，通常记为：
ＷＰＬ＝
∑
ｎ
ｋ＝１
ｗ
ｋ
ｌ
ｋ
ＷＰＬ（ａ）＝７×２＋５×２＋２×２＋４×２＝３６
ＷＰＬ（ｂ）＝４×２＋７×３＋５×３＋２×１＝４６
ＷＰＬ（ｃ）＝７×１＋５×２＋２×３＋４×３＝３５
⑤哈夫曼树（最优二叉树）
设二叉树具有ｎ个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度与相应结点权
值的乘积的和，叫做二叉树的带权路径长度。
具有最小带权路径长度的二叉树称为哈夫曼树。
２．构造哈夫曼树（哈夫曼算法）
１）由给定的ｎ个权值｛Ｗ
１
，Ｗ
２
，．．．，Ｗ
ｎ
｝，构造ｎ棵只有一个叶子结点的二叉树，从而得到一个二
叉树的集合Ｆ＝｛Ｔ
１
，Ｔ
２
，．．．，Ｔ
ｎ
｝；
２）在Ｆ中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵
新的二叉树根结点的权值为其左、右子树根结点权值之和；
３）在集合Ｆ中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合Ｆ中；
４）重复（２）、（３）两步，当Ｆ中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
给定权值ｗ＝（１，３，５，７）来构造一棵哈夫曼树。
３．哈夫曼编码
１）编码
例，传送ＡＢＡＣＣＤ，四种字符，可以分别编码为００，０１，１０，１１。
则原电文转换为０００１００１０１０１１。
对方接收后，采用二位一分进行译码。
当然，为电文编码时，总是希望总长越短越好。
如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用较短的编码，则可以
减短电文的总长。
例 对ＡＢＡＣＣＤ重新编码，分别编码为０，００，１，０１。
Ａ Ｂ Ｃ Ｄ
则原电文转换为００００１１０１。减短了。
问题：
如何译码？
前四个二进制字符就可以多种译法。
ＡＡＡＡ ＢＢ
２）前缀编码
若设计的长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀
编码。
例，Ａ，Ｂ，Ｃ，Ｄ前缀编码可以为０，１１０，１０，１１１利用二叉树设计二进制前缀编码。
叶子结点表示Ａ，Ｂ，Ｃ，Ｄ这４个字符左分支表示‘０’，右分支表示‘１’；从根结点到叶子结
点的路径上经过的二进制符号串作为该叶子结点字符的编码，证明路径长度为编码长度
其必为前缀编码。
如何得到最短的二进制前缀编码？
３）赫夫曼编码
设每种字符在电文中出现的概率ｗ
ｉ
为，则依此ｎ个字符出现的概率做权，可以设计一棵赫夫曼
树，使
ＷＰＬ＝
∑
ｎ
ｉ＝１
ｗ
ｉ
ｌ
ｉ
最小
ｗ
ｉ
为叶子结点的出现概率（权）
ｌ
ｉ
为根结点到叶子结点的路径长度
例 某通信可能出现ＡＢＣＤＥＦＧＨ８个字符，其概率分别为０．０５，０．２９，０．０７，０．０８，０．
１４，０．２３，０．０３，０．１１，试设计赫夫曼编码。
ＡＣＥＡ编码为０１１０ １１１０１１００１１０
如何译码？
１．从根结点出发，从左至右扫描编码；
２．若为‘０’则走左分支，若为‘１’则走右分支，直至叶结点为止；
３．取叶结点字符为译码结果，返回重复执行１，２，３直至全部译完为止；
４．哈夫曼编码算法的实现。
哈夫曼树中没有度为１的结点（严格的或正则的二叉树）。
ｎ个叶子结点，共有２ｎ－１个结点。
ｔｙｐｅｄｅｆｓｔｒｕｃｔ
｛
ｕｎｓｉｇｎｅｄｉｎｔｗｅｉｇｈｔ； ／／结点的权值
ｕｎｓｉｇｎｅｄｉｎｔｐａｒｅｎｔ， ｌｃｈｉｌｄ，ｒｃｈｉｌｄ；
｝ＨＴＮｏｄｅ， ＨｕｆｆｍａｎＴｒｅｅ； ／／动态分配数组存储哈夫曼树
ｔｙｐｅｄｅｆｃｈａｒ ＨｕｆｆｍａｎＣｏｄｅ；／／动态分配数组存储哈夫曼编码
ｖｏｉｄＨｕｆｆｍａｎＣｏｄｉｎｇ（ＨｕｆｆｍａｎＴｒｅｅ＆ＨＴ，
ＨｕｆｆｍａｎＣｏｄｅ＆ＨＣ，ｉｎｔｗ， ｉｎｔｎ）
｛
ｍ＝２ｎ－１；
ＨＴ＝（ＨｕｆｆｍａｎＴｒｅｅ）ｍａｌｌｏｃ（（ｍ＋１）ｓｉｚｅｏｆ（ＨＴＮｏｄｅ））；
ｆｏｒ（ｐ＝ＨＴ＋１，ｉ＝１；ｉ＜＝ｎ；＋＋ｉ，＋＋ｐ，＋＋ｗ）ｐ＝｛ｗ，０，０，０｝；
ｆｏｒ（；ｉ＜＝ｍ；＋＋ｉ）ｐ＝｛０，０，０，０｝；
ｆｏｒ（ｉ＝ｎ＋１；ｉ＜＝ｍ；ｉ＋＋）｛
ｓｅｌｅｃｔ（ＨＴ，ｉ－１，ｓ１，ｓ２）；／／在ＨＴ［１．．ｉ－１］，
ＨＴ［ｓ１］．ｐａｒｅｎｔ＝ｉ； ＨＴ［ｓ２］．ｐａｒｅｎｔ＝ｉ；
ＨＴ［ｉ］．ｌｃｈｉｌｄ＝ｓ１； ＨＴ［ｉ］．ｒｃｈｉｌｄ＝ｓ２；
ＨＴ［ｉ］．ｗｅｉｇｈｔ＝ＨＴ［ｓ１］．ｗｅｉｇｈｔ＋ＨＴ［ｓ２］．ｗｅｉｇｈｔ；
｝
｝
ＨＣ＝（ＨｕｆｆｍａｎＣｏｄｅ）ｍａｌｌｏｃ（（ｎ＋１）ｓｉｚｅｏｆ（ｃｈａｒ））；
ｃｄ＝（ｃｈａｒ）ｍａｌｌｏｃ（ｎｓｉｚｅｏｆ（ｃｈａｒ））；
ｃｄ［ｎ－１］＝‘＼０’；
ｆｏｒ（ｉ＝１；ｉ＜＝ｎ；ｉ＋＋）｛
ｓｔａｒｔ＝ｎ－１；
ｆｏｒ（ｃ＝ｉ，ｆ＝ＨＴ［ｉ］．ｐａｒｅｎｔ；ｆ！＝０；ｃ＝ｆ，ｆ＝ＨＴ［ｆ］．ｐａｒｅｎｔ）
ｉｆ（ＨＴ［ｆ］．ｌｃｈｉｌｄ＝＝ｃ） ｃｄ［－－ｓｔａｒｔ］＝‘０’；
ｅｌｓｅ ｃｄ［－－ｓｔａｒｔ］＝‘１’；
ＨＣ［ｉ］＝（ｃｈａｒ）ｍａｌｌｏｃ（（ｎ－ｓｔａｒｔ）ｓｉｚｅｏｆ（ｃｈａｒ））；
ｓｔｒｃｐｙ（ＨＣ［ｉ］，＆ｃｄ［ｓｔａｒｔ］）；
｝
ｆｒｅｅ（ｃｄ）；
ＨＣ＝ｍａｌｌｏｃ（…）； ｃｄ＝ｍａｌｌｏｃ（…）；
ｐ＝ｍ；ｃｄｌｅｎ＝０； ｆｏｒ（ｉ＝１；ｉ＜＝ｍ；＋＋ｉ） ＨＴ［ｉ］．ｗｅｉｇｈｔ＝０；
ｗｈｉｌｅ（ｐ）｛
ｉｆ（ＨＴ［ｐ］．ｗｅｉｇｈｔ＝＝０）｛／／向左
ＨＴ［ｐ］．ｗｅｉｇｈｔ＝１；
ｉｆ（ＨＴ［ｐ］．ｌｃｈｉｌｄ！＝０）｛ｐ＝ＨＴ［ｐ］．ｌｃｈｉｌｄ；ｃｄ［ｃｄｌｅｎ＋＋］＝‘０’；｝
ｅｌｓｅｉｆ（ＨＴ［ｐ］．ｒｃｈｉｌｄ＝＝０）｛
ＨＣ［ｐ］＝（ｃｈａｒ）ｍａｌｌｏｃ（（ｃｄｌｅｎ＋１）ｓｉｚｅｏｆ（ｃｈａｒ））；
Ｕ＝｛ｖ
１
｝，Ｖ－Ｕ＝｛ｖ
２
，ｖ
３
，ｖ
４
，ｖ
５
，ｖ
６
｝ ＴＥ＝｛｝
Ｕ＝｛ｖ
１
，ｖ
３
｝，Ｖ－Ｕ＝｛ｖ
２
，ｖ
４
，ｖ
５
，ｖ
６
｝ ＜ｖ
１
，ｖ
３
＞
Ｕ＝｛ｖ
１
，ｖ
３
，ｖ
６
｝，Ｖ－Ｕ＝｛ｖ
２
，ｖ
４
，ｖ
５
｝ ＜ｖ
３
，ｖ
６
＞
Ｕ＝｛ｖ
１
，ｖ
３
，ｖ
４
，ｖ
６
｝，Ｖ－Ｕ＝｛ｖ
２
，ｖ
５
｝ ＜ｖ
６
，ｖ
４
＞
Ｕ＝｛ｖ
１
，ｖ
２
，ｖ
３
，ｖ
４
，ｖ
６
｝，Ｖ－Ｕ＝｛ｖ
５
｝ ＜ｖ
３
，ｖ
２
＞
Ｕ＝｛ｖ
１
，ｖ
２
，ｖ
３
，ｖ
４
，ｖ
５
，ｖ
６
｝，Ｖ－Ｕ＝｛｝ ＜ｖ
２
，ｖ
５
＞
重点：边一定存在于Ｕ与Ｖ－Ｕ之间。
设置一个辅助数组，对当前Ｖ－Ｕ集中的每个顶点，记录和顶点集Ｕ中顶点相连接的代价最小
的边：
对每个顶点ｖ
ｉ
∈Ｖ－Ｕ，在辅助数组中存在一个分量ｃｌｏｓｅｄｇｅ［ｖ
ｉ
］，它包括两个域ａｄｊｖｅｘ和ｌｏｗｃｏｓｔ，
其中ｌｏｗｃｏｓｔ存储该边上的权，显然有ｃｌｏｓｅｄｇｅ［ｉ－１］．ｌｏｗｃｏｓｔ＝Ｍｉｎ（｛ｃｏｓｔ（ｕ，ｖ
ｉ
）｜ｕ∈Ｕ｝）
ｓｔｒｕｃｔ｛
ＶｅｒｔｅｘＴｙｐｅ ａｄｊｖｅｘ；／／顶点名称
ｉｎｔ ｌｏｗｃｏｓｔ；
｝ｃｌｏｓｅｄｇｅ［ＭＡＸ＿ＶＥＲＴＥＸ＿ＮＵＭ］；
例 （详见视频）
ｖｏｉｄＭｉｎｉＳｐａｎＴｒｅｅ＿ＰＲＩＭ（ＭＧｒａｐｈＧ，ＶｅｒｔｅｘＴｙｐｅｕ）
｛ ｋ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｕ）；
ｆｏｒ（ｊ＝０；ｊ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｊ）
ｉｆ（ｊ！＝ｋ）ｃｌｏｓｅｄｇｅ［ｊ］＝｛ｕ，Ｇ．ａｒｃｓ［ｋ］［ｊ］．ａｄｊ｝；
ｃｌｏｓｅｄｇｅ［ｋ］．ｌｏｗｃｏｓｔ＝０；
ｆｏｒ（ｉ＝１；ｉ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｉ）｛
ｋ＝ｍｉｎｉｍｕｎ（ｃｌｏｓｅｄｇｅ）；
ｐｒｉｎｔｆ（ｃｏｌｓｅｄｇｅ［ｋ］．ａｄｊｖｅｘ，Ｇ．ｖｅｘｓ［ｋ］）；
ｃｌｏｓｅｄｇｅ［ｋ］．ｌｏｗｃｏｓｔ＝０；
ｆｏｒ（ｊ＝０；ｊ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｊ）
ｉｆ（Ｇ．ａｒｃｓ［ｋ］［ｊ］．ａｄｊ＜ｃｌｏｓｅｄｇｅ［ｊ］．ｌｏｗｃｏｓｔ）
ｃｏｌｓｅｄｇｅ［ｊ］＝｛Ｇ．ｖｅｘｓ［ｋ］，Ｇ．ａｒｃｓ［ｋ］［ｊ］．ａｄｊ｝；
｝
｝
Ｐｒｉｍ（）算法中有两重ｆｏｒ循环，所以时间复杂度为Ｏ（ｎ
２
）。与网中的边数无关，适用于求边稠
密的网的最小生成树。
Ｋｒｕｓｋａｌ算法
·Ｋｒｕｓｋａｌ于１９５６年提出
思想：考虑问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权
值尽可能地小。
Ｎ＝（Ｖ，Ｅ）是ｎ顶点的连通网，设Ｅ是连通网中边的集合；
构造最小生成树Ｎ’＝（Ｖ，ＴＥ），ＴＥ是最小生成树中边的集合，初始ＴＥ＝｛｝；
重复执行：
选取Ｅ中权值最小的边（ｕ，ｖ），判断边（ｕ，ｖ）与ＴＥ中的边是否构成回路？
例 （详见视频）
完整的克鲁斯卡尔算法应包括对边按权值递增排序，上述算法假设边已排序的情况下，时间复杂
度为Ｏ（ｎ
２
）。
如果给定的带权连通无向图Ｇ有ｅ条边，ｎ个顶点，采用堆排序（在第１０章中介绍）对边按权值
递增排序，那么用克鲁斯卡尔算法构造最小生成树的时间复杂度降为Ｏ（ｅｌｏｇｅ）。由于它与ｎ无关，只
与ｅ有关，所以说克鲁斯卡尔算法适合于求边稀疏的网的最小生成树。
７．５ 有向无环图及其应用
１．拓扑排序（ＴｏｐｏｌｏｇｉｃａｌＳｏｒｔ）
设Ｇ＝（Ｖ，Ｅ）是一个具有ｎ个顶点的有向图，Ｖ中顶点序列ｖ
１
，ｖ
２
，…，ｖ
ｎ
称为一个拓扑（有序）序
列，当且仅当该顶点序列满足下列条件：若＜ｖ
ｉ
，ｖ
ｊ
＞是图中的弧（即从顶点ｖ
ｉ
到ｖ
ｊ
有一条路径），则在
序列中顶点ｖ
ｉ
必须排在顶点ｖ
ｊ
之前。
在一个有向图中找一个拓扑序列的过程称为拓扑排序。
拓扑序列：Ｃ
１
，Ｃ
２
，Ｃ
３
，Ｃ
４
，Ｃ
５
，Ｃ
８
，Ｃ
９
，Ｃ
７
，Ｃ
６
。
拓扑序列：Ｃ
１
，Ｃ
２
，Ｃ
３
，Ｃ
８
，Ｃ
４
，Ｃ
５
，Ｃ
９
，Ｃ
７
，Ｃ
６
。
用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网（ＡｃｔｉｖｉｔｙＯｎＶｅｒ
ｔｅｘＮｅｔｗｏｒｋ），简称为ＡＯＶ－网。
如何进行拓扑排序？
方法一：（从图中顶点的入度考虑）
１）从有向图中选择一个没有前驱（即入度为０）的顶点并且输出它。
２）从网中删去该顶点和所有以它为尾的弧；
３）重复上述两步，直到图全部顶点输出；或当前图中不再存在没有前驱的顶点。
方法二：（从图中顶点的出度考虑，得到逆拓扑序列）
１）从有向图中选择一个出度为０的顶点并且输出它。
２）从网中删去该顶点和所有以它为头的弧；
３）重复上述两步，直到图全部顶点输出；或当前图中不再存在出度为０的顶点。
方法三：当有向图中无环时，利用深度优先遍历进行拓扑排序
从某点出发进行ＤＦＳ遍历时，最先退出ＤＦＳ函数的顶点即出度为０的顶点，是拓扑序列中最后一
个顶点。按退出ＤＦＳ函数的先后记录下来的顶点序列即为逆拓扑序列。
问题：判定一个图是否有圈（回路）的方法？
ＳｔａｔｕｓＴｏｐｏｌｏｇｉｃａｌＳｏｒｔ（ＡＬＧｒａｐｈＧ）
｛ｉｎｔＳｔ［ＭＡＸＶ］，ｔｏｐ＝－１； ／栈Ｓｔ的指针为ｔｏｐ／
ＦｉｎｄＩｎＤｅｇｒｅｅ（Ｇ，ｉｎｄｅｇｒｅｅ）；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
ｉｆ（！ｉｎｄｅｇｒｅｅ［ｉ］） ｛ ｔｏｐ＋＋；Ｓｔ［ｔｏｐ］＝ｉ；｝
ｃｏｕｎｔ＝０；
ｗｈｉｌｅ（ｔｏｐ＞－１）｛／栈不为空时循环／
ｉ＝Ｓｔ［ｔｏｐ］； ｔｏｐ－－；ｐｒｉｎｔｆ（＂％ｄ＂，ｉ）； ＋＋ｃｏｕｎｔ；
ｆｏｒ（ｐ＝Ｇ．ｖｅｒｔｉｃｅｓ［ｉ］．ｆｉｒｓｔａｒｃ；ｐ；ｐ＝ｐ－＞ｎｅｘｔａｒｃ）｛
ｋ＝ｐ－＞ａｄｊｖｅｘ；
ｉｆ（！（－－ｉｎｄｅｇｒｅｅ［ｋ］））｛ ｔｏｐ＋＋； Ｓｔ［ｔｏｐ］＝ｋ； ｝
｝
｝
ｉｆ（ｃｏｕｎｔ＜Ｇ．ｖｅｘｎｕｍ） ｒｅｔｕｒｎＥＲＲＯＲ； ｅｌｓｅｒｅｔｕｒｎＯＫ；
｝
ｖｏｉｄＦｉｎｄＩｎＤｅｇｒｅｅ（ＡＬＧｒａｐｈＧ， ｉｎｔｉｎｄｅｇｒｅｅ）
｛ｉｎｔｉ； ＡｒｃＮｏｄｅｐ；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋） ｉｎｄｅｇｒｅｅ［ｉ］＝０；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）｛
ｐ＝Ｇ．ｖｅｒｔｅｘｅｓ［ｉ］．ｆｉｒｓｔａｒｃ；
ｗｈｉｌｅ（ｐ！ ＝ＮＵＬＬ）｛
ｉｎｄｅｇｒｅｅ［ｐ－＞ａｄｊｖｅｘ］＋＋；
ｐ＝ｐ－＞ｎｅｘｔａｒｃ；｝／／ｗｈｉｌｅ
｝／／ｆｏｒ
｝
二、真题举例
１．（１）如果Ｇ１是一个具有ｎ个顶点的连通无向图，那么Ｇ１最多有多少条边？Ｇ１最少有多少
条边？
（２）如果Ｇ２是一个具有ｎ个顶点的强连通有向图，那么Ｇ２最多有多少条边？Ｇ２最少有多少条
边？【复旦大学】
２．已知一个无向图如下图所示，要求分别用Ｐｒｉｍ和Ｋｒｕｓｋａｌ算法生成最小树（假设以①为起点，
试画出构造过程）。【哈尔滨工业大学】
３．一带权无向图的邻接矩阵如右图，试画出它的一棵最小生成树。【浙江大学】
三、本讲小结
图的最小生成树、拓扑排序算法。
第３讲
一、考点讲解
２．关键路径
有向图在工程计划和经营管理中有着广泛的应用。通常用有向图来表示工程计划时有两种方法：
·用顶点表示活动，用有向弧表示活动间的优先关系，即上节所讨论的ＡＯＶ－网。
·用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。带权的有向无环图叫做
边表示活动的网（ＡｃｔｉｖｉｔｙＯｎＥｄｇｅＮｅｔｗｏｒｋ），简称ＡＯＥ－网。
·事件：表示在它之前的活动已经完成，在它之后的活动可以开始。
·ＡＯＥ－网有待解决的问题：
①哪些活动是影响工程进度的关键活动？
②至少需要多长时间能完成整个工程？
·源点：在ＡＯＥ网中存在唯一的、入度为零的顶点；
·汇点：存在唯一的、出度为零的顶点。
·关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关
键路径。
·关键活动：关键路径上的活动。
定义几个与计算关键活动有关的量：
·事件Ｖ
ｊ
的最早发生时间ｖｅ（ｊ）是从源点Ｖ
０
到顶点Ｖ
ｊ
的最长路径长度。
·事件Ｖ
ｊ
的最迟发生时间ｖｌ（ｊ）是在保证汇点Ｖ
ｎ－１
在ｖｅ（ｎ－１）时刻完成的前提下，事件Ｖ
ｊ
的允
许的最迟开始时间。
·活动ａ
ｉ
的最早开始时间ｅ（ｉ）
设活动ａ
ｉ
在弧＜Ｖ
ｊ
，Ｖ
ｋ
＞上，则ｅ（ｉ）是从源点Ｖ
０
到顶点Ｖ
ｊ
的最长路径长度。因此，ｅ（ｉ）＝ｖｅ
（ｊ）。
·活动ａ
ｉ
的最迟开始时间ｌ（ｉ）
ｌ（ｉ）是在不会引起时间延误的前提下，该活动允许的最迟开始时间。
ｌ（ｉ）＝ｖｌ（ｋ）－ｄｕｒ（＜ｊ，ｋ＞）。其中，ｄｕｒ（＜ｊ，ｋ＞）是完成ａ
ｉ
所需的时间。
·时间余量ｌ（ｉ）G22ｅ（ｉ）
表示活动ａ
ｉ
的最早开始时间和最迟开始时间的时间余量。
ｌ（ｉ）＝＝ｅ（ｉ）表示活动ａ
ｉ
是没有时间余量的关键活动。
·为找出关键活动，需要求各个活动的ｅ（ｉ）与ｌ（ｉ），以判别是否ｌ（ｉ）＝＝ｅ（ｉ）。
·为求得ｅ（ｉ）与ｌ（ｉ），需要先求得从源点Ｖ
０
到各个顶点Ｖ
ｊ
的ｖｅ（ｊ）和ｖｌ（ｊ）。
·从ｖｅ（０）＝０开始，向前递推
ｖｅ（ｊ）＝ｍａｘ
ｉ
｛ｖｅ（ｉ）＋ｄｕｒ（＜Ｖ
ｉ
，Ｖ
ｊ
＞）｝，＜Ｖ
ｉ
，Ｖ
ｊ
＞G28Ｔ，ｊ＝１，２，G29，ｎ－１
·其中Ｔ是所有以Ｖ
ｊ
为头的弧的集合。
从ｖｌ（ｎ－１）＝ｖｅ（ｎ－１）开始，反向递推
ｖｌ（ｉ）＝ｍｉｎ
ｊ
｛ｖｌ（ｊ）－ｄｕｒ（＜Ｖ
ｉ
，Ｖ
ｊ
＞）｝，＜Ｖ
ｉ
，Ｖ
ｊ
＞Ｓ，ｉ＝ｎ－２，ｎ－３，G29，０
其中Ｓ是所有以Ｖ
ｉ
为尾的弧的集合。
·ｅ（ｉ）＝ｖｅ（ｊ），ｌ（ｉ）＝ｖｌ（ｋ）－ｄｕｒ（＜ｊ，ｋ＞）
（详见视频）
·算法时间复杂度：
在拓扑排序求Ｖｅ（ｉ）和逆拓扑有序求Ｖｌ（ｉ）时，所需时间为Ｏ（ｎ＋ｅ），求各个活动的ｅ（ｉ）和ｌ（ｉ）
时所需时间为Ｏ（ｅ），总共花费时间仍然是Ｏ（ｎ＋ｅ）。
７．６ 最短路径
旅客希望停靠站越少越好，则应选择：济南———北京———太原———兰州
旅客考虑的是旅程越短越好，济南———徐州———郑州———西安———兰州
带权图的最短路径计算问题
通常在实际中，航运、铁路、船行都具有有向性，故我们以带权有向图为例介绍最短路径算法。
带权无向图的最短路径算法也通用。
从单个源点到其余各顶点的最短路径算法。
从一个顶点到其余各顶点的最短路径
问题：给定一个带权有向图Ｇ与源点ｖ，求从ｖ到Ｇ中其他顶点的最短路径，并限定各边上的权
值大于或等于０。
迪杰斯特拉（Ｄｉｊｋｓｔｒａ）算法思想：
贪心算法（局部最优），按路径长度递增的次序产生最短路径。
贪心算法：利用局部最优来计算全局最优。
利用已得到的顶点的最短路径来计算其它顶点的最短路径。
·路径长度最短的最短路径的特点：
在这条路径上，必定只含一条弧，并且这条弧的权值最小。
·下一条路径长度次短的最短路径的特点：
它只可能有两种情况：或者是直接从源点到该点（只含一条弧）；或者是，从源点经过顶点ｖ
１
，再到
达该顶点（由两条弧组成）。
·其余最短路径的特点：
它或者是直接从源点到该点（只含一条弧）；或者是，从源点经过已求得最短路径的顶点，再到达
该顶点。
·采用迪杰斯特拉（Ｄｉｊｋｓｔｒａ）算法求解
Ｄｉｊｋｓｔｒａ提出按路径长度的递增次序，逐步产生最短路径的算法。
引入一个辅助数组Ｄ。它的每一个分量Ｄ［ｉ］表示当前找到的从源点ｖ
０
到终点ｖ
ｉ
的最短路径的长
度。初始状态：
若从源点ｖ
０
到顶点ｖ
ｉ
有边，则Ｄ［ｉ］为该边上的权值；
若从源点ｖ
０
到顶点ｖ
ｉ
没有边，则Ｄ［ｉ］为＋G27。
一般情况下，假设Ｓ是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从ｖ
０
出发，中间只经过Ｓ中的顶点便可到达的那些顶点ｖ
ｘ
（ｖ
ｘ
G28Ｖ－Ｓ）的路径中的一条。
每次求得一条最短路径之后，其终点ｖ
ｋ
加入集合Ｓ，然后对所有的ｖ
ｉ
G28Ｖ－Ｓ，修改其Ｄ［ｉ］值。
·Ｄｉｊｋｓｔｒａ算法可描述如下：
①初始化：Ｓ←｛ｖ
０
｝；
Ｄ［ｊ］
←
ａｒｃｓ［０］［ｊ］， ｊ＝１，２，…，ｎ－１；
②求出最短路径的长度：
Ｄ［ｋ］
←
ｍｉｎ｛Ｄ［ｉ］｝， ｉG28Ｖ－Ｓ；
Ｓ
←
Ｓ∪｛ｋ｝；
③修改：
Ｄ［ｉ］
←
ｍｉｎ｛Ｄ［ｉ］， Ｄ［ｋ］＋ａｒｃｓ［ｋ］［ｉ］｝，
对于每一个ｉG28Ｖ－Ｓ；
④判断：若Ｓ＝Ｖ，则算法结束，否则转②。
一般情况，假设Ｓ为已求得最短路径的终点的集合，则有：下一条最短路径（设终点为ｘ）或者是
弧（ｖ
０
，ｘ），或者是ｖ
０
出发中间只经过Ｓ中的顶点而最后到达顶点ｘ的路径。
反证法：
假设下一条最短路径上有一个顶点不在Ｓ中，不妨设ｖ’；
则必存在一条终点为ｖ’的最短路径，其长度比该路径短；
可这是不可能的，因为我们是按照路径长度递增的次序来依次产生最短路径，即长度比该路径短
的所有路径都已产生；矛盾。
Ｄ［ｎ］：从源点到其余顶点的最短路径长度；
Ｆ［ｎ］：已找到最短路径的顶点，属于Ｓ集ｏｒ属于Ｖ－Ｓ集；
Ｐ［ｎ］：记录已找到的路径。Ｐ［ｉ］记录路径上ｖ
ｉ
的前驱。
例 （详见视频）
ｖｏｉｄＤｉｊｋｓｔｒａ（ＭＧｒａｐｈＧ）
｛ｉｎｔＤ［ＭＡＸＶ］，Ｐ［ＭＡＸＶ］，Ｆ［ＭＡＸＶ］；Ｆ［０］＝１；
ｆｏｒ（ｉ＝１；ｉ＜Ｇ．ｖｅｒｎｕｍ；ｉ＋＋）｛
Ｄ［ｉ］＝Ｇ．ａｒｃｓ［０］［ｉ］；Ｆ［ｉ］＝０；
ｉｆ（Ｄ［ｉ］＜ＩＮＴ＿ＭＡＸ） Ｐ［ｉ］＝０；
ｅｌｓｅ Ｐ［ｉ］＝－１；
｝
ｆｏｒ（ｉ＝１；ｉ＜Ｇ．ｖｅｒｎｕｍ；ｉ＋＋）｛
…．．
｝
Ｄｉｓｐａｔｈ（Ｄ，Ｐ，Ｆ，Ｇ．ｖｅｒｎｕｍ，０）；
｝
ｆｏｒ（ｉ＝１；ｉ＜Ｇ．ｖｅｒｎｕｍ；ｉ＋＋）｛
ｍｉｎ＝ＩＮＴ＿ＭＡＸ；
ｆｏｒ（ｊ＝１；ｊ＜Ｇ．ｖｅｒｎｕｍ；ｊ＋＋）
ｉｆ（！Ｆ［ｊ］）
ｉｆ（Ｄ［ｊ］＜ｍｉｎ）｛ｗ＝ｊ；ｍｉｎ＝Ｄ［ｊ］；｝
Ｆ［ｗ］＝１；
ｆｏｒ（ｊ＝１；ｊ＜Ｇ．ｖｅｒｎｕｍ；ｊ＋＋）｛
ｉｆ（！Ｆ［ｊ］＆＆（（Ｄ［ｗ］＋Ｇ．ａｒｃｓ［ｗ］［ｊ］）＜Ｄ［ｊ］））｛
Ｄ［ｊ］＝Ｄ［ｗ］＋Ｇ．ａｒｃｓ［ｗ］［ｊ］；
Ｐ［ｊ］＝ｗ；
｝
｝
ｖｏｉｄＰｐａｔｈ（ｉｎｔｐａｔｈ，ｉｎｔｉ，ｉｎｔｖ０）／前向递归查找路径上的顶点／
｛
ｋ＝ｐａｔｈ［ｉ］；
ｉｆ（ｋ＝＝ｖ０） ｒｅｔｕｒｎ； ／找到了起点则返回／
Ｐｐａｔｈ（ｐａｔｈ，ｋ，ｖ０）； ／找ｋ顶点的前一个顶点／
ｐｒｉｎｔｆ（＂％ｄ，＂，ｋ）； ／输出ｋ顶点／
｝
ｖｏｉｄＤｉｓｐａｔｈ（ｉｎｔｄｉｓｔ，ｉｎｔｐａｔｈ，ｉｎｔｆｉｎａｌ，ｉｎｔｎ，ｉｎｔｖ０）
｛
ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）｛
ｉｆ（ｆｉｎａｌ［ｉ］＝＝１）｛
ｐｒｉｎｔｆ（“从％ｄ到％ｄ的最短路径长度为：
％ｄ＼ｔ路径为：＂，ｖ０，ｉ，ｄｉｓｔ［ｉ］）；
ｐｒｉｎｔｆ（＂％ｄ，＂，ｖ０）；／输出路径上的起点／
Ｐｐａｔｈ（ｐａｔｈ，ｉ，ｖ０）；／输出路径上的中间点／
ｐｒｉｎｔｆ（＂％ｄ＼ｎ＂，ｉ）；／输出路径上的终点／
｝
ｅｌｓｅｐｒｉｎｔｆ（＂从％ｄ到％ｄ不存在路径＼ｎ＂，ｖ０，ｉ）；
｝
｝
２．每对顶点之间的最短路径
·问题的提法：已知一个各边权值均大于０的带权有向图，对每一对顶点ｖ
ｉ
G2Aｖ
ｊ
，要求求出ｖ
ｉ
与ｖ
ｊ
之间的最短路径和最短路径长度。
·弗洛伊德（Ｆｌｏｙｄ）算法的基本思想：
定义一个ｎ阶方阵序列：Ｄ
（－１）
，Ｄ
（０）
，…，Ｄ
（ｎ－１）
．
其中Ｄ
（－１）
［ｉ］［ｊ］＝ａｒｃｓ［ｉ］［ｊ］；
Ｄ
（ｋ）
［ｉ］［ｊ］＝Ｍｉｎ｛Ｄ
（ｋ－１）
［ｉ］［ｊ］，Ｄ
（ｋ－１）
［ｉ］［ｋ］＋Ｄ
（ｋ－１）
［ｋ］［ｊ］｝，ｋ＝０，１，…，ｎ－１
Ｄ
（０）
［ｉ］［ｊ］是从顶点ｖ
ｉ
到ｖ
ｊ
，中间顶点是ｖ
０
的最短路径的长度，Ｄ
（ｋ）
［ｉ］［ｊ］是从顶点ｖ
ｉ
到ｖ
ｊ
，中
间顶点的序号不大于ｋ的最短路径的长度，Ｄ（ｎ－１）［ｉ］［ｊ］是从顶点ｖ
ｉ
到ｖ
ｊ
的最短路径长度。
ｖｏｉｄＳｈｏｒｔｅｓｔＰａｔｈ＿Ｆｌｏｙｄ（ＭＧｒａｐｈＧ）
｛
ｉｎｔｐａｔｈ［ＮｕｍＶｅｒｔｉｃｅｓ］［ＮｕｍＶｅｒｔｉｃｅｓ］；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋） ／／矩阵Ｄ与ｐａｔｈ初始化
ｆｏｒ（ｊ＝０；ｊ＜Ｇ．ｖｅｘｎｕｍ；ｊ＋＋）｛
Ｄ［ｉ］［ｊ］＝Ｇ．ａｒｃｓ［ｉ］［ｊ］；
ｆｏｒ（ｋ＝０；ｋ＜Ｇ．ｖｅｘｎｕｍ；ｋ＋＋）ｐａｔｈ［ｉ］［ｊ］［ｋ］＝ＦＡＬＳＥ；
ｉｆ（Ｄ［ｉ］［ｊ］＜ＭＡＸＩＮＴ）｛
ｐａｔｈ［ｉ］［ｊ］［ｉ］＝ＴＲＵＥ；ｐａｔｈ［ｉ］［ｊ］［ｊ］＝ＴＲＵＥ；｝
｝
ｆｏｒ（ｋ＝０；ｋ＜Ｇ．ｖｅｘｎｕｍ；ｋ＋＋）
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
ｆｏｒ（ｊ＝０；ｊ＜Ｇ．ｖｅｘｎｕｍ；ｊ＋＋）
ｉｆ（Ｄ［ｉ］［ｊ］＞Ｄ［ｉ］［ｋ］＋Ｄ［ｋ］［ｊ］）｛
Ｄ［ｉ］［ｊ］＝Ｄ［ｉ］［ｋ］＋Ｄ［ｋ］［ｊ］；
ｆｏｒ（ｌ＝０；ｌ＜Ｇ．ｖｅｘｎｕｍ；ｌ＋＋）
ｐａｔｈ［ｉ］［ｊ］［ｌ］＝ｐａｔｈ［ｉ］［ｋ］［ｌ］｜｜ｐａｔｈ［ｋ］［ｊ］［ｌ］；
｝
｝
二、真题举例
１．用最短路径算法，求如下图中ａ到ｚ的最短通路。【西南财经大学】
２．下图是带权的有向图Ｇ的邻接表表示法，求：
（１）以结点Ｖ
１
出发深度遍历图Ｇ所得的结点序列；
（２）以结点Ｖ
１
出发广度遍历图Ｇ所得的结点序列；
（３）从结点Ｖ
１
到结点Ｖ
８
的最短路径；
（４）从结点Ｖ
１
到结点Ｖ
８
的关键路径。【青岛海洋大学】
三、本讲小结
图的关键路径、最短路径
第八章 查找
一、目录分析
９．１查找的基本概念
９．２静态查找表———基于线性表的查找法
９．３动态查找表———基于树表的查找法
９．４哈希表———计算式查找法
二、考点讲解
查找和排序是数据处理系统中最重要的两个操作；
其次是插入、删除操作；
讨论查找、排序，不可避免要涉及文件、记录、关键字等概念。
文件———查找表，是由同一类型的数据元素（记录）构成的集合
记录———构成文件的数据元素，是文件中可存取的数据的基本单位
字段———数据项，数据的最小单位
关键字———某个可以用来标识记录的数据项
主关键字———某个可以用来唯一标识记录的数据项
次关键字———可以用来识别若干记录的数据项
对文件经常进行的操作有：
１）查询某个“特定”的数据元素是否存在 查找算法
２）插入某个数据元素
３）删除某个数据元素
４）对数据元素进行排序 排序算法
不管何种操作，都遵循一个重要的性质：都是对主关键字操作
１．查找的基本概念
—１２１—
·查找表
由同一类型的数据元素（记录）构成的集合。
·查找的定义
给定一个值ｋｅｙ，在含有ｎ个记录的表中找出关键字等于ｋｅｙ的记录。若找到，则查找成功，返回
该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。
采用何种查找方法？
（１）使用哪种数据结构来表示“表”，即表中记录是按何种方式组织的。
（２）表中关键字的次序。是对无序集合查找还是对有序集合查找？
·静态查找表（ＳｔａｔｉｃＳｅａｒｃｈＴａｂｌｅ）：查询某个特定的元素是否在表中；检索某个特定的元素的各
种属性。
·动态查找表（ＤｙｎａｍｉｃＳｅａｒｃｈＴａｂｌｅ）：若在查找的同时对表做修改运算（如插入和删除）。
２．查找操作的性能分析
ＡＳＬ＝
∑
·基本操作：将记录的关键字和给定值进行比较。
·平均查找长度ＡＳＬ（ＡｖｅｒａｇｅＳｅａｒｃｈＬｅｎｇｔｈ）：为确定数据元素在查找表中的位置，需和给定值
进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
ｎ
ｉ＝１
ｐ
ｉ
ｃ
ｉ
Ｐ
ｉ
为查找表中第ｉ个记录的概率，Ｃ
ｉ
为找到第ｉ个记录时，和给定值已经进行过比较的关键字
个数。
９．１ 静态查找表
在表的组织方式中，线性表是最简单的一种。三种在线性表上进行查找的方法：
（１）顺序查找
（２）折半查找（二分查找）
（３）索引顺序表查找（分块查找）。
因为不考虑在查找的同时对表做修改，故上述三种查找操作都是在静态查找表上实现的。
１．顺序查找
顺序查找法的特点：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储
结构通常为顺序结构，也可为链式结构。
例如，在关键字序列为｛３，９，１，５，８，１０，６，７，２，４｝的线性表查找关键字为８的元素。
ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛
ＥｌｅｍＴｙｐｅｅｌｅｍ；
ｉｎｔｌｅｎｇｔｈ；
｝ＳＳＴａｂｌｅ；
ｉｎｔＳｅａｒｃｈ＿Ｓｅｑ（ＳＳｔａｂｌｅＳＴ，ＫｅｙＴｙｐｅｋｅｙ）
｛
ＳＴ．ｅｌｅｍ［０］．ｋｅｙ＝ｋｅｙ；
ｆｏｒ（ｉ＝ＳＴ．ｌｅｎｇｔｈ；！ＥＱ（ＳＴ．ｅｌｅｍ［ｉ］．ｋｅｙ，ｋｅｙ）；－－ｉ）；
ｒｅｔｕｒｎｉ；
｝
ｆｏｒ（ｉ＝ＳＴ．ｌｅｎｇｔｈ；ｉ＞０＆＆！ＥＱ（ＳＴ．ｅｌｅｍ［ｉ］．ｋｅｙ，ｋｅｙ）；－－ｉ）；
·顺序查找的平均查找长度ＡＳＬ：
假设表长度为ｎ，那么查找到第ｉ个记录时，和给定值已进行过比较的关键字个数为ｎ－ｉ＋１，即
Ｃ
ｉ
＝ｎ－ｉ＋１。又假设查找每个数据元素的概率相等，即Ｐ
ｉ
＝１／ｎ，则顺序查找算法的平均查找长
度为：
ＡＳＬ
ＳＳ
＝
∑
ｎ
ｉ＝１
Ｐ
ｉ
Ｃ
ｉ
＝
１
ｎ
∑
ｎ
ｉ＝１
Ｃ
ｉ
＝
１
ｎ
∑
ｎ
ｉ＝１
（ｎ－ｉ＋１）＝
１
２
（ｎ＋１）
·查找不成功时的平均查找长度：
假设查找成功和不成功的可能性相等，且每个记录的查找概率也相等，即Ｐ
ｉ
＝１／（２ｎ），则
ＡＳＬ
ＳＳ
＝
１
２ｎ
∑
ｎ
ｉ＝１
（ｎ－ｉ＋１）＋
１
２ｎ
ｎ（ｎ＋１）＝
３
４
（ｎ＋１）
２．折半查找法（二分法查找法）
要求待查找的表必须是按关键字大小有序排列的顺序表。
折半查找的思想：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否
则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一
步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，
或直到子表不存在为止，此时查找不成功。
折半查找（详见课程视频）
ｉｎｔＳｅａｒｃｈ＿Ｂｉｎ（ＳＳＴａｂｌｅＳＴ， ｉｎｔｋｅｙ）
｛
ｌｏｗ＝１； ｈｉｇｈ＝ＳＴ．ｌｅｎｇｔｈ；
ｗｈｉｌｅ（ｌｏｗ＜＝ｈｉｇｈ）｛
ｍｉｄ＝（ｌｏｗ＋ｈｉｇｈ）／２；
ｉｆ（ＳＴ．ｅｌｅｍ［ｍｉｄ］．ｋｅｙ＝＝ｋｅｙ） ／查找成功返回／
ｒｅｔｕｒｎ ｍｉｄ；
ｉｆ（ＳＴ．ｅｌｅｍ［ｍｉｄ］．ｋｅｙ＞ｋｅｙ）
ｈｉｇｈ＝ｍｉｄ－１； ／继续在［ｌｏｗ．．ｍｉｄ－１］中查找／
ｅｌｓｅ
ｌｏｗ＝ｍｉｄ＋１； ／继续在［ｍｉｄ＋１．．ｈｉｇｈ］中查找／
｝
ｒｅｔｕｒｎ０；
｝
判定树（比较树）：二分查找过程可用二叉树来描述，把当前查找区间的中间位置上的记录作为
根，左子表和右子表中的记录分别作为根的左子树和右子树。
·折半查找成功时的平均查找长度ＡＳＬ
假定表的长度ｎ＝２
ｈ
－１，则相应判定树必为深度是ｈ的满二叉树，ｈ＝ｌｏｇ
２
（ｎ＋１）。又假设每个
记录的查找概率相等，则折半查找成功时的平均查找长度为：
ＡＳＬ
ｂｓ
＝
∑
ｎ
ｉ＝１
Ｐ
ｉ
Ｃ
ｉ
＝
１
ｎ
∑
ｈ
ｊ＝１
ｊ×２
ｊ－１
＝
ｎ＋１
ｎ
ｌｏｇ
２
（ｎ＋１）－１
当ｎ较大（ｎ＞５０）时，有近似结果：
ＡＳＬ
ｂｓ
＝ｌｏｇ
２
（ｎ＋１）－１
折半查找判定树
（１）在查找成功时，会找到图中某个圆形结点，则成功时的平均查找长度：
ＡＳＬｓｕｃｃ＝
１×１＋２×２＋４×３＋４×４
１１
＝３
（２）在查找不成功时，会找到图中某个方形结点，则不成功时的平均查找长度：
ＡＳＬｕｎｓｕｃｃ＝
４×３＋８×４
１２
＝３．６７
３．索引顺序查找（分块查找）
是一种性能介于顺序查找和二分查找之间的查找方法。
将表［１．．ｎ－１］均分为ｂ块，前ｂ－１块中记录个数为ｓ＝「ｎ／ｂ?，最后一块即第ｂ块的记录数小
于等于ｓ；
每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要
“分块有序”。
抽取各块中的最大关键字及其起始位置构成一个索引表ＩＤ［ｂ］。由于表Ｒ［ｎ］是分块有序的，所
以索引表是一个递增有序表。
例如，设有一个线性表，其中包含２５个记录，其关键字序列为｛８，１４，６，９，１０，２２，３４，１８，１９，３１，
４０，３８，５４，６６，４６，７１，７８，６８，８０，８５，１００，９４，８８，９６，８７｝。假设将２５个记录分为５块，每块中有５个
记录，该线性表的索引存储结构如下图所示。
查找索引表的ＡＳＬ为：Ｌ
Ｂ
；块内进行顺序查找的ＡＳＬ为Ｌ
Ｗ
。
ＡＳＬ
ｂｓ
＝Ｌ
Ｂ
＋Ｌ
Ｗ
ｂ块，每块含ｓ个元素。查找概率相等，则每个索引项的查找概率为１／ｂ，块中每个元素的查找概
率为１／ｓ。
·若用顺序查找法确定待查元素所在的块，则有
ＡＳＬ
ｂｓ
＝Ｌ
Ｂ
＋Ｌ
Ｗ
＝
１
ｂ
∑
ｂ
ｊ＝１
ｊ＋
１
ｓ
∑
ｓ
ｉ＝１
ｉ＝
ｂ＋ｓ
２
＋１＝
１
２
（
ｎ
ｓ
＋ｓ）＋１
·若用折半查找法确定待查元素所在的块，则有
ＡＳＬ
ｂｓ
＝ｌｏｇ
２
（ｂ＋１）－１＋
ｓ＋１
２
≈ｌｏｇ
２
ｎ
ｓ
＋
( )
１＋
ｓ
２
·静态查找表的三种查找方法的比较
·顺序查找对对于表有序、无序均适用；折半查找仅适用于有序表；分块查找要求表分块后“分块
有序”。
·从表的存储结构上看，顺序查找和分块查找对于表的顺序和链式存储结构均适用，而折半查找
只适用于顺序存储结构。
·平均查找长度ＡＳＬ而言，折半最小（ｌｏｇ
２
（ｎ＋１）－１），分块次之（
槡
ｎ＋１），顺序最大（（ｎ＋１）／２）。
９．２ 动态查找表
动态查找表的特点：表结构本身在查找过程中动态生成，即对于给定值ｋｅｙ，若表中存在关键字等
于ｋｅｙ的记录，则查找成功，否则插入关键字等于ｋｅｙ的记录。
二叉排序树、平衡二叉排序树和Ｂ树等。
１．二叉排序树ＢＳＴ（ＢｉｎａｒｙＳｏｒｔＴｒｅｅ）的定义
或者是一棵空树，或者是具有如下性质的二叉树：
（１）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
（２）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
（３）它的左右子树也分别为二叉排序树。
ｔｙｐｅｄｅｆＳｑＬｉｓｔＨｅａｐＴｙｐｅ；
ｖｏｉｄＨｅａｐＡｄｊｕｓｔ（ＨｅａｐＴｙｐｅ＆Ｈ，ｉｎｔｓ，ｉｎｔｍ）
｛
ｒｃ＝Ｈ．ｒ［ｓ］；
ｆｏｒ（ｊ＝２ｓ；ｊ＜＝ｍ；ｊ＝２）｛
ｉｆ（ｊ＜ｍ＆＆Ｈ．ｒ［ｊ］．ｋｅｙ＜Ｈ．ｒ［ｊ＋１］．ｋｅｙ） ＋＋ｊ；
ｉｆ（ｒｃ．ｋｅｙ＞＝Ｈ．ｒ［ｊ］．ｋｅｙ） ｂｒｅａｋ；
Ｈ．ｒ［ｓ］＝Ｈ．ｒ［ｊ］；ｓ＝ｊ；
｝
Ｈ．ｒ［ｓ］＝ｒｃ；
｝
ｖｏｉｄＨｅａｐＳｏｒｔ（ＨｅａｐＴｙｐｅ＆Ｈ）
｛
ｆｏｒ（ｉ＝Ｈ．ｌｅｎｇｔｈ／２；ｉ＞０；－－ｉ） ／／建立初始堆
ＨｅａｐＡｄｊｕｓｔ（Ｈ，ｉ，Ｈ．ｌｅｎｇｔｈ）；
ｆｏｒ（ｉ＝Ｈ．ｌｅｎｇｔｈ；ｉ＞１；－－ｉ）｛
Ｈ．ｒ［１］
←→
Ｈ．ｒ［ｉ］；
ＨｅａｐＡｄｊｕｓｔ（Ｈ，１，ｉ－１）；
｝
｝
·算法分析
深度为ｋ的堆，筛选算法中进行的关键字比较次数至多为２（ｋ－１）。
建初始堆进行了G22ｎ／２G23次筛选，关键字比较次数至多为：
∑
１
ｉ＝ｈ－１
２
ｉ－１
·２（ｈ－ｉ）＝
∑
１
ｉ＝ｈ－１
２
ｉ
·（ｈ－ｉ）＝
∑
ｈ－１
ｊ＝１
２
ｈ－ｊ
·ｊG21（２ｎ）
∑
ｈ－１
ｊ＝１
ｊ／２
ｊ
G21４ｎ
ｎ个关键字，完全二叉树的深度G22ｌｏｇ
２
ｎG23＋１。调整建立新堆时，调用ＨｅａｐＡｄｊｕｓｔ过程ｎ－１次，关
键字比较次数至多为：
２（?ｌｏｇ
２
（ｎ－１）G23＋?ｌｏｇ
２
（ｎ－２）G23＋．．．＋ｌｏｇ
２
２）＜２ｎ（?ｌｏｇ
２
ｎG23）
堆排序的时间复杂度为Ｏ（ｎｌｏｇ
２
ｎ），空间复杂性为Ｏ（１）．
堆排序是一个不稳定的排序方法。
１０．５ 归并排序（ＭｅｒｇｉｎｇＳｏｒｔ）
·归并：是将两个或两个以上的有序表合并成一个新的有序表。
·２－路归并：假设初始序列有ｎ个记录，首先把它看成是ｎ个长度为１的有序子序列（归并
项），先做两两归并，得到G24ｎ／２G25个长度为２的归并项（如果ｎ为奇数，则最后一个有序子序列的长度
为１）；再做两两归并，…，如此重复，最后得到一个长度为ｎ的有序序列。
采用２－路归并排序方法进行排序的过程（１１个记录）。
一趟归并进行G24ｎ／（２ｈ）G25次两个有序子表的归并操作Ｍｅｒｇｅｒ．
将有序的ＳＲ［ｉ．．ｍ］和ＳＲ［ｍ＋１．．ｎ］归并为有序的ＴＲ［ｉ．．ｎ］．
ｖｏｉｄＭｅｒｇｅ（ＲｃｄＴｙｐｅＳＲ［］，ＲｃｄＴｙｐｅ＆ＴＲ［］，ｉｎｔｉ，ｉｎｔｍ，ｉｎｔｎ）
｛
ｆｏｒ（ｊ＝ｍ＋１，ｋ＝ｉ；ｉ＜＝ｍ＆＆ｊ＜＝ｎ；＋＋ｋ）｛
ｉｆ（ＳＲ［ｉ］．ｋｅｙ＜＝ＳＲ［ｊ］．ｋｅｙ） ＴＲ［ｋ］＝ＳＲ［ｉ＋＋］；
ｅｌｓｅ ＴＲ［ｋ］＝ＳＲ［ｊ＋＋］；
｝
ｉｆ（ｉ＜＝ｍ） ＴＲ［ｋ．．ｎ］＝ＳＲ［ｉ．．ｍ］；
ｉｆ（ｊ＜＝ｎ） ＴＲ［ｋ．．ｎ］＝ＳＲ［ｊ．．ｎ］；
｝
有序子表长度分别为：ｎ，ｍ． 则Ｍｅｒｇｅ的时间复杂度为：Ｏ（ｎ＋ｍ）．
ｖｏｉｄＭｅｒｇｅＰａｓｓ（ＲｃｄＴｙｐｅＳＲ［］，ＲｃｄＴｙｐｅ＆ＴＲ［］，ｉｎｔｈ，ｉｎｔｎ）
｛
ｆｏｒ（ｉ＝１；ｉ＋２ｈ－１＜＝ｎ；ｉ＝ｉ＋２ｈ） ／／归并ｈ长的两相邻子表
Ｍｅｒｇｅ（ＳＲ，ＴＲ，ｉ，ｉ＋ｈ－１，ｉ＋２ｈ－１）；
ｉｆ（ｉ＋ｈ－１＜＝ｎ） ／／余下部分
Ｍｅｒｇｅ（ＳＲ，ＴＲ，ｉ，ｉ＋ｈ－１，ｎ）；
｝
迭代的归并排序算法（一趟归并排序的情形）
ｖｏｉｄＭｅｒｇｅＳｏｒｔ（ＳｑＬｉｓｔ＆Ｌ） ／／自底向上的二路归并算法
｛ＲｃｄＴｙｐｅＴＲ［］；
ｆｏｒ（ｈ＝１；ｈ＜Ｌ．ｌｅｎｇｔｈ；ｈ＝２ｈ）
｛ＭｅｒｇｅＰａｓｓ（Ｌ．ｒ，ＴＲ，ｈ，Ｌ．ｌｅｎｇｔｈ）；
Ｌ．ｒ［１．．Ｌ．ｌｅｎｇｔｈ］＝ＴＲ［１．．Ｌ．ｌｅｎｇｔｈ］；
｝
｝
算法总的时间复杂度：Ｏ（ｎｌｏｇ
２
ｎ）
递归的归并排序算法
ｖｏｉｄＭＳｏｒｔ（ＲｃｄＴｙｐｅＳＲ［］，ＲｃｄＴｙｐｅ＆ＴＲ１［］，ｉｎｔｓ，ｉｎｔｔ）
｛
ｉｆ（ｓ＝＝ｔ） ＴＲ１［ｓ］＝ＳＲ［ｓ］；
ｅｌｓｅ｛
ｍ＝（ｓ＋ｔ）／２；
ＭＳｏｒｔ（ＳＲ，ＴＲ２，ｓ，ｍ）；
ＭＳｏｒｔ（ＳＲ，ＴＲ２，ｍ＋１，ｔ）；
Ｍｅｒｇｅ（ＴＲ２，ＴＲ１，ｓ，ｍ，ｔ）；
｝
｝
ｖｏｉｄＭｅｒｇｅＳｏｒｔ（ＳｑＬｉｓｔ＆Ｌ）
｛
ＭＳｏｒｔ（Ｌ．ｒ，Ｌ．ｒ，１，Ｌ．ｌｅｎｇｔｈ）；
｝
算法分析
·在迭代的归并排序算法中，函数ＭｅｒｇｅＰａｓｓ（）做一趟两路归并排序，要调用ｍｅｒｇｅ（）函数G24ｎ／
（２ｈ）G25次，函数ＭｅｒｇｅＳｏｒｔ（）调用ＭｅｒｇｅＰａｓｓ（）正好G24ｌｏｇ
２
ｎG25次，而每次ｍｅｒｇｅ（）至多执行比较２ｈ次，
所以算法总的时间复杂度为Ｏ（ｎｌｏｇ
２
ｎ）。
·递归的归并排序方法的递归深度为G24ｌｏｇ
２
ｎG25，算法总的时间复杂度为Ｏ（ｎｌｏｇ
２
ｎ）。
·归并排序占用附加存储较多，需要另外一个与原待排序记录数组同样大小的辅助数组。Ｏ（ｎ）
这是这个算法的缺点。
·归并排序是一个稳定的排序方法。
１０．６ 基数排序（ＲａｄｉｘＳｏｒｔ）
基数排序是通过“分配”和“收集”过程来实现排序，是一种借助于多关键字排序的思想对单关键
字排序的方法。
１．多关键字排序
每张扑克牌有两个“关键码”：花色和面值。其有序关系为：
花色：G2C G2D G2E G2D G2F G2D G30
面值：２＜３＜４＜５＜６＜７＜８＜９＜１０＜Ｊ＜Ｑ＜Ｋ＜Ａ
所有扑克牌排成以下次序：
G2C２，…，G2CＡ，G2E２，…，G2EＡ，G2F２，…，G2FＡ，G30２，…，G30Ａ
有ｎ个记录的序列｛Ｒ
１
，Ｒ
２
，…，Ｒ
ｎ
｝，且每个记录Ｒ
ｉ
中含有ｄ个关键字
Ｋ
１
ｉ
，Ｋ
２
ｉ
，…，Ｋ
( )
ｄ
ｉ
序列中任意两个对象Ｒ
ｉ
和Ｒ
ｊ
（１G21ｉ＜ｊG21ｎ）都满足：
Ｋ
１
ｉ
，Ｋ
２
ｉ
，…，Ｋ
( )
ｄ
ｉ
＜
Ｋ
１
ｊ
，Ｋ
２
ｊ
，…，Ｋ
( )
ｄ
ｊ
则称序列对关键字（Ｋ
１
，Ｋ
２
，…，Ｋ
ｄ
）有序。其中，Ｋ
１
称为最主
位关键字，Ｋ
ｄ
称为最次位关键字。
实现多关键字排序有两种常用的方法
·最高位优先ＭＳＤ（ＭｏｓｔＳｉｇｎｉｆｉｃａｎｔＤｉｇｉｔｆｉｒｓｔ）
·先根据最高位关键字Ｋ
１
排序，得到若干组，每组中每个记录都有相同关键字Ｋ
１
。
·再分别对每组中记录根据关键字Ｋ
２
进行排序，按Ｋ
２
值的不同，再分成若干个更小的子组，每个
子组中的记录具有相同的Ｋ
１
和Ｋ
２
值。
·依此重复，直到对关键字Ｋ
ｄ
完成排序为止。
·最后，把所有子组中的记录依次连接起来，就得到一个有序的序列。
·最低位优先ＬＳＤ（ＬｅａｓｔＳｉｇｎｉｆｉｃａｎｔＤｉｇｉｔｆｉｒｓｔ）
首先依据最低位关键字Ｋ
ｄ
对所有记录进行一趟排序，再依据次低位关键字Ｋ
ｄ－１
对上一趟排序的
结果再排序，依次重复，直到依据关键字Ｋ１最后一趟排序完成，就可以得到一个有序的序列。使用这
种排序方法对每一个关键字进行排序时，不需要再分组，而是整个记录都参加排序。
５２张牌排序方法：
最高位优先法（ＭＳＤＦ）：
先按不同“花色”分成有次序的４堆，每一堆均具有相同的花色；
然后分别对每一堆按“面值”大小整理有序。
最低位优先法（ＬＳＤＦ）：
先按不同“面值”分成１３堆；
然后将这１３堆牌自小至大叠在一起（２，３，．．．，Ａ）；
然后将这付牌整个颠倒过来再重新按不同的“花色”分成４堆；
最后将这４堆牌按自小至大的次序合在一起。
２．链式基数排序
·基数排序是典型的ＬＳＤ排序方法，利用“分配”和“收集”两种运算对单关键字进行排序。在这
种方法中，把单关键字Ｋ
ｉ
看成是一个ｄ元组：
Ｋ
１
ｉ
，Ｋ
２
ｉ
，…，Ｋ
( )
ｄ
ｉ
·分量有ｒａｄｉｘ种取值，则称ｒａｄｉｘ为基数，即分量的取值范围。
关键字９８４可以看成是一个３元组（９，８，４），每一位有０，１，…，９等１０种取值，基数ｒａｄｉｘ＝
１０。关键字‘ｄａｔａ’可以看成是一个４元组（ｄ，ａ，ｔ，ａ），每一位有‘ａ’，‘ｂ’，…，‘ｚ’等２６种取值，ｒａ
ｄｉｘ＝２６。
·记录的关键字Ｋ
０
，Ｋ
１
，…，Ｋ
ｄ－１
，依次对各位的分量，分别用“分配”、“收集”的运算逐趟进行
排序，
·各队列采用链式队列结构，分配到同一队列的关键字用指针链接起来。每一队列设置两个指
针：ｆｒｏｎｔ［ｒａｄｉｘ］指示队头，ｒｅａｒ［ｒａｄｉｘ］指向队尾。
·以静态链表作为ｎ个记录的存储结构。在记录重排时不必移动记录，只需修改各记录的链接
指针即可。
例 序列 ２７８ １０９ ０６３ ９３０ ５８９ １８４ ５０５ ２６９ ００８ ０８３
（详见视频）
算法分析
·若每个关键字有ｄ位，需要重复执行ｄ趟“分配”与“收集”。每趟对ｎ个记录进行“分配”，对
ｒａｄｉｘ个队列进行“收集”。总时间复杂度为Ｏ（ｄ（ｎ＋ｒａｄｉｘ））。
·若基数ｒａｄｉｘ相同，对于记录个数较多而关键字位数较少的情况，使用链式基数排序较好。
·基数排序需要增加ｎ＋２ｒａｄｉｘ个附加链接指针。
·基数排序是稳定的排序方法。
１０．７ 各种内部排序方法的比较讨论
１．选择排序方法时需考虑的因素
·待排序的记录数目；
·记录本身信息量的大小；
·关键字的结构及其分布情况；
·对排序稳定性的要求；
·语言工具的条件，辅助空间的大小。
２．各种内部排序方法的性能
３．结论：没有哪一种排序方法是绝对好的，都有其优缺点
·若ｎ较小，可采用直接插入排序或简单选择排序
·若序列的初始状态已按关键字基本有序，则选用直接插入或起泡排序为宜；
·若ｎ较大，采用Ｏ（ｎｌｏｇ
２
ｎ）的排序方法；
·若ｎ很大，记录的关键字位数较少且可以分解时，采用基数排序较好；
·避免移动记录，用链表作存储结构，如表插入；
·内部排序可能达到的最快速度是什么？时间下界？
时间上界Ｏ（ｎ
２
）
任何借助于“比较”的排序方法，至少需要Ｏ（ｎｌｏｇ
２
ｎ）的时间。
·三个关键字：ｋ
１
，ｋ
２
，ｋ
３
，则描述３个记录排序过程的判定树必有３！＝６个叶子结点。
·ｎ个记录的序列，初始状态有ｎ！个，则描述ｎ个记录排序过程的判定树必有ｎ！个叶子结点。
则判定树的树高至少为G24ｌｏｇ
２
ｎ！G25＋１，ｌｏｇ
２
ｎ！≈ｎｌｏｇ
２
ｎ，
·最坏情况下能达到的最好的时间复杂度为Ｏ（ｎｌｏｇ
２
ｎ）．
二、真题举例
１．已知一关键码序列为：３，８７，１２，６１，７０，９７，２６，４５。试根据堆排序原理，填写完整下示各步骤结
果。【首都经贸大学】
建立堆结构：
交换与调整：（１）８７７０２６６１４５１２３９７；（２）；
（３）６１４５２６３１２７０８７９７；（４）；
（５）２６１２３４５６１７０８７９７；（６）；；
（７）３１２２６４５６１７０８７９７；
|
|
