三、数据结构

发表于 2025-05-05 更新于 2025-05-07 分类于软件设计师

1 线性结构

数据结构是程序设计的重要基础，它讨论数据元素集合及其相互关系和构造方法。
数据结构分为线性结构和非线性结构，非线性结构包括树结构和图结构。
算法设计依赖数据结构，合理数据结构可提升算法效率。

1.1 线性表

1.1.1 线性表的定义

线性表是 $n(n \geq 0)$ 个元素的有限序列，通常表示为 $(a_1, a_2, \cdots, a_n)$ 。
非空线性表的特点：
- 存在唯一的“第一个”元素。
- 存在唯一的“最后一个”元素。
- 除第一个元素外，每个元素只有一个直接前驱。
- 除最后一个元素外，每个元素只有一个直接后继。

1.1.2 线性表的存储结构

1.1.2.1 线性表的存储结构

1. 顺序存储

定义：用一组连续存储单元依次存储线性表元素，逻辑相邻则物理相邻。
优点：可随机访问元素。
缺点：插入和删除需移动元素。
插入操作：平均需移动 $\frac{n}{2}$ 个元素。
删除操作：平均需移动 $\frac{n-1}{2}$ 个元素。

1.1.2.2 链式存储

定义：用指针链接结点存储数据元素。
基本结构：每个结点包含数据域和指针域。
单链表：
- 插入操作：修改指针。
- 删除操作：修改指针并释放空间。
查找操作：从头指针开始顺序查找。
插入操作：在指定位置插入新结点。
删除操作：删除指定位置的结点。
优点：插入和删除无需移动元素。

变种链表结构

双向链表：每个结点包含两个指针，分别指向前驱和后继。
循环链表：尾结点指针指向头结点。
静态链表：用数组模拟链表结构。

1.2 栈和队列

1.2.1 栈

定义：后进先出（LIFO）的线性表，一端为栈顶，另一端为栈底。
基本运算：
- 初始化栈 InitStack(S)。
- 判空 isEmpty(S)。
- 入栈 Push(S, x)。
- 出栈 Pop(S)。
- 读取栈顶元素 Top(S)。
存储结构：
- 顺序存储：用连续存储单元，附设指针 top。
- 链式存储：用链表，头指针为栈顶指针。
应用：表达式求值、括号匹配、递归处理。

1.2.2 队列

队列是一种先进先出（FIFO）的线性表，元素从队尾插入，从队头删除。其基本运算包括：

初始化队列 InitQueue(Q)。
判空 isEmpty(Q)。
入队 EnQueue(Q, x)。
出队 DelQueue(Q)。
读取队头元素 FrontQue(Q)。

顺序存储

顺序队列利用连续存储单元存放元素，设置队头指针 front 和队尾指针 rear。为提高空间利用率，常将顺序队列设计为循环队列。

入队操作：rear = (rear + 1) % MAXSIZE。
出队操作：front = (front + 1) % MAXSIZE。
特殊情况处理：需区分队空（front == rear）和队满（(rear + 1) % MAXSIZE == front）。

链式存储：链队列（队列的链式存储）包含头指针和尾指针，便于操作。队空时头指针和尾指针均指头结点。
队列的应用：队列适用于需要排队的场景，如操作系统中的打印任务队列、事件模拟等。

1.3 串

1.3.1 串的定义及基本运算

串是字符构成的有限序列，记作 $S = 'a_1a_2 \cdots a_n'$ ，其中 $S$ 是串名，单引号内是串值。

基本概念

空串：长度为 0 的串。
空格串：由一个或多个空格组成的串。
子串：串中任意连续字符的序列，所在位置是首次出现时的第一个字符位置。
串相等：两串长度相等且对应字符相同。
串比较：比较两串大小时，逐字符比较 ASCII 值，较短的串较小。

基本操作

