【读书笔记】数据结构（C语言版）（第三版）人民邮电出版社

2022/05/02    57 min read

第一章 概论

• 数据：
  • 逻辑结构：数据与数据之间所存在的逻辑关系
  • 存储结构：数据在计算机中的存储结构，体现逻辑结构
  • 运算集合：由为数据定义的所有运算构成，定义在逻辑结构上，实现依赖于存储结构
• 结点：
  • 开始结点：无前驱结点
  • 内部结点：不是开始结点，也不是终端结点
  • 终端结点：无后继结点
• 线性结构：只有一个开始和终端，其余每个结点有且仅有一个前驱和后继
• 非线性结构：
  • 树型结构：一个开始，多个终端，除开始外都有且只有一个前驱
  • 图形结构：多个前驱，多个后继
• 存储结构：
  • 顺序存储：物理位置相邻
  • 链式存储：每个结点有若干个指针
  • 索引存储：根据结点索引号确定存储地址
  • 散列存储：结点 k_i 的存储地址有函数 h(k_i) 确定
• 数据的抽象发展阶段：
  1. 无类型的二进制数：基本数据类型
  2. 基本：用户自定义类型
  3. 自定义：抽象数据类型
• 数据类型：
  • 数据属性
  • 在这些数据上可施加的运算集合
• 算法：求解问题的一种方法或一个过程
  • 特征：有穷性；确定性；输入；输出；可行性
• 时间复杂度：用算法执行过程中基本操作的执行次数来衡量
  • O(1) 常数阶
  • O(log_2n) 对数阶
  • O(n) 线性阶
  • O(n^2) 平方阶
  • O(n^3) 立方阶
  • O(n^k) k 次方阶
  • O(2^n) 指数阶

第二章 线性表及其顺序存储

• 线性表：线性结构
  • 顺序存储：顺序表
  • 链式存储：链式表
  • 实现（边界条件）：
    • 插入：考虑满的情况
    • 删除：考虑空的情况
• 顺序表：结点存储的地址连续
  • 随机访问：只要知道第一个结点，就可以任意访问其余结点
  • 操作：
    • 插入：O(n)：要把新结点后的元素依次前移一个位置
    • 删除：O(n)：要把被删除结点后的元素依次前移一个位置
• 栈：特殊线性表
  • 特点：
    • 只允许在同一端（栈顶或栈底）插入（进栈）和删除（出栈）
    • 后进先出（LIFO）
  • 实现：
    • 顺序存储：顺序栈，用数组表示
    • 链式存储：链式栈
  • 应用：
    • 括号匹配
    • 算术表达式求值：后缀表达式
• 队列：特殊线性表
  • 特点：
    • 插入（进队）和删除（出队）分别在两端（队首或队尾）进行
    • 先进先出（FIFO）
  • 实现：
    • 顺序存储
      • 循环队列：把队首和队尾元素视为相邻
        • 队列满的条件：(rear+1) % MAXSIZE == front
        • 队列空的条件：rear == front
        • 插入删除时指针加 1 时，需增加取模操作
    • 链式存储
• 整数取余或模：
  1. 先求商（整数）：c = a / b
  2. 再求余或模：r = a - cb

第三章 线性表的链式存储

• 链式存储：
  • 用附设指针来体现结点之间的逻辑关系
  • 必须有一个指针指向第一个结点的存储位置，否则各个结点都无法访问
• 单链表：
  • 结构：
    • 存放数据的域
    • 指向该结点后继结点的指针域
  • 无法随机访问，必须从第一个结点开始沿着指针向后遍历
  • 插入删除无需移动结点
  • 插入删除时需考虑结点为第一个结点的情况
• 带头结点的单链表：
  • 头结点：指向第一个实际结点的结点，不存放数据
• 循环单链表：
  • 功能：可从任意结点开始访问到任意结点
  • 实现：最后结点指针域指向第一个结点
  • 当前结点为最后结点的特征：下个元素是第一个元素
  • 增加头结点：带头结点的循环单链表
• 双链表：
  • 结构：
    • 存放数据的域
    • 两个指针分别指向该结点的前驱和后继
  • 第一个结点没有前驱，左指针域为空
  • 最后的结点没有后继，右指针域为空
  • 操作：
    • 插入：
      • 最前面插入
      • 中间插入
      • 最后面插入
    • 删除：
      • 唯一结点
      • 第一个结点
      • 最后结点
      • 中间结点
• 链式栈：特殊单链表
  • 维持一个栈顶指针
• 链式队列：特殊单链表
  • 维持队首队尾两个指针
  • 插入：
    • 空队列插入
    • 非空队列插入
  • 删除：
    • 只有一个结点
    • 不只一个结点

第四章 字符串、数组和特殊矩阵

字符串

• 定义：元素类型为字符的特殊线性表
• 子串：串中任意个连续字符构成的子序列
• 主串：包含子串的串
• 长度：串中所含字符个数
• 位置：字符在串序列中的序号
• 相等：长度相等且对应位置字符都相等
• 实现：
  • 顺序串（顺序存储）：
    • 插入：从新字符往后的元素需向后移动
    • 删除：从被删除字符往后的元素需向前移动
    • 连接
    • 求子串
  • 链式串（链式存储）：
    • 插入：链表插入
    • 删除：链表删除
    • 连接
    • 求子串
