Skip to content

Latest commit

 

History

History
2676 lines (1731 loc) · 165 KB

数据结构考纲知识点.md

File metadata and controls

2676 lines (1731 loc) · 165 KB

数据结构考纲知识点

🔖 目录

考纲

一、总体要求

《数据结构》是计算机程序设计的重要理论技术基础，是计算机科学与技术学科的核心课程。

要求：

理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

掌握基本的数据处理原理和方法的基础上，能够分析算法的时间复杂度与空间复杂度。

能够选择合适的数据结构和算法策略进行问题求解，具备采用 C 或 C++ 或 JAVA 语言设计与实现算法的能力。

二、内容

  1. 数据结构及算法的相关概念和术语

（1）数据结构及算法的概念

（2）数据的逻辑结构和存储结构

（3）算法的定义及特性

（4）算法时间复杂度和空间复杂度的分析方法

  1. 线性表

（1）线性表的定义

（2）线性表的基本操作及在顺序存储及链式存储上的实现

（3）各种变形链表（循环链表、双向链表、带头结点的链表等）的表示和基本操作的实现

（4）递归过程的特点及实现方法

（5）栈和队列的基本概念；栈和队列的顺序存储结构、链式储存结构及其存储特点

（6）栈和队列的应用

（7）循环队列的判满、判空方法

（8）特殊矩阵的压缩储存

  1. 广义表的基本概念、存储结构和基本操作

  2. 树和二叉树

（1）树与森林的基本概念

（2）树与森林的存储结构及遍历

（3）二叉树的定义及 6 大性质

（4）二叉树的顺序储存与链式储存结构

（5）二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现

（6）线索二叉树的基本概念与构造方法

（7）树与二叉树的应用：二叉排序树；二叉平衡树；哈夫曼树与哈夫曼编码

  1. 图

（1）图的基本概念和术语

（2）图的存储结构：邻接矩阵、邻接表、逆邻接表

（3）遍历算法：深度优先搜索算法和广度优先搜索算法

（4）应用：最小生成树；最短路径，拓扑排序和关键路径

  1. 查找

（1）查找的基本概念；静态查找与动态查找

（2）顺序查找、折半查找、索引查找

（3）哈希查找（哈希函数的基本构造方法，解决地址冲突的基本策略）

（4）各种查找算法的时间复杂度和空间复杂度

  1. 排序

（1）排序的基本概念

（2）插入排序

（3）简单选择排序

（4）希尔排序

（5）快速排序

（6）堆排序

（7）归并排序

（8）基数排序

（9）排序算法的比较

  1. 算法题要求

其中算法题分为阅读、修改和编写算法三类：

（1）阅读算法：阅读指定算法，回答使用的数据结构、算法实现的功能或执行的结果；

（2）修改算法：阅读指定算法，指出算法的错误并修正；指出算法的不足并改进；按给定功能填写 算法空缺部分；

（3）编写算法：根据算法功能要求，选择或者设计合适的数据结构，用程序设计语言编写算法，实 现指定功能。

（4）以上皆可分析给定或者设计的算法时空复杂度。

1. 数据结构及算法的相关概念和术语

1.1 数据结构及算法的概念 ★

1.1.1 数据结构

  1. 数据

    数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

  2. 数据元素和数据项

    数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

  3. 数据对象

    数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合 $\small N = {0,±1,±2,\dots}$。

  4. 数据类型

    数据类型是一个值的集合和定义在此集合上的一组操作的总称。

    • ① 原子类型。其值不可再分的数据类型。
    • ② 结构类型。其值可以再分解为若干成分(分量)的数据类型。
    • ③ 抽象数据类型。抽象数据组织及与之相关的操作。

  5. 数据结构

    数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

    数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。

    数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

数据、数据对象、数据元素、数据项之间的关系

数据、数据对象、数据元素、数据项之间的关系

1.1.2 算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。详见：1.3 算法的定义及特性

1.2 数据的逻辑结构和存储结构 ★

1.2.1 数据的逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此， 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的逻辑结构有两个要素：一是数据元素；二是关系。数据元素的含义如前所述，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构：

  • 集合结构：结构中的数据元素之间除“同属一个集合”外，别无其他关系，如 (a) 所示。
  • 线性结构：结构中的数据元素之间只存在一对一的关系，如图 (b) 所示。
  • 树形结构：结构中的数据元素之间存在一对多的关系，如图 (c) 所示。
  • 图状结构或网状结构：结构中的数据元素之间存在多对多的关系 ，如图 (d) 所示。

其中集合结构、树结构和图结构都属于非线性结构。

4 类基本结构关系示例图

4 类基本结构关系示例图

线性结构包括：

  • 线性表：典型的线性结构；
  • 栈和队列：具有特殊限制的线性表，数据操作只能在表的一端或两端进行；
  • 字符串：也是特殊的线性表，其特殊性表现在它的数据元素仅由一个字符组成；
  • 数组：是线性表的推广，它的数据元素是一个线性表；
  • 广义表：也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表。

非线性结构包括：

  • 树：具有多个分支的层次结构；
  • 二叉树：具有两个分支的层次结构；
  • 有向图：一种图结构，边是顶点的有序对；
  • 无向图：另一种图结构，边是顶点的无序对。

这几种逻辑结构可以用一个层次图描述，如图所示。

几种逻辑结构层次图

几种逻辑结构层次图

1.2.2 数据的存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系。

数据的存储结构主要有：顺序存储结构、链式存储结构、索引存储结构、散列（哈希 Hash）存储结构。

  • 顺序存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中， 元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空 间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外 部碎片。
  • 链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象, 能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
  • 索引存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
  • 散列（哈希 Hash）存储结构：根据元素的关键字直接计算出该元素的存储地址。其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

1.3 算法的定义及特性 ★

1.3.1 算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列 5 个重要特性：

  • ① 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  • ② 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得岀相同的输出。
  • ③ 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  • ④ 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
  • ⑤ 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

1.3.2 算法设计的要求

通常，设计一个“好”的算法应考虑达到以下目标：

  • ① 正确性：算法应能够正确地解决求解问题。
  • ② 可读性：算法应具有良好的可读性，以帮助人们理解。
  • ③ 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
  • ④ 高效性（效率与低存储量需求）：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

1.4 算法时间复杂度和空间复杂度的分析方法 ★★

算法效率的度量是通过时间复杂度和空间复杂度来描述的 。

1.4.1 时间复杂度

TODO

1.4.2 空间复杂度

TODO

1.4.3 常见算法时间、空间复杂度汇总