赋值操作 StrAssign(s, t)。
连接操作 Concat(s, t)。
求串长 StrLength(s)。
串比较 StrCompare(s, t)。
取子串 SubString(s, start, len)。

1.3.2 串的存储结构

顺序存储：用连续存储单元存储字符序列，可通过字符数组或动态申请空间实现。
链式存储：用链表存储字符，结点可存储一个或多个字符，需考虑存储密度。

1.3.3 串的模式匹配

模式匹配是查找子串（模式串）在主串中的位置，是串处理的重要运算。

1.3.3.1 朴素的模式匹配算法

基本思想：从主串第一个字符开始逐个比较，不匹配则主串指针回退。
时间复杂度：
- 最好情况： $O(n + m)$ 。
- 最坏情况： $O(n \times m)$ 。

1.3.3.2 改进的 KMP 算法

核心思想：不回退主串指针，利用部分匹配信息移动模式串。
关键：构造 next 数组，记录模式串的部分匹配长度。
时间复杂度： $O(n + m)$ 。

2 数组、矩阵和广义表

2.1 数组

数组的定义及基本运算

数组是线性表在维数上的扩展，元素类型相同，结构一致。

数组的顺序存储

特点：数组元素数目固定，适合采用顺序存储结构。
存储方式：
- 行优先存储：按行存储元素。
- 列优先存储：按列存储元素。
地址计算公式(设每个元素占 L 个单元，二维数组有 m 行 n 列)：
- 行优先： $\text{Loc}(a_{ij}) = \text{Loc}(a_{11}) + ((i-1) \times n + (j-1)) \times L$
- 列优先： $\text{Loc}(a_{ij}) = \text{Loc}(a_{11}) + ((j-1) \times m + (i-1)) \times L$

2.2 矩阵

矩阵是数组的一种特殊形式，通常用于表示二维数据结构。

特殊矩阵

特殊矩阵是指矩阵中 0 元素（或非 0 元素）的分布有一定规律的矩阵。常见的特殊矩阵包括：

对称矩阵：nxn的矩阵中元素都满足 $a_{ij} = a_{ji}$
三角矩阵：三对角矩阵的非 0 元素 $a_{ij}$ 仅存在于主对角线及其上下各一条对角线上。
对角矩阵：对角矩阵是指矩阵中的非 0 元素都集中在以主对角线为中心的带状区域中。

稀疏矩阵

稀疏矩阵是指矩阵中的非 0 元素远少于 0 元素的矩阵。稀疏矩阵的存储方式有：

三元组顺序表
十字链表

2.3 广义表

广义表是线性表的推广，由 0 个或多个单元素或子表组成的有限序列。广义表一般记为： $LS = (a_1, a_2, \cdots, a_n)$ ，其中， $a_i$ 可以是单个元素或广义表。

基本操作

取表头 head(LS)：获取广义表的第一个元素。
取表尾 tail(LS)：获取除第一个元素外的其余元素。

特点

可以是多层次的结构，元素可以是子表。
元素可以是已定义的广义表的名字，支持共享。
可以是一个递归的表，元素也可以是本广义表的名字。

存储结构

由于广义表的元素可以具有结构，通常采用链式存储结构：

表头和表尾指针：用于唯一确定广义表。
元素结点：包含标记（tag）和数据指针（hp），用于存储元素值或指向子表。

3 树

3.1 树与二叉树的定义

3.1.1 树的定义

树是一种非线性结构，由有限个节点组成，满足以下条件：

有且仅有一个称为根的节点。
其余节点分为 $m (m \geq 0)$ 个互不相交的有限子集 $T_1, T_2, \cdots, T_m$ ，每个子集本身是一棵树，称为根节点的子树。

树的定义是递归的，表明树由若干棵子树构成，子树又由更小的子树构成。

树的特点

树中元素之间有严格的层次关系。
每个节点最多和上一层的一个节点（双亲结点）有直接关系，和下一层的多个节点（孩子结点）有直接关系。

