1. 基本数据结构

# 基本概念

# 数据与数据结构

• 数据结构：描述现实世界实体之间的数学模型，以及在计算机中的表示与实现。
• 数据元素（Data Element）：数据的基本单位，通常被视为一个整体。
• 数据项（Data Item）：数据结构中讨论的最小单位，是构成数据元素的最小不可分割的部分。
• 数据类型：一个值的集合和定义在该集合上的一组操作的总称。在高级语言中，数据类型可分为原子类型（不可再分）和结构类型（由多个值组成）。
• 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。

---

# 关系与性质

• 二元关系：元素之间的一一对应关系，可以用笛卡尔积来表示。
• 等价关系：满足自反性、对称性、传递性的关系。例如，数学中的“=”关系。
• 偏序关系：满足自反性、反对称性、传递性的关系。例如，数学中的“≤”关系。
• 拟序关系：满足反自反性、反对称性、传递性的关系。例如，数学中的“<”关系。
• 全序关系：满足偏序关系且任意两个元素都可比较的关系。例如，数学中的“≤”关系。

---

# 线性结构

# 线性表

• 基本概念：
  • 前驱、后驱、直接前驱、直接后驱：用于描述元素在序列中的位置关系。
  • 有序：元素之间存在确定的先后次序。
  • 同质：所有数据元素都属于同一数据类型。
  • 位序：元素在表中的位置序号。
• 实现方式：
  • 顺序表：基于数组实现。访问方便（时间复杂度为 O(1)），但插入和删除困难（需要移动元素，时间复杂度为 O(n)）。
  • 链表：基于指针实现。访问困难（需要从头遍历），但插入和删除相对简单（只需修改指针），空间利用率高。
• 链表类型：
  • 带表头结点的单向链表：方便处理链表头部的操作。
  • 双向循环链表：可从两个方向遍历，且尾部与头部相连，提高操作的灵活性。

---

# 栈

• 基本概念：一种特殊的线性表，遵循“后进先出”（LIFO）原则。
• 常见应用：
  • 括号匹配：利用栈的特性检查表达式中的括号是否正确匹配。
  • 进制转换：通过反复取余和压栈实现。
  • 算术表达式求值：
    • 前缀、中缀、后缀表达式的相互转换。
    • 后缀表达式计算：遇到操作数则进栈，遇到操作符则将栈顶的两个操作数出栈运算，并将结果进栈。
      • 注意：处理减法时，需要确保运算顺序正确，如 s.push(-s.pop() + s.pop())。
• 递归与栈：
  • 递归本质上是利用了系统栈来实现。
  • 常见递归问题：阶乘求值、辗转相除法、斐波那契数列、汉诺塔问题等。
  • 汉诺塔问题：将 $n$ 个盘子从塔座 $X$ 移动到塔座 $Z$，借助 $Y$。总移动次数为 $2^n - 1$。
  • 递归的消除：
    • 没有统一的解决方案。
    • 部分递归可直接通过循环或递推实现。
    • 很多情况下，需要显式地使用栈来模拟递归过程，实现非递归。

---

# 队列

• 基本概念：一种特殊的线性表，遵循“先进先出”（FIFO）原则。
  • 队尾（rear）：允许插入的一端，执行入队操作。
  • 队头（front）：允许删除的一端，执行出队操作。
• 实现方式：
  • 循环队列：通过数组实现。
    • 当 front == rear 时，无法区分队列是空还是满。解决方法包括：设置一个空位、使用一个标志变量或记录队列长度。
  • 链式队列：通过链表实现。
    • 队头在链表头，队尾在链表尾。
    • 入队时不会出现队满问题，但需要注意队空情况，条件为 front == NULL。

---

# 串（字符串）

• 基本概念：
  • 串是限定数据元素为字符的有限长度线性表。
  • 子串：主串中任意一个连续的字符序列。子串在主串中的位置通常指其第一个字符在主串中的位置。
  • 串的操作通常以子串为单位进行。