分类 算法 时间复杂度 空间复杂度
排序（详细信息参考 https://www.notion.so/93f7750387ae4247b11a2aa0351e3c61?pvs=21） 冒泡排序 $O(n^2)$ $O(1)$
直接选择排序 $O(n^2)$ $O(1)$
直接插入排序 $O(n^2)$ $O(1)$
二分插入排序 $O(n^2)$ $O(1)$
希尔排序 https://zh.wikipedia.org/zh-cn/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F#%E6%AD%A5%E9%95%B7%E5%BA%8F%E5%88%97 $O(1)$
堆排序 $O(nlogn)$ $O(1)$
归并排序 $O(nlogn)$ $O(n)$
快速排序 $O(nlogn)$ $O(logn)$
基数排序 $O(d(n + r))$（n 个记录，d 个关键码，关键码的取值范围为 r） $O(r)$
查找
图算法 广度优先搜索 - BFS
深度优先搜索 - DFS
最小生成树 - Prim 算法 $O( V
最小生成树 - Kruskal 算法 $O( E
单源最短路径 - Dijkstra 算法 $O( V
多对节点最短路径 - Floyd 算法 $O( V

TODO

2. 线性表

2.1 线性表的定义 ★

TODO

2.2 线性表的基本操作及在顺序存储及链式存储上的实现 ★★★

2.2.1 线性表的基本操作

2.2.2 线性表在顺序存储上的实现

2.2.3 线性表在链式存储上的实现

2.3 各种变形链表（循环链表、双向链表、带头结点的链表等）的表示和基本操作的实现 ★★★

2.3.1 双向链表

TODO

2.3.2 循环链表

2.3.3 静态链表

2.4 递归过程的特点及实现方法 ★

2.4.1 递归的定义及特点

2.4.2 递归的实现方法

2.5 栈和队列的基本概念；栈和队列的顺序存储结构、链式储存结构及其存储特点 ★★★★

2.5.1 栈的基本概念

  1. 栈的定义

    栈（Stack）是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作，如图所示。

    栈的示意图

    栈的示意图

    栈顶（Top）。线性表允许进行插入删除的那一端。

    栈底（Bottom）。固定的，不允许进行插入和删除的另一端。

    空栈。不含任何元素的空表。

    假设某个栈 $\small S = (a_1, a_2, a_3, a_4, a_5)$，如上图所示，则 $\small a_1$ 为栈底元素，$\small a_5$ 为栈顶元素。由于栈只能在栈顶进行插入和删除操作，进栈次序依次为 $\small a_1, a_2, a_3, a_4, a_5$，而出栈次序为 $\small a_5, a_4, a_3, a_2, a_1$。 由此可见，栈的操作特性可以明显地概括为后进先出（Last In First Out, LIFO）。

    栈的数学性质：n 个不同元素进栈，出栈元素不同排列的个数为 $\small C_n = \frac{1}{n+1} C_{2n}^{n} = \frac{(2n)!}{(n+1)!n!}$，该公式称为卡特兰（Catalan）数。卡特兰数的更多应用见：2.6.7 卡特兰数

  2. 栈的基本操作

    InitStack(&S)：初始化一个空栈 S（“&”表示引用调用）。

    StackEmpty (S)：判断一个栈是否为空，若栈 S 为空则返回 true，否则返回 false。

    Push(&S, x)：进栈，若栈 S 未满，则将 x 加入使之成为新栈顶。

    Pop(&S, &x)：岀栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。

    GetTop(S, &x)：读栈顶元素，若栈 S 非空，则用 x 返回栈顶元素。

    DestroyStack(&S)：销毁栈，并释放栈 S 占用的存储空间。

2.5.2 栈的顺序存储结构及其存储特点

2.5.3 栈的链式存储结构及其存储特点

2.5.4 队列的基本概念

2.5.5 队列的顺序存储结构及其存储特点

2.5.6 队列的链式存储结构及其存储特点

2.6 栈和队列的应用 ★★

表达式求值与栈例题

2.6.1 栈在括号匹配中的应用

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意即 $\small (~)$ 或 $\small [([][])]$ 等均为正确的格式，$\small [(])$ 或 $\small ([())$ 或 $\small (()]$ 均为不正确的格式。

考虑下列括号序列：

Untitled

分析如下：

① 计算机接收第 1 个括号“[”后，期待与之匹配的第 8 个括号“]”出现。

② 获得了第 2 个括号“(”，此时第 1 个括号“[”暂时放在一边，而急迫期待与之匹配的第 7 个括号“)”出现。

③ 获得了第 3 个括号“[”，此时第 2 个括号“(”暂时放在一边，而急迫期待与之匹配的第 4 个括号“]”出现。第 3 个括号的期待得到满足，消解之后，第 2 个括号的期待匹配又成为当前最急迫的任务。

以此类推，可见该处理过程与栈的思想吻合。

算法的思想如下：

① 初始设置一个空栈，顺序读入括号。

② 若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序）。

③ 若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。

2.6.2 栈在表达式求值中的应用

💡 手工中缀表达式转后缀后缀表达式，以 $\small \mathrm{A + B * (C - D) - E/F}$ 为例
  • 根据运算优先级加括号：$\small \mathrm{((A + (B * (C - D))) - (E/F))}$
  • 把运算符提到所在层级括号外：$\small \mathrm{((A (B (CD)-)*)+ (EF)/)-}$
  • 去掉括号即得到后缀表达式：$\small \mathrm{A B CD-*+ EF/-}$

（还可以将表达式对应的二叉树画出来，然后进行后续遍历）

表达式求值是程序设计语言编译中一个最基本的问题，它的实现是栈应用的一个典型范例。 中缀表达式不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符。中缀表达式 $\small \mathrm{A+B*(C-D) -E/F}$ 所对应的后缀表达式为 $\small \mathrm{ABCD-*+EF/-}$。

表达式 $\small \mathrm{A+B*(C-D) -E/F}$ 对应的二叉树

表达式 $\small \mathrm{A+B*(C-D) -E/F}$ 对应的二叉树

2.6.3 队列在层次遍历中的应用

2.6.4 队列在计算机系统的应用

2.6.5 卡特兰数

卡特兰数 $\large C_n = \frac{1}{n+1} C_{2n}^{n} = \frac{(2n)!}{(n+1)!n!}$ 应用

  • Cn 表示 n 个不同元素进栈后可能的出栈序列数目
  • Cn 表示所有包含 n 组括号的合法运算式的个数
  • Cn 表示有 n 个节点组成不同构二叉树的方案数
  • Cn 表示有 2n+1 个节点组成不同构满二叉树的方案数

2.7 循环队列的判满、判空方法 ★★★★★

2.7.1 循环队列定义

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环 ，称为循环队列。当队首指针 Q.front=MaxSize - 1 后，再前进一个位置就自动到 0，这可以利用除法取余运算（％）来实现。

  • 初始时：Q. front = Q.rear =0。
  • 队首指针进 1：Q. front = (Q.front + 1) % MaxSize。
  • 队尾指针进 1： Q.rear = (Q.rear + 1) % MaxSize。
  • 队列长度：(Q.rear + MaxSize - Q.front) % MaxSize。
  • 出队入队时：指针都按顺时针方向进 1（如下图 (a) (b) (c) 所示）。

循环队列出入队示意图

循环队列出入队示意图

那么，循环队列队空和队满的判断条件是什么呢？显然，队空的条件是 Q. front == Q. rear。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如上图 (dl) 所示， 此时可以看出队满时也有 Q.front == Q.rear。为了区分是队空还是队满的情况，有三种处理方式：

  1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法, 约定以“队头指针在队尾指针的下一位置作为队满的标志”，如上图 (d2) 所示。

    • 队满条件：(Q.rear + 1) % MaxSize == Q.front。
    • 队空条件：Q.front == Q.rear。
    • 队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize。

  2. 类型中增设表示元素个数的数据成员 size。

    • 队空条件：Q.size == 0；
    • 队满条件：Q.size == MaxSize。

    这两种情况都有 Q.front == Q.rear。

  3. 类型中增设 tag 数据成员，以区分是队满还是队空。

    • tag 等于 0 时，若因删除导致 Q.front == Q.rear，则为队空；
    • tag 等于 1 时，若因插入导致 Q.front == Q.rear，则为队满。

2.7.2 循环队列判满判空

假设循环队列队首指针为 front，队尾指针为 rear，队列最大长度为 MaxSize。

判满判空方法 计数变量 size 标志位 tag 牺牲一个元素的存储单元
初始空队列各变量初值 front = 0; rear = 0 front = 0; rear = 0 front = 0; rear = 0
出队前判断队空条件 size == 0 tag == 0 && front == rear front == rear
入队前判断队满条件 size == MaxSize tag == 1 && front == rear (rear + 1) % MaxSize == front
出队前该方法的特殊处理 size-- tag = 0 无，或填 front = (front +1) % MaxSize
入队前该方法的特殊处理 size++ tag = 1 无，或填 rear = (rear +1) % MaxSize

2.8 特殊矩阵的压缩储存 ★★

2.8.1 基本概念

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一 定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律 性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

2.8.2 对称矩阵

若对一个 n 阶方阵 $\small A [1\dots n][1\dots n]$ 中的任意一个元素 $\small a_{i,j}$ 都有 $\small a_{i, j} = a_{j,i}(1 \le i,j \le n)$，则称其为对称矩阵。对于一个 n 阶方阵，其中的元素可以划分为 3 个部分，即上三角区、主对角线和下三角区，如图所示。

n 阶方阵的划分

n 阶方阵的划分

对于 n 阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将对称矩阵 $\small A [1\dots n][1\dots n]$ 存放在一维数组 $\small B[n(n+1)/2]$ 中，即元素 $\small a_{i, j}$ 存放在 $\small b_k$ 中。只存放下三角部分（含主对角）的元素。

在数组 B 中，位于元素 $\small a_{i, j}(i \ge j)$ 前面的元素个数为：

  • 第 1 行：1 个元素 $\small (a_{1,1})$。
  • 第 2 行：2 个元素 $\small (a_{2,1}, a_{2,2})$。
  • ……
  • 第 i - 1 行：i - 1 个元素 $\small (a_{i-1, 1}, a_{i-1,2}, \dots, a_{i-1, i-1})$。
  • 第 i 行：j - 1 个元素 $\small (a_{i, 1}, a_{i,2}, \dots, a_{i, j-1})$。

因此，元素 $\small a_{i, j}$ 在数组 B 中的下标 $\small k= 1+2+ \dots +(i-1)+j-1=i(i-1)/2+j-1$（数组下标从 0 开始）。因此，元素下标之间的对应关系如下：

$$ \small k = \begin{cases} \frac{i(i-1)}{2}+j-1, & i \ge j（下三角区和主对角线元素）\\ \frac{j(j-1)}{2}+i-1, & i < j （上三角区元素 a_{i,j} =a_{j,i}）& \end{cases} $$

2.8.3 三角矩阵

  1. 下三角矩阵

    如图，在下三角矩阵中，上三角区的所有元素均为同一常量 。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵 $\small A [1\dots n][1\dots n]$ 压缩存储在数组 $\small B[n(n+1)/2 + 1]$ 中。

    下三角矩阵

    下三角矩阵

    元素下标之间的对应关系为：

    $$ \small k = \begin{cases} \frac{i(i-1)}{2}+j-1, & i \ge j（下三角区和主对角线元素）\ \frac{n(n+1)}{2}, & i < j （上三角区元素） \end{cases} $$

    下三角矩阵在内存中的压缩存储形式如图所示。

    下三角矩阵的压缩存储

    下三角矩阵的压缩存储

  2. 上三角矩阵

如图，上三角矩阵中，下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在数组 $\small B[n(n+1)/2 + 1]$ 中。

上三角矩阵

上三角矩阵

在数组 B 中，位于元素 $\small a_{i, j}(i \ge j)$ 前面的元素个数为：

  • 第 1 行：n 个元素
  • 第 2 行：n - 1 个元素
  • ……
  • 第 i - 1 行：n - i + 2 个元素
  • 第 i 行：j - i 个元素

因此，元素 $\small a_{i,j}$ 在数组 B 中的下标 $\small k = n + (n - 1) + \dots + (n - i + 2) + (j - i + 1) - 1 = (i - 1)(2n - i + 2)/2 + (j - i)$。元素下标之间的对应关系如下：

$$ \small k = \begin{cases} \frac{i(2n-i+2)}{2}+(j-i), & i \ge j（上三角区和主对角线元素）\\ \frac{n(n+1)}{2}, & i < j （下三角区元素） \end{cases} $$

上三角矩阵在内存中的压缩存储形式如图所示。

上三角矩阵的压缩存储

上三角矩阵的压缩存储

2.8.4 三对角矩阵

对角矩阵也称带状矩阵。对于 n 阶方阵 A 中的任一元素 $\small a_{i,j}$，当 $\small |i - j| &gt; 1$ 时，有 $\small a_{i,j}=0(i \le i,j \le n)$，则称为三对角矩阵，如图所示。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的 3 条对角线的区域，其他区域的元素都为零。

三对角矩阵 A

三对角矩阵 A

三对角矩阵 A 也可以采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一维数组 B 中，且 $\small a_{1, 1}$ 存放于 B[0] 中，其存储形式如图所示。

三对角矩阵的压缩存储

三对角矩阵的压缩存储

由此可以计算矩阵 A 中 3 条对角线上的元素 $\small a_{i,j}(1 \le i,j \le n, |i-j| \le 1)$ 在一维数组 B 中存放的下标为 $\small k = 2i + j - 3$。

反之，若已知三对角线矩阵中某元素 $\small a_{i, j}$ 存放于一维数组 B 的第 k 个位置，则可得 $\small i = \left \lfloor (k+1)/3 + 1 \right \rfloor , ~ j = k - 2i + 3$。

例如：

  • 当 $\small k = 0$ 时，$\small i = \left \lfloor (0+1)/3 + 1 \right \rfloor = 1 , ~ j = 0 - 2×1 + 3 = 1$，存放的是 $\small a_{1, 1}$；
  • 当 $\small k = 2$ 时，$\small i = \left \lfloor (2+1)/3 + 1 \right \rfloor = 2 , ~ j = 2 - 2×2 + 3 = 1$，存放的是 $\small a_{2, 1}$；
  • 当 $\small k = 4$ 时，$\small i = \left \lfloor (4+1)/3 + 1 \right \rfloor = 2 , ~ j = 4 - 2×2 + 3 = 3$，存放的是 $\small a_{2, 3}$；

2.8.5 稀疏矩阵

矩阵中非零元素的个数 t，相对矩阵元素的个数 s 来说非常少，即 $\small s \gg t$ 的矩阵称为稀疏矩阵。 例如，一个 100×100 的矩阵，该矩阵中只有少于 100 个非零元素。

若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组 （行标，列标，值），如图所示。然后按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。

稀疏矩阵及其对应的三元组

稀疏矩阵及其对应的三元组

若需对由三元组表示的稀疏矩阵进行转置，只需将三元组中每个元素的行标和列标进行调换，然后根据调换后的行标和列标进行排序即可。例如三元组(2, 1, 9) 转置后对应 (1, 2, 9)；(1, 2, 6) 转置后为 (2, 1, 6)。

i   j   v              i   j   v             i   j   v
0   0   4     转置      0   0   4    重排序    0   0   4
1   2   6   =======>   2   1   6   =======>  1   2   9 
2   1   9              1   2   9             1   3   23
3   1   23             1   3   23            2   1   6

稀疏矩阵的三元组既可以采用数组存储 ，也可以采用十字链表法存储。

3. 广义表的基本概念、存储结构和基本操作

3.1 广义表的基本概念 ★★★

广义表是线性表的推广，也称为列表，一般记作 $\small \mathrm{LS = (a_1, a_2, \dots , a_n)}$。其中，LS 是广义表的名称， n 是其长度，$a_i$ 可以是单个元素（称为原子，一般用小写字母表示），也可以是广义表（称为子表，一般用大写字母表示）。广义表的深度定义为广义表中括弧的重数（最大嵌套数目）。

广义表示例：

  • A = ( ) —— A 是一个空表，其长度为 0。
  • B = ( e ) —— B 只有一个原子 e， 其长度为 1 。
  • C = ( a, ( b, c, d ) ) —— C 的长度为 2，两个元素分别为原子 a 和子表 ( b, c, d )。
  • D = ( A, B, C ) —— D 的长度为 3。3 个元素都是广义表。显然，将子表的值代入后，则有 D = ( ( ), ( e ), ( a, ( b, c, d ) ) ) 。
  • E = ( a, E ) —— 这是一个递归的表，其长度为 2。E 相当于一个无限的广义表 E = ( a, ( a, ( a, ··· ) ) )。

从上述定义和例子可推出广义表的如下 3 个重要结论：

  • 广义表的元素可以是子表，而子表的元素还可以是子表…… 由此，广义表是一个多层次的结构，可以用图形象地表示。例如，下图表示的是广义表 D，图中以圆圈表示广义表，以方块表示原子。

    广义表 D 的图形表示

    广义表 D 的图形表示

  • 广义表可为其他广义表所共享。例如在上述例子中，广义表 A 、 B 和 C 为 D 的子表， 则在 D 中可以不必列出子表的值，而是通过子表的名称来引用。

  • 广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。例如，表 E 就是一个递归的表。

❓ 广义表 $\small \mathrm {(((a,b,(),c),d),e,((f),g))}$ 的长度是 ____，深度是 ____？

广义表长度通过数第一层括号内的逗号数目可以知道，因为只有一个元素 ((a,b,(),c),d),e,((f),g)，所以长度是 1；

广义表的深度是广义表中括号最大的嵌套次数（重数），通过数括号嵌套数目得到，深度为 4。

3.2 广义表的存储结构 ★

由于广义表中的数据元素可以有不同的结构（或是原子，或是列表），因此通常采用链式存储结构。常用的链式存储结构有两种，头尾链表的存储结构和扩展线性链表的存储结构。

  1. 头尾链表的存储结构

    由于广义表中的数据元素可能为原子或广义表，由此需要两种结构的结点：一种是表结点，用以表示广义表；一种是原子结点，用以表示原子。从上节得知：若广义表不空，则可分解成表头和表尾，因此，一对确定的表头和表尾可唯一确定广义表。一个表结点可由 3 个域组成：标志域、指示表头的指针域和指示表尾的指针域。而原子结点只需两个域：标志域和值域。如下图所示，其中 tag 是标志域，值为 1 时表明结点是子表，值为 0 时表明结点是原子。

    头尾链表表示的结点结构

    头尾链表表示的结点结构

    其形式定义说明如下：

    // ------ 广义表的头尾链表存储表示 ------
typedef enum{ATOM, LISTI} ElemTag;            // ATOM==O: 原子，LIST==1: 子表
typedef struct GLNode {
    ElemTag tag;                              // 公共部分，用于区分原子结点和表结点
    union {                                   // 原子结点和表结点的联合部分
        AtomType atom;                        // atom 是原子结点的值域， AtomType 由用户定义
        struct {struct GLNode *hp, *tp} ptr;  // ptr 是表结点的指针域，ptr.hp和 ptr.tp 分别指向表头和表尾
    };
}*GList;                                      // 广义表类型

    上节中曾列举了广义表的例子，它们的存储结构如图所示，在这种存储结构中有以下几 种情况。

    头尾链表表示的存储结构示例

    头尾链表表示的存储结构示例

    • ① 除空表的表头指针为空外，对任何非空广义表，其表头指针均指向一个表结点，且该结点中的 hp 域指示广义表表头（或为原子结点，或为表结点），tp 域指向广义表表尾（除非表尾为空，则指针为空，否则必为表结点）。
    • ② 容易分清列表中原子和子表所在层次。如在广义表 D 中，原子 a 和 e 在同一层次上， 而 b 、 c 和 d 在同一层次且比 a 和 e 低一层， B 和 C 是同一层的子表。
    • ③ 最高层的表结点个数即为广义表的长度。

  2. 扩展线性链表的存储结构

    在这种结构中，无论是原子结点还是表结点均由三个域组成，其结点结构如图所示。

    扩展线性链表表示的结点结构

    扩展线性链表表示的结点结构

    // ------ 广义表的扩展线性链表存储表示 ------
typedef enum{ATOM, LISTI} ElemTag; // ATOM==O: 原子，LIST==1: 子表
typedef struct GLNode {
    ElemTag tag;                   // 公共部分，用于区分原子结点和表结点
    union {                        // 原子结点和表结点的联合部分
        AtomType atom;             // 原子结点的值域
        struct GLNode *hp;         // 表节点的表头指针
    };
    struct GLNode *tp;             // 相当于线性链表的 next，指向下一个元素结点
} *GList;                          // 广义表类型 GList 是一种扩展的线性链表

    上一节中广义表例子所对应的这种表示法的存储结构，如图所示。

    扩展线性链表表示的存储结构示例

    扩展线性链表表示的存储结构示例

3.3 广义表的基本操作 ★★

由于广义表的结构比较复杂，其各种运算的实现也不如线性表简单，其中，最重要的两个运算如下。

  • 取表头 GetHead(LS)： 取出的表头为非空广义表的第一个元素，它可以是一个单原子，也可以是一个子表。
  • 取表尾 GetTail(LS)：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。

例如：对于广义表 A = ( )；B = ( e )；C = ( a, ( b, c, d ) )；D = ( A, B, C )；E = ( a, E )。

  • GetHead(B) = e，GetTail(B) = ()；
  • GetHead(D) = A，GetTail(D) = (B, C)；
  • 由于 (B, C) 为非空广义表，则可继续分解得到：GetHead(B, C) = B，GetTail (B, C) = (C)。

值得提醒的是，广义表 () 和 (( )) 不同。前者为空表，长度 n = 0；后者长度 n = 1，可分解得到其表头、表尾均为空表 ( )。

4. 树和二叉树

4.1 树与森林的基本概念 ★★

4.1.1 树的定义

4.1.2 森林的定义

4.1.3 基本术语

4.2 树与森林的存储结构及遍历 ★★

4.2.1 树的存储结构

树的存储方式有多种，既可釆用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系 ，这里介绍 3 种常用的存储结构。

  1. 双亲表示法

    这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。如图所示，根结点下标为 0，其伪指针域为 -1。

    树的双亲表示法

    树的双亲表示法

    双亲表示法的存储结构描述如下：

    #define MAX_TREE_SIZE 100  // 树中最多结点数
typedef struct{            // 树的结点定义 
    ElemType data;         // 数据元素 
    int parent;            // 双亲位置域
} PTNode;

typedef struct{                  // 树的类型定义 
    PTNode nodes[MAX_TREE_SIZE]; // 双亲表示 
    int n;                       // 结点数
} PTree;

    该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的 双亲结点，但求结点的孩子时需要遍历整个结构 。

  2. 孩子表示法

    孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时 n 个结点就有 n 个孩子链表（叶子结点的孩子链表为空表），如下图所示。

    这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历 n 个结点中孩子链表指针域所指向的 n 个孩子链表。

    孩子表示法

    孩子表示法

    可以把双亲表示法和孩子表示法结合起来，即将双亲表示和孩 子链表合在一起。

    带双亲的孩子链表

    带双亲的孩子链表

  3. 孩子兄弟表示法

    孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点），如图所示。

    孩子兄弟表示法

    孩子兄弟表示法

4.2.2 树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树与二 叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上看， 它们的二叉链表是相同的，只是解释不同而已。

树转换为二叉树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树，如图所示。

树与二叉树的对应关系

树与二叉树的对应关系

树转换成二叉树的画法：

  • ① 在兄弟结点之间加一连线；
  • ② 对每个结点，只保留它与第一个 孩子的连线，而与其他孩子的连线全部抹掉；
  • ③ 以树根为轴心，顺时针旋转 45°。

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟 ，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右 子树…… 以此类推，就可以将森林转换为二叉树。

森林转换成二叉树的画法：

  • ① 将森林中的每棵树转换成相应的二叉树；
  • ② 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
  • ③ 以第一棵树的根为轴心顺时针旋转 45°。

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树，就得到了原森林，如图所示。二叉树转换为树或森林是唯一的。

森林与二叉树的对应关系

森林与二叉树的对应关系

4.2.3 树和森林的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式:

  • ① 先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。 其遍历序列与这棵树相应二叉树的先序序列相同。
  • ② 后根遍历。若树非空, 先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。 其遍历序列与这棵树相应二叉树的中序序列相同。

Untitled

上图所示树的先根遍历序列为 ABEFCDG，后根遍历序列为 EFBCGDA。

另外，树也有层次遍历，与二叉树的层次遍历思想基本相同 ，即按层序依次访问各结点。 按照森林和树相互递归的定义，可得到森林的两种遍历方法。

  • ① 先序遍历森林。若森林为非空，则
    • 访问森林中第一棵树的根结点。
    • 先序遍历第一棵树中根结点的子树森林。
    • 先序遍历除去第一棵树之后剩余的树构成的森林。
  • ② 中序遍历森林。森林为非空时，按如下规则进行遍历:
    • 中序遍历森林中第一棵树的根结点的子树森林。
    • 访问第一棵树的根结点。
    • 中序遍历除去第一棵树之后剩余的树构成的森林。

森林的中序遍历确实本应该是后序遍历，之所以这样命名为中序遍历，是因为这种遍历等同于将森林转换为二叉树之后，对应二叉树的中序遍历。

Untitled

上图的森林的先序遍历序列为 ABCDEFGHI，中序遍历序列为 BCDAFEHIG。

当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，可知森林的先序和中序遍历即为其对应二叉树的先序和中序遍历。

树和森林的遍历与二叉树的遍历关系见下表。

树和森林的遍历与 二叉树遍历的对应关系

树和森林的遍历与 二叉树遍历的对应关系

4.3 二叉树的定义及 6 大性质 ★★★★

4.3.1 二叉树的定义

4.3.2 几个特殊的二叉树

4.3.3 二叉树的性质

4.4 二叉树的顺序储存与链式储存结构 ★★★

4.4.1 顺序存储结构

4.4.2 链式存储结构

4.5 二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现 ★★★★

4.5.1 二叉树的遍历

遍历二叉树是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访问的含义很广，可以是对结点做各种处理，包括输出结点的信息，对结点进行运算和修改等。遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础，遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列。由于二叉树的每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR） 和后序（LRN）三种遍历算法，其中"序"指的是根结点在何时被访问。

4.5.2 先序遍历

/**
 * 迭代实现（借助栈）
 */
public List<Integer> preorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while(node != null || !stack.empty()) {
        while(node != null) {
            list.add(node.val);
            stack.push(node);
            // 访问左孩子
            node = node.left;
        }
        node = stack.pop();
        // 访问右孩子
        node = node.right;
    }
    return list;

}

// 先序遍历II（迭代）
template<typename T, typename VST>
void travPreII(BinNodePosi<T> x, VST &v) {
    Stack<BinNodePosi<T>> S;
    S.push(x);
    while (!S.empty()) {
        x = S.pop();
        v(x->data);
        // 右孩子后访问，先入栈
        if (x->rc) S.push(x->rc);
        if (x->lc) S.push(x->lc);
    }
}

// 先序遍历III（迭代）
// 与中序遍历大致相同，不同在于把访问结点操作放在入栈操作之前
template<typename T, typename VST>
void travPreIII(BinNodePosi<T> x, VST &v) {
    Stack<BinNodePosi<T>> S;
    while (true) {
        // 左侧链入栈
        while (x) {
            v(x->data);
            S.push(x);
            x = x->lc;
        }
        // 栈为空时，所有节点处理完毕
        if (S.empty()) break;
        // x 的左子树为空转向右子树
        x = S.pop();
        x = x->rc;
    }
}

// 先序遍历IV（迭代）
template<typename T, typename VST>
void travPreIV(BinNodePosi<T> x, VST &v) {
    Stack<BinNodePosi<T>> S;
    while (true) {
        // 访问子树x的左侧链，右子树入栈缓存
        while (x) {
            v(x->data);
            // 栈内只保存右孩子
            if (x->rc) S.push(x->rc);
            x = x->lc;
        }
        if (S.empty()) break;
        // 弹出下一子树
        x = S.pop();
    }
}

4.5.3 中序遍历

/**
 * 迭代实现（借助栈的非递归实现）
 */
public List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.empty()) {
        // 一路压入最后一个子树的左孩子
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        list.add(node.val);
        // 若该节点有右孩子，则下一步压入其右孩子
        node = node.right;
    }
    return list;
}

// 中序遍历II（迭代）
template<typename T, typename VST>
void travInII(BinNodePosi<T> x, VST &v) {
    // 因 Stack 没有编写析构函数函数，在循环中调用会出问题
    // 兼容方法是将下列的的声明写成 auto S = new Stack<BinNodePosi<T>>()
    // 重点不是在学习C++语法，这里暂时先搁置
    Stack<BinNodePosi<T>> S;
    while (true) {
        // 左侧链入栈
        while (x) {
            S.push(x);
            x = x->lc;
        }
        // 栈为空时，所有节点处理完毕
        if (S.empty()) break;
        // x 的左子树为空，或者已经被访问，此时可以直接访问 x
        x = S.pop();
        v(x->data);
        // 转向右子树
        x = x->rc;
    }
}

4.5.4 后序遍历

/**
 * 后续遍历栈方式
 * 需要增加一个节点记录，用于记录上次出栈的节点
 * 1、如果栈顶元素非空且左节点存在，将其入栈，重复该过程。
 *    若不存在则进入第2步（该过程和中序遍历一致）
 * 2、判断上一次出栈节点是否当前节点的右节点，或者当前节
 *    点是否存在右节点，满足任一条件，将当前节点输出，并
 *    出栈。否则将右节点压栈。跳至第1步
 */
public List<Integer> postorderTraversal2(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    TreeNode lastNode = null;
    while (node != null || !stack.empty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.peek();
        if (node.right == null || node.right == lastNode) {
            lastNode = stack.pop();
            list.add(node.val);
            node = null;
        } else {
            node = node.right;
        }
    }
    return list;
}

// 后序遍历III（迭代）
template<typename T, typename VST>
void travPostIII(BinNodePosi<T> x, VST &v) {
    Stack<BinNodePosi<T>> S;
    if (x) S.push(x);
    while (!S.empty()) {
        // x 指向当前节点
        // 栈顶不为 x 的父节点时，必为其右兄弟，此时需要处理右兄弟所在的子树
        BinNodePosi<T> t;
        if ((t = S.top()) != x->parent) {
            while (t) {
                // 若左侧链节点有右孩子，先入栈缓存起来
                if (t->rc) S.push(t->rc);
                // 优先向左，处理左侧链，不得已才转向右侧
                if (t->lc) {
                    S.push(t->lc);
                    t = t->lc;
                } else {
                    t = t->rc;
                }
            }
        }
        // 弹出栈顶更新 x，这里的 x 为上一次迭代中 x 的 parent
        // x 的左右子树为空，或者已经被访问，此时可以直接访问
        x = S.pop();
        v(x->data);
    }
}

4.5.5 三种遍历算法的关系

4.5.6 层序遍历

4.5.7 由遍历序列构造二叉树

  1. 由先序序列和中序序列构造二叉树

    由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树 。 在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。 如此递归地进行下去，便能唯一地确定这棵二叉树。

    例如，求先序序列（CABCDEFGHI）和中序序列（BCAEDGHFI）所确定的二叉树。

    首先，由先序序列可知 A 为二叉树的根结点。中序序列中 A 之前的 EC 为左子树的中序序列，EDGHFI 为右子树的中序序列。然后由先序序列可知 B 是左子树的根结点，D 是右子树的根结点。 以此类推，就能将剩下的结点继续分解下去，最后得到的二叉树如图所示。

    由先序序列和中序序列构造二叉树

    由先序序列和中序序列构造二叉树

  2. 由后序序列和中序序列构造二叉树

    二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

  3. 由层序序列和中序序列构造二叉树

    由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树 。层序遍历的第一个节点即是树的根节点，通过该根节点在中序遍历中可以划分出左右两颗子树的中序序列，再通过与子树中序序列元素对比，将层序序列分成两棵子树的层序序列，然后对两棵子树的层序序列和中序序列分别进行上述递归，最后可得到一棵二叉树。

需要注意的是，若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。

4.6 线索二叉树的基本概念与构造方法 ★★

4.6.1 线索二叉树的基本概念

4.6.2 线索二叉树的构造方法

4.7 树与二叉树的应用：二叉排序树；二叉平衡树；哈夫曼树与哈夫曼编码 ★★★★★

4.7.1 二叉排序树（BST）

二叉排序树（Binary Sort Tree）又称二叉查找树

  1. 二叉排序树的定义

    二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

    • 若它的左子树不空，则左子树上所有结点的值均小千它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大千它的根结点的值；
    • 它的左、右子树也分别为二叉排序树。

    二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉 树时可以得到一个结点值递增的有序序列。

4.7.2 平衡二叉树（AVL 树）

  1. 平衡二叉树的定义

    为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时， 要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树 。定义结点左子树与右子树的高度差为该结点的平衡因子， 则平衡二叉树结点的平衡因子的值只可能是 -1、0 或 1。

    因此，平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：

    • 左子树和右子树的高度差的绝对值不超过 1；
    • 左子树和 右子树也是平衡二叉树。

    图 (a) 所示是平衡二叉 树，图 (b) 所示是不平衡的二叉树。结点中的值为该结点的平衡因子。

    平衡二叉树和不平衡的二叉树

    平衡二叉树和不平衡的二叉树

  2. 平衡二叉树的插入

    二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树 ， 在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

    注意：每次调整的对象都是最小不平衡子树 ，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。下图虚线框内为最小不平衡子树。

    最小不平衡子树示意

    最小不平衡子树示意

    平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径 上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列 4 种情况：

    1. LL 型失衡调整（右单旋转）：由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。

      如图所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

      右单旋转调整 LL 型失衡

      右单旋转调整 LL 型失衡

    2. RR 型失衡调整（左单旋转）：由于在结点 A 的右孩子（R）的右子树（R）上插入了新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡 ，需要一次向左的旋转操作。 将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树，如图所示。

      左单旋转调整 RR 型失衡

      左单旋转调整 RR 型失衡

    3. LR 型失衡调整（先左后右双旋转）：由于在 A 的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后把该 C 结点向右上旋转提升到 A 结点的位置，如图所示。（简言之，先在失衡节点左孩子处左旋转，然后在失衡节点处右旋转）

      先左后右双旋转调整 LR 型失衡

      先左后右双旋转调整 LR 型失衡

    4. RL 型失衡调整（先右后左双旋转）：由于在 A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点 的位置，然后把该 C 结点向左上旋转提升到 A 结点的位置，如图所示。（简言之，先在失衡节点右孩子处右旋转，然后在失衡节点处左旋转）

      先右后左双旋转调整 RL 型失衡

      先右后左双旋转调整 RL 型失衡

    注意：失衡类型为 LR 和 RL 型时，新结点究竟是插入 C 的左子树还是插入 C 的右子树不影响旋转过程，上述是以插入 C 的左子树中为例。

    假设关键字序列为 {15, 3, 7, 10, 9, 8}，通过该序列生成平衡二叉树的过程如图所示。 图 (d) 插入 7 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的右子树， 故执行 LR 型失衡调整，先左后右双旋转，调整后的结果如图 (e) 所示。图 (g) 插入 9 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的左子树，故执行 LL 型失衡调整，右单旋转，调整后的结果如图 (h) 所示。图 (i) 插入 8 后导致不平衡，最小不平衡子树的根为 7，插入位置为其右孩子的左子树，故执行 RL 型失衡调整，先右后左双旋转，调整后的结果如图 (j) 所示。

    平衡二叉树的生成过程

    平衡二叉树的生成过程

    ❓ 输入数据序列为（10, 30, 40, 20, 15, 25）。请按输入序列构造二叉平衡树，给出每添加一个节点后平衡二叉树的调整结果。 
    // 1.插入节点 10，无失衡节点
10

// 2.插入节点 30，无失衡节点 
10
  \
   30

// 3.插入节点 40，结点 10 发生失衡，失衡类型为 RR，进行左单旋转调整
10                            
  \                       30
   30       ---->        /  \ 
     \                 10    40
      40

// 4.插入节点 20，无失衡节点
     30
    /  \
  10    40
    \
     20

// 5.插入节点 15，结点 10 发生失衡，失衡类型为 RL，进行先右后左双旋转调整
     30                      30
    /  \                    /  \                      30
  10    40                10    40                   /  \
    \            ---->      \           ---->      15    40
     20                      15                   /  \
    /                          \                10    20
  15                            20

// 6.插入节点 25，节点 30 发生失衡，失衡类型为 LR，进行先左后右双旋转调整
       30                       30         
      /  \                     /  \                   20
    15    40                 20    40                /  \
   /  \          ---->      /  \        ---->      15    30
 10    20                 15    25                /     /  \
         \               /                      10    25    40
          25           10

  3. 平衡二叉树的删除

    与平衡二叉树的插入操作类似，以删除结点 w 为例来说明平衡二叉树删除操作的步骤：

    • 用二叉排序树的方法对结点 w 执行删除操作。
    • 从结点 w 开始，向上回溯，找到第一个不平衡的结点 z（即最小不平衡子树）；y 为结点 z 的高度最高的孩子结点；x 是结点 y 的高度最高的孩子结点。
    • 然后对以 z 为根的子树进行平衡调整，其中 x、y 和 z 可能的位置有 4 种情况：
      • y 是 z 的左孩子，x 是 y 的左孩子（LL 型失衡，右单旋转）；
      • y 是 z 的左孩子，x 是 y 的右孩子（LR 型失衡，先左后右双旋转）；
      • y 是 z 的右孩子，x 是 y 的右孩子（RR 型失衡，左单旋转）；
      • y 是 z 的右孩子，x 是 y 的左孩子（RL 型失衡，先右后左双旋转）。

    这四种情况与插入操作的调整方式一样。不同之处在于，插入操作仅需要对以 z 为根的子树进行平衡调整；而删除操作就不一样，先对以 z 为根的子树进行平衡调整，如果调整后子树的高度减 1，则可能需要对 z 的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减1）。

    以删除下图 (a) 的结点 32 为例，由于 32 为叶结点，直接删除即可，向上回溯找到第一个不 平衡结点 44 （即为 z），z 的高度最高的孩子结点为 78（即为 y），y 的高度最高的孩子结点为 50（即为 x），满足 RL 失衡情况，先右后左双旋转，调整后的结果如图 (c) 所示。

    平衡二叉树的删除

    平衡二叉树的删除

4.7.3 哈夫曼树和哈夫曼编码

  1. 哈夫曼树的定义

    在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根 到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度（WPL），记为 $\small \mathrm{WPL} = \sum\limits_{i=1}^{n} w_i l_i$。式中，$\small w_i$ 是第 i 个叶结点所带的权值，$\small l_i$ 是该叶结点到根结点的路径长度。

    在含有 n 个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。例如，下图中的 3 棵二叉树都有 4 个叶子结点 a、b、c、d，分别带权 7、5、2、4。

    具有不同带权长度的二叉树

    具有不同带权长度的二叉树

    它们的带权路径长度分别为：

    （a）WPL = 7×2 + 5×2 + 2×2 + 4×2 = 36

    （b）WPL = 4×2 + 7×3 + 5×3 + 2×1 =46

    （c）WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35

    其中，图中（c）树的 WPL 最小。可以验证，它恰好为哈夫曼树。

  2. 哈夫曼树的构造

    给定 n 个权值分别为 $\small w_1,w_2,\dots,w_n$ 的结点，构造哈夫曼树的算法描述如下：

    • ① 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。
    • ② 构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
    • ③ 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
    • ④ 重复步骤 ② 和 ③，直至 F 中只剩下一棵树为止。

    从上述构造过程中可以看岀哈夫曼树具有如下特点：

    • 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大 。
    • 构造过程中共新建了n - 1 个结点（双分支结点），因此哈夫曼树的结点总数为 2n - 1。
    • 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

    例如，权值 {7, 5, 2, 4} 的哈夫曼树的构造过程如图所示。

    哈夫曼树的构造过程

    哈夫曼树的构造过程

  3. 哈夫曼编码

    在数据通信中，若对每个字符用相等长度的二进制位表示 ，称这种编码方式为固定长度编码。 若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短 ，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

    若任何一个编码都不是其他编码的前缀，则称这样的编码为前缀编码。例如：设计字符 A、B 和 C 对应的编码 0、101 和 100 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。例如，码串 00101100 可被唯一地翻译为 0，0，101 和 100。另举反例：如果再将字符 D 的编码设计为 00，此时 0 是 00 的前缀，那么这样的码串的前两位就无法唯一翻译 。

    由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列 ，其中边标记为 0 表示“转向左孩子”，标记为 1 表示“转向右孩子”。下图所示为一个由哈夫曼树构造哈夫曼编码的示例， 矩形方块表示字符及其出现的次数。

    由哈夫曼树构造哈夫曼编码

    由哈夫曼树构造哈夫曼编码

    这棵哈夫曼树的 WPL 为：WPL = 1×45 + 3×(13+12+16) + 4×(5+9) = 224。此处的 WPL 可视为最终编码得到二进制编码的长度，共 224 位。若采用 3 位固定长度编码，则得到的二进制编码长度为 300 位，因此哈夫曼编码共压缩了 25% 的数据。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

    注意：0 和 1 究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的， 所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同（深度也可能不同），但 WPL 必然相同且是最优的，如下图。

    相同节点可构造不同哈夫曼树

    相同节点可构造不同哈夫曼树

5. 图

5.1 图的基本概念和术语 ★★

5.1.1 图的定义

图（Graph） G 由顶点集 V 和边集 E 组成，记为G = (V, E)，其中 V 表示图 G 中顶点的有限非空集；E 表示图 G 中顶点之间的关系（边）集合。若 $\small$ $\small \mathrm{V={v_1, v_2, \dots, v_n}}$，则用 $\small \mathrm{|V|}$ 表示图 G 中顶点的个数；$\small \mathrm{E= {(u,v)|u \in V, v \in V}}$，用 $\small \mathrm{|E|}$ 表示图 G 中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集 V —定非空，但边集 E 可以为空，此时图中只有顶点而没有边。

5.1.2 图的基本概念和术语

  1. 有向图

    若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 <v,w>，其中 v，w 是顶点，v 称为弧尾，w 称为弧头，<v, w> 称为从 v 到 w 的弧，也称 v 邻接到 w。

    下图 (a) 所示的有向图 $\small \mathrm{G_1}$ 可表示为：

    • $\small \mathrm{ G_1=(V_1, E_1) }$
    • $\small \mathrm{ V_1={l,2,3 } }$
    • $\small \mathrm{ E_1={&lt;1,2&gt;,&lt;2,1&gt;,&lt;2, 3&gt;} }$

  2. 无向图

    若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v, w) 或 (w, v)。可以说 v 和 w 互为邻接点。边 (v, w) 依附于 v 和 w，或称边 (v, w) 和 v，w 相关联。

    下图 (b) 所示的无向图 $\small \mathrm{G_2}$ 可表示为：

    • $\small \mathrm{G_2=(V_2,E_2)}$
    • $\small \mathrm{V_2={1,2,3,4}}$
    • $\small \mathrm{E_2={(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}}$

    图的示例

    图的示例

  3. 简单图、多重图

    一个图 G 如果满足：① 不存在重复边；② 不存在顶点到自身的边，那么称图 G 为简单图。 上图中 $\small \mathrm{G_1}$ 和 $\small \mathrm{G_2}$ 均为简单图。若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图 G 为多重图。多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

  4. 完全图(也称简单完全图)

    对于无向图，$\small \mathrm{|E|}$ 的取值范围为 0 到 $\small n(n-1)/2$，有 $\small n(n -1)/2$ 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。

    对于有向图，$\small \mathrm{|E|}$ 的取值范围为 0 到 $\small n(n-1)$，有 $\small n(n-1)$ 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图 $\small \mathrm{G_2}$ 为无向完全图，而 $\small \mathrm{G_3}$ 为有向完全图。

  5. 子图

    设有两个图 $\small \mathrm{G = (V, E)}$ 和 $\small \mathrm{G'=(V',E')}$，若 $\small \mathrm{V'}$ 是 $\small \mathrm{V}$ 的子集，且 $\small \mathrm{E'}$ 是 $\small \mathrm{E}$ 的子集，则称 $\small \mathrm{G'}$ 是 $\small \mathrm{G}$ 的 子图。若有满足 $\small \mathrm{V(G')=V(G)}$ 的子图 $\small \mathrm{G'}$，则称其为 $\small \mathrm{G}$ 的生成子图。上图 $\small \mathrm{G_3}$ 为 $\small \mathrm{G_1}$ 的子图。

    注意：并非 $\small \mathrm{V}$ 和 $\small \mathrm{E}$ 的任何子集都能构成 $\small \mathrm{G}$ 的子图，因为这样的子集可能不是图，即 $\small \mathrm{E}$ 的子集中的某些边关联的顶点可能不在这个 $\small \mathrm{V}$ 的子集中。

  6. 连通、连通图和连通分量

    在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量，在下图 (a )中，图 $\small \mathrm{G_4}$ 有 3 个连通分量如图 (b) 所示。假设一个图有 n 个顶点，如果边数小 于 n - 1，那么此图必是非连通图。

    无向图及其连通分量

    无向图及其连通分量

    ❓ 思考，如果含 n 个顶点的无向图是非连通图，那么最多可以有多少条边？

    无向图非连通情况下边最多的情况，由 n - 1 个顶点构成一个完全图，此时再任意加入一条边则变成连通图。 故 n 个顶点的非连通图最多可以有 $\mathrm{\frac{(n - 1)(n-2)}{2}}$ 条边。

  7. 强连通图、强连通分量

    在有向图中，如果有一对顶点 v 和 w，从 v 到 w 和从 w 到 v 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，有向图 $\small \mathrm{G_1}$ 的强连通分量如下图所示。

    图 $\small \mathrm{G_1}$的强连通分量

    图 $\small \mathrm{G_1}$的强连通分量

    注意：在无向图中讨论连通性，在有向图中讨论强连通性。

    ❓ 思考，假设一个有向图有 n 个顶点，且是强连通图，那么最少需要有多少条边？

    有向图强连通情况下边最少的情况，至少需要 n 条边，构成一个环路。

  8. 生成树、生成森林

    连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n - 1 条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。图 $\small \mathrm{G_2}$ 的一个生成树如图所示。

    图 $\small \mathrm{G_1}$ 的一个生成树

    图 $\small \mathrm{G_1}$ 的一个生成树

    注意：区分极大连通子图和极小连通子图。极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图 。

  9. 顶点的度、入度和出度

    在无向图中，顶点 v 的度是指依附于顶点 v 的边的条数，记为 TD(v)。在上述无向图 $\small \mathrm{G_2}$ 中，每个顶点的度均为 3。对于具有 n 个顶点、e 条边的无向图，$\small \mathrm{\sum\limits_{i=1}^{n}TD(v_i)=2e}$，即无向图的全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联。

    在有向图中，顶点 v 的度分为入度和出度，入度是以顶点 v 为终点的有向边的数目，记为 ID(v)；而出度是以顶点 v 为起点的有向边的数目，记为 OD(v)。在上述有向图 $\small \mathrm{G_1}$ 中，顶点 2 的出度为 2，入度为 1。顶点 v 的度等于其入度与出度之和，即 TD(v) = ID(v) + OD(v)。对于具有 n 个顶点、e 条边的有向图，$\small \mathrm{\sum \limits_{i=1}^{n}ID(v_i) = \sum \limits_{i=1}^{n}OD(v_i) = e}$，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。

  10. 边的权和网

    在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值，可以表示从一个顶点到另一个顶点的距离或耗费。这种边上带有权值的图称为带权图，也称网。

  11. 稠密图、稀疏图

    边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 G 满足 $\small \mathrm{|E| &lt; |V|log|V|}$ 时，可以将 G 视为稀疏图。

  12. 路径、路径长度

    顶点 $\small v_p$ 到顶点 $\small v_q$ 之间的一条路径是指顶点序列 $\small {v_p, v_{i1}, v_{i2}, \dots, v_{im}, v_q}$，当然关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同时，路径称为回路或环。若一个图有 n 个顶点，并且有大于 n - 1 条边，则此图一定有环。

  13. 简单路径、简单回路（简单环）

    在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

  14. 距离

    从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。

  15. 有向树

    一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树。

5.2 图的存储结构：邻接矩阵、邻接表、逆邻接表 ★★★

5.2.1 邻接矩阵

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

若图 $\small G =(V, E)$ 的节点数为 n，则其邻接矩阵 $\small A$ 为 $\small n × n$ 的二维数组。将 $\small G$ 的顶点编号为 $\small v_1, v_2, \dots, v_n$。邻接矩阵 $\small A$ 满足如下性质：

$$ \small { A[i][j] = \begin{cases} 1 & 若(v_i, v_j) 或 <v_i, v_j> ~\in E \ 0 & 反之\end{cases} } $$

对于带权图而言，若顶点 $\small v_i$ 和 $\small v_j$ 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值 $\small w_{ij}$，若不相连，则用 $\small \infty$ 代表这两个顶点之间不存在边：

$$ \small { A[i][j] = \begin{cases} w_{ij} & 若(v_i, v_j) 或 <v_i, v_j> ~\in E \ \infty & 反之\end{cases} } $$

有向图、无向图和网对应的邻接矩阵示例如图所示。

有向图、无向图及网的邻接矩阵

有向图、无向图及网的邻接矩阵

图的邻接矩阵存储结构定义如下：

#define MaxVertexNum 100 // 顶点数目的最大值
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType;    // 带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];               // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum] ; // 邻接矩阵，边表
    int vexnum, arcnum;                         // 图的当前顶点数和弧数
}MGraph;

图的邻接矩阵存储表示法具有以下特点：

  • ① 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。参考：2.8 特殊矩阵的压缩存储
  • ② 对于无向图，邻接矩阵的第 i 行（或第 i 列）非零元素（或非 $\small \infty$ 元素）的个数正好是顶点 $\small v_i$ 的度 $\small TD(v_i)$。
  • ③ 对于有向图，邻接矩阵的第 i 行非零元素（或非 $\small \infty$ 元素）的个数正好是顶点 $\small v_i$ 的出度 $\small OD(v_i)$；第 i 列非零元素（或非 $\small \infty$ 元素）的个数正好是顶点 $\small v_i$ 的入度 $\small ID(v_i)$。
  • ④ 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
  • ⑤ 稠密图适合使用邻接矩阵的存储表示。
  • ⑥ 设图 G 的邻接矩阵为 $\small A$，$\small A^n$ 的元素 $\small A^n[i][j]$ 等于由顶点 $\small v_i$ 到顶点 $\small v_j$ 的长度为 n 的路径的数目。

注意：

  • ① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）。
  • ② 当邻接矩阵的元素仅表示相应边是否存在时，EdgeType 可采用值为 0 和 1 的枚举类型。
  • ④ 邻接矩阵表示法的空间复杂度为 $\small O(n^2)$，其中 n 为图的顶点数 $\small |V|$。

5.2.2 邻接表和逆邻接表

  1. 领接表

    当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

    所谓邻接表，是指对图 G 中的每个顶点 $\small v_i$ 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 $\small v_i$ 的边（对于有向图则是以顶点 $\small v_i$ 为尾的弧），这个单链表就称为顶点 $\small v_i$ 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点，如图所示。

    顶点表和边表结点结构

    顶点表和边表结点结构

    顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。

    无向图的邻接表实例如下图所示：

    无向图邻接表表示法实例

    无向图邻接表表示法实例

    有向图的邻接表实例如下图所示：

    有向图邻接表表示法实例

    有向图邻接表表示法实例

    图的邻接表存储结构定义如下：

    #define MaxVertexNum 100  // 图中顶点数目的最大值

typedef struct VNode{  // 顶点表结点
    VertexType data;   // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];

typedef struct ArcNode{      // 边表结点
    int adjvex;              // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
    //InfoType info;         // 和边相关的信息，例如网的边权值
}ArcNode;

typedef struct{
    AdjList vertices;   // 邻接表
    int vexnum, arcnum; // 图的顶点数和弧数
} ALGraph;              // ALGraph 是以邻接表存储的图类型

    图的邻接表存储方法具有以下特点：

    • ① 若 G 为无向图，则所需的存储空间为 $\small O(|V|+2|E|)$（每条边在邻接表中出现了两次）；若 G 为有向图，则所需的存储空间为 $\small O(|V| + |E|)$。
    • ② 对于稀疏图，采用邻接表表示将极大地节省存储空间。
    • ③ 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。但是，若要确定给定的两个顶点间是否存在边，需要在相应结点对应的边表中查找另一结点 ，效率较低。
    • ④ 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数 ；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。
    • ⑤ 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

  2. 逆邻接表

    逆邻接表与邻接表结构相同，区别在于逆邻接表中第 i 个单链表中的结点表示的是以顶点 $\small v_i$ 为头的弧，整个单链表为顶点 $\small v_i$ 的入边构成的表。通过邻接表可以快速求解顶点的出度，而通过逆邻接表则可以快速求解顶点的入度。

5.2.3 十字链表

TODO

5.2.4 邻接多重表

TODO

5.2.3 图的基本操作

5.3 遍历算法：深度优先搜索算法和广度优先搜索算法 ★★★★

5.3.1 深度优先搜索算法（DFS）

  1. 算法介绍

    深度优先搜索（Depth-First-Search, DFS）类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。

    它的基本思想如下：首先访问图中某一起始顶点 $\small v$，然后由 $\small v$ 岀发，访问与 $\small v$ 邻接且未被访问的任一顶点 $\small w_1$，再访问与 $\small w_1$ 邻接且未被访问的任一顶点 $\small w_2$…… 重复上述过程。当不能再继续向下访问时，退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

    一般情况下，其递归形式的算法十分简洁，算法过程如下：

    bool visited[MAX_VERTEX_NUM];     // 访问标记数组

void DFSTraverse(Graph G){        // 对图 G 进行深度优先遍历
    for(v = 0; v < G.vexnum; ++v)
        visited[v]=FALSE;         // 初始化已访问标记数据
    for(v = 0; v < G.vexnum; ++v) // 本代码中是从 v = 0 开始遍历
        if(!visited[v]){
            DFS(G,v);
        }
}

void DFS(Graph G,int v){   // 从顶点 v 出发，深度优先遍历图 G
    visit(v);              // 访问顶点 v
    visited[v] = TRUE;     // 设置已访问标记
    for(w = FirstNeighbor(G,v); w >= 0 ; w = NextNeighbor(G, v, w))
        if(!visited[w]){   // w 为 v 的尚未访问的邻接顶点
            DFS(G, w);
        }
}

    以下图所示无向图为例，深度优先搜索的过程：

    • 首先访问 a，并置 a 访问标记；
    • 然后访问与 a 邻接且未被访问的顶点 b，置 b 访问标记；
    • 然后访问与 b 邻接且未被访问的顶点 d，置 d 访问标记；
    • 此时 d 已没有未被访问过的邻接点，故返回上一个访问过的顶点 b，访问与其邻接且未被访问的顶点 e，置 e 访问标记……

    以此类推，直至图中所有的顶点都被访问一次。遍历结果为 abdehcfg。

    Untitled

    注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的 DFS 序列和 BFS 序列是唯一的，基于邻接表的遍历所得到的 DFS 序列和 BFS 序列是不唯一的。

  2. 性能分析

    DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为 $\small O(|V|)$。

    遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。

    • 以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为 $\small O(|V|)$，故总的时间复杂度为 $\small O(|V|^2)$。
    • 以邻接表表示时，查找所有顶点的邻接点所需的时间为 $\small O(|E|)$，访问顶点所需的时间为 $\small O(|V|)$，总的时间复杂度为 $\small O(|V| + |E|)$。

  3. 深度优先的生成树和生成森林

    与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，对连通图调用 DFS 才能产生深度优先生成树，否则产生的将是深度优先生成森林，如下图所示。与 BFS 类似，基于邻接表存储的深度优先生成树是不唯一的 。

    图的深度优先生成森林

    图的深度优先生成森林

5.3.1 广度优先搜索算法（BFS）

  1. 算法介绍

    广度优先搜索（Breadth-First-Search, BFS）类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点 $\small v$，接着由 $\small v$ 出发，依次访问 $\small v$ 的各个未访问过的邻接顶点 $\small w_1, w_2, \dots, w_i$，然后依次访问 $\small w_1, w_2, \dots, w_i$ 的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。 Dijkstra 单源最短路径算法和 Prim 最小生成树算法也应用了类似的思想。

    换句话说，广度优先搜索遍历图的过程是以 $\small v$ 为起始点，由近至远依次访问和 $\small v$ 有路径相通且路径长度为 1，2，··· 的顶点。广度优先搜索是一种分层的查找过程 ，每向前走一步可能访问一 批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

    广度优先搜索算法的伪代码如下:

    bool visited[MAX_VERTEX_NUM];     // 访问标记数组

void BFSTraverse(Graph G){        // 对图 G 进行广度优先遍历
    for(i = 0; i < G.vexnum; ++i)
        visited[i] = FALSE;       // 访问标记数组初始化
    InitQueue(Q);                 // 初始化辅助队列 Q
    for(i = 0; i < G.vexnum; ++i) // 从 0 号顶点开始遍历
        if(!visited[i])           // 对每个连通分量调用一次 BFS
            BFS(G,i);             // vi 未访问过，从 vi 开始 BFS
}

void BFS(Graph G, int v){ // 从顶点 v 出发，广度优先遍历图 G
    visit(v);             // 访问初始顶点 v
    visited[v] = TRUE;    // 对 v 做已访问标记
    Enqueue(Q, v);        // 顶点 v 入队列 Q
    while(!isEmpty(Q)){
        DeQueue(Q, v);    // 顶点 v 出队列
        for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))  //检测 v 所有邻接点
            if(!visited[w]){     // w 为 v 的尚未访问的邻接顶点
               visit(w);         // 访问顶点 w
               visited[w] =TRUE; // 对 w 做已访问标记
               EnQueue(Q, w);    // 顶点 w 入队列
            }
    }
}

    下面通过实例演示广度优先搜索的过程，给定图 G 如图所示。

    Untitled

    • 假设从 a 结点开始访问，a 先入队。
    • 此时队列非空，取岀队头元素 a，由于 b、c 与 a 邻接且未被访问过，于是依次访问 b、c，并将 b、c 依次入队。
    • 队列非空，取出队头元素 b，依次访问与 b 邻接且未被访问的顶点 d、e，并 将 d、e 入队（注意：a 与 b 也邻接，但 a 已置访问标记，故不再重复访问)。
    • 此时队列非空，取出队头元素 c，访问与 c 邻接且未被访问的顶点 f、g，并 将 f、g 入队。
    • 此时，取出队头元素 d，但与 d 邻接且未被访问的顶点为空， 故不进行任何操作。
    • 继续取出队头元素 e，将 h 放入队列……
    • 最终取出队头元素 h 后，队列为空，从而循环自动跳出。遍历结果为 abcdefgh。

    从上例不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了 图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。

  2. 性能分析

    无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列 Q， n 个顶点均需入队一次，在最坏的情况下，空间复杂度为 $\small O(|V|)$。

    采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为 $\small O(|V|)$，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为 $\small O(|E|)$，算法总的时间复杂度为 $\small O(|V| + |E|)$。

    采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为 $\small O(|V|)$，故算法总的时间复杂度为 $\small O(|V|^2)$。

  3. 广度优先生成树

    在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树，如图所示。需 要注意的是，给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

    图的广度优先生成树

    图的广度优先生成树

  4. BFS 算法求解单源最短路径问題

    若图 $\small G = (V, E)$ 为非带权图，定义 $\small d(u, v)$ 为顶点 $\small u$ 到顶点 $\small v$ 的最短路径的长度，若从 $\small u$ 到 $\small v$ 没有通路，则 $\small d(u, v) = \infty$。

    使用 BFS，可以求解一个满足上述定义的非带权图的单源最短路径问题 ，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

    BFS 算法求解单源最短路径问题的算法如下：

    void BFS_MIN_Distance(Graph G, int u){
    // d[i] 表示从 u 到 i 结点的最短路径
    for(i = 0; i < G.vexnum; ++i)
        d[i] = ∞; // 初始化路径长度
    visited[u] = TRUE; 
    d[u] = 0;
    EnQueue(Q, u);
    while(!isEmpty(Q)){ // BFS 算法主过程
        DeQueue(Q, u);  // 队头元素 u 出队
        for(w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
            if(!visited[w]){       // w 为 u 的尚未访问的邻接顶点
                visited[w] = TRUE; // 设已访问标记
                d[w] = d[u] + 1;   // 路径长度加 1
                EnQueue(Q, w) ;    // 顶点 w 入队
            }
    }
}

5.4 应用：最小生成树；最短路径，拓扑排序和关键路径 ★★★★★

5.4.1 最小生成树（Prim、Kruskal）

在一个连通图的所有生成树中，各边的代价之和最小的那棵生成树称为该连通图的最小生成树（Minimum-Spanning-Tree, MST）。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树性质：假设 G = ( V, E ) 是一个带权连通无向图，U 是顶点集 V 的一个非空子集。若 ( u, v ) 是一条具有最小权值的边，其中 u ∈ U，v ∈ V - U，则必存在一棵包含边 ( u, v ) 的最小生成树。

Prim 算法和 Kruskal 算法是两个构造最小生成树的算法。

  1. Prim 算法

    Prim （普里姆）算法的执行非常类似于寻找图的最短路径的 Dijkstra 算法。两者主要区别在于选择下一个待加入到点集的点时，Dijkstra 算法选择到源点最近的点，而 Prim 选择到已选点集最近的点。

    Prim算法构造最小生成树的过程如图所示。初始时从图中任取一顶点（如顶点 1）加入树 T，此时树中只含有一个顶点，之后选择一个与当前 T 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 T，每次操作后 T 中的顶点数和边数都增 1。以此类推，直至图中所有的顶点都并入 T，得到的 T 就是最小生成树。此时 T 中必有 n - 1 条边。

    Prim 算法构造最小生成树的过程

    Prim 算法构造最小生成树的过程

    Prim 算法的步骤如下：

    • 假设 $\small G = { V, E }$ 是连通图，其最小生成树 $\small T = ( U , E_T )$，$\small E_T$ 是最小生成树中边的集合。
    • 初始化：向空树 $\small T = ( U , E_T )$ 中添加图 $\small G = { V, E }$ 的任一顶点 $\small u_0$，使 $\small U = { u_0 }$，$\small E_T = \emptyset$

    。

    • 循环，重复下列操作直至 $\small U = V$：从图 $\small G$ 中选择满足 $\small { (u, v)|u \in U, v \in V-U }$ 且具有最小权值的边 $\small (u,v)$，加入树 $\small T$，置 $\small U = U \cup {v}$，$\small E_T = E_T \cup {(u, v)}$。

    Prim 算法的简单实现如下：

    void Prim(G, T){
	T=∅;                   // 初始化空树
	U= {w};                // 添加任一顶点w
	while ( (V-U) != ∅) {  // 若树中不含全部顶点
		// 设 (u, v) 是使 u∈U 与 v∈(V-U)，且权值最小的边
		T=T∪{(u,v)};         // 边归入树
		U=U∪{v};             // 顶点归入树
	}
}

    Prim 算法的时间复杂度为 $\small O(|V|^2)$，不依赖于边数 $\small |E|$，因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度，但增加了实现的复杂性。

  2. Kruskal 算法

    与 Prim 算法从顶点开始扩展（即选点）最小生成树不同 ，Kruskal（克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边（即选边）来构造最小生成树的方法。

    Kruskal 算法构造最小生成树的过程如图所示。初始时为只有 n 个顶点而无边的非连通图 $\small T= {V, {}}$，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 $\small T$ 中不同的连通分量上（即加入此边不会构成环），则将此边加入 $\small T$，否则舍弃此边而选择下一条权值最小的边。 以此类推，直至 $\small T$ 中所有顶点都在一个连通分量上。

    Kruskal 算法构造最小生成树的过程

    Kruskal 算法构造最小生成树的过程

    Kruskal 算法的步骤如下：

    • 假设 $\small G = { V, E }$ 是连通图，其最小生成树 $\small T = ( U , E_T )$。
    • 初始化：$\small U = V$，$\small E_T = \emptyset$。即每个顶点构成一棵独立的树，$\small T$ 此时是一个仅含 $\small |V|$ 个顶点的森林。
    • 循环，重复下列操作直至 $\small T$ 是一棵树：按 $\small G$ 的边的权值递增顺序依次从 $\small E - E_T$ 中选择一条边，若这条边加入 $\small T$ 后不构成回路，则将其加入 $\small E_T$，否则舍弃，直到 $\small E_T$ 中含有 n - 1条边。

    Kruskal 算法的简单实现如下：

    void Kruskal(V, T){
	T=V;                // 初始化树T,仅含顶点
	numS=n;             // 连通分量数
	while(numS > 1){    // 若连通分量数大于 1
		// 从 E 中取岀权值最小的边 (v,u)
		if(v和u属于T中不同的连通分量){
			T=T∪{(v,u)};    // 将此边加入生成树中
	    numS--;         // 连通分量数减 1
		}
	}
}

    根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。

    通常在 Kruskal 算法中，采用堆来存放边的集合，因此每次选择最小权值的边只需 $\small O(log|E|)$ 的时间。此外，由于生成树 $\small T$ 中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述 $\small T$，从而构造 $\small T$ 的时间复杂度为 $\small O(|E|log|E|)$。因此，Kruskal 算法适合于边稀疏而顶点较多的图。

5.4.2 最短路径（Dijkstra、Floyd）

当图是带权图时，把从一个顶点 $\small v_0$ 到图中其余任意一个顶点 $\small v_i$ 的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质 ，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图 G 的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra （迪杰斯特拉）算法求解；二是求每对顶点间的最短路径，可通过 Floyd （弗洛伊德）算法来求解。

  1. Dijkstra 算法求单源最短路径问题

    Dijkstra 算法设置一个集合 S 记录已求得的最短路径的顶点，初始时把源点 $\small v_0$ 放入S，集合 S 每并入一个新顶点 $\small v_i$，都需要对与 $\small v_i$ 相连但还未并入 S 的顶点更新其与源点 $\small v_0$ 的最短路径长度。

    在构造的过程中还设置了两个辅助数组：

    • dist[ ]：记录从源点 $\small v_0$ 到其他各顶点当前的最短路径长度，它的初态为：若从 $\small v_0$ 到 $\small v_i$ 有弧，则 dist [i] 为弧上的权值；否则置dist[i] 为 ∞。
    • path[ ]：path[i] 表示从源点到顶点 $\small v_i$ 之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 $\small v_0$ 到顶点 $\small v_i$ 的最短路径。其初值为：如果从 $\small v_0$ 到 $\small v_i$ 有弧，则 Path[i] 为 $\small v_0$；否则为 -1。

    假设从顶点 0 出发，即 $\small v_0 = 0$，集合 S 最初只包含顶点 0，邻接矩阵 arcs 表示带权有向图，arcs[i][j] 表示有向边 ＜i, j＞ 的权值，若不存在有向边则 arcs[i][j] 为 ∞。

    Dijkstra 算法的步骤如下：

    • 初始化：
      • 将源点 $\small v_0$ 加到 S 中；
      • 将 $\small v_0$ 到各个终点的最短路径长度初始化为权值，即 $\small dist[i] = arcs[v_0][v_i],~(v_i \in V-S)$；
      • 如果从 $\small v_0$ 和顶点 $\small v_i$ 之间有弧，则将 $\small v_i$ 的前驱置为 $\small v_0$，即 $\small path[i]$ 为 $\small v_0$；否则为 path[i] = -1。
    • 执行以下操作，直到所有的顶点都包含在 S 中，循环 $\small n - 1$ 次：
      • 选择下一条最短路径的终点 $\small v_k$，使得 $\small dist[k]=Min{dist[i]|v_i \in V-S}$；
      • 将 $\small v_k$ 加到 S 中；
      • 根据条件更新从 $\small v_0$ 出发到集合 $\small V-S$ 上任一顶点的最短路径的长度，若条件 $\small dist[k]+arcs[k][i] &lt; dist[i]$ 成立（即通过 $\small v_k$ 中转，$\small v_i$ 到 $\small v_0$ 的路径更短），则更新 $\small \small dist[i] = dist[k]+arcs[k][i]$ ，同时更改 $\small v_i$ 的前驱为 $\small v_k$，即 $\small path[i] = k$。

    例如，下图应用 Dijkstra 算法求从顶点 1 出发至其余顶点的最短路径的过程，如表所示。算法执行过程的说明如下。

    应用Dijkstra算法图

    应用Dijkstra算法图

    从 $\small v_1$ 到各终点的 dist 值和最短路径的求解过程

    从 $\small v_1$ 到各终点的 dist 值和最短路径的求解过程

    • 初始化：集合 $\small S$ 初始为 $\small {v_1}$， $\small v_1$ 可达 $\small v_2$ 和 $\small v_5$，不可达 $\small v_3$ 和 $\small v_4$，因此 $\small dist[]$ 数组各元素的初值依次设置为 $\small dist[2]=10,~dist[3]=\infty,~dist [4]=\infty,~dist[5]=5$； $\small path[]$ 数组各元素的初值为 $\small path[2]=1,~path[3]=-1,~path[4]=-1,~path[5]=1$。

      更新后：$\small S = {v_1};~~dist[]={0,10,\infty,~\infty,5};~~path[]={-1,1,-1,-1,~1}$

    • 第一轮：选出最小值 $\small dist[5]$，将顶点 $\small v_5$ 并入集合 $\small S$，即此时已找到 $\small v_1$ 到 $\small v_5$ 的最短路径。 当 $\small v_5$ 加入 $\small S$ 后，从 $\small v_1$ 到集合 $\small V-S$ 中可达顶点的最短路径长度可能会产生变化。因此需要更新 $\small dist[]$ 数组。$\small v_5$ 可达 $\small v_2$，因 $\small v_1\to v_5 \to v_2$ 的距离 8 比 $\small dist[2]=10$ 小，更新 $\small dist[2]=8,~path[2]=5$；$\small v_5$ 可达 $\small v_3$， $\small v_1\to v_5 \to v_3$ 的距离为14，更新 $\small dist[3]=14,~path[3]=5$；$\small v_5$ 可达 $\small v_4$，$\small v_1\to v_5 \to v_4$ 的距离为 7，更新 $\small dist[4]=7,~path[4]=5$。

      更新后：$\small S={v_1,~v_5};~~dist[]={0,~8,~14,~7,~5};~~path[]={-1,~5,~5,~5,~1}$

    • 第二轮：选出最小值 $\small dist[4]$，将顶点 $\small v_4$ 并入集合 $\small S$。继续更新 $\small dist[]$ 数组。$\small v_4$ 不可达 $\small v_2$（没有边直接相连），$\small dist[2]$ 不变；$\small v_4$ 可达 $\small v_3$，$\small v_1\to v_5 \to v_4 \to v_3$ 的距离 13 比 $\small dist[3]$ 小，故更新 $\small dist[3]=13,~path[3]=4$。

      更新后：$\small S={v_1,~v_5,~v_4};~~dist[]={0,~8,~13,~7,~5};~~path[]={-1,~5,~4,~5,~1}$

    • 第三轮：选出最小值 $\small dist[2]$，将顶点 $\small v_2$ 并入集合 $\small S$。继续更新 $\small dist[]$ 数组。$\small v_2$ 可达 $\small v_3$，$\small v_1\to v_5 \to v_2 \to v_3$ 的距离9比 $\small dist[3]$ 小，更新 $\small dist[3]=9,~path[3]=2$。

      更新后：$\small S={v_1,~v_5,~v_4,~v_2};~~dist[]={0,~8,~9,~7,~5};~~path[]={-1,~5,~2,~5,~1}$

    • 第四轮：选出唯一最小值 $\small dist[3]$，将顶点 $\small v_3$ 并入集合 $\small S$，此时全部顶点都已包含在 $\small S$ 中。

      更新后：$\small S={v_1,~v_5,~v_4,~v_2,~v_1};~~dist[]={0,~8,~9,~7,~5};~~path[]={-1,~5,~2,~5,~1}$

    显然，Dijkstra 算法是基于贪心策略的。 使用邻接矩阵表示时，时间复杂度为 $\small O(|V|^2)$，空间复杂度 $\small O(|V|)$。使用带权的邻接表表示时，虽然修改 $\small dist[]$ 的时间可以减少，但由于在 $\small dist[]$ 中选择最小分量的时间不变，时间复杂度仍为 $\small O(|V|^2)$。

    值得注意的是，边上带有负权值时，Dijkstra 算法并不适用。若允许边上带有负权值，则在与 $\small S$（已求得最短路径的顶点集，归入 $\small S$ 内的结点的最短路径不再变更）内某点（记为 $\small a$）以负边相连的点（记为 $\small b$）确定其最短路径时，其最短路径长度加上这条负边的权值结果可能小于 $\small a$ 原先确定的最短路径长度，而此时 $\small a$ 在 Dijkstra 算法下是无法更新的。例如，对于下图所示的带有负权的有向图，利用 Dijkstra 算法不一定能得到正确的结果。

    边上带有负权值的有向带权图

    边上带有负权值的有向带权图

  2. Floyd 算法求各顶点之间最短路径问题

    求所有顶点之间的最短路径问题描述如下：已知一个各边权值均大于 0 的带权有向图，对任意两个顶点 $\small v_i \ne v_j$，要求求出 $\small v_i$ 与 $\small v_j$ 之间的最短路径和最短路径长度。

    对以上问题有两种方法可以求解：其一是分别以图中的每个顶点为源点共调用 n 次 Dijkstra 算法；其二是采用下面介绍的 Floyd 算法。两种算法的时间复杂度均为 $\small O(n^3)$，但后者形式上较简单。

    Floyd 算法仍然使用带权的邻接矩阵 arcs 来表示有向图 G，求从顶点 $\small v_i$ 到 $\small v_j$ 的最短路径。算法的实现要引入以下辅助的数据结构：

    • 二维数组 $\small path[i][j]$：最短路径上顶点 $\small v_j$ 的前一顶点的序号。
    • 二维数组 $\small dist[i][j]$：记录顶点 $\small v_i$ 和 $\small v_j$ 之间的最短路径长度。

    Floyd 算法的基本思想是：递推产生一个 n 阶方阵序列 $\small dist^{(-1)},dist^{(0)},\dots,dist^{(k)},\dots,dist^{(n-1)}$，其中 $\small dist^{(k)}[i][j]$ 表示绕行第 $\small k$ 个顶点，从顶点 $\small v_i$ 到顶点 $\small v_j$ 的路径长度。

    初始时，对于任意两个 顶点 $\small v_i$ 和 $\small v_j$，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以 $\small \infty$ 作为它们之间的最短路径长度。即 $\small dist^{(-1)}[i][j]=arcs[i][j]$。

    以后逐步尝试在原路径中加入顶点 $\small k~(k=0,1,\dots,n-1)$ 作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了 ，则以此新路径代替原路径。即 $\small dist^{(k)}[i][j]=min{dist^{(k-1)}[i][j],~dist^{(k-1)}[i][k]+dist^{(k-1)}[k][j]}$。

    算法步骤如下：

    • 将 $v_i$ 到 $\small v_j$ 的最短路径长度初始化，即 $\small dist[i][j]=arcs[i][j]$；若 $\small v_i$ 与 $\small v_j$ 之间有弧，$\small path[i][j]=i$，否则，$\small path[i][j]=-1$。
    • 在 $\small v_i$ 和 $\small v_j$ 间加入顶点 $\small v_0$，比较 $\small (v_i, v_j)$ 和 $\small (v_i, v_0, v_j)$ 的路径长度，取其中较短者作为 $v_i$ 到 $\small v_j$ 的最短路径。即 $\small dist[i][j]=min{dist[i][j], dist[i][0] + dist[0][k]}$。若 $\small (v_i, v_0, v_j)$ 更短，还需更新 $\small path[i][j]=path[0][j]$。
    • 依次类推，在 $\small v_i$ 和 $\small v_j$ 间加入顶点 $\small v_k$，若 $\small (v_i, \dots, v_k)$ 和 $\small (v_k, \dots, v_j)$ 分别是从 $\small v_i$ 到 $\small v_k$ 和从 $\small v_k$ 到 $\small v_j$ 的最短路径，则将 $\small (v_i, \dots, v_k, \dots, v_j)$ 和已经得到的从 $\small v_i$ 到 $\small v_j$ 的最短路径相比较，其长度较短者便是从 $\small v_i$ 到 $\small v_j$ 的最短路径。若 $\small (v_i, \dots, v_k, \dots, v_j)$ 更短，还需更新 $\small path[i][j]=path[k][j]$。这样，经过 n 次比较后，最后求得的 $\small dist^{(n-1)}[i][j]$ 必是从 $\small v_i$ 到 $\small v_j$ 的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

      • Q：若 $\small (v_i, \dots, v_k, \dots, v_j)$ 更短，更新 $\small path[i][j]$ 时，令 $\small path[i][j]=k$ 是否可行？为什么要使 $\small path[i][j]=path[k][j]$？

        不可行，因为节点 $v_k$在 $v_i$ 和 $v_j$ 最短路径的上的位置不确定，算法结束后通过 path 数组无法得到完整的路径信息。

        令 $\small path[i][j]=path[k][j]$，即 $\small path[i][j]$ 保存的是 $v_i$ 和 $v_j$ 最短路径上离终点 $v_j$ 最近的节点的索引。在算法结束后通过 $\small path[i][j]$可获得路径上倒数第二个节点，记为 $\small v_{n}$，再通过 $\small path[i][n]$ 获取路径上倒数第三个节点，记为 $\small v_m$，再通过 $\small path[i][m]$ 获取下一个节点…… 依次类推，最后到达 $\small path[i][i]$。将沿路遍历到的节点反转便是 $v_i$ 和 $v_j$ 最短路径信息：$i \to \dots \to m \to n \to j$。

        从这里我们可以看到， $v_i$ 和 $v_j$ 的最短路径信息中包含着 $v_i$ 到 $v_m$、 $v_i$ 到 $v_n$ 等的最短路径信息。

    下图所示为带权有向图 G 及其邻接矩阵。应用 Floyd 算法求所有顶点之间的最短路径长度的过程如表所示。算法执行过程的说明如下。

    带权有向图G及其邻接矩阵

    带权有向图G及其邻接矩阵

    每一对顶点 $\small i$ 和 $\small j$ 之间的最短路径 $\small path[i][j]$（表中用 $\small Path[i][j]$ 表示）以及其路径长度 $\small dist[i][j]$（表中用 $\small D[i][j]$ 表示）在求解过程中的变化如表所示（高亮为每轮相比上一轮修改之处）。

    Floyd 算法求解过程中最短路径及其路径长度的变化

    Floyd 算法求解过程中最短路径及其路径长度的变化

    Floyd 算法的时间复杂度为 $\small O(|V|^3)$，空间复杂度 $\small O(|V|^2)$。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。

    Floyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

5.4.3 拓扑排序

  1. AOV 网

    一个无环的有向图称作有向无环图（Directed Acycline Graph），简称 DAG 图。有向无环图是描述一项工程或系统的进行过程的有效工具。通常把计划、施工过程、生产流程、程序流程等都当成一个工程。除了很小的工程外，一般的工程都可分为若干个称做活动（Activity）的子工程， 而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。

    若用 DAG 图表示一个工程，其顶点表示活动，用有向边 $\small &lt;V_i, V_j&gt;$ 表示活动 $\small V_i$ 必须先于活动 $\small V_j$ 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络（Activity On Vertex Network），记为 AOV 网。在 AOV网中，活动 $\small V_i$ 是活动 $\small V_j$ 的直接前驱，活动 $\small V_j$ 是活动 $\small V_i$ 的直接后继，这种前驱和后继关系具有传递性，且任何活动 $\small V_i$ 不能以它自己作为自己的前驱或后继。

    在 AOV 网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。显然，这是荒谬的。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的 AOV 网应首先判定网中是否存在环。检测的办法是对有向图的顶点进行拓扑排序，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网中必定不存在环。

  2. 拓扑排序

    在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

    • ① 每个顶点出现且只出现一次。
    • ② 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

    或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。每个 A0V 网都有一个或多个拓扑排序序列。

    对一个A0V网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

    • ① 从 A0V 网中选择一个没有前驱的顶点并输出。
    • ② 从网中删除该顶点和所有以它为起点的有向边 。
    • ③ 重复 ① 和 ② 直到当前的 A0V 网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

    下图所示为拓扑排序过程的示例。每轮选择一个入度为 0 的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 {1, 2, 4, 3, 5}。

    有向无环图的拓扑排序过程

    有向无环图的拓扑排序过程

    拓扑排序算法的实现如下：

    bool TopologicalSort(Graph G){
    InitStack(S);               // 初始化栈，存储入度为 0 的顶点
    for(int i = 0; i < G.vexnum; i++){
        if(indegree[i] == 0)
            Push(S, i);         // 将所有入度为 0 的顶点进栈
    }
    int count = 0;              // 计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){         // 栈不空，则存在入度为 0 的顶点
        Pop(S, i);              // 栈顶元素出栈
        print[count++] = i;     // 输出顶点 i
        for(p = G.vertices[i].firstarc; p; p = p->nextarc){
            // 将所有 i 指向的顶点的入度减 1，并且将入度减为 0 的顶点压入栈 S
            v = p->adjvex;
            if (!(--indegree[v]))
                Push(S, v);     // 入度为 0，则入栈
        }
    }
    if(count < G.vexnum)
        return false;           // 排序失败，有向图中有回路
    else
        return true;            // 拓扑排序成功
}

    由于输出每个顶点的同时还要删除以它为起点的边，故采用邻接表存储时拓扑排序的时间复杂度为 $\small O(|V|+|E|)$，采用邻接矩阵存储时拓扑排序的时间复杂度为 $\small O(|V|^2)$。此外，利用深度优先遍历也可实现有向无环图的拓扑排序。

    对一个 AOV 网，如果采用下列步骤进行排序，则称之为逆拓扑排序:

    • ① 从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出。
    • ② 从网中删除该顶点和所有以它为终点的有向边。
    • ③ 重复 ① 和 ② 直到当前的 AOV 网为空。

    用拓扑排序算法处理 AOV 网时，应注意以下问题：

    • 入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点 ，工程可以从这个顶点所代表的活动开始或继续。
    • 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一 个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
    • 由于 AOV 网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

5.4.4 关键路径

  1. AOE 网

    在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络（Activity On Edge），简称 AOE 网。AOE 网和 AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE 网中的边有权值；而 AOV 网中的边无权值，仅表示顶点之间的前后关系。

    AOE 网具有以下两个性质：

    • ① 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
    • ② 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

    在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始；网中也仅存在一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。

  2. 关键路径和关键活动

    在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

    完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

    下面给出在寻找关键活动时所用到的几个参量的定义。

    1. 事件 $\small v_k$ 的最早发生时间 $\small ve(k)$

      进入事件 $\small v_k$ 的每一活动都结束，$\small v_k$ 才可能发生，故 $\small ve(k)$ 是指从源点 $\small v_1$ 到顶点 $\small v_k$ 的最长路径长度。事件 $\small v_k$ 的最早发生时间决定了所有从 $\small v_k$ 开始的活动能够开工的最早时间。可用下面的递推公式来计算：

      • $\small ve(源点)=0$；
      • $\small ve(k) = Max{ve(j) + Weight(v_j,v_k)}$， $\small v_k$ 为 $\small v_j$ 的任意后继， $\small Weight（v_j, v_k)$ 表示 $\small &lt;v_j, v_k&gt;$ 上的权值。

      计算 $\small ve()$ 值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算：

      • ① 初始时，令 $\small ve[1 \dots n] = 0$；
      • ② 输出一个入度为 0 的顶点 $\small v_j$ 时，计算它所有直接后继顶点 $\small v_k$ 的最早发生时间，若 $\small ve[j] + Weight(v_j, v_k) &gt; ve[k]$， 则 $\small ve[k] = ve[j] + Weight(v_j, v_k)$。以此类推，直至输出全部顶点。

    2. 事件 $\small v_k$ 的最迟发生时间 $\small vl(k)$

      它是指在不推迟整个工程完成的前提下，即保证它的后继事件 $\small v_j$ 在其最迟发生时间 $\small vl(j)$ 能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算：

      • $\small vl(汇点)=ve(汇点)$；
      • $\small vl(k) = Min{vl(j) - Weight(v_j,v_k)}$，$\small v_k$ 为 $\small v_j$ 的任意前驱。

      计算 $\small vl(k)$ 值时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。在上述拓扑排序中，增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下：

      • ① 初始时，令 $\small ve[1 \dots n] = ve[n]$；
      • ② 栈顶顶点 $\small v_j$ 出栈，计算其所有直接前驱顶点 $\small v_k$ 的最迟发生时间 ，若 $\small vl[j] - Weight(v_k, v_j) &lt; ve[k]$，则 $\small vl[k] = vl[j] - Weight(v_k, v_j)$。以此类推，直至输出全部栈中顶点。

    3. 活动 $\small a_i=~&lt;v_j, v_k&gt;$ 的最早开始时间 $\small e(i)$

      它是指该活动弧的起点所表示的事件的最早发生时间。只有事件 $\small v_j$ 发生了，活动 $\small a_i$ 才能开始。所以活动 $\small a_i$ 的最早开始时间等于事件 $\small v_j$ 的最早发生时间 ，即 $\small e(i)=ve(j)$。

    4. 活动 $\small a_i=~&lt;v_j, v_k&gt;$ 的最迟开始时间 $\small l(i)$

      它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差 。活动 $\small a_i$ 的开始时间需保证不延误事件 $\small v_k$ 的最迟发生时间。所以活动 $\small a_i$ 的最晚开始时间 $\small l(i)$ 等于事件 $\small v_k$ 的最迟发生时间减去活动 $\small a_i$ 的持续时间，即 $\small l(i) = vl(j)-Weight(j, k)$。

    5. 一个活动 $\small a_i$ 的最迟开始时间 $\small l(i)$ 和其最早开始时间 $\small e(i)$ 的差额 $\small d(i) = l(i) - e(i)$

      它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 可以 $\small a_i$ 拖延的时间。若一个活动的时间余量为 0，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 $\small l(i) - e(i) = 0$ 即 $\small l(i) = e(i)$ 的活动 $\small a_i$ 是关键活动。

  3. 关键路径求解

    求关键路径的算法步骤如下：

    • ① 从源点出发，令 $\small ve(源点)=0$，按拓扑有序求其余顶点的最早发生时间 $\small ve()$。
    • ② 从汇点出发，令 $\small vl(汇点)=ve(汇点)$，按逆拓扑有序求其余顶点的最迟发生时间 $\small vl()$。
    • ③ 根据各顶点的 $\small ve()$ 值求所有弧（每个活动 $\small a_i$）的最早开始时间 $\small e()$。
    • ④ 根据各顶点的 $\small vl()$ 值求所有弧（每个活动 $\small a_i$）的最迟开始时间 $\small l()$。
    • ⑤ 求 AOE 网中所有活动的差额 $\small d()$，找出所有 $\small d() = 0$ 即 $\small l(i) = e(i)$ 的活动构成关键路径。

    求解关键路径的过程

    求解关键路径的过程

    上图所示为求解关键路径的过程，简单说明如下：

    • ① 求 $\small ve()$：初始 $\small ve(1)=0$，在拓扑排序输出顶点过程中，求得
      • $\small ve(2) = 3$
      • $\small ve(3) = 2$
      • $\small ve(4)=max{ve(2) + 2,~ve(3) + 4} = max{5, 6} = 6$
      • $\small ve(5) = 6$
      • $\small ve(6) = max{ve(5) + 1, ve(4) + 2, ve(3) + 3} = max{7, 8, 5} = 8$
    • ② 求 $\small vl()$：初始 $\small vl(6)=ve(6)=8$，在逆拓扑排序出栈过程中，求得
      • $\small vl(5) = 7$
      • $\small vl(4) = 6$
      • $\small vl(3) = min{vl(4)-4, vl(6)-3} = min{2, 5} = 2$
      • $\small vl(2) = min{vl(5)-3, vl(4)-2} = min{4, 4} = 4$
      • $\small vl(1)$ 必然为 0 而无须再求
    • ③ 弧的最早开始时间 $\small e()$ 等于该弧的起点的顶点的 $\small ve()$，求得结果如上表所示。
    • ④ 弧的最迟开始时间 $\small l()$ 等于该弧的终点的顶点的 $\small vl()$ 减去该弧持续的时间，求得结果如上表所示。
    • ⑤ 根据 $\small l(i) - e(i) = 0$ 找到关键活动，得到的关键路径为 $\small (v_1, v_3, v_4, v_6)$。

    对于关键路径，需要注意以下两点：

    • 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
    • 网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动 才能达到缩短工期的目的。

6. 查找

6.1 查找的基本概念；静态查找与动态查找 ★

6.1.1 查找的基本概念

6.1.2 静态查找与动态查找

TODO：动态查找表

6.2 顺序查找、折半查找、索引查找 ★★

6.2.1 顺序查找

6.2.2 折半查找

6.2.3 索引查找（分块查找）

6.3 哈希查找（哈希函数的基本构造方法，解决地址冲突的基本策略）★★★

6.3.1 哈希查找（散列查找）的基本概念

如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是哈希查找法（Hash Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。

  • 哈希函数：又称散列函数，一个把查找表中的关键字映射成该关键字对应的哈希（散列）地址的函数，记为 Hash(key)= Addr（这里的地址可以是数组下标、索引或内存地址等）。

    哈希函数可能会把两个或两个以上的不同关键字映射到同一地址 ，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的哈希函数应尽量减少这样的冲突；另一 方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

  • 哈希表：一个有限连续的地址空间，用以存储按哈希函数计算得到相应地址的数据记录。通常哈希表的存储空间是一个一维数组，地址是数组的下标。

理想情况下，对哈希表进行查找的时间复杂度为 O(1)，即与表中元素的个数无关。

6.3.2 哈希函数的基本构造方法

在构造哈希函数时，必须注意以下几点：

  • 哈希函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于哈希表的大小或地址范围。
  • 哈希函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
  • 哈希函数应尽量简单，能够在较短的时间内计算出任一关键字对应的地址。

下面介绍常用的哈希函数。

  1. 直接定址法

    直接取关键字的某个线性函数值为哈希地址，哈希函数为 $\small H(key) = key$ 或 $\small H(key) = a×key + b$。式中，a 和 b 是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

  2. 除留余数法

    这是一种最简单、最常用的方法，假定哈希表表长为 m，取一个不大于 m 但最接近或等于 m 的质数P，利用哈希函数 $\small H(key) = key~%~p$ 把关键字转换成哈希地址。

    除留余数法的关键是选好 p，使得每个关键字通过该函数转换后等概率地映射到哈希表上的任一地址，从而尽可能减少冲突的可能性。

  3. 数字分析法 设关键字是 r 进制数(如十进制数)，而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为哈希地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的哈希函数。

  4. 平方取中法

    取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。适用于关键字的每位取值都不够均匀或均小于哈希地址所需的位数。

  5. 折叠法

    将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去最高位的进位）作为哈希地址。适合于哈希地址的位数较少，而关键字的位数较多，且难于直接从关键字中找到取值较分散的几位。

  6. 随机数法

    选择一随机函数，取关键字的随机值作为哈希地址，即 $\small H(key)=random(key)$ 其中 random 为随机函数，通常用于关键字长度不等的场合。

6.3.3 解决地址冲突的基本策略

  1. 开放定址法

    所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为 $\small H_i = (H(key) + d_i) ~% m$。式中，$\small H(key)$ 为哈希函数；$\small i=0,1,2,\dots,k(k \le m - 1)$；$\small m$ 表示哈希表表长；$\small d_i$ 为增量序列。

    取定某一增量序列后，对应的处理方法就是确定的。增量序列通常有以下 4 种取法：

    1. 线性探测法

      当 $\small d_i = 0, 1, 2, \dots,m-1$ 时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址时，下一个探测地址是表首地址 0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

      线性探测法可能使第 i 个哈希地址的同义词存入第 i + 1 个哈希地址，这样本应存入第 i + 1 个哈希地址的元素就争夺第 i + 2 个哈希地址的元素的地址…… 从而造成大量元素在相邻的哈希地址上“聚集”（或堆积）起来，大大降低了查找效率。

    2. 平方探测法

      当 $\small d_i = 1^2, -1^2, 2^2, -2^2, \dots,k^2, -k^2$ 时，称为平方探测法（二次探测法），其中 $\small k ≤ m / 2$，哈希表长度 $\small m$ 必须是一个可以表示成 $\small 4k + 3$ 的素数。

      平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。

    3. 双散列法

      当 $\small d_i=Hash_2(key)$ 时，称为双散列法。需要使用两个散列函数，当通过第一个散列函数 $\small H(key)$ 得到的地址发生冲突时，则利用第二个散列函数 $\small Hash2(key)$ 计算该关键字的地址增量。

      它的具体散列函数形式为：$\small H_i = (H(key) + i×Hash_2(key))~%m$。初始探测位置 $\small H_0 = H(key)%~m$。$\small i$ 是冲突的次数，初始为 0。在再散列法中，最多经过加 m - 1 次探测就会遍历表中所有位置，回到 $\small H_0$ 位置。

    4. 伪随机序列法

      当 $\small d_i=$ 伪随机数序列时，称为伪随机序列法。可以避免“聚集“现象，但不能保证一定找到不发生冲突的地址。

    注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同哈希地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是执行多次删除后，表面上看起来哈希表很满，实际上有许多位置未利用，因此需要定期维护哈希表，要把删除标记的元素物理删除。

  2. 再哈希法

    $\small H_i = RH_i(key)~~~~i=1,2,\dots,k$。$\small RH_i$ 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

  3. 链地址法（拉链法）

    为了避免与非同义词发生冲突，可以把所有同义词存储在一个线性链表中，这个线性链表由其哈希地址唯一标识。假设哈希地址为 i 的同义词链表的头指针存放在哈希表的第 i 个单元中，因而查找、插入和删除操作主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    例如，关键字序列为 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，哈希函数 $\small H(key)=key~%~13$，用链地址法处理冲突，建立的哈希表如图所示。

    链地址法处理冲突时的哈希表

    链地址法处理冲突时的哈希表

  4. 建立公共溢出区

    将哈希表分为基本表和溢出表两部分，当关键字通过哈希函数计算出的地址在基本表中发生冲突时，将其填入溢出表。

6.3.4 哈希表的查找及其分析

哈希表的查找过程与构造哈希表的过程基本一致。对于一个给定的关键字 key，根据哈希函数可以计算出其哈希地址，执行步骤如下：

  • ① 初始化：Addr = Hash(key);
  • ② 检测查找表中地址为 Addr 的位置上是否有记录
    • 若无记录，返回查找失败；
    • 若有记录，比较它与 key 的值，若相等，则返回查找成功标志，否则执行步骤 ③。
  • ③ 用给定的处理冲突方法计算下一个散列地址，并把 Addr 置为此地址，转入步骤 ②。

例如，关键字序列 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79} 按散列函数 H(key) = key % 13 和线性探测处理冲突构造所得的散列表 L 如图所示。