这种层次结构使得树在描述分类和组织数据时非常有用。

3.1.2 树的基本概念

双亲、孩子和兄弟：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲，具有相同双亲的节点互为兄弟。
节点的度：一个节点的子树个数称为该节点的度。
叶子节点：度为 0 的节点称为叶子节点或终端节点。
内部节点：度不为 0 的节点，也称为分支节点或非终端节点。除根节点外，分之节点也称为内部节点。
节点的层次：根节点为第一层，根的孩子为第二层，依此类推。
树的高度：树的最大层数称为树的高度。
有序树：若树中节点的各子树从左到右具有次序，则称为有序树，否则为无序树。

3.1.3 二叉树的定义

二叉树是 n 个节点的有限集合，它或者是空树 $(n = 0)$ ，或者是由一个根节点及两棵不相交的且分别称为左、右子树的二叉树所组成。二叉树同样具有递归性质。

二叉树的特点

二叉树中每个节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。
二叉树节点最大度为 2，而树中不限制节点的度数。

3.2 二叉树的性质与存储结构

3.2.1 二叉树的性质

第 $i$ 层最多有 $2^{i-1}$ 个结点。
高度为 $k$ 的二叉树最多有 $2^k - 1$ 个结点。
对于任意二叉树，若终端结点数为 $n_0$ ，度为 2 的结点数为 $n_2$ ，则 $n_0 = n_2 + 1$ 。
有 $n$ 个结点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$ 。

3.2.2 二叉树的存储结构

顺序存储结构

顺序存储适用于完全二叉树，结点按层次顺序存储。
每个结点的双亲、左孩子和右孩子的编号可通过公式计算。

链式存储结构

链式存储使用二叉链表，每个结点包含数据域和两个指针域。
适用于任意二叉树，包括完全二叉树和非完全二叉树。

节点类型定义

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

3.3 二叉树的遍历

二叉树的遍历是指按照某种策略访问树中的每个结点，且仅访问一次的过程。二叉树的遍历有三种基本方法：先序遍历、中序遍历和后序遍历。

先序遍历（PreOrder）

访问顺序：根结点 -> 左子树 -> 右子树

函数实现：

void PreOrder(BiTree root) {
   if (root != NULL) {
       printf("%d", root->data);  // 访问根结点
       PreOrder(root->lchild);  // 先序遍历左子树
       PreOrder(root->rchild);  // 先序遍历右子树
   }
}

中序遍历（InOrder）访问顺序：左子树 -> 根结点 -> 右子树
后序遍历（PostOrder）访问顺序：左子树 -> 右子树 -> 根结点
非递归中序遍历：使用栈实现非递归中序遍历。

3.4 线索二叉树

线索二叉树是对非线性结构进行线性化的过程，使得每个结点（除第一个和最后一个）在这些线性序列中均有一个直接前驱和直接后继。

建立线索二叉树

增加两个指针域：ltag和rtag，以区分孩子指针的指向。
ltag = 0：lchild域指示结点的左孩子。
ltag = 1：lchild域指示结点的直接前驱。
rtag = 0：rchild域指示结点的右孩子。
rtag = 1：rchild域指示结点的直接后继。

3.5 最优二叉树

3.5.1 最优二叉树

树的先导知识

路径：是指从树中一个结点到另一个结点的分支所构成的路线。
路径长度：路径上的分支数目
树的路径长度：指从根结点到每个叶子结点的路径之和。
结点的权：树中结点被赋予一个表示某种意义的数值
带权路径长度：从结点到根之间的路径长度乘以结点的权值
树的带权路径长度（WPL）：所有叶子结点的带权路径长度之和，记为 $\text{WPL} = \sum_{k=1}^{n} w_k \cdot h_k$ 。其中， $n$ 为带权叶子结点数目， $w_k$ 为叶子结点的权值， $h_k$ 为叶子结点到根的路径长度。

构造最优二叉树的哈夫曼算法