• 串匹配算法：
  • Brute-Force 算法：最简单的匹配算法，效率较低。
  • KMP 算法：
    • 通过预先计算部分匹配表（next 数组），在主串和模式串失配时，模式串可以跳过部分字符，避免不必要的比较。
    • 移动步数只与模式串有关，与主串无关。
    • 时间复杂度为 $O(m+n)$。
  • Horspool 算法：
    • 通过预先计算Last-Occurence 函数，实现从右向左的匹配。
    • 当发生失配时，根据不匹配的字符在模式串中的位置，跳过尽可能多的字符。
    • 最好时间复杂度为 $O(n/m)$，最坏为 $O(nm)$。

---

# 非线性结构

# 树

# 树的基本概念与性质

• 基本概念：
  • 结点：树的基本组成单位。
  • 根结点：树中没有前驱的结点。
  • 分支结点：度（子树个数）不为零的结点。
  • 叶子结点：度为零的结点。
  • 结点的度：结点的子树个数。
  • 树的度：所有结点中度的最大值。
  • 堂兄弟：处于同一层，且根结点是兄弟关系的结点。
  • 祖先：从根结点到该结点的路径上的所有结点。
  • 子孙：某个结点所有子树中的所有结点。
  • 结点的层次：根结点为第1层。
  • 树的深度：树中叶子结点所在的最大层次。
• 性质：
  • 树中的结点总数等于所有结点的度数之和加1。
  • 若 $k$ 叉树的层次从1开始，第 $i$ 层上至多有 $k^{i-1}$ 个结点。

---

# 二叉树

• 基本概念：
  • 二叉树可以为空，每个结点最多有两个子树（左子树和右子树）。
  • 满二叉树：所有分支结点都有左右子树，且所有叶子结点都在同一层次。
  • 完全二叉树：除最后一层外，其他各层都是满的，且最后一层的所有结点都集中在左边。
• 性质：
  • 任何一棵二叉树中，叶子结点个数比度为2的结点个数多1。
  • 用数组存储时，编号为 $i$ 的结点的孩子结点分别为 $2i+1$ 和 $2i+2$（从0开始编号）。
• 存储方式：
  • 顺序表存储：适用于完全二叉树，但空间浪费大。
  • 链式存储：通过指针连接，更灵活。
• 遍历方式：
  • 先序遍历（根-左-右）
  • 中序遍历（左-根-右）
  • 后序遍历（左-右-根）
  • 层序遍历：借助队列实现。
  • 非递归遍历：需要借助栈来模拟递归过程。
  • 唯一确定二叉树：中序遍历配合任意其他遍历方式（先序或后序）都可以唯一确定一棵二叉树。

---

# 霍夫曼树与编码

• 霍夫曼树（最优二叉树）：
  • 路径长度：从根结点到该结点的分支数目。
  • 带权路径长度（WPL）：所有叶子结点的带权路径长度之和。
  • 霍夫曼树：WPL 最小的二叉树。特点是权值大的结点离根结点最近。
• 霍夫曼编码：
  • 前缀编码：任何字符的编码都不是其他字符编码的前缀。
  • 可以使用霍夫曼树来构造前缀编码，叶子结点代表字符，左分支为0，右分支为1。

---

# 图

# 图的基本概念

• 图（Graph）：由顶点（V）和边（E）组成的集合。
• 邻接顶点：由同一条边连接的两个顶点。
• 完全图：任意两个顶点之间都存在边。
• 度：与顶点相连的边数。
• 握手定理：无向图中所有顶点的度数之和等于边数的两倍。
• 网络：边带有权值的图。
• 连通分量：无向图的极大连通子图。
• 桥/边连通：移除该边会增加连通分量数。
• 关节点/重连通图：移除该顶点会增加连通分量数。
• 强连通图：任意两个顶点之间都存在路径。
• 强连通分量：有向图的极大强连通子图。
• 欧拉路径/欧拉回路：经过图中所有边恰好一次的路径/回路。

---

# 图的存储与遍历