• 模式匹配：寻找字符串 p（模式）在字符串 t（正文）中出现的位置
  • 实现：
    • 朴素：用模式中的字符与正文中的字符一一比较
      • 最坏：O(nm)：n、m 分别为模式、正文中的字符数
    • 快速（KMP算法）：
      • 前缀：除最后一个字符外的全部头部组合
      • 后缀：除第一个字符外的全部尾部组合
      1. 先求模式的部分匹配表（前缀后缀最长共有元素长度）
      2. 根据匹配表移动元素
         • 当模式的第一个字符相等时：移动位数 = 已匹配字符数 - 对应匹配值（从匹配表中得）
         • 当模式的第一个字符不相等时：移动位数 = 1 即不考虑匹配表

KMP 算法：

KMP 算法可部分匹配，也可找出全部匹配

正文：BBC_ABCDAB_ABCDABCDABDE 模式：ABCDABD（部分匹配表）（Next 数组）

部分匹配值：0 0 0 0 1 2 0 一一对应，来自于前缀和后缀的最长共有元素个数

1 的得来：ABCDA 前缀为 [A, AB, ABC, ABCD] 后缀为 [BCDA, CDA, CD, A] 共有元素为 A，只有一个，所以为1

前缀：除最后一个字符外全部头部组合 -> [A, AB, ABC, ABCD, ABCDA, ABCDAB] 后缀：除第一个字符外全部尾部组合 -> [BCDABD, CDABD, DABD, ABD, BD, D]

如果第一个字符就不匹配，直接移动一位，不考虑匹配表。 移动位数 = 已匹配字符数 - 对应的部分匹配值

数组

• 定义：
  • 每个元素有一个值和一组下标确定，每个下标对应每个值
  • 数组中的元素数量固定，无法添加和删除，只能访问和改变值
• 实现：顺序存储结构，使用连续的存储空间存储
• 多维数组存储顺序：
  • 按行优先：第一行顺序存储、第二行顺序存储等
  • 按列优先：第一列顺序存储、第二行顺序存储等
• 地址计算：
  • 二维数组：设有二维数组 A[m][n]，共有 m 行、n 列
    • 按行优先：a[i][j] 地址 = 首地址 + (i*n+j) * 单个元素存储空间
    • 按列优先：a[i][j] 地址 = 首地址 + (j*m+i) * 单个元素存储空间
  • 多维数组：设有多维数组 B[m][n][o][p]
    • 按行优先：a[i][j][k][l] 地址 = 首地址 + (i*n*o*p+j*o*p+k*p+l) * 单个元素存储空间
    • 按列优先：a[i][j][k][l] 地址 = 首地址 + (l*o*n*m+k*n*m+j*m+i) * 单个元素存储空间
• 操作：
  • 初始化数组：求出各维 C_i 值，这个值只依赖于各维大小和单个元素存储空间
  • 访问数组元素
  • 赋值给数组元素

特殊矩阵

• 定义：矩阵中包含许多相同值或零
• 压缩存储：
  • 多个相同值元素只分配一个存储空间
  • 值为 0 的元素不分配存储空间
• 对称矩阵：满足 a[i][j] = a[j][i]
  • 方阵：行数和列数相等
  • 对角线以上（i>=j）：a[i][j] 地址 = 首地址 + [i*(i+1)/2+j] * 单个元素存储空间
  • 对角线以上（i<=j）：a[i][j] 地址 = 首地址 + [j*(j+1)/2+i] * 单个元素存储空间
• 三角矩阵：对角线以上或以下的元素值均为 0
  • 下三角矩阵：对角线以上（i>=j）元素均为 0
    • a[i][j] 地址 = 首地址 + [i*(i+1)/2+j] * 单个元素存储空间
  • 上三角矩阵：对角线以上（i<=j）元素均为 0
    • a[i][j] 地址 = 首地址 + [i*n-(i-1)*i/2+j-i] * 单个元素存储空间
• 带状矩阵：全部非零元素落在以对角线为中心的带状区域
  • 包含：主对角线 + 主对角线上面和下面各 b 条对角线（半带宽：b，带宽：2b+1）
  • 特点：当 |i-j| > b 时，a[i][j] 为特殊元素（零值、相同值或可忽略值）
  • 存储：除第一行和最后一行外，每行都会分配 2b+1 个空间，共有空间：[(2b+1)*n-2b] * 单个元素存储空间
  • 当 |i-j| <= b 时，a[i][j] 地址 = 首地址 + [i*(2b+1)+j-i] * 单个元素存储空间
• 稀疏矩阵：为零元素个数远远大于非零元素个数
  • 顺序存储：
    • 方法：
      • 三元组表示法：行号、列号、值，按行号递增，同一行按列号递增
      • 带辅助行向量的二元组表示法
      • 伪地址法
    • 三元组表示时的矩阵转置
  • 链式存储：
    • 方法：
      • 带行指针向量的单链表表示法
      • 行列表示法
      • 十字链表表示法：只存储非零元素。三个环形链表（带表头结点）：1、2 两个链表共用表头结点（第 i 行链表和第 i 列链表）
        1. 同一行元素链表
        2. 同一列元素链表
        3. 表头结点链表

第五章 递归

• 概念：
  • 分类：
    • 直接递归：函数定义中出现了对自身的调用
    • 间接递归：函数 a 调用函数 b，b 中又调用 a（环状调用链）
  • 分治设计：将问题分解为若干子问题，子问题与原问题结构相同、求解过程相同，但规模较小
    • 利用子问题的解组合成原问题的解
    • 递归出口：通过修改参数再进行自身调用，直至子问题可被直接求解，可有多个递归出口
    • 参数的修改必定使递归出口的条件得以满足
• 调用栈：用于存放函数调用和返回所需的各种数据，包含：
  • 函数调用执行完成时的返回地址
  • 函数返回值
  • 每次函数调用的实参
  • 局部变量