最优二叉树（哈夫曼树）是一类带权路径长度最短的树（可能不唯一，但能保证最优）。

根据给定的 $n$ 个权值 $\{ w_1, w_2, \cdots, w_n \}$ ，构成 $n$ 棵二叉树的集合 $F = \{ T_1, T_2, \cdots, T_n \}$ ，每棵 $T_i$ 中只有一个带权为 $w_i$ 的根结点，其左、右子树均空。
在 $F$ 中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，重新构造二叉树的根结点的权值为左、右子树根结点的权值之和。
从 $F$ 中删除这两棵树，同时将新得到的二叉树加入到 $F$ 中。
重复步骤 2 和 3，直到 $F$ 中只含一棵树为止，这棵树便是最优二叉树。

3.5.2 哈夫曼编码

哈夫曼编码是一种最优前缀编码方法，用于数据压缩。它通过构造最优二叉树（哈夫曼树）来实现字符的不等长编码。

构造哈夫曼树

根据给定的权值集合构造初始的二叉树集合，每棵树只有一个带权根结点，其余结点为空。
选择两棵权值最小的树作为左、右子树构造新树，新树的根结点权值为两棵树根结点权值之和。
重复步骤 2，直到集合中只剩一棵树，这棵树即为哈夫曼树。

编码过程

从哈夫曼树的根结点出发，根据路径上 0 和 1 的不同选择，为每个字符生成编码。
左子树路径为 0，右子路径为 1。

解码过程

从根结点出发，根据编码的二进制位串确定路径，到达叶子结点时输出对应字符。
若位串未结束，回到根结点继续译码。

3.6 树和森林

3.6.1 树的存储结构

双亲表示法：用数组存储结点，每个结点附带一个指示器，指向其双亲结点在数组中的位置。
孩子表示法：为每个结点建立一个链表，包含其所有孩子的指针。
二叉链表表示法：每个结点有两指针，一个指向第一个孩子，一个指向兄弟结点。

3.6.2 树和森林的遍历

树的遍历

先根遍历：访问根结点，然后依次先根遍历各子树。
后根遍历：依次后根遍历各子树，然后访问根结点。

森林的遍历

先序遍历：访问第一棵树的根结点，先序遍历其子树森林，再先序遍历剩余树。
中序遍历：中序遍历第一棵树的子树森林，访问根结点，再中序遍历剩余树。

3.6.3 树、森林和二叉树的相互转换

树转换为二叉树

树的孩子兄弟表示法与二叉树的二叉链表表示法结构相同，可将树转换为二叉树：
- 根的左孩子指向第一个子结点。
- 每个结点的右指针指向下一个兄弟结点。

树转二叉树的记忆口诀：兄弟相连留长子，顺时针转 45 度。（）

森林转换为二叉树 - 将森林中的每棵树转换为二叉树，第一棵树的根作为转换后的二叉树根，后续树依次作为右子树。

二叉树转换为树或森林

二叉树可唯一转换为树或森林：
- 树的根结点由二叉树根结点转换而来。
- 左子树转换为根结点的子树森林。
- 右子树转换为兄弟树。

4 图

图是一种复杂数据结构，允许多个前驱和后继结点，相比树结构更加灵活。

4.1 图的定义与存储

4.1.1 图的定义

图 G 是由顶点集 V 和边集 E 构成的二元组，记作 $G = (V, E)$ 。

1. 有向图

边有方向，用有序对 $<v_i, v_j>$ 表示。
$v_i$ 是弧尾， $v_j$ 是弧头。

2. 无向图：边无方向，用无序对 $(v_i, v_j)$ 表示。

3. 完全图

无向完全图：任意两个顶点之间都有边。
有向完全图：任意两个顶点之间都有方向相反的两条弧。

4. 度、入度、出度

