🪫数据结构—期末笔记

栈

1. 一个栈 (无穷大) 的进栈顺序 1, 2, ⋯, n 有多少个不同的出栈顺序?卡特兰数:

2. 中缀表达式转后缀表达式
1. 代码实现引入: 操作符优先级, 分栈内和栈外. 当遇到操作数时, 直接输出. 当遇到操作符时: 如果当前操作符的栈外优先级大于栈顶操作符的栈内优先级, 当前操作符进栈, 否则 pop 栈顶操作符并输出.
2. 人工: 按照中缀表达式的运算顺序, 先算哪个就先转哪个.

数组, 串与广义表

字符串

1. KMP 算法
1. 简介: 通过预处理目标字符串, 避免在查找时产生回溯, 线性复杂度.
2. next 数组
3. 查找

广义表

1. 表的第一个元素称为广义表的表头(head), 其它表元素组成的表称为广义表的表尾(tail)

2. 长度: 元素个数, 子表算一个元素

3. 深度: 最多能脱几层括号. 空表的深度为 1.

4. 类型定义
1. 节点类型 utype: 表头(0), 原子数据(1), 子表(2)
2. 信息 info: 表头的信息是引用计数, 原子数据的信息是其值, 子表的信息是子表指针.
3. 尾指针 tlink: 表头的尾指针指向表的第一个节点, 其他的尾指针指向同一层的下一个节点.

5. 示例

6. 广义表的图形表示和存储表示

7. 广义表的复制: 标准的 DFS 递归算法

8. 广义表的删除:
1. 算法
1. 引用计数 -1
2. 如果引用计数为 0, 横扫表顶层, 遇到原子节点(即 utype = 1)直接删掉, 遇到子表节点(即 utype = 2)先递归调用删除子表节点指向的子表, 然后删除子表节点.
3. 注意: 只有表头(即 utype = 0 的)节点需要调用 remove 进行递归删除.
2. 示例



B G H F C L K J I D E A

树

1. 二叉树
1. 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为 2 的结点有 n2 个, 则有 n0 = n2 + 1
1. 推导: 二叉树有 n 个顶点, n - 1 条边, n = n0 + n1 + n2, n - 1 = 2n2 + n1, 移项可得
2. 即: 二叉树的叶子结点总比度为 2 的结点多一个.
2. 具有 n 个结点的完全二叉树的深度为

2. 二叉树的表示
1. 顺序表示
1. 用数组, 适合表示完全二叉树, 如: -1 1 2 3 4 5 6 7 8
这种情况下, 假设一个结点位于下标 i, 那么其父结点位于 i / 2, 左子结点位于 2 * i, 右子结点位于 2 * i + 1
2. 前序遍历的非递归算法: 拿到一个结点, 先访问, 然后将右子树压栈, 进入左子树. 当进入的是空树时, 退栈并拿到栈顶元素访问(重复).
3. 中序遍历的非递归算法: 拿到一个结点, 先将其压入栈中, 然后拿到左子树访问. 当访问的是空树时, 退栈, 拿到栈顶元素, 先访问, 然后拿到右子树(重复).
4. 后序遍历的非递归算法: (后序遍历的非递归算法要求必须知道栈中结点是第几次退栈, 这里我们假设将一个计数和结点一起压栈.) 拿到一个结点, 先将其压入栈中(with 0), 然后拿到其左子树(重复). 当进入空树时, 退栈, 拿到栈顶元素, 看其计数. 若为 0, 则拿到其右子树(重复). 若为 1, 则访问, 并再次退栈, 拿到栈顶元素(重复).
5. 层序遍历算法: 用一个队列, 每当拿到一个节点, 先访问, 然后将左右子树按顺序入队, 再拿到队首元素(重复).
6. 在二叉树的遍历中, 前序和后序遍历不可以用来确定一棵唯一的二叉树(左右子树无法区分).
2. 树对应的二叉树: 子女-兄弟表示法. 示例:
3. 森林对应的二叉树: 先将各树转换为对应的二叉树, 然后把第二棵树的根节点作为第一棵树的右子树, 第三棵树的根节点作为第二棵树的右子树, 以此类推.
4. 根结点的高度为 .

3. 线索化二叉树
1. 基本概念
1. 线索(Thread):
• 如果一个节点的左子节点为空, 则该节点的左指针指向该节点的前驱节点.
• 如果一个节点的右子节点为空, 则该节点的右指针指向该节点的后继节点.
2. 线索化:
• 按照某种遍历方式, 将二叉树中的空指针替换为指向前驱或后继节点的指针的过程称为线索化.
2. 数据结构:
3. 代码实现思路: 在X序遍历的函数中, 添加一个参数 pre 作为当前结点的前驱. 拿到一个结点, 若空返回. 检查其左子树, 若不空则递归调用, 若空则 root->left = pre. 检查前驱, 若 pre != NULL && pre->right == NULL, 则 pre->right = curr;. 递归调用其右子树.