• 递归程序转换成非递归程序：
  • 简单递归问题：直接求值，无需回溯（递推方法）
  • 复杂递归问题：不能直接求值，必须试探和回溯（使用栈来记忆回溯点）
  • 递推方法：自底向上，先计算子问题避免重复计算

第六章 树型结构

• 定义：
  • 有且只有一个结点称为根
  • 其余结点又都是一棵树，称为根节点的子树
  • 递归定义：一棵树由根和子树构成，子树又由子树根和更小的子树构成
• 表示方法：树型结构法、括号表示法、凹入表示法、嵌套集合表示法
• 关系：
  • A 在 B 上端：称 A 是 B 的双亲（父母、前件）
  • B 在 A 下端：称 B 是 A 的子女（孩子、后件）
  • B、C、D 的双亲为同一结点：称 B、C、D 互为兄弟
• 除根结点外，其余结点有且只有一个双亲，零个或多个子女
• 度：
  • 结点的度：一个结点拥有的子女数
  • 树的度：树中所有结点度的最大值
• 结点的分类：
  • 终端结点（叶子结点）：度为 0 的结点
  • 非终端结点（分支结点）：度不为 0 的结点
• 树枝：连接两个结点的线段
• 路径：从某结点从上而下到另一结点，则称这两个结点之间存在着一条路径
• 路径长度：所经过的树枝的条数
• 根节点到任何一个结点均存在一条路径
• 祖先：从根到 A 结点所经过的所有结点称为 A 的祖先
• 子孙：以 A 结点为根的子树中任何一个结点称为 A 的子孙
• 层次：根节点为第 1 层，子女结点为第 2 层，以此类推
• 树的深度（高度）：树中结点的最大层次数
• 有序树：任意结点的子树均为从左到右有次序，不能随意交换
• 无序树：子树可随意交换，不影响实际意义
• 森林：m 棵互不相交的树构成的集合
  • 树转换为森林：一棵树中每个结点的子树集合
  • 森林转换为树：森林中每棵树加上一个共同的根

树的存储结构

• 双亲表示法：指出双亲位置
  • 除根结点无双亲外，其余结点有唯一确定的双亲
  • 结构：数据域 + 该结点的双亲指针或数组下标
• 孩子表示法：指出子女位置
  • 结构：
    • 指针方式：数据域 + 指针数组，数组中元素为指向该结点子女的指针
    • 数组方式：数据域 + 数组下标，树中结点存储在一维数组中；缺点：数组大小由树的度决定
    • 链表方式：数据域 + 单链表，由各个结点的子女组成，各单链表头指针也可以用数组来存储
• 孩子兄弟表示法：指出孩子和兄弟，再串联起来
  • 以二叉链表方式存储（二叉树表示法）
  • 结构：数据域 + 指向当前结点的第一个子女结点 + 指向当前结点的右兄弟结点

树的遍历

• 定义：
  • 按某种规定的顺序访问树中结点一次，且仅一次
  • 把树的结点排成一个线性序列
• 前序遍历：先根后左右：先根，再对子树从左到右
• 后序遍历：先左右后根：先对子树从左到右，再跟
• 层序遍历：从上到下，从左到右：队列

树的线性表示

• 树型结构分支性和层次性
• 根据树的遍历序列无法唯一的确定一棵树
• 线性表示：在遍历序列中附加信息从而唯一地确定一棵树
  • 括号表示法：A(B, C(F, G, H), D, E(J, I))
    • 左括号前的元素为括号内元素的根结点
    • 转换：用栈来匹配括号
  • 层号表示法：1A, 2B, 2C, 5F, 5G, 5H, 2D, 2E, 3J, 3I
    • 层号：
      • A 为 B 的孩子，则 A 的层号大于 B 的层号
      • A、B 都为同一结点的孩子，则 A、B 层号相同
    • 为每个结点规定层号，在按前序遍历顺序写出结点，结点前再加上层号
    • 一棵树的层号表示并不唯一，只要满足层号条件即可
    • 转换

第七章 二叉树

• 定义：
  • 非空结点最多有两个子女
  • 明确区分是左子树还是右子树，即使只有一颗子树
• 性质：
  • 第 i 层最多有 2^{i-1} 个结点（i>=1）
  • 深度 h 最多有 2^h-1 个结点（h>=1）
  • 设终端结点数为 A，度为 2 的结点数为 B，则有 A = B + 1
• 满二叉树：终端结点在同一层且非终端结点的度均为 2，结点数为 2^h-1
• 完全二叉树：
  • 扣除最后一层后变成满二叉树，且最后一层结点向左靠齐
  • 只有最下面两层的结点的度可以 < 2
  • 序号由层序遍历给出，对于序号为 i 的结点有：
    • i = 1：结点 i 为根节点，无双亲；i > 1：结点 i 双亲序号为 /lfloor i/2 /rfloor
    • 2i > n：结点 i 为终端结点；2i <= n：结点 i 左子女为结点 2i
    • 2i+1 > n：结点 i 无右子女；2i+1 <= n：结点 i 右子女为 2i + 1

存储结构

• 顺序存储：
  • 完全二叉树：按层序遍历的序号存入数组
  • 一般二叉树：共有 3 个域（3个数组），分别存放：数据 + 左孩子下标 + 右孩子下标，还可再增加一个域来存放双亲下标
• 链式存储：数据域 + 指向左右子树的指针

操作

• 二叉树遍历：
  • 前序遍历：先根后左右
  • 中序遍历：先左中根后右
  • 后序遍历：先左右后根
  • 创建二叉树的算法可由遍历算法得到
  • 非递归实现可用栈来保存回溯点