度：顶点关联的边数，记作 $D(v)$ 。
入度：有向图中以顶点为终点的边数，记作 $ID(v)$ 。
出度：有向图中以顶点为起点的边数，记作 $OD(v)$ 。
边数 $e$ 与顶点度的关系： $e = \frac{1}{2} \sum_{i=1}^{n} D(v_i)$

5. 路径与回路

路径：顶点序列，相邻顶点间有边。
回路：起点和终点相同的路径。

6. 子图：若 $V' \subseteq V$ 且 $E' \subseteq E$ ，则 $G' = (V', E')$ 是 $G$ 的子图。

7. 连通图与强连通图

连通图：无向图中任意两顶点间有路径。无向图 G 的极大连通子图称为无向图的连通分量。
强连通图：有向图中任意两顶点间互相可达。有向图 G 的极大连通子图称为有向图的强连通分量。

8. 网：边有权值的图称为网。

4.1.2 图的存储结构

1. 邻接矩阵

用矩阵表示顶点间的连接关系。
无向图的邻接矩阵对称。
有向图的邻接矩阵不一定对称。
网的邻接矩阵存储边的权值。

2. 邻接链表

为每个顶点建立一个单链表，存储其邻接顶点。
包含 表结点 和 表头结点：
- 表结点：存储邻接顶点的序号、权值和指针。
- 表头结点：存储顶点信息和指针。

4.2 图的遍历

4.2.1 深度优先搜索（DFS）

深度优先搜索（DFS）是一种类似于树的先根遍历的图遍历算法，尽可能深地搜索图中的顶点。

步骤

选择一个未被访问的顶点作为起点。
访问该顶点并标记为已访问。
递归地访问该顶点的所有未被访问的邻接顶点。

算法特点

深度优先搜索会尽可能深地探索图中的顶点，直到不能再深入时才回溯（不撞南墙不回头）。
可以使用递归或栈来实现。
时间复杂度为 $(n+e)$ ，其中 $n$ 是顶点数， $e$ 是边数。

C 代码示例

int visited[MaxN] = {0};  // 记录顶点是否被访问过

void Dfs(Graph G, int i) {
    EdgeNode *t;
    int j;
    printf("%d", i);      // 访问顶点 i
    visited[i] = 1;       // 标记顶点 i 已访问
    t = G.Vertices[i].firstarc;
    while (t != NULL) {
        j = t->adjvex;
        if (visited[j] == 0) {
            Dfs(G, j);  // 递归访问邻接顶点 j
        }
        t = t->nextarc;
    }
}

4.2.2 广度优先搜索（BFS）

广（宽）度优先搜索（BFS），英文全称 Breadth First Search。 BFS 并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。是一种类似于树的层次遍历的图遍历算法，按层次访问图中的顶点。

为了便于理解 BFS，可以想象拽住某个顶点去拉绳子连接的球，这样图的层次会很清晰。

步骤

选择一个未被访问的顶点作为起点。
访问该顶点并标记为已访问。
将该顶点的所有未被访问的邻接顶点加入队列。
从队列中取出一个顶点，重复步骤 2 和 3，直到队列为空。

算法特点

广度优先搜索会尽可能广地访问图中的顶点，按层次进行搜索。
使用队列来实现。
时间复杂度为 $O(n+e)$ ，其中 $n$ 是顶点数， $e$ 是边数。

4.3 生成树及最小生成树

4.3.1 生成树概念

生成树是包含图中所有顶点且无回路的极小子图。对于 n 个顶点的连通图，生成树有 n-1 条边。

常见生成树

深度优先生成树：基于深度优先搜索构建。
广度优先生成树：基于广度优先搜索构建。

4.3.2 最小生成树

最小生成树是边权总和最小的生成树，适用于连通网。

4.3.2.1 普里姆（Prim）算法

初始化：选择一个起始顶点，加入集合 U。
迭代：在 U 与 $V-U$ 之间找权值最小的边，加入集合 TE，并扩展 U。
终止：当 $U = V$ 时，得到最小生成树。

