复习日志：数据结构
基本概念
- 算法设计的要求包括：健壮性、正确性、可读性。
- 算法的重要特性包括：有输入和输出、确定性、可行性、有穷性。
- 数据结构可以形式化地定义为一个二元组 $(D，R)$，其中 D 是数据元素的集合，R 是数据元素之间的关系集合。
- 数据结构通常分为四类基本结构：集合、线性结构、树形结构和图状结构。
- 抽象数据类型按其值的不同特性，可分为原子类型、固定聚合类型、可变聚合类型。
- 内排序的排序过程在内存中进行。外排序是指待排序的元素存储在外存上，由于待排序的全部元素无法一次装人内存，需要在内存和外存之间移动，以达到排序全部元素的目的。
线性结构
- 采用顺序查找法查找长度为 n 的顺序表时，查找成功的平均查找长度为 $(n + 1) / 2$。
- 在一个顺序表的表尾插入一个元素的时间复杂度为 $O(1)$。
- 将长度为 n 的单链表接在长度为 m 的单链表之后，这个过程的时间复杂度为 $O(m)$。
- 设顺序表的长度为 n，则顺序查找的平均比较次数为 $(n + 1) / 2$。
- 顺序表和一维数组一样，都可以按下标随机（或直接）访问。
- 顺序表查找是指在顺序存储结构上进行查找。
哈希表
- 在散列表（哈希表）中，处理冲突的方法主要有两种：开放定址法和链接法。
- 开放定址法：
- 当发生冲突时，会按照某种探测方法（如线性探测、二次探测等）在散列表中寻找下一个空闲的位置。
- 这种方法可能会导致“聚集”现象，即冲突的元素会集中在某些区域，从而增加查找时间。
- 平均查找长度（ASL）通常较高，尤其是在散列表填充因子较高时。
- 链接法：
- 当发生冲突时，冲突的元素会被存储在同一个位置的链表中。
- 这种方法避免了聚集现象，查找效率通常较高。
- 平均查找长度（ASL）通常较低，尤其是在散列表填充因子较高时。
- 比较：
- 开放定址法的平均查找长度通常高于链接法，因为开放定址法需要更多的探测次数来解决冲突。
- 二分查找的平均查找长度是 $O(\log n)$，而散列表的平均查找长度在理想情况下是 $O(1)$，但在开放定址法中，由于冲突处理效率较低，平均查找长度可能会高于二分查找。
- 开放定址法：
- 例题：设有 n 个关键字具有相同的 Hash 函数值，则用线性探测法把这 n 个关键字映射到 Hash 表中，需要做 $n(n - 1) / 2$ 次线性探测。
- 线性探测法解决冲突的办法是一旦目标空间被占有，则探测相邻的下一个空间，如果空闲则插入，否则继续向下一个探测，如果到了 Hash 表末尾则返回 Hash 表开头进行探测，一旦全部空间都被占据，则无法插入。第一个关键字映射到 Hash 表时插入成功，从第二个关键字开始出现冲突，第二个关键字映射时做 1 次线性探测，第三个关键字映射时做 2 次线性探测，以此类推，第 n 个关键字映射时做 n - 1 次线性探测，因此共需要做 $n(n - 1) / 2$ 线性探测。
排序
- 冒泡排序在最坏的情况下需要比较 $n(n - 1) / 2$ 次，时间复杂度为 $O(n^2)$，无论数据的初始状态如何。
- 选择排序在最好、最坏、平均情况下的时间复杂度均为 $O(n^2)$。
- 快速排序的平均时间复杂度为 $O(n\log n)$，在最坏情况下的时间复杂度为 $O(n^2)$ 。
- 在快速排序的第 i 趟排序结果中，至少有 i 个元素在其最终位置上。
- 希尔排序的时间复杂度取决于增量序列的选择，通常介于 $O(n\log n)$ 和 $O(n^2)$ 之间。
- 堆排序、冒泡排序和插入排序的空间复杂度都为 $O(1)$，归并排序的空间复杂度最高，为 $O(n)$。
- 例题：设有 n 个待排序的记录关键字，则在堆排序中需要 1 个辅助记录单元。
- 堆排序和希尔排序都利用了顺序存储的随机访问特性。
- 二分查找法又称折半查找法，最多比较次数为 $\log\lceil (n + 1) \rceil$。
- 堆排序的时间复杂度始终为 $O(n\log n)$，无论数据的初始状态如何。
- 例题：将 32 个元素进行堆排序，则最坏的情况需要比较 160 次。
- 静态查找与动态查找的根本区别在于施加在其上的操作不一样。静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。
- 插入排序的比较次数依赖于数据的初始状态：在最优情况下（数据已经有序），比较次数是 $O(n)$，而在最坏情况下（数据是逆序的），比较次数是 $O(n^2)$。
树 / 图论
树
- 对于任一棵树，它的节点总数等于总度数加 1。
- 例题：在一棵度为 3 的树中，度为 3 的节点个数为 2，度为 2 的节点个数为 1，度为 1 的节点个数为 0，则度为 0 的节点个数为 6 。
- 解析：$2 + 1 + 0 + x = 6 + 2 + 1\ \rightarrow \ x = 6$。
- 例题：在一棵度为 3 的树中，度为 3 的节点个数为 2，度为 2 的节点个数为 1，度为 1 的节点个数为 0，则度为 0 的节点个数为 6 。
- 设哈夫曼树中的叶节点总数为 $m$，若用二叉链表作为存储结构，则该哈夫曼树中总共有 $2m$ 个空指针域。
- 哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。在哈夫曼树中：
- 叶节点：表示实际的字符或数据，总数为 $m$。
- 内部节点：表示合并过程中的中间节点。哈夫曼树的构造过程会生成 $m − 1$ 个内部节点。
- 总节点数：哈夫曼树的总节点数为叶节点数加上内部节点数，即 $m + (m − 1) = 2m − 1$。
- 哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。在哈夫曼树中：
- 在线索二叉树中，一个节点是叶节点的充要条件是左、右线索标志均为 1。
- 例题：线索二叉树中某节点 R 没有左孩子节点的充要条件是
R.ltag = 1。
- 例题：线索二叉树中某节点 R 没有左孩子节点的充要条件是
- 树的存储形式有顺序存储表示和链式存储表示。其中，链式存储表示又包括双亲表示、左子女右兄弟表示等。
- 例题：常用的表示树的链表结构的有双亲表示法、孩子兄弟表示法、孩子表示法。
- 二叉树由左子树、右子树和根节点基本单元构成。
- B 树是一种平衡的多路搜索树，常用于数据库和文件系统。对于一棵 m 阶的 B 树：
- 在 B 树中，根节点的子树数量范围为 $[2，m]$。
- B 树的叶节点之间通常不通过指针链接。
- 各节点内的关键字均按升序或降序排列。
- B 树是一种平衡树，所有叶节点必须位于同一层。
- 将树转换为二叉树后，其根节点的右子树一定为空。
图论基础
- 设某强连通图中有 n 个顶点，则该强连通图中至少有 n 条边。
- 在一个有向图中，若从节点 i 到节点 j 有路径，并且节点 j 到 i 有路径，那么该图为强连通图。当强连通图中存在一个环时，边数最少，因此至少 n 条边。
- 在含有 n 个顶点的无向图中，边数 $e\leq n(n - 1) / 2$。
- 稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压宿规律找出相应的映象函数。
- 广义表的第一个表元素为表头，由表中除表头外的其他元素组成的表称为广义表的表尾。
- 广义表是对线性表的扩展，各表元素在表中以线性序列排列，这个顺序不能交换，因此广义表是一种线性结构。广义表的性质包括有次序性、有长度、有深度（多层次）、可递归、可共享。
- 有向图的连通包括强连通、弱连通、单侧连通。
- 强连通是指有向图中任意两个节点之间都存在双向路径。即对于任意节点 u 和 v，都存在从 u 到 v 的路径和从 v 到 u 的路径。
- 弱连通是指将有向图的所有边视为无向边后，图是连通的。即忽略边的方向后，图中任意两个节点之间都存在路径。
- 单侧连通是指有向图中任意两个节点之间至少存在一条单向路径。即对于任意节点 u 和 v，要么存在从 u 到 v 的路径，要么存在从 v 到 u 的路径。
- 最小生成树的代价（即所有边的权值之和）是唯一的。如果一条边是图中权值最小的边，并且它不会与已选边形成环，那么它一定会出现在最小生成树中。但如果存在多条权值相同的最小边，可能不会全部出现在同一个最小生成树中。
- 若路径上各个顶点不互相重复，则称为简单路径。若路径上的第一个顶点与最后一个顶点重合，则称为回路。若有向图中存在回路，则不存在拓扑序列。
AOV 网络
- AOV 网络（Activity On Vertex Network）是一种用于表示工程项目的活动及其依赖关系的有向图。在 AOV 网络中：
- 顶点（Vertex）：表示活动（任务或事件）。每个顶点代表一个具体的活动。
- 有向边（Directed Edge）：表示活动之间的依赖关系。如果存在一条从顶点 (A) 指向顶点 (B) 的有向边，则表示活动 (A) 必须在活动 (B) 开始之前完成。
- 特点
- AOV 网络是一个有向无环图（DAG，Directed Acyclic Graph），因为如果图中存在环，则意味着某些活动相互依赖，无法确定执行顺序，从而导致项目无法完成。
- AOV 网络通常用于项目管理中的拓扑排序，以确定活动的合理执行顺序。
- 拓扑排序：拓扑排序是对 AOV 网络中的顶点进行线性排序，使得对于每一条有向边 ( (u，v) )，顶点 ( u ) 在顶点 ( v ) 之前出现。拓扑排序的步骤通常如下：
- 找到入度为 0 的顶点（即没有前置活动的顶点），将其加入排序结果。
- 从图中移除该顶点及其所有出边。
- 重复上述过程，直到图中没有顶点为止。 如果图中存在环，则无法完成拓扑排序。
- 示例：假设有一个项目包含以下活动及其依赖关系：
- 活动 (A) 必须在活动 (B) 和 (C) 之前完成。
- 活动 (B) 必须在活动 (D) 之前完成。
- 活动 (C) 必须在活动 (D) 之前完成。 对应的 AOV 网络如下：
1 2 3 4 5
A / \ B C \ / D拓扑排序的结果可能是：(A，B，C，D) 或 (A，C，B，D)。
- 应用：AOV 网络广泛应用于项目管理、任务调度、编译器设计等领域，用于确定任务执行的合理顺序。
This post is licensed under CC BY 4.0 by the author.