• 其它操作：
  • 查找：返回给定值在树中的位置
  • 统计结点个数
  • 判断两树是否等价
  • 求二叉树的高度（深度）：左子树高度和右子树高度中的最大值，再加 1

穿线二叉树（线索二叉树）

• 解决一般二叉树的空间浪费：设一颗二叉树有 n 个结点，则共有 2n 个指针，指针中只有 n-1 个被使用，n+1 个为空指针
• 定义：
  • 指针：左右子树非空，则与正常二叉树相同指向
  • 线索：左子树为空，则让左指针指向某种遍历顺序下的前驱结点；右子树为空，则让右指针指向某种遍历顺序下的后驱结点
  • 当遍历顺序为前序时，则称之为前序穿线二叉树，以此类推
• 实现结构：增加两个标志位
• 运算：
  • 创建：先创建普通二叉树，再对其进行线索化
  • 中序遍历

树（森林）和二叉树的相互转换

• 定义：
  • 树（森林）唯一对应一颗二叉树
  • 一颗二叉树唯一对应一棵树（森林）
• 树（森林）转换为二叉树：
  1. 兄弟结点间添加一条连线（森林时，则各个树根间也加）
  2. 对每个结点，只保留到第一个子女的连线，撤销到其它子女的连线
  3. 顺时针方向旋转 45°
• 二叉树转换为树（森林）：
  1. 将二叉树逆时针方向旋转 45°
  2. 连接新右子女：如果某结点是其双亲的左子女，则将该结点的右子女、右子女的右子女等（直到没有右子女）都与该结点的双亲结点连线
  3. 删除旧右子女：去掉双亲到右子女的连线

第八章 图

• 定义：非空顶点集合 + 描述顶点间多对多关系的边集合（弧集合）
• n：顶点数；e：边数
• 弧（有向边）：
  • 弧尾：弧的始点
  • 弧头：弧的终点
• 无向图：图的边没有方向：e <= n(n-1)/2
• 完全图：拥有最多的边数，任意一对顶点间均有边相连
  • 有向完全图：e = n(n-1)
  • 无向完全图：e = n(n-1)/2
• 邻接术语说明：
  • 无向边：(A, B)：
    • 顶点 A 和顶点 B 互为邻接点；A 与 B 相邻接
    • 边 (A, B) 关联于顶点 A 和顶点 B；边 (A, B) 与顶点 A 和 B 相关联
  • 有向边：<A, B>：
    • A 邻接到 B；B 邻接于 A
    • 边 <A, B> 关联于顶点 A 和顶点 B；边 <A, B> 与顶点 A 和 B 相关联
• 度：一个顶点的度就是与该顶点相关联的边的数目
  • 有向图时：
    • 入度：以顶点为终点的边数
    • 出度：以顶点为始点的边数
• 子图：设 G_i = (V_i, E_i)，G_j = (V_j, E_j)，如果满足 V_i <= V_j，E_i <= E_j，则 G_i 是 G_j 的子图
• 路径：从顶点 A 到顶点 B 经过的边都在图的边集中，称这个序列为 A 到 B 的一条路径
  • 图为有向图时，路径也是有向的
  • 路径长度：该路径上的边的数目
  • 简单路径：除起点和终点外，其余路径上的顶点均不相同
    • 简单回路（简单环）：起点和终点相同的简单路径
• 连通术语说明：
  • 无向图：
    • 连通：任意两个顶点 A、B 互相有路径
      • 极大连通子图（又称为连通分量）为其自身
      • 极小连通子图为其生成树
    • 不连通：
      • 多个极大连通子图
      • 多个极小连通子图
  • 有向图：
    • 连通（称为强连通）：任意两个顶点 A、B：A 到 B、B 到 A 有路径
      • 极大连通子图（又称为强连通分量）为其自身
    • 不连通：
      • 多个极大连通子图
    • 没有极小连通子图的概念
• 权：与边相关的数值
• 带权图（网络）：图的每条边都有权

图的存储结构

• 要求：既要存储图的顶点信息，又要存储顶点之间的联系（边）
• 邻接矩阵：
  • 结构：
    1. 先用一维数组（顺序表）存储数据元素的信息
    2. 再用二维数组（邻接矩阵）存储数据元素之间的关系（边）
  • 度数：
    • 无向图：当顶点为 V_i 时，度数为第 i 行或第 i 列值为 1 的元素个数
    • 有向图：当顶点为 V_i 时，
      • 出度：第 i 行值为 1 的元素个数
      • 入度：第 i 列值为 1 的元素个数
  • 存储网络：边：(i, j)
    • 边在边集中：存储权值
    • 边不在边集中且 i = j：存储 0
    • 边不在边集中且 i != j：存储无穷大
  • 存储空间：
    • 无向图：n^2
      • 无向图时邻接矩阵时对称的，可用三角压缩存储：n(n+1)/2
    • 有向图：n^2
  • 表示唯一
  • 适合稠密图
• 邻接表：
  • 占用的存储空间与边数无关，只与顶点数有关
  • 方法：顶点 V_i 的邻接表：对于每个顶点 V_i，把所有邻接于 V_i 的顶点链成一个带头结点的单链表
  • 结构：
    • 邻接点域：只是这个顶点在图中的位序
    • 链域（单链表中的链域）：指示与顶点 V_i 邻接的下一个结点
    • 头结点中存储顶点数据，再把各个头结点存放在数组中
  • 无向图：每个表结点对应与 V_i 相关联的一条边
  • 有向图：
    • 出边表（有向图的邻接表）：每个表结点对应以 V_i 为始点射出的一条边
    • 入边表（有向图的逆邻接表）：每个表结点对应以 V_i 为终点的边，即摄入 V_i 的边
  • 当无向图中有 n 个顶点、e 条边时：需要 n 个头结点、2e 个边结点
  • 度数：
    • 无向图：第 i 个链表中结点的个数
    • 有向图（出边表）：
      • 出度：第 i 个链表中结点的个数
      • 入度：扫描邻接表（所有链表），其中邻接点域值为 i 的结点个数
  • 表示不唯一
  • 适合稀疏图（e 远小于 n(n-1)/2）