时间复杂度： $O(n^2)$ ，适合密集图。

4.3.2.2 克鲁斯卡尔（Kruskal）算法

初始化：将所有边按权值升序排序，每个顶点自成连通分量。
迭代：依次选取最小权值边，若边的两个顶点不在同一连通分量，则加入最小生成树。
终止：当所有顶点在一个连通分量时结束。

时间复杂度： $O(eloge)$ ，适合稀疏图。

4.4 拓扑排序和关键路径

4.4.1 AOV 网

AOV网是有向无环图（DAG），用于表示活动的优先关系。顶点表示活动，有向边表示活动间的优先顺序。

4.4.2 拓扑排序

将 AOV 网中的顶点排成线性序列，满足若存在路径从顶点 $v_i$ 到 $v_j$ ，则 $v_i$ 在序列中出现在 $v_j$ 之前。

算法步骤

选择入度为 0 的顶点并输出。
删除该顶点及其所有出边。
重复步骤 1 和 2，直到所有顶点输出或图中仍有顶点但无入度为0的顶点（说明存在环）。

时间复杂度为 $O(n+e)$ ，其中 n 是顶点数，e 是边数。

4.4.3 AOE 网

AOE 网是有向有权图，顶点表示事件，边表示活动，边的权值表示活动持续时间。

4.4.4 关键路径与关键活动

关键路径：从源点到汇点的最长路径，决定了工程的最短完成时间。

若活动 $a_k$ 的最早开始时间等于最晚开始时间 $e(k) = l(k)$ ，则 $a_k$ 是关键活动。关键活动组成的路径是关键路径。

4.5 最短路径

4.5.1 单源点最短路径

Dijkstra算法用于求解带权有向图中单源点到其他顶点的最短路径，适用于权值非负的图。

算法步骤

初始化：将顶点分为两个集合 S 和 T，其中 S 初始包含源点 $v_0$ ，T 包含其余顶点。
距离数组：维护一个距离数组 dist，其中 $dist[i] $ 表示当前已知从源点到顶点 i 的最短路径长度。
选择顶点：每次从 T 中选择一个距离最小的顶点 u，将其加入 S。
更新距离：更新 T 中顶点的距离，若经过 u 到 T 中顶点 v 的路径更短，则更新 $dist[v]$ 。

Dijkstra 算法的时间复杂度为 $O(n^2)$ ，其中 n 是顶点数。

4.5.2 每对顶点间的最短路径

Floyd 算法用于求解带权有向图中每对顶点之间的最短路径。

算法思想：通过逐步引入中间顶点，更新顶点之间的最短路径。

算法步骤

初始化：邻接矩阵初始化为图的直接边权值。
迭代更新：对于每个中间顶点 ( k )，更新所有顶点对 ( (i, j) ) 的最短路径，考虑是否经过 ( k )。

Floyd 算法的时间复杂度为 $O(n^3)$ ，其中 n 是顶点数。

5 查找

5.1 查找的基本概念

查找表是由同一类型的数据元素构成的集合，用于进行数据元素的查询、检索、插入和删除操作。根据是否允许插入和删除操作，查找表分为静态查找表和动态查找表。

平均查找长度（ASL）用于衡量查找算法的效率，定义为成功查找时进行比较的记录个数的期望值。对于等概率情况，公式为： $ASL = \sum_{i=1}^{n} P_i C_i$
其中， $P_i$ 是查找第 i 个记录的概率， $C_i$ 是找到第 i 个记录所需比较的次数。

5.2 静态查找表的查找方法

顺序查找从表的一端开始，逐个比较记录的关键字与给定值。适用于任何存储方式，但在等概率情况下平均查找长度较大，效率较低。
折半查找适用于按关键字递增顺序排列的表。通过比较中间位置的记录关键字进行查找，每次比较将查找区间缩小一半。折半查找的性能优于顺序查找，但要求表按关键字有序且顺序存储。
分块查找将表分为若干块，每块内关键字无序，但块间有序。通过建立索引表实现快速定位块，再在块内进行顺序查找。分块查找的效率介于顺序查找和折半查找之间。