用线性探测法得到的散列表 L

用线性探测法得到的散列表 L

给定值 84 的查找过程为：首先求得哈希地址 H(84) = 6，因 L[6] 不空且 L[6] ≠ 84，则找第 一次冲突处理后的地址 $\small \mathrm{H}_1=(6+1)~%16 = 7$（注意这里是对表长 16 求余，不再是对 13，否则无法探测全表），而 L[7] 不空且 L[7] ≠ 84,则找第二次冲突处理后的地址 $\small \mathrm{H}_2=(6+2)%~16 = 8$，L[8] 不空且 L[8] = 84，查找成功，返回记录在表中的序号 8。

给定值 38 的查找过程为：先求哈希地址 H(38) = 12，L[12] 不空且 L[12] ≠ 38，则找下一 地址 $\small \mathrm{H}_1=(12+1)~%~16 = 13$，由于 L[13] 是空记录，故表中不存在关键字为 38 的记录。

查找各关键字的比较次数如图所示。

查找各关键字的比较次数

查找各关键字的比较次数

平均查找长度为：ASL = (1×6 + 2×1 + 3×3 + 4×1 + 9×1) / 12 = 2.5。

对同一组关键字，设定相同的哈希函数，则不同的处理冲突的方法得到的哈希表不同 ，它们的平均查找长度也不同。