• 存储方式：
  • 邻接矩阵：适用于稠密图，方便检查两点之间是否有边。
  • 邻接表：适用于稀疏图，节省空间。
• 遍历算法：
  • 深度优先搜索（DFS）：使用栈实现。
  • 广度优先搜索（BFS）：使用队列实现。
  • 可用于求简单路径和最短路径。

---

# 最小生成树（MST）

• 概念：连接图中所有顶点的，且总权重最小的子图。
• 算法：
  • Prim 算法：从一个顶点开始，逐步加入最近的顶点。
    • 适用于稠密图，使用邻接矩阵实现。
    • 时间复杂度为 $O(V^2)$。
  • Kruskal 算法：按边权重从小到大排序，逐步加入边，直到所有顶点连通。
    • 适用于稀疏图，使用邻接表和并查集实现。
    • 时间复杂度为 $O(E \log E)$。

---

# 最短路径算法

• 单源最短路径：从一个源点到其他所有顶点的最短路径。
  • Dijkstra 算法：
    • 与 Prim 算法类似，但根据路径权重而非边权重。
    • 时间复杂度为 $O(V^2)$。
• 全源最短路径：求图中所有顶点对之间的最短路径。
  • Floyd 算法：
    • 基于动态规划，通过中间点逐步更新路径。
    • 时间复杂度为 $O(V^3)$。

---

# 图算法对比

算法	优先级（原则）	结果
DFS	停留时间短	DFS 树
BFS	停留时间长	BFS 树
Prim/Kruskal	边权值	最小生成树（MST）
Dijkstra	路径权值	单源最短路径树（SPT）

---

# 其他数据结构

# 并查集

• 概念：一种用于处理不相交集合的树形数据结构。
• 基本操作：
  • Union（并）：将两个集合合并为一个。
  • Find（查）：查找某个元素所在的集合。
• 实现方式：
  • 基于数组：简单，但查找和合并效率低。
  • 基于指针：效率较高，可通过路径压缩进行优化。
• 效率对比：

实现方式	查找复杂度	一次合并复杂度	多次合并（构造）复杂度
基于数组	$O(1)$	$O(n)$	$O(n \log n)$
基于指针	$O(\log n)$	$O(1)$	$O(n)$
改进的基于指针（路径压缩）	$O(\alpha(n))$	$O(1)$	$O(n)$

---

# 优先级队列与堆

# 优先级队列

• 概念：一种特殊的队列，每次出队的元素是优先级最高的。
• 特点：
  • 只能对优先级最高的元素进行查询和删除。
  • 可以对所有元素进行修改优先级。
• 实现方式：
  • 可以使用各种线性表，但效率不一。
  • 基于堆的实现最为高效。

---

# 堆

• 概念：一种特殊的完全二叉树。
  • 最大堆：每个父结点的值都大于或等于其子结点。
  • 最小堆：每个父结点的值都小于或等于其子结点。
• 存储方式：通常使用一维数组。
• 堆的修复（Heapify）：
  • 自顶向下：当父结点的值不满足堆性质时，将其与子结点交换。时间复杂度为 $O(\log n)$。
  • 自底向上：当子结点的值不满足堆性质时，将其与父结点交换。时间复杂度为 $O(\log n)$。
• 堆的构造：
  • 自顶向下：逐个插入新元素并进行自底向上堆化，时间复杂度为 $O(n \log n)$。
  • 自底向上：将数组视为树，从最后一个非叶子结点开始进行自顶向下堆化，时间复杂度为 $O(n)$。

---

# 优先级队列效率对比

实现方式	插入	查找	删除	修改
无序顺序表	$O(1)$	$O(n)$	$O(n)$	$O(1)$
有序顺序表	$O(n)$	$O(1)$	$O(n)$	$O(n)$
无序链表	$O(1)$	$O(n)$	$O(n)$	$O(1)$
有序链表	$O(n)$	$O(1)$	$O(1)$	$O(n)$
堆	$O(\log n)$	$O(1)$	$O(\log n)$	$O(\log n)$