5.3 动态查找表

5.3.1 二叉排序树

定义

二叉排序树（BST）是一种动态查找表，支持高效的插入、删除和查找操作。其结构特性如下：

若左子树非空，所有左子树节点值小于根节点值。
若右子树非空，所有右子树节点值大于根节点值。
左右子树本身也是二叉排序树。

查找过程

从根节点开始，将目标值与当前节点值比较：

若相等，查找成功。
若目标值小于当前节点值，查找左子树。
若目标值大于当前节点值，查找右子树。
若到达空节点，查找失败。

插入操作

插入新节点时，从根节点开始比较，确定插入位置：

若小于根节点值，插入到左子树。
若大于根节点值，插入到右子树。
若树为空，新节点成为根节点。

5.3.2 平衡二叉树

平衡二叉树又称为 AV树，它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过 1。平衡二叉树通过旋转操作维持平衡，主要类型包括：

LL型：插入左子树的左子树，需右旋。
RR型：插入右子树的右子树，需左旋。
LR型：插入左子树的右子树，需先左旋后右旋。
RL型：插入右子树的左子树，需先右旋后左旋。

5.3.3 B 树

m 阶 B 树：每个结点最多有 m 棵子树，根结点至少两棵，其他非叶子结点至少有 $\lceil m/2 \rceil$ 棵子树。
非终端结点结构：包含关键字和子树指针。
叶子结点：在同一层次，指针为空。

5.4 哈希表

哈希表通过哈希函数将关键字映射到存储地址，支持快速查找。

哈希函数：计算存储地址的函数。
冲突：不同关键字映射到同一地址。
同义词：映射到同一地址的关键字。

哈希函数的构造方法

常用的哈希函数构造方法包括直接定址法、除留余数法等，需考虑压缩性和均匀性。

哈希表的定义与冲突处理

哈希表通过哈希函数将关键字映射到存储地址，支持快速查找。冲突是不同关键字映射到同一地址的现象，解决冲突的方法包括：

开放定址法：线性探测、二次探测和随机探测。
链地址法：每个记录增加链域，冲突记录链接成链表。
再哈希法：使用多个哈希函数。
公共溢出区：冲突记录存入公共溢出区。

哈希表的查找过程

查找过程使用相同的哈希函数和冲突处理方法，查找效率受哈希函数、冲突处理方法和装填因子影响。

6 排序

6.1 排序的基本概念

排序是将一组记录按关键字的递增或递减顺序排列的过程。根据记录存储位置，排序分为内部排序和外部排序。

排序算法的稳定性可以保持金额相同的两个对象，在排序之后的前后顺序不变。

6.2 简单排序

6.2.1 直接插入排序

基本思想：将第 i 个记录插入到已排好的序列中。
时间复杂度： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定

6.2.2 冒泡排序

基本思想：取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，交换相邻的逆序元素，直到未排序区间中元素为空。
时间复杂度： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定

6.2.3 简单选择排序

基本思想：每次从待排序序列中选出最小的元素，放到序列的起始位置。
时间复杂度：最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 $O(n^2)$
空间复杂度： $O(1)$
稳定性：不稳定

6.3 希尔排序

希尔排序又称为“缩小增量排序”，它是对直接插入排序方法的改进。

基本思想：将序列分组，对每组进行直接插入排序，逐步减小分组间隔。
时间复杂度： $O(n^{1.3})$
空间复杂度： $O(1)$
稳定性：不稳定

6.4 快速排序

快速排序通过一趟排序将记录分为两部分，前半区记录的关键字均不大于后半区记录的关键字，再递归排序这两部分。

算法步骤

划分：选择一个基准元素（pivot），将数组分为两部分。
递归排序：对前后两部分分别进行快速排序。