从哈希表的查找过程可见：

  • 虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量哈希表的查找效率的度量。

  • 哈希表的查找效率取决于三个因素：哈希函数、处理冲突的方法和装填因子。

    哈希表的装填因子一般记为 $\small \alpha$，定义为一个表的装满程度，即 $\alpha = \frac{表中记录数n}{哈希表长度m}$。

    哈希表的平均查找长度依赖于散列表的装填因子 $\small \alpha$，而不直接依赖于表中记录数 n 或表长度 m。直观地看，$\small \alpha$ 越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

6.4 各种查找算法的时间复杂度和空间复杂度 ★★

TODO

7. 排序

7.1 排序的基本概念 ★

7.2 插入排序 ★★★

7.2.1 直接插入排序

7.2.2 折半插入排序

7.3 简单选择排序 ★★★

TODO

7.4 希尔排序 ★★★

从前面的分析可知，直接插入排序算法的时间复杂度为 OS?),但若待排序列为“正序”时, 其时间复杂度可提高至0(”)，由此可见它更适用于基本有序的排序表和数据量不大的排序表 。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

TODO

希尔排序示例

希尔排序示例

用 Java 语言实现的希尔排序如下：

// 希尔排序
// 1. 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。
// 2. 这样可以让一个元素可以一次性地朝最终位置前进一大步。
// 3. 然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，
//    但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
public int[] sortArray(int[] nums) {
    int n = nums.length;
    // step 为步长
    for (int step = n / 2; step >= 1; step /= 2) {
        for (int i = step; i < n; i++) {
            int t = nums[i];
            int j;
            for (j = i; j >= step && t < nums[j - step]; j -= step) {
                nums[j] = nums[j - step];
            }
            nums[j] = t;
        }
    }
    return nums;
}