• 邻接多重表：
  • 定义：
    • 每个顶点用一个表头结点表示，指向关联于顶点的第一条边
    • 每条边只有一个边结点表示，且可被多个链表共享
  • 结构：
    • 标志域：用于标记该边是否被搜索过
    • 有两个域用来表示该边的两个顶点在图中的位序
    • 有两个指针域分别指向关联于两个顶点的下一条边

图的遍历

• 定义：从某点出发访问图中其余顶点，且每个顶点仅访问一次
• 解决图可能存在回路：记录每个已访问过的顶点
• 深度优先搜索（DFS）：类似于树的前序遍历
  • 步骤：
    1. 先将所有顶点标记为未被访问
    2. 从中选取一个源点标记为已访问
    3. 再将源点的邻接点加入搜索，以此类推
  • 时间复杂度：O(n+e)
• 广度优先搜索（BFS）：类似于树的层序遍历
  • 步骤：
    1. 先访问源点
    2. 再访问源点的邻接点，直到全部邻接点都已访问才继续
  • 尽可能先对横向结点进行搜索
  • 当所有与源点有路径相通的顶点都已访问，此时从源点开始的搜索已完成，但：
    • 连通图：遍历完成
    • 非连通图：另选一个新的源点继续搜索，直到所有顶点都已访问
  • 用队列保存顶点序列
  • 时间复杂度：O(n+e)

图的生成树

• 定义：
  • G 的子图 G’ 包含 G 中所有顶点，且 G’ 无回路连通，则称 G’ 为 G 的一颗生成树
  • 使用 DFS 或 BFS 搜索到的 n 个顶点和经过的边集（共 n-1 条边）组成的极小连通子图
  • 连通图中包含所有顶点的极小连通子图
• 最小生成树（MST）：
  • 定义：总权值最小的生成树
  • 树权：生成树各边的权值总和
  • 构造准则：
    • 必须只使用边集中的边
    • 必须仅使用 n-1 条边连接 n 个顶点
    • 不能使用产生回路的边
  • 性质：必存在包含最小两栖边的最小生成树
  • 两栖边：设 G = (V, E)，u 为 V（顶点集）的一个非空真子集。这时，如果边 (u, v) 满足 u /subseteq U 和 v /subseteq V-U，则称这条边为两栖边，即一个顶点在一边，另一个顶点在另一边
  • 最小两栖边：两栖边中具有最小的权值
• 最小生成树算法：
  • Prim 算法：
    • 思想：从所有两栖边中选取最小两栖边 (u, v)，将顶点 v 加入 U，边加入边集合，直到 U = V
    • 步骤：
      1. 初始化 U = {u_0}，tree = {}
      2. 终止条件：V = U
      3. 选边加入（最小两栖边不只一条时可任选一条）
      4. 调整
      5. 循环直到满足终止条件
    • 调整：对于任意顶点 v_j，如果顶点 v 与 v_j 之间的权值小于原来的两栖边 (v_i, v_j) 的权值，则用新边 (v, v_j) 代替旧边 (v_i, v_j)
    • 设顶点数为 n，则计算时间为 n^2
  • Kruskal 算法：
    • 思想：
      • 按网络中边权值递增顺序构造
      • 初始化时仅包含所有顶点而没有边，把边按非递减排列，每个顶点各自构成一个连通分量，选边时：
        • 如果边关联的两个顶点分别在两个连通分量中，则将边加入边集、合并连通分量
        • 如果边关联的两个顶点在同一个连通分量中，则放弃该边，因为会产生回路
    • 步骤：
      1. 初始化
      2. 终止条件：已有 n-1 条边
      3. 选边加入
      4. 循环直至满足终止条件
    • 时间复杂度：取决于边排序的性能，使用快排时：O(elog_2e)
    • 避圈法：求解过程中不让在生成树中出现环
    • 破圈法：每次从图中找出一个环（回路），然后删除该环中最大权值的边，直至图中无环

图的最短路径

• 定义：从源点到终点权值和最小的路径
• 单源最短路径：
  • Dijkstra 算法
  • 设有 n 个顶点，e 条边的带权有向图的邻接矩阵：时间复杂度：O(n^2)
  • 步骤：
    1. 先写出全部顶点，在顶点旁标注源点到该顶点的距离：
       • 顶点与源点的距离为一条边：正常距离
       • 顶点与源点的距离大于一条边：正无穷
    2. 从表中选出距离最小的顶点，现在从该顶点出发，计算所有与该顶点距离一边的顶点到源点的距离：
       • 如果该距离比表中距离小：更新
       • 否则：保持表不变
    3. 已选过的顶点不能再选取，重复选点直到所有点都选过
• 多源最短路径（所有顶点对最短路径）：
  • 重复执行 Dijkstra 算法 n 次：O(n^3)
  • Floyd 算法：O(n^3)
  • 思想：求解 A_{k+1}[i][j] 的递推公式：
    • A_-1[j][j] = g.edges[i][j]
    • A_{k+1}[i][j] = min(A_k[i][j], A_k[i][k+1] + A_k[k+1][j])