时间复杂度

平均情况： $O(n \log n)$
最坏情况： $O(n^2)$ 当初始序列有序时）

快速排序是不稳定的排序方法。

6.5 堆排序

堆排序利用堆的性质进行排序。堆是一棵完全二叉树，其中父节点的值大于（大根堆）或小于（小根堆）其子节点的值。

优于完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。

算法步骤

构建初始堆：将待排序序列构造成一个堆。建议从最后一个非叶子节点开始，依次从上往下堆化。
调整堆：移除堆顶元素，将最后一个元素移到堆顶，然后从上往下堆化。
重复：缩小堆的范围，重复调整堆的过程，直到所有元素有序。

时间复杂度

构建堆： $O(n)$
每次调整堆： $O(\log n)$
总时间复杂度： $O(n \log n)$

堆排序是不稳定的排序方法。

6.6 归并排序

归并排序是一种分治算法，通过反复合并两个有序子序列来构建有序序列。具体过程分为两两归并，直到整个序列有序。

算法步骤

递归分割：将数组不断分割为两部分。
合并排序：将两个有序部分合并为一个有序序列。

时间复杂度： $O(n \log n)$
空间复杂度： $O(n)$

归并排序是稳定的排序方法。

6.7 基数排序

基数排序是一种分配排序，通过关键字的各位数值进行排序。可以按最低有效位优先或最高有效位优先进行排序。

算法步骤

分配：将记录分配到多个队列中，每个队列对应一个关键字值。
收集：按顺序收集队列中的记录。
重复：对每个关键字位重复上述过程。

时间复杂度： $O(d(n + r))$ ，其中 d 是关键字的位数，r 是基数。
空间复杂度： $O(n + r)$

基数排序是稳定的排序方法。

6.8 内部排序方法小结

各种排序方法的性能比较

排序方法	时间复杂度	辅助空间	稳定性
直接插入排序	$O(n^2)$	$O(1)$	稳定
冒泡排序	$O(n^2)$	$O(1)$	稳定
简单选择排序	$O(n^2)$	$O(1)$	不稳定
希尔排序	$O(n^{1.3})$	$O(1)$	不稳定
快速排序	$O(n \log n)$	$O(\log n)$	不稳定
堆排序	$O(n \log n)$	$O(1)$	不稳定
归并排序	$O(n \log n)$	$O(n)$	稳定
基数排序	$O(d(n + rd))$	$O(rd)$	稳定

选择排序方法的建议

记录数目较小：可采用直接插入排序或简单选择排序。记录信息量较大时，简单选择排序更优。
关键字基本有序：宜采用直接插入排序或冒泡排序。
n 很大且关键字位数较少：采用链式基数排序较好。
n 较大：应采用时间复杂度为 $O(n \log n)$ 的排序方法，如快速排序、堆排序或归并排序。快速排序平均运行时间最短，堆排序辅助空间小且无快速排序的最坏情况。要求排序稳定时，可选择归并排序。

6.9 外部排序

外部排序用于对大型文件排序，待排序记录存储在外存中。由于内存有限，排序过程需要多次内外存数据交换。

多路平衡归并方法

归并过程

初始归并段生成：将文件记录分段读入内存，利用内部排序方法排序后输出到外存，形成初始归并段。
多路归并：对初始归并段进行多路归并，逐步扩大有序段，直到整个文件有序。

树形选择排序

使用完全二叉树结构，通过多轮比较选出最小关键字。
在输出最小关键字后，更新相关记录并调整树结构以选出次小关键字。

败者树

败者树是一种用于多路归并的数据结构，记录比较后的失败者。
每个非终端结点记录其左右孩子的优胜者，根结点关键字为所有叶子中的最小值。
在更新最小关键字后，调整路径上的关键字以确定次小关键字。

利用败者树实现 k 路平衡归并，通过调整败者树结构逐步输出有序关键字。

7 加餐和总结

排序算法是常考点。