4. 多叉树
1. 先根遍历与这棵树对应的二叉树的前序遍历结果相同.
2. 后根遍历与这棵树对应的二叉树的中序遍历结果相同(存疑, 这是 PPT 上的说法, 实际上应该对应后序遍历).
3. 用”子女-兄弟表示法”表示森林, 就相当于把第一棵树的根作为根, 将其他树作为这个根的后继.

5. 哈夫曼树
1. 路径长度
1. 结点间的路径长度 (Path Length) = 两点之间的边数
2. 树的外部路径长度 (External PL) = 叶结点到根结点路径长度之和
3. 树的内部路径长度 (Internal PL) = 非叶结点到根结点路径长度之和
4. 带权路径长度 (Weighted PL) = (叶结点到根结点路径长度 * 叶结点的权值) 之和
2. 哈夫曼树的定义: 带权路径长度达到最小的扩充二叉树
3. 构造方法: 选择两个最小的权值, 构造一棵二叉树, 这棵新树的权值就为两个子节点权值之和. 重复至只剩一个结点.
4. 特点: 权值大的节点离根近
5. 哈夫曼编码: 前缀码. 一个叶结点的权值表示它在串中出现的次数.

集合与字典

并查集

散列表

1. 数字分析法：计算符号分布均匀度 值。
1. 仅用于事先明确知道表中所有关键码每一位的数值分布情况。
2. 本质：已知离散的均匀分布，计算方差。
3. n 个 d 位数，每一位上可能有 r 个不同的符号，每种符号出现的机会均等。公式如下： 表示第 i 个符号在第 k 位上出现的次数。

2. 线性探查法（Linear Probing）（闭散列法处理冲突）
1. 插入：计算 hash，从 hash 为下标开始找第一个空地插入（若查到数组尾可从头开始）。
2. 查找：计算 hash，从 hash 为下标开始找，直到找到元素，或找到空地查找失败。
3. 搜索成功的搜索长度：表中所有的元素各查找一遍，计算平均值。
4. 搜索失败的搜索长度：表中_可以被 hash 覆盖_的下标各进行一次查找失败，计算平均值。
5. 注意：内部的数组长度可能比 hash 覆盖的要长，这一部分是为了处理冲突使用的。

3. 二次探测再散列
1. 计算出 hash 值后，如果有冲突，依此检测以下位置：hash+1^2, hash-1^2, hash+2^2, hash-2b^2, … , hash+k^2, hash-k^2

4. 链地址法（开散列法处理冲突）
1. 搜索成功的搜索长度：
2. 搜索失败的搜索长度：设空表的长度为 1，则所有表长度之和的平均值。

搜索结构

1. 搜索判定树
1. 用圆圈表示有值节点，用方框表示空节点（搜索失败的点）
2. 计算搜索长度时注意：判断节点为空不算一次搜索次数。
3. 例题：有序顺序表中的元素为：17, 94, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908. 求折半搜索的判定树和搜索成功/失败的平均搜索长度。

2. 二叉搜索树
1. 性质：左小右大。
2. 对 BST 进行中序遍历，可以得到一个从小到大的序列。
3. 删除：叶子直接删；左/右为空则用右/左替代；都不为空则选择右子树最左节点替代，并改为删除该节点。

3. AVL 树
1. 节点的平衡因子：右子树的高度减去左子树的高度的高度差（右-左）。
2. 插入的平衡化旋转
1. 判断方法：插入后，从插入结点沿通向根的路径向上回溯。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点（即从不平衡节点沿着插入路径取两个节点）。再根据下图进行判断：
2. 删除的平衡化旋转
1. 删除方法和 BST 相同（中序的直接前驱或后继替代）
2. 维护一个 shorter 变量，若 shorter 为 True 说明树被缩短，需要继续检查。若为 False 则说明树没有缩短，则无需向上继续检查。
3. 在 shorter 为 True 时执行以下检查：
1. 当前节点的 bf 为 0，则将 bf 改为 1 或 -1，并停止检查。
2. 当前节点的 bf 不为 0 且较高的子树被缩短，则将 bf 改为 0，还需要继续向上检查。
3. 当前节点的 bf 不为 0 且较矮的子树被缩短，则设当前节点为 p，较高子树根为 q，根据 bf 进行操作：
1. 若 q 的 bf 为 0，则执行一个单旋转，并停止检查。
2. 若 p 和 q 的 bf 相同，则执行一个单旋转，并将 p 和 q 的 bf 均设置为 0，还需要继续向上检查。
3. 若 p 和 q 的 bf 异号，则执行双旋，将根节点的 bf 设置为 0，继续向上检查。
3. 性能分析：搜索、插入、删除（并作平衡化旋转）的时间复杂度