图的拓扑排序

• 有向无环图：有向图中没有包含简单回路
• AOV 网：用顶点表示活动，弧表示活动间优化关系的有向图
• 有向边 <u, v>：事件 u 必须先于事件 v 完成，称 u 为 v 的直接前驱，v 为 u 的直接后继
• 有向路径 <u, ..., v>：称 u 为 v 的前驱，v 为 u 的后继
• 拓扑序列：AOV 网中两个顶点的路径，这条路径满足顶点间前驱后继的关系
• 拓扑排序：给出 AOV 网的拓扑序列的过程
• 步骤：
  1. 在图中找到一个没有前驱（入度为0）的顶点并输出
  2. 删除该顶点和所有从该顶点发出的边
  3. 循环执行 1、2。终止条件：所有顶点被输出或再无入度为 0 的顶点
• 执行时间：O(n+e)
• AOE 网：用顶点表示事件，弧表示活动，边权值表示活动持续时间
• 源点：入度为 0 的事件
• 汇点：出度为 0 的事件
• AOE 网的关键路径：从源点到汇点的最短距离，即完成工程的最短时间
  • 方法：求解每个事件的最早发生时间和最晚允许的开始时间：O(n+e)

第九章 检索

• 检索：从数据元素集合中确定是否存在给定数据或满足某种特征的过程
• 关键字：唯一标识每个元素
• 静态查找表：检索前后并不改变表的内容
• 动态查找表：检索伴随着数据的增、删、改
• 平均查找长度：表示与集合中关键字的比较次数，是衡量检索算法的标准

线性表检索

• 在线性表上进行
• 顺序检索：从表头扫描到表尾，逐个比较
  • 效率：
    • 成功时：平均 (n+1) / 2
    • 失败时：平均 n
  • 优化：
    • 哨兵：在表尾设置一个与关键字相等的哨兵，这样就不用每次都要判断是否查找完成（到达表尾）
    • 动态查找表（适合链式存储）：每个结点附设一个访问频率域
• 二分法检索（折半查找）：跟中间关键字来比较以决定范围
  • 要求：关键字有序
  • 时间复杂度：O(log_2n)
  • 适合静态查找表
• 分块检索（索引顺序查找）：将线性表分块，块中有若干元素，快中元素可以无序，但块与块间必须有序
  • 顺序检索和二分检索的结合
  • 建立一个索引表，将每块中的最大元素放入表中
  • 最大查找长度：n 个元素分为 b 块：b + n / b
  • 效率：在顺序检索和二分检索之间
  • 分块：可根据数据的特征分块
  • 块中元素无序：适合动态地增、删

二叉排序树（二叉查找树）

• 性质：左子树上所有结点 < 根结点 < 右子树上所有结点
• 递增序列：中序遍历（树排序）
• 查找：
  1. 根结点 = 给定关键字：查找成功
  2. 根结点 < 给定关键字：在右子树中查找
  3. 根结点 > 给定关键字：在左子树中查找
  4. 二叉树变为空树：查找失败
• 效率与树的形状相关：比较次数不会超过树的深度
• 效率：
  • 最坏：退化成深度为 n 的单支树（单链表）：(n+1) / 2（顺序检索）
  • 最好：形状匀称：O(log_2n)
• 适合动态查找表，方便地增、删
• 插入：插入位置为检索失败的最终叶结点位置
• 创建：不断插入，树的形状与插入次序有关
• 删除：
  • 叶结点：直接删除
  • 只有左子树没有右子树：左子树替代被删结点位置
  • 只有右子树没有左子树：右子树替代被删结点位置
  • 左右子树都有：
    • 方法一：
      1. 让被删结点右子树代替被删结点
      2. 被删结点左子树收为被删结点右子树中序首点的左孩子
    • 方法二：
      1. 让被删结点左子树代替被删结点
      2. 被删结点右子树收为被删结点左子树中序尾点的右孩子

保持树的平衡

• 使二叉树的高度尽可能为 O(log_2n)
• 丰满树：
  • 定义：任意两个非双孩子结点的高度差绝对值 <= 1
  • 子女结点数 < 2 的结点只出现在最低两层
  • 具有最小内部路径长度
  • 平分法构造丰满树
  • 缺点：非丰满树改造成丰满树非常困难
• 平衡二叉树（AVL树）：
  • 定义：左子树与右子树高度差绝对值 <= 1
  • 平衡度（平衡因子）：该结点左右子树高度差，从 [-1, 0, 1] 中取值
  • 丰满树一定是平衡树，但平衡树不一定是丰满树
  • Adelson 方法构造：
    1. 插入：正常插入，设新结点平衡度为 0
    2. 调整平衡度：
       • LL 型平衡旋转
       • RR 型平衡旋转
       • LR 型平衡旋转
       • RL 型平衡旋转
    3. 改组

各种特性树

• 扩充二叉树：
  • 定义：对树中不足两个孩子的结点（包括叶子结点）添上附加结点，使得每个结点都有两个孩子结点
  • 外部结点：附加的结点
  • 内部结点：树中原来结点
  • 有 n 个内部结点，则有 n+1 个外部结点
  • 扩充查找树：对二叉排序树进行扩充
    • 中序遍历得到序列时：
      • 最左外部结点：码值小于内部结点最小码值的可能结点集
      • 最右外部结点：码值大于内部结点最大码值的可能结点集
      • 其余外部结点：码值处在相邻结点码值之间的可能结点集
    • 失败结点（外部结点）：检索时到达外部结点表示失败
    • 路径关系：所有外部结点路径长度和 = 所有内部结点路径长度和 + 2 * 内部结点数
    • 如果有最大（最小）内部路径长度，就有最大（最小）外部路径长度的二叉树，反之亦然