7.5 快速排序 ★★★★

快速排序的基本思想是基于分治法的：在待排序表 $\small \mathrm{L[1 \dots n]}$ 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 $\small \mathrm{L[1 \dots k-1]}$ 和 $\small \mathrm{L[k+l \dots n]}$，使得 $\small \mathrm{L[1 \dots k-1]}$ 中的所有元素小于 pivot，$\small \mathrm{L[k+l \dots n]}$ 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 $\small \mathrm{L[k]}$ 上，这个过程称为一趟快速排序（或一次划分）。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程 ，下面通过实例来介绍，附设两个指针 i 和 j，初值分别为 low 和 high，取第一个元素 49 为枢轴赋值到变量 pivot。

指针 j 从 high 往前搜索找到第一个小于枢轴的元素 27，将 27 交换到 i 所指位置。

Untitled

指针 i 从 low 往后搜索找到第一个大于枢轴的元素 65，将 65 交换到 j 所指位置。

Untitled

指针 j 继续往前搜索找到小于枢轴的元素 13，将 13 交换到 i 所指位置。

Untitled

指针 i 继续往后搜索找到大于枢轴的元素 97，将 97 交换到 j 所指位置。

Untitled

指针 j 继续往前搜索小于枢轴的元素，直至 i==j。

Untitled