图

1. 图的表示
演示示例：



注：XX表分为顶点表和边表。顶点表存放该顶点的名字和边链表头指针。一般在顶点表左侧编号，在边链表中就用编号代替节点。边链表中的节点按照表的要求存放不同数据。
1. 有向图的逆邻接表（入边表）
2. 无向图的邻接多重表
顶点节点：名称 + 第一条出边。（这里的排序按照 pair<first_vec, second_vec> 规则，小的在前）
边节点：mark | v1 | v2 | path1 | path2
mark 记录是否处理过的标记，v1 v2 表示该边两个的节点，path1 指向 v1 的下一条边，path2 指向 v2 的下一条边。
例图：



注意这里画的看上去 v2 的边链表头指针指向的是 1-2 边的末尾，其只是为了在视觉上像链表，和 v1 指向的是一个东西。
要点：先画边再连线。
3. 有向图的邻接多重表（十字链表）
顶点节点：data | first in | first out
data 表示名称，first in 指向以该节点为终点的第一条边，first out 指向以该节点为起点的第一条边。
边节点：mark | v1 | v2 | path1 | path2
mark 是处理标记，v1 和 v2 为起点和终点，path1 指向以 v1 为起点的下一条边，path2 指向以 v2 为终点的下一条边。



4. 最小生成树
1. Prim
1. 描述: 从任意一个顶点开始, 每次选择一个与当前顶点集最近的一个顶点, 并将两顶点之间的边加入到树中 (贪心).
2. 时间复杂度
3. 适用于稠密图
2. Kruskal
1. 描述：每次在 E 中选择一个最小权值的，落在两个连通分量之间的边。
2. 时间复杂度 (E < V^2). if pre sorted.
3. 适用于稀疏图
3. 当有相同权值的边时，产生的最小生成树可能不唯一。
5. 最短路
1. 非负权值单源最短路（Dijkstra）
• 广度优先搜索：基于 当前节点到源点的累计距离 来排序。
• 时间复杂度
• 非堆优化（线性查找）：
• 堆优化（二叉堆）：
• 记录路径的算法示意：
2. 所有顶点之间的最短路（Floyd）
• 可以处理负边，不能处理负圈。
• 时间复杂度：，空间复杂度
• 算法示意：
6. 活动网络
1. AOV 网络（Activity On Vertex，用顶点表示活动的网络）
• 拓扑排序：不能存在有向环，时间复杂度
2. AOE 网络（Activity On Edges，用边表示活动的网络）
1. 工程只存在一个开始点（源点）和结束点（汇点）。
2. “事件”指的是一个顶点，这个顶点一般有多条边，“活动”指的是一条边。事件开始，活动不一定开始，一个事件的多个活动可以在不同的时间开始。因此 [事件的最早开始时间] 指的是源点到该事件的最长路径，[活动的最早开始时间] 和 [事件的最早开始时间] 相同。事件的开始一定伴随着活动的开始，但不一定是所有活动开始。
3. 算法：
1. 事件的最早开始时间：源点到该点的最长路径。简单起见，为 max(其所有前驱的最早开始时间 + 边长度)。
2. 事件的最晚开始时间：min(其所有后继的最晚开始时间 - 边长度)
3. 活动的最早开始时间：= 事件的最早开始时间
4. 活动的最晚开始时间：<i, j> = j 事件最晚开始时间 - 边长度
4. 示例：

排序

1. 插入排序
1. 直接插入排序
1. 从第一个元素开始，将后面的元素插入前面元素形成的序列中。将每次插入的元素放入 temp 变量暂存（方便腾地方）。
2. 稳定。适用于基本有序的序列。
3. 时间复杂度：平均情况下，
2. 折半插入排序
1. 直接插入的改进，利用序列的有序性进行折半查找。
2. 稳定。
3. 时间复杂度：
3. 希尔排序
1. 逐渐缩小增量的分组插入排序。
2. 不稳定。
3. 示例：