• 最佳二叉排序树（最优查找树）：
  • 定义：具有最少比较次数
  • 构造要求：
    • 相同序列的不同二叉排序树应该有相同的中序遍历序列
    • 最佳二叉排序树子树也是最佳的
  • 构造过程：由一个结点、两个结点、依次构造
  • 构造代价：O(n^3)
• 哈夫曼树（Huffman 树）：
  • 定义：具有最小带权外部路径长度的二叉树
  • 特点：权值大的叶子结点应该尽可能离根结点近
  • 应用：
    • 分支程序（条件语句）的判断流程
    • 数据通信的二进制编码
  • 哈夫曼算法（构造哈夫曼树）：
    1. 用有序链表存放权值（可以看作是各子树的根结点）
    2. 每次取前两小的子树构造新树，新树权值为两子树权值和
    3. 根据新树根权值大小重新插入有序链表，保持有序，直至链表只剩一棵树
  • 计算 WPL（带权外部路径长度）：
    • 根结点高度为 0，下面每层 +1
    • WPL = 0 + 1*20 + 2*16 + 3*(10+6)
• B 树（B-tree）：多路平衡查找树
  • 针对较大的、在外存储器的文件
  • 应用：在文件系统中作为索引文件的结构
  • 基本操作：查找；插入；删除
  • 定义：设有一颗 m 阶（m>=3）B 树：
    • m 叉树：每个结点最多有 m 棵子树
    • 如果根结点不是叶子结点（树中只有根结点），那么它至少有两个子结点
    • 非根结点至少有 ceil(m/2) 棵子树和 ceil(m/2)-1 个关键字
    • 非终端结点结构：(n, p0, k1, p1, k2, p2, …, kn, pn)
      • n 为关键字的个数，n+1 为子树个数：ceil(m/2)-1 <= n <= m-1
      • k 为关键字，且递增排列
      • p 指向子树，且子树中的关键字会对应 p 的范围，如：
        • p0 指向的子树所有关键字都小于 k1
        • p1 指向的子树所有关键字在 [k1, k2] 之间
        • p2 指向的子树所有关键字都大于 k2
• B+ 树（B+ tree）：
  • 构造：自底向上地把每个结点的最大（最小）关键字复写到上一层结点中
  • 两个头指针：
    1. 指向根结点
    2. 指向关键字最小的叶子结点
  • 非叶子结点只用于索引，不含有该关键字对应记录的存储地址
  • 基本操作：查找；插入；删除
  • 定义：
    • 每个结点最多有 m 棵子树
    • 非根结点至少有 ceil(m/2) 棵子树：ceil(m/2) <= n <= m
    • 如果根结点不是叶子结点（树中只有根结点），那么它至少有两个子结点：2 <= n <= m
    • 所有叶子结点包含全部关键字且有序排列（链表）
    • 结点有多少个关键字就有多少个子树
    • 每层结点是下一层结点中最大（最小）关键字的副本

散列

• 散列存储：
  • 定义：以关键字为自变量通过散列函数计算出对应的值，以此作该结点的存储地址。检索时用同样的函数计算出地址再去取
  • 散列表：用散列法存储的线性表
  • 检索时间与元素个数无关：O(1)
  • 冲突（碰撞）：不同关键字具有相同的存放地址
  • 同义词：发生碰撞的多个关键字
  • 负载因子 α：反映装填程度
    • α = 当前结点数目 / 可容纳的结点数目
    • α > 1 时冲突不可避免
  • 两个主要问题：
    • 使用计算简单、冲突几率小的散列函数
    • 确定解决冲突的方法
• 散列函数：
  • 原则：均匀映射、降低冲突概率
  • 除余法：选择一个略小于地址个数的质数，用它除以关键字得到的余数作为地址
  • 平方取中法：取关键字平方后的中间几位作为地址：因为一个数平方后中间几位和数的每一位都有关
  • 折叠法：将关键字分割成位数相同的几部分，取这些部分的叠加和（舍去进位）作为地址
    • 适合关键字位数很多且每位数字分布均匀时
    • 移位叠加：将分割后的每一部分最低位对齐相加
    • 间界叠加：从一端到另一端沿分割界来回折叠对齐相加
  • 数字分析法：丢掉分布不均匀的位，保留分布均匀的位作为地址
  • 直接地址法：取关键字或关键字的线性函数值作为地址
    • 哈希函数简单、不会冲突
    • 元素分布离散，大量空间浪费
• 冲突处理：
  • 发生冲突的几率与负载因子 α 呈正相关
  • 开放定址法：发生冲突时用某种方法探测到一个空位置（开放地址）
    • 需要某种标记区分空位置和非空位置
    • 形式：H_i(k) = (H(k)+d_i) mod m H(k) 为直接哈希地址，m 为哈希表长、d_i 为每次再探测时的地址增量
    • 线性探测再散列：d_i = 1, 2, 3, …, m-1
    • 二次探测再散列：d_i = 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2
    • 随机探测再散列：d_i = 随机数序列
    • 聚集：哈希地址形成区块的现象
  • 再哈希法：发生冲突时用下一个不同的哈希函数计算地址，直至无冲突
    • 不易发生聚集，但增加了计算时间
  • 拉链法：散列表中每个位置对应一条单链表，同义词（地址相同）均放入链表中，冲突时在链表后面加入
    • 处理冲突简单，无聚集：非同义词不会冲突，平均查找长度较短
    • 删除结点的操作易于实现
    • 动态申请空间，适合无法确定表长的情况
    • 指针会占用额外空间
  • 差值法：冲突时用一个固定的差值得到新地址，超出时循环
  • 公共溢出区法：发生冲突时忽略哈希函数得到的地址，直接添加到溢出表