此时，指针 i（指针 j） 之前的元素均小于等于 49，指针 i 之后的元素均大于等于 49，将 49 放在 i 所指位置即其最终位置，经过一趟划分，将原序列分割成了前后两个子序列。

Untitled

按照同样的方法对各子序列进行快速排序，若待排序列中只有一个元素，显然已有序。

Untitled

假设划分算法已知，记为 Partition()，返回的是上述的 k，注意到 $\small \mathrm{L[k]}$ 已在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序，具体的程序结构如下：

void Quicksort(ElemType A[], int low, int high){
    if(low < high) {                             // 递归跳出的条件
        // Partition() 就是划分操作，将表 A[low...high] 划分为满足上述条件的两个子表
        int pivotpos = Partition (A, low, high); // 划分
        Quicksort (A, low, pivotpos - 1);        // 依次对两个子表进行递归排序
        QuickSort(A, pivotpos + 1, high);
    }
}

// 算法的性能主要取决于划分操作的好坏，考研以严蔚敏版本为主
// 假设每次总以当前表中第一个元素作为枢轴来对表进行划分
int Partition (ElemType A[], int low, int high) { // 一趟划分
    ElemType pivot = A[low]; // 将当前表中第一个元素设为枢轴，对表进行划分
    while(low < high) {      // 循环跳出条件
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];    // 将比枢轴小的元素移动到左端
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];    //将比枢轴大的元素移动到右端
    }
    A[low] = pivot; // 枢轴元素存放到最终位置
    return low;     // 返回存放枢轴的最终位置
}