4. 快速排序
1. 选一个 pivot，通常为第一个。维护一个 pivot pos 为 left。从第二个元素开始，每次发现比 pivot 小的元素（i），pivot pos ++，并交换 pivot pos 处的元素和 i 处的元素。最后将 pivot pos 处的元素和首位元素交换。并对两侧的序列递归操作。
2. 不稳定。
3. 时间复杂度：平均 ，最坏情况退化为
5. 选择排序
1. 直接选择排序
1. 每次从后面的序列中选择一个最小的，和前面序列尾部元素交换。
2. 不稳定。
3. 时间复杂度：
2. 锦标赛排序
1. 胜者树：一棵完全二叉树。其中的叶结点是要排序的元素，非叶结点是两个子结点中胜者的代表。根节点代表着所有元素中的胜者。胜者树一般存放待排序元素的下标（当然如果元素足够基本，也可以直接存放元素）。
2. 注：当某个叶子被标记为 时，其兄弟直接上浮，这不算一次比较（与无穷比较不算比较，因为只需要看对方是否为无穷，并不需要真正比较）。
3. 稳定。（相同元素，左边先出）
4. 时间复杂度：。空间复杂度：。
3. 堆排序
1. 为了从小到大排序，需要建立最大堆。使得堆顶始终在数组的起始地址，便于维护堆。
2. 不稳定。
3. 时间复杂度：。空间复杂度：。
6. 归并排序
1. 见图：
2. 稳定。
3. 时间复杂度：。空间复杂度：。
7. 各种排序方法的比较

文件、外部排序与外部搜索

1. B 树
1. 定义，m 阶 B 树
1. 每个节点最多有 m-1 个关键码
2. 根节点可以只有 1 个关键码
3. 非根节点（不包括失败节点）至少有 个关键码（失败节点至少有 个）。
4. 所有的叶节点（失败节点）都位于同一层。
2. 结论
1. B 树第 h 层至少有 个节点。
2. 树中关键码有 N 个，N + 1 = 失败节点数 = 位于 h + 1 层的节点数，N + 1 ，。
3. 插入
• 分裂操作：将第 m / 2 个元素当作新根，这个新根上移到父节点，新根的左右指针分别指向左、右两部分。
4. 删除
1. 若该节点不是叶节点，则用左子树最大或右子树最小来替换。
2. 在叶节点上的删除
1. 如果在根节点，或删除前关键码 ，则直接删除。
2. 如果删除前关键码数量 ，但是其兄弟关键码 ，则将根下移作为删除节点的补充，从兄弟节点选一个作为新根。
3. 如果删除前关键码数量和其兄弟的关键码数量均 ，则需要合并这两个节点。合并时将父节点指针下移与两个节点合并为一个节点。然后向上检查，最坏情况必须检查到根节点。（保证失败节点都在一层，不在一层肯定不对）
4. 图例：

2. B+ 树
1. 区别：所有关键码都存放在叶结点中，上层的非叶结点的关键码是其子树中最小（或最大）关键码的复写。叶结点包含了全部关键码及指向相应数据记录存放地址的指针，且叶结点本身按关键码从小到大顺序链接。
2. 定义：m 阶 B+ 树（最大关键码覆写）
1. 每个节点最多 m 棵子树
2. 根节点最少 1 棵子树，其他节点至少 棵子树。
3. 所有叶节点在同一层，按从小到大的顺序排列。
3. 插入：
1. 插入仅在叶节点上进行。每次插入都要检查是否超出 m 个。
2. 若超出，则进行分裂。原则是左多右少。（左 ，右 ）。分裂后将缺少的最大值复制一份放入根节点。
3. 示例：4 阶 B+ 树，最大关键码覆写，插入 53, 63, 90, 88, 15, 10, 44, 68, 74



提示：注意下面红色的箭头不要忘了。
4. 删除
1. 删除仅在叶节点上进行。若删除后关键码 ，则直接删除。若删除的是最大节点，上层的副本可以保留。
2. 若删除后关键码 ，但兄弟的关键码 ，则把兄弟最左的拿来，并修改上层分界关键码的值。
3. 如果兄弟的关键码已达下限，那么直接将左右兄弟合并。合并后会导致父节点的关键码数量减少，可能需要再进行合并。
注：第 2 条说的借兄弟的，可能借一个，也可能借一块，如下（根节点的右兄弟向左兄弟借了一块）：

往年卷

1. 长度有限不是算法的基本特征.

2. 带有一个头结点 XX, 这个头结点不算 XX 中的元素. 也就是说, XX 为空等价于只有一个头结点.

3. 一棵有 个结点的满二叉树共有 个叶子, 个非叶结点.

4. 树的后根遍历序列等同于对该树对应的二叉树进行 的序列

5. 二叉树的遍历
1. 前序：根左右，中序：左根右，后序：左右根
2. 前序与中序相同：空树（别忘了！）或左子树为空的单支树
3. 中序与后序相同：空树或右子树为空的单支树
4. 前序与后序相同：空树或只有根的树

6. 并查集
1. 根据树高执行 union：每次都将矮树并到高树上
2. 根据节点个数执行 union：每次都将节点少的树并到节点多的树上

7. 闭散列的线性探查法：ASL不成功的算式中，分数的分母是散列函数可计算的地址范围，非表长度。

8. 线性探查法：

9. 筛选法建堆从最后一个非叶子节点开始。