第十章 内排序

• 排序的定义：以记录中某个（几个）字段值（排序码）递增（递减）的次序将这些记录重新排列
• 关键码：唯一标识一个记录的字段
• 关键码可为排序码，但排序码不一定为关键码，即排序码可能会相同
• 由存储介质分类：
  • 内排序：数据只在内存中处理
  • 外排序：数据过大，内存不够，还需要用到外存
• 稳定性：
  • 稳定：有相同排序码的记录，排序后次序不变
  • 不稳定：有相同排序码的记录，排序后次序改变

插入排序

• 直接插入排序：将未排序记录插入到已排序记录的适当位置，且保持有序
  • 从右到左找到适当位置，将该位置后面的元素后移来空出位置
  • 哨兵：将表中第一个位置前的值设为当前待插入元素的值
  • 在比较过程中后移，每次一符合条件就后移一位
  • 最好情况：一开始就是有序的
  • 最坏情况：一开始就是逆序的
  • 时间复杂度：O(n^2)
  • 附加空间：1（哨兵）
  • 稳定性：稳定
• 二分法插入排序：插入时用二分法在已有序记录中找到合适位置
  • 比较次数：少于直接插入的最多比较次数，多于直接插入的最少比较次数
  • 当 n 较大时，二分插入比较次数远少于直接插入平均比较次数，但移动次数相同
  • 时间复杂度：O(n^2)
  • 附加空间：1
  • 稳定性：稳定
• 表插入排序：在不进行记录移动的情况下，通过存储结构信息的改变来完成排序
  • 从下标 0 开始沿着 link 域得到递增的静态链表
  • 时间复杂度：O(n^2)
  • 稳定性：稳定
• Shell 插入排序：对于 n 个记录可分为 d 组，每隔 d 取一个数，每组有 n/d 个元素，对每组分别进行直接插入排序，逐渐缩小 d 的值，直至为 1，此时有序
  • 关键在于选取高效的增量序列
  • 稳定性：不稳定

选择排序

• 直接选择排序：每次从待排序记录中选择最小（最大）元素，将其放入正确的位置（与第一个记录交换）
  • 初始有序时：无任何移动记录的操作
  • 时间复杂度：O(n^2)
  • 附加空间：1
  • 稳定性：不稳定
• 树型选择排序：保存比较的结果，而不用重复比较
  • 结构：所有排序码均在叶子结点，分支结点保存左右子树的较小（大）者
  • 记录数个数为奇数时：可增加一个大于（小于）所有值的结点进行比较
  • 每次从根结点取出最小（最大）的值后，用正无穷值替换原来的位置
  • 时间复杂度：O(nlog_2n)
  • 附加空间：
    • n-1 个分支结点用于存放中间比较结果
    • 存储已排序记录的空间
• 堆排序：堆是一颗完全二叉树，且任意分支结点的值都小于（大于）或等于左右结点
  • 即保存中间比较结果，有不占用过多存储空间
  • 用数组（顺序方式）存放该完全二叉树
  • 建堆：从第 floor(n/2) 个结点开始，直到以第一个结点为根的整棵树有堆的性质
  • 筛选算法：对某个序号进行调整的算法
  • 排序：不断从根结点取出元素，再重新满足堆的性质
  • 重新建堆：
    1. 堆中最后一个元素与根结点（数组中的第一个元素）交换，堆中元素总数 -1
    2. 再从根结点重新调整
  • 适用于 n 较大的文件：因为建堆和调整需要多次筛选
  • 时间复杂度：O(nlog_2n)
  • 附加空间：1
  • 稳定性：不稳定

交换排序

• 冒泡排序：排序码之间两两比较，如果不满足排序顺序则交换。每趟将一个元素放到最终正确位置，在某趟中未发生元素交换则表示已排序
  • 时间复杂度：O(n^2)
  • 附加空间：1
  • 稳定性：稳定
• 快速排序：取一记录为 pivot，使得它前面的记录小于它，它后面的记录大于它。再对前面和后面的记录递归重复
  • 分区：在数组左右两端设置两个指针，向中间扫描，停止时（满足条件）交换
  • 时间复杂度：O(nlog_2n)
  • 附加空间：1 + 递归调用所占空间
  • 稳定性：不稳定

归并排序

• 思想：对多个有序子文件合并成一个大的有序文件
• 归并：2 个有序子文件进行比较，取出较小（较大）元素放入目标文件
• 三路归并排序：归并的有序子文件有 3 个
• 一次归并
• 一趟归并
• 时间复杂度：O(nlog_2n)
• 附加空间：与待排序文件空间相同
• 稳定性：稳定

基数排序（分配排序）

• 思想：运用多排序码的思想进行单排序码排序
• 多排序码的排序：
  • 分配：分成若干份
  • 收集：将若干份按序叠在一起
• 静态链式基数排序：
  • 步骤：
    1. 先建立一个单链表，一个结点对应一个记录
    2. 分配：从个位分配到对应的队列中，在同一队列的元素个位数都相同
    3. 收集：从队列中的元素按序还原成单链表
    4. 重复执行 2、3，从最低位到最高位
  • 设排序码的取值范围中值的个数为 rd（十进制则为10）：
    • 收集：O(rd)
    • 总共要进行 b 趟分配和 b 趟收集
  • 时间复杂度：O(b(n+rd))
  • 附加空间：2rd 个队列指针 + n 个 link 指针域
  • 稳定性：稳定