快速排序算法的性能分析如下：

  • 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 $\small \mathrm{O(log_2n)}$；最坏情况下，因为要进行 n - 1 次递归调用，所以栈的深度为 $\small \mathrm{O(n)}$；平均情况下，栈的深度为 $\small \mathrm{O(log_2n)}$，即空间复杂度为 $\small \mathrm{O(log_2n)}$。

  • 时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 n - 1个元素和 0 个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 $\small \mathrm{O(n^2)}$。

    有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头、尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

    在最理想的状态下，即 Partition() 可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 $\small \mathrm{O(nlog_2n)}$。快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，即时间复杂度为 $\small \mathrm{O(nlog_2n)}$。快速排序是所有内部排序算法中平均性能最优的排序算法。

  • 稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。

    例如，表 L = {3, 2, 2}，经过一趟排序后 L = {2, 2, 3}，最终排序序列也是 L = {2, 2, 3}，显然，2 与 2 的相对次序已发生了变化。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。

用 Java 语言实现的快速排序如下：

注意：以下对 pivot 的选取和 i，j 指针的设置与严蔚敏版本不同，仅用于参考，考试时尽量采用严蔚敏版本。

/**
 * 快速排序
 * 1. 从数列中挑出一个元素，称为"基准"（pivot）。
 * 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 *    在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 */
public class QuickSort {
    public void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(Comparable[] arr, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        // 切分
        int j = partition(arr, lo, hi);
        // 将左半部分 arr[lo..j-1] 排序
        sort(arr, lo, j - 1);
        // 将右半部分 arr[j+1, hi] 排序
        sort(arr, j + 1, hi);
    }

    /**
     * 将数组分为 arr[lo..i-1], arr[i], arr[i+1.. hi]
     */
    private int partition(Comparable[] arr, int lo, int hi) {
        // 随机在arr[lo...hi]的范围中, 选择一个数值作为标定点 pivot，保证在数组近乎有序的情况下也能良好完成排序
        swap(arr, lo, (int) (Math.random() * (hi - lo + 1)) + lo);
        Comparable v = arr[lo];
        // 左右扫描指针
        int i = lo + 1;
        int j = hi;
        while (true) {
            // 扫描左右，检查是否结束并交换元素
            // 注意条件，减少等值元素的交换，防止算法时间复杂度退化为 O(n^2)
            while (i <= hi && arr[i].compareTo(v) <= 0) {
                i++;
            }
            while (j >= lo && arr[j].compareTo(v) > 0) {
                j--;
            }
            if (i >= j) {
                // 此时 j 一定指向的是小于或等于的元素
                break;
            }
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }

    private void swap(Comparable[] arr, int i, int j) {
        Comparable e = arr[i];
        arr[i] = arr[j];
        arr[j] = e;
    }
}

7.6 堆排序 ★★★★

堆排序 （Heap Sort）是一种树形选择排序，在排序过程中，将待排序的记录 L[ 1..n] 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

堆的定义如下，n 个关键字序列 L[1...n] 称为堆，当且仅当该序列满足：

  • ① L(i) ≥ L(2i) 且 L(i) ≥ L(2i + 1) 或
  • ② L(i) ≤ L(2i) 且 L(i) ≤ L(2i + 1) $\small (1 \le i \le \left \lfloor n/2 \right \rfloor)$

可以将该一维数组视为一棵完全二叉树，满足条件 ① 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。满足条件 ② 的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。下图所示为一个大根堆。

一个大根堆示意图

一个大根堆示意图

堆排序的思路很简单：首先将存放在 L[l...n] 中的 n 个元素建成初始堆，由于堆本身的特点（以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质 ，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：① 如何将无序序列构造成初始堆？② 输出堆顶元素后，如何将剩余元素调整成新的堆？

堆排序的关键是构造初始堆。n 个结点的完全二叉树，最后一个结点是第 $\small \left \lfloor n/2 \right \rfloor$ 个结点的孩 子。对第 $\small \left \lfloor n/2 \right \rfloor$ 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则两者交换），使该子树成为堆。之后向前依次对各结点 ($\small \left \lfloor n/2 \right \rfloor - 1 \sim 1$) 为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆 ，直到根结点。

如图所示，初始时调整 L(4) 子树，09 < 32，两者交换，交换后满足堆的定义；向前继续调整 L(3) 子树，78 < 左右孩子的较大者 87，交换，交换后满足堆的定义；向前调整 L(2) 子树， 17 < 左右孩子的较大者45，交换后满足堆的定义；向前调整至根结点 L(1)，53 < 左右孩子的较大者 87，交换，交换后破坏了 L(3) 子树的堆，采用上述方法对 L(3) 进行调整，53 < 左右孩子的较大者 78，交换，至此该完全二叉树满足堆的定义。

自下往上逐步调整为大根堆

自下往上逐步调整为大根堆

❓ 已知 7 项数据记录为 (7, 6, 5, 4, 3, 2, 1)。将它调整为小顶堆，给出筛选过程。 
// 初始状态，共有 7 个节点
        7
      /   \
     6     5
    / \   / \
   4   3 2   1 

// 第一个待调整节点序号为 i = 7 / 2 = 3，即值为 5 的节点，对其进行调整，将其与
// 左右孩子较小者（值为 1 的节点）进行交换，交换后以序号 i = 3 的子树已是最小堆，无需继续调整
        7                      7 
      /   \                  /   \
     6     5       -->      6     1  
    / \   / \              / \   / \
   4   3 2   1            4   3 2   5

// 第二个待调整节点序号为 i = 2，即值为 6 的节点，对其进行调整，将其与左右孩子
// 较小者（值为 3 的节点）进行交换，交换后以序号 i = 2 的子树已是最小堆，无需继续调整
        7                      7 
      /   \                  /   \
     6     1       -->      3     1  
    / \   / \              / \   / \
   4   3 2   5            4   6 2   5

// 最后一个待调整节点序号为 i = 1，即值为 7 的节点，对其进行调整，将其与左右孩子
// 较小者（值为 1 的节点）进行交换，交换后以序号 i = 3 的子树不满足最小堆性质，
// 对其继续调整，将其与左右孩子较小者（值为 2 的节点）进行交换。至此，调整结束。
        7                      1                      1 
      /   \                  /   \                  /   \
     3     1       -->      3     7       -->      3     2
    / \   / \              / \   / \              / \   / \
   4   6 2   5            4   6 2   5            4   6 7   5

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将 09 和左右孩子的较大者 78 交换，交换后破坏了 L(3) 子树的堆，继续对 L(3) 子树向 下筛选，将 09 和左右孩子的较大者 65 交换，交换后得到了新堆，调整过程如图所示。

输出堆顶元素后再将剩余元素调整成新堆

输出堆顶元素后再将剩余元素调整成新堆

下面是建立大根堆的算法：

void BuildMaxHeap(ElemType A[], int len) {
    for(int i = len / 2; i > 0; i--)      // 从 i = [n/2] 〜 1，反复调整堆
        HeadAdjust(A, i, len);
}

// 函数 HeadAdjust 将元素 k 为根的子树进行调整
void HeadAdjust(ElemType A[], int k, int len) {
    A[O]=A[k];                            // A[0]暂存子树的根结点
    for(i = 2 * k; i <= len; i *= 2) {    // 沿 key较大的子结点向下筛选
        if(i < len && A[i] < A[i+1]) i++; // 取 key较大的子结点的下标
        if(A[O] >= A[i]) {
            break;                        // 筛选结束
        } else {
            A[k] = A[i];                  // 将 A[i] 调整到双亲结点上
            k = i;                        // 修改 k 值，以便继续向下筛选
        }

    }
    A[k] = A[O]; // 被筛选结点的值放入最终位置
}

调整的时间与树高有关，为 $\small O(h)$。在建含 n 个元素的堆时，关键字的比较总次数不超过 4n，时间复杂度为 $\small O(n)$，这说明可以在线性时间内将一个无序数组建成一个堆。

下面是堆排序算法：

void HeapSort(ElemType A[], int len){
    BuildMaxHeap(A, len);         // 初始建堆
    for(i = len; i > 1; i--){     // n - 1 趟的交换和建堆过程
		    Swap(A[i], A[1]);         // 输出堆顶元素(和堆底元素交换)
		    HeadAdjust(A, 1, i - 1);  // 调整，把剩余的 i - 1 个元素整理成堆
		}
}

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如图所示。

大根堆的插入操作示例

大根堆的插入操作示例

堆排序适合关键字较多的情况。例如，在 1 亿个数中选出前 100 个最大值？首先使用一个大小为 100 的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。 堆排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，所以空间复杂度为 0(1)。

时间效率：建堆时间为 $\small O(n)$，之后有 n - 1 次向下调整操作，每次调整的时间复杂度为 $\small O(h)$，故在最好、最坏和平均情况下，堆排序的时间复杂度为 $\small O(nlogn)$。

稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。例如，表 L = {1, 2, 2}，构造初始堆时可能将 2 交换到堆顶，此时 L = {2, 1, 2}，最终排序序列为 L = {1, 2, 2}，显然，2 与 2 的相对次序已发生变化。

用 Java 语言实现的堆排序如下：

/**
 * 堆排序
 * 1.创建最大堆（Build Max Heap）：将堆所有数据重新排序。
 * 2.最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
 * 3.堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。
 */
public class HeapSort {
    public int[] sort(int[] nums) {
        int n = nums.length;
        // 构建最大堆
        for (int k = n / 2 - 1; k >= 0; k--) {
            sink(nums, k, n);
        }
        while (n > 0) {
            // 将堆顶元素与堆最后一个元素交换，使得堆尾渐渐有序
            swap(nums, 0, --n);
            // 对新的堆顶元素做下层操作
            sink(nums, 0, n);
        }
        return nums;
    }

    /**
     * 下沉操作
     *
     * @param arr 待排序数组
     * @param k   待下沉元素索引
     * @param n   至多能下沉到 n - 1 处，n 及其之后的元素已排好序
     */
    private void sink(int[] arr, int k, int n) {
        while (2 * k + 1 < n) {
            // 选出左右孩子中较大的那个，进行交换
            int j = 2 * k + 1;
            // j + 1 < n，是为了确保右孩子存在
            if (j + 1 < n && arr[j]< arr[j + 1]) {
                j++;
            }
            // 查看交换是否满足堆的性质，不满足就不交换
            if (arr[k] >= arr[j]) {
                break;
            }
            swap(arr, k, j);
            k = j;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int e = arr[i];
        arr[i] = arr[j];
        arr[j] = e;
    }
}

7.7 归并排序 ★★★

TODO：有大题考怎么手动把一组数据排序

2路归并排序示例

2路归并排序示例

7.8 基数排序 ★★★

TODO

基数排序不需要关键字之间的比较

数据结构：链队列，链表，链表元素是队列

LSD

Untitled

MSD

Untitled

7.9 排序算法的比较 ★★

排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
直接选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
二分插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 https://zh.wikipedia.org/zh-cn/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F#%E6%AD%A5%E9%95%B7%E5%BA%8F%E5%88%97 $O(1)$ 不稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(logn)$ 不稳定
基数排序 $O(d(n + r))$ $O(d(n + r))$
n 个记录，d 个关键码，关键码的取值范围为 r $O(d(n + r))$ $O(r)$ 稳定
  • 与待排序列初始有序状态无关：堆排序、归并排序、选择排序、基数排序（一堆乌龟选基友）
  • 不能保证一趟排序后一定有元素放在最终位置上：插入排序、归并排序（茶柜）

8. 算法题要求

其中算法题分为阅读、修改和编写算法三类：

（1）阅读算法：阅读指定算法，回答使用的数据结构、算法实现的功能或执行的结果；

（2）修改算法：阅读指定算法，指出算法的错误并修正；指出算法的不足并改进；按给定功能填写算法空缺部分；

（3）编写算法：根据算法功能要求，选择或者设计合适的数据结构，用程序设计语言编写算法，实现指定功能。

（4）以上皆可分析给定或者设计的算法时空复杂度。

📚 参考书目
  • 《820 计算机专业基础》电子科大知博书店
  • 严蔚敏《数据结构（C 语言版）》、《数据结构题集（C 语言版）》
  • 邓俊辉《数据结构（C++ 语言）》、《数据结构习题解析》
  • [美] Robert Sedgewick / [美] Kevin Wayne 谢路云译《算法（第 4 版）》