数据结构期末复习

资料依据当前文件夹中的 lecture1、2.pdf 至 lecture8.pdf 整理，覆盖绪论与线性表、栈和队列、串和数组、树、图、索引结构与散列技术、缩小规模算法。复习时建议优先掌握“概念定义 + 存储结构 + 基本操作 + 复杂度 + 典型算法过程”。

一、考试重点总览

高优先级

1. 线性表的顺序存储与链式存储：插入、删除、查找、合并，时间复杂度比较。
2. 栈和队列：顺序栈、链栈、循环队列、链队列的判空/判满/入队/出队。
3. 二叉树：性质、顺序/链式存储、三种深度优先遍历、层次遍历、由遍历序列恢复二叉树。
4. 哈夫曼树与哈夫曼编码：WPL、构造过程、编码/译码。
5. 图：邻接矩阵、邻接表、DFS、BFS、最小生成树、最短路径、拓扑排序、关键路径。
6. 索引与散列：分块查找、散列函数、装填因子、冲突处理、ASL 计算。
7. 缩小规模算法：二分搜索、归并排序、快速排序、动态规划、备忘录、贪心。

中优先级

1. 串的基本概念、朴素模式匹配算法及最坏时间复杂度。
2. 数组地址计算、特殊矩阵压缩存储、稀疏矩阵三元组表和转置。
3. 二叉排序树的查找、插入、删除。
4. 树、森林与二叉树之间的转换。
5. 矩阵连乘、0-1 背包与分数背包的思想区别。

容易丢分点

1. 下标从 0 开始还是从 1 开始要看题目，公式不能混用。
2. 循环队列通常牺牲一个存储单元区分队空和队满。
3. 链表插入、删除时先后指针顺序不能写反。
4. 二叉树中“完全二叉树”“满二叉树”“哈夫曼树”不是同一个概念。
5. Dijkstra 不能处理带负权边的最短路径问题。
6. 拓扑排序只适用于 AOV 网，并且图中不能有有向环。
7. 关键路径中关键活动满足 e(i) = l(i)，不是看边权最大的一条边。
8. 散列表的平均查找长度主要受装填因子影响，不只由结点数或表长决定。
9. 0-1 背包不能直接用“单位价值最高优先”的贪心法，分数背包才适合这种贪心策略。

二、绪论与线性表

1. 数据结构基本概念

数据结构研究三件事：

1. 逻辑结构：数据元素之间的逻辑关系。
2. 存储结构：逻辑关系在计算机中的存储表示。
3. 数据运算：在结构上定义的操作，如查找、插入、删除、遍历。

数据结构可形式化表示为：

Data-Structure = (D, R)
D：数据元素集合
R：D 上关系的集合

常见逻辑结构：

1. 线性结构：除第一个和最后一个元素外，每个元素有唯一前驱和唯一后继。
2. 树形结构：一对多的层次关系。
3. 图形结构：多对多关系。
4. 集合结构：元素之间除同属一个集合外无其他关系。

常见存储结构：

1. 顺序存储：逻辑相邻，物理也相邻；支持随机存取。
2. 链式存储：通过指针表示逻辑关系；插入删除方便，不支持随机存取。
3. 索引存储：建立索引表辅助定位。
4. 散列存储：由关键字直接计算存储位置。

2. 线性表

线性表是由 n >= 0 个数据元素组成的有限序列：

L = (a1, a2, ..., an)

常用操作：

1. SetNull(L)：置空表。
2. Length(L)：求长度。
3. Get(L, i)：取第 i 个元素。
4. Locate(L, x)：按值定位。
5. Insert(L, x, i)：在第 i 个位置插入 x。
6. Delete(L, i)：删除第 i 个元素。
7. Prior(L, ai) / Next(L, ai)：求前驱/后继。

3. 顺序表

顺序表使用一组连续空间存放线性表元素。典型结构：

#define maxsize 1024
typedef int datatype;
typedef struct {
    datatype data[maxsize];
    int last;
} sequenlist;

其中 last 常表示最后一个元素的下标。若下标从 0 开始，则长度为 last + 1。

顺序表操作复杂度：

操作	复杂度	说明
按下标访问	O(1)	随机存取
按值查找	O(n)	需要顺序扫描
插入	O(n)	平均需要移动约一半元素
删除	O(n)	平均需要移动约一半元素
表尾插入/删除	O(1)	不考虑扩容

顺序表插入核心过程：

1. 判断表满。
2. 判断插入位置是否合法。
3. 从最后一个元素开始，依次后移。
4. 将新元素放入目标位置。
5. last 加 1。

顺序表删除核心过程：

1. 判断删除位置是否合法。
2. 从被删位置后一位开始，依次前移。
3. last 减 1。

优点：

1. 支持随机存取。
2. 存储密度高，不需要额外指针域。

缺点：

1. 插入和删除需要移动大量元素。
2. 需要预先分配连续空间，容量不灵活。

4. 单链表

单链表结点由数据域和指针域组成：

typedef int datatype;
struct node {
    datatype data;
    struct node *next;
};

带头结点单链表常用于简化插入和删除，头结点不存储有效数据。

头插法建表：

新结点 s 插入到 head 之后。
输入顺序为 a, b, c，链表结果通常为 c, b, a。

尾插法建表：

使用尾指针 r，始终让 r 指向当前尾结点。
输入顺序为 a, b, c，链表结果为 a, b, c。

单链表常见操作：

操作	关键点	复杂度
按序号查找	从头结点开始计数扫描	O(n)
按值查找	逐个比较 data	O(n)
在 p 后插入 s	s->next = p->next; p->next = s;	O(1)
删除 p 后继结点	r = p->next; p->next = r->next; free(r);	O(1)
删除指定第 i 个结点	先找第 i-1 个结点	O(n)

链表插入时最重要的两句：

s->next = p->next;
p->next = s;

链表删除时最重要的三句：

r = p->next;
p->next = r->next;
free(r);

5. 顺序表与链表比较

比较项	顺序表	链表
存储空间	连续	可不连续
随机访问	O(1)	O(n)
插入删除	需要移动元素	只需改指针，但要先定位
存储密度	高	低，有指针域
容量	通常固定或需扩容	动态申请释放
适合场景	查找多、修改少	插入删除多

6. 循环链表与多项式

循环链表最后一个结点的指针指向头结点。若用尾指针 rear 表示单循环链表：

终端结点：rear
开始结点：rear->next->next  （带头结点时）

一元多项式可用有序链表表示：

struct pnode {
    float coef;       // 系数
    int exp;          // 指数
    struct pnode *next;
};

多项式相加核心思想：

1. 两个指针分别扫描 A、B。
2. 指数小的项直接进入结果。
3. 指数相同则系数相加。
4. 若相加结果为 0，则删除该项。
5. 剩余项直接链接到结果表。

三、栈和队列

1. 栈

栈是限定仅在表尾进行插入和删除的线性表。表尾称为栈顶，表头称为栈底。

特点：

后进先出 LIFO
先进后出 FILO

基本操作：

1. SetNull(S)：置空栈。
2. Empty(S)：判栈空。
3. Push(S, e)：入栈。
4. Pop(S)：出栈。
5. GetTop(S)：取栈顶元素，不改变栈状态。

顺序栈常见约定：

top = -1       表示空栈
top == maxsize - 1 表示栈满
入栈：先 top++，再赋值
出栈：先取值，再 top--

链栈：

1. 链栈是运算受限的单链表。
2. 通常在表头进行插入和删除。
3. top == NULL 表示空栈。

栈的典型应用：

1. 递归调用。
2. 表达式求值。
3. 括号匹配。
4. 迷宫求解、地图染色等回溯问题。

递归题要会写：

递归出口 + 递归调用式

例如 Fibonacci：

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2), n > 1

2. 队列

队列是限定在一端插入、另一端删除的线性表。

队尾 rear：插入端
队头 front：删除端
先进先出 FIFO

顺序队列的问题是假溢出：数组前端空间已经释放，但普通 rear++ 无法重新利用。

循环队列用取模解决：

rear = (rear + 1) % maxsize
front = (front + 1) % maxsize

常见约定之一：

队空：front == rear
队满：(rear + 1) % maxsize == front
队列长度：(rear - front + maxsize) % maxsize

注意：这种约定会牺牲一个单元。

链队列：

typedef struct {
    linklist *front;
    linklist *rear;
} linkqueue;

常用带头结点表示：

空队列：front == rear
入队：新结点插入 rear 之后，再移动 rear
出队：删除 front->next；若删除后队空，rear 也要指向 front

队列典型应用：

1. 杨辉三角。
2. 图或树的广度优先遍历。
3. 子集划分、分层处理问题。

四、串、数组与矩阵

1. 串

串是由零个或多个字符组成的有限序列：

S = "a1a2...an"

基本概念：

1. 串长：串中字符个数。
2. 空串：长度为 0 的串。
3. 子串：串中任意连续字符组成的子序列。
4. 主串：包含子串的串。
5. 子串位置：子串第一个字符在主串中的序号。

串与线性表的区别：

1. 串的元素类型固定为字符。
2. 串的操作通常以“串整体”为对象，如求子串、插入子串、删除子串、查找子串。

串的存储结构：

1. 顺序存储：用字符数组存放。
2. 链式存储：链串，每个结点可存一个或多个字符。
3. 索引存储：用索引表指向串值位置。

2. 朴素模式匹配

目标：求模式串 T 在主串 S 中首次出现的位置。

朴素算法思想：

1. 从主串某个起始位置开始，与模式串逐字符比较。
2. 若相等，则继续比较后继字符。
3. 若不相等，则主串起始位置后移一位，模式串回到开头。
4. 直到匹配成功或主串剩余长度不足。

最坏情况：

主串中每一趟都比较到模式串最后一个字符才失败。
时间复杂度：O(n * m)
n：主串长度
m：模式串长度

典型最坏例子：

S = "aaaaaaaaab"
T = "aaaab"

3. 数组

数组是由值和下标构成的有序对。性质：

1. 数据元素数目固定。
2. 数据元素类型相同。
3. 下标有上下界且有序。

二维数组 A[m][n] 行优先存储地址公式：

若下标从 1 开始：

Loc(aij) = Loc(a11) + [(i - 1) * n + (j - 1)] * d

若下标从 0 开始：

Loc(aij) = Loc(a00) + (i * n + j) * d

列优先存储地址公式，下标从 1 开始：

Loc(aij) = Loc(a11) + [(j - 1) * m + (i - 1)] * d

三维数组 A[m][n][p] 行优先，下标从 1 开始：

Loc(aijk) = Loc(a111) + [(i - 1) * n * p + (j - 1) * p + (k - 1)] * d

4. 矩阵压缩存储

压缩存储：多个值相同的元素只分配一个空间，对零元素不分配空间。

适合压缩的矩阵：

1. 对角矩阵。
2. 三角矩阵。
3. 对称矩阵。
4. 稀疏矩阵。

对称矩阵：

aij = aji
只存下三角或上三角，共 n * (n + 1) / 2 个元素

以下三角按行优先存入一维数组 A[k]，下标从 0 开始：

若 i >= j：k = i * (i + 1) / 2 + j
若 i < j： k = j * (j + 1) / 2 + i

稀疏矩阵：

非零元素个数 s 远小于零元素个数 t，即 s << t

三元组表：

(i, j, v)
i：行号
j：列号
v：非零元素值

三元组表结构：

typedef struct {
    int i, j;
    datatype v;
} node;

typedef struct {
    int m, n, t;      // 行数、列数、非零元素个数
    node data[smax];
} spmatrix;

稀疏矩阵转置：

1. 交换矩阵行数和列数。
2. 对原矩阵每一列，从三元组表中找列号等于该列的元素。
3. 交换三元组的 i 和 j，按新矩阵行优先顺序放入结果表。

普通三元组转置复杂度：

O(n * t)
n：原矩阵列数
t：非零元素个数

五、树和二叉树

1. 树的基本概念

树是按层次关系组织起来的分支结构，是非线性数据结构。

重要术语：

1. 根结点：没有前驱的唯一结点。
2. 叶子结点：度为 0 的结点。
3. 孩子、双亲、兄弟、祖先、子孙。
4. 结点的度：结点拥有的子树数。
5. 树的度：树中各结点度的最大值。
6. 结点层次：根为第一层。
7. 树的深度：树中结点的最大层次数。

树与线性结构比较：

线性结构	树结构
一个首元素	一个根结点
一个尾元素	可有多个叶子
中间元素有唯一前驱和唯一后继	非根结点有唯一双亲，可有多个孩子

2. 二叉树

二叉树是 n >= 0 个结点的有限集合，或为空树，或由根结点、左子树、右子树组成。二叉树是递归定义。

注意：

二叉树的左子树和右子树有次序，不能随意交换。

二叉树重要性质：

1. 第 i 层至多有 2^(i-1) 个结点。
2. 深度为 k 的二叉树至多有 2^k - 1 个结点。
3. 对任意二叉树，若叶子结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。
4. 具有 n 个结点的完全二叉树深度为 floor(log2 n) + 1，也可写为 ceil(log2(n + 1))。

完全二叉树编号性质，编号从 1 开始：

若 i = 1，则 i 是根。
若 i > 1，则双亲为 floor(i / 2)。
若 2i <= n，则左孩子为 2i；否则无左孩子。
若 2i + 1 <= n，则右孩子为 2i + 1；否则无右孩子。
若 i 为奇数且 i != 1，则左兄弟为 i - 1。
若 i 为偶数且 i < n，则右兄弟为 i + 1。

3. 二叉树存储结构

顺序存储：

1. 适合完全二叉树。
2. 对一般二叉树可能浪费空间。

链式存储：

typedef struct TreeNode {
    datatype data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} bitree;

4. 二叉树遍历

先序遍历：

根 -> 左 -> 右

中序遍历：

左 -> 根 -> 右

后序遍历：

左 -> 右 -> 根

层次遍历：

使用队列，从根结点开始，访问一个结点后依次入队其左孩子、右孩子。

遍历常考形式：

1. 给树画遍历序列。
2. 给先序和中序恢复二叉树。
3. 给后序和中序恢复二叉树。
4. 写递归遍历算法。
5. 写中序遍历非递归算法。

由先序和中序恢复二叉树：

1. 先序第一个元素是根。
2. 在中序序列中找到根。
3. 根左边是左子树中序，根右边是右子树中序。
4. 按左右子树规模切分先序序列。
5. 递归构造。

只有先序和后序通常不能唯一确定普通二叉树。

5. 树、森林与二叉树转换

树转二叉树：

左孩子右兄弟法
1. 兄弟之间连线。
2. 每个结点只保留与最左孩子的连线。
3. 以根为轴顺时针旋转。

口诀：

左指针指向第一个孩子，右指针指向下一个兄弟。

森林转二叉树：

1. 每棵树分别转为二叉树。
2. 各棵树的根视为兄弟，用右指针连接。

6. 哈夫曼树与编码

路径长度：两个结点之间路径经过的边数。

带权路径长度：

WPL = sum(wi * li)
wi：第 i 个叶子结点权值
li：第 i 个叶子到根的路径长度

哈夫曼树：在所有具有相同带权叶子结点的二叉树中，WPL 最小的树。

构造算法：

1. 将 n 个权值看成 n 棵只有根结点的树。
2. 每次选取权值最小的两棵树合并。
3. 新树根权值为两棵树根权值之和。
4. 删除原两棵树，加入新树。
5. 重复直到只剩一棵树。

哈夫曼编码：

从根到叶子，左分支记 0，右分支记 1。
每个叶子对应一个字符编码。

性质：

1. 哈夫曼编码是前缀编码，一个字符编码不会是另一个字符编码的前缀。
2. 权值越大的字符通常离根越近，编码越短。
3. 哈夫曼树可能不唯一，但最小 WPL 相同。

7. 二叉排序树

定义：

左子树所有结点关键字 < 根结点关键字 < 右子树所有结点关键字
左右子树也都是二叉排序树

性质：

二叉排序树的中序遍历序列是递增有序序列。

查找：

若 k == 根：成功
若 k < 根：查左子树
若 k > 根：查右子树

插入：

按查找路径找到空位置，作为叶子结点插入。

删除分三种：

1. 删除叶子：直接删除。
2. 删除只有一棵子树的结点：用其子树替代它。
3. 删除有两棵子树的结点：用直接前驱或直接后继替代，再删除前驱/后继原结点。

六、图

1. 图的基本概念

图：

G = (V, E)
V：顶点集合，非空有限集合
E：边或弧的集合

有向图：

边有方向，记为 <vi, vj>
vi 是弧尾，vj 是弧头

无向图：

边无方向，记为 (vi, vj)

度：

无向图：D(v) 为关联于 v 的边数
有向图：ID(v) 为入度，OD(v) 为出度，D(v) = ID(v) + OD(v)

重要公式：

无向图所有顶点度数之和 = 2e
有向图所有顶点入度之和 = 出度之和 = e

其他术语：

1. 权：边或弧上的数值。
2. 网：带权图。
3. 路径：顶点序列。
4. 简单路径：顶点不重复的路径。
5. 回路/环：起点和终点相同的路径。
6. 连通图：无向图中任意两点连通。
7. 连通分量：无向图的极大连通子图。
8. 强连通图：有向图中任意两点互相可达。

2. 图的存储结构

邻接矩阵：

使用一维数组存顶点信息，二维数组存边关系。

无权图：

A[i][j] = 1 表示 vi 到 vj 有边或弧
A[i][j] = 0 表示无边或弧

带权图：

A[i][j] = wij 表示权值
A[i][j] = ∞ 表示无边
A[i][i] 通常为 0

邻接矩阵特点：

1. 空间复杂度 O(n^2)。
2. 判断两点是否有边为 O(1)。
3. 适合稠密图。
4. 无向图邻接矩阵对称。
5. 有向图第 i 行非零元素个数对应出度，第 i 列非零元素个数对应入度。

邻接表：

顶点表 + 邻接链表

顶点表结点：

typedef struct {
    vextype vertex;
    edgenode *link;
} vexnode;

边表结点：

typedef struct node {
    int adjvex;
    struct node *next;
} edgenode;

邻接表特点：

1. 空间复杂度约为 O(n + e)。
2. 适合稀疏图。
3. 查找某顶点所有邻接点方便。
4. 判断任意两点是否有边不如邻接矩阵直接。

3. 图的遍历

深度优先搜索 DFS：

类似树的先序遍历。
从一个顶点出发，访问未访问过的邻接点，沿路径尽可能深入。
走不下去时回溯。

DFS 可用递归或栈实现。

广度优先搜索 BFS：

类似树的层次遍历。
从一个顶点出发，先访问所有未访问邻接点，再依次访问下一层。

BFS 用队列实现。

遍历复杂度：

存储结构	DFS/BFS 复杂度
邻接矩阵	O(n^2)
邻接表	O(n + e)

4. 最小生成树

生成树：

包含图中全部 n 个顶点，且只有 n - 1 条边的连通无回路子图。

最小生成树：

带权连通无向图中，权值总和最小的生成树。

Prim 算法：

1. 从任意顶点开始，将其加入 U。
2. 每次选择一条连接 U 和 V-U 的最小权边。
3. 将该边和对应顶点加入生成树。
4. 重复直到加入 n-1 条边。

特点：

时间复杂度 O(n^2)
适合稠密图

Kruskal 算法：

1. 将所有边按权值从小到大考虑。
2. 每次选择当前最小且不会形成回路的边。
3. 直到选出 n-1 条边。

特点：

时间复杂度约 O(e log e)
适合稀疏图

Prim 与 Kruskal 比较：

算法	选择对象	防止回路方式	适合图
Prim	顶点集合到外部的最小边	始终连接 U 和 V-U	稠密图
Kruskal	全局最小边	判断两个端点是否属于同一连通分量	稀疏图

5. 最短路径

Dijkstra 算法：求单源最短路径。

核心数组：

D[i]：源点到 i 的当前最短距离
p[i]：最短路径上 i 的前驱顶点
s[i]：是否已经确定源点到 i 的最短路径

过程：

1. 初始化源点到各顶点的距离。
2. 从未确定顶点中选择 D 值最小的顶点 k。
3. 将 k 加入已确定集合。
4. 用 k 松弛其他未确定顶点：
   若 D[j] > D[k] + dist[k][j]，则更新 D[j] 和 p[j]。
5. 重复 n-1 次。

复杂度：

时间复杂度 O(n^2)
辅助空间 O(n)

Floyd 算法：求每一对顶点之间的最短路径。

核心思想：

依次尝试让每个顶点 k 作为中间顶点。
若 A[i][j] > A[i][k] + A[k][j]，则更新 A[i][j]。

递推式：

A[i][j] = min(A[i][j], A[i][k] + A[k][j])

复杂度：

时间复杂度 O(n^3)
空间复杂度 O(n^2)

6. 拓扑排序

AOV 网：

用顶点表示活动，用有向边表示活动之间先后关系的有向图。

拓扑序列：

若图中存在从 vi 到 vj 的路径，则 vi 必须排在 vj 前面。

拓扑排序基本过程：

1. 找入度为 0 的顶点并输出。
2. 删除该顶点及其所有出边。
3. 新产生入度为 0 的顶点继续输出。
4. 若所有顶点输出完，则排序成功。
5. 若还有顶点未输出但无入度为 0 的顶点，则图中有环。

邻接表实现复杂度：

O(n + e)

7. 关键路径

AOE 网：

用边表示活动、顶点表示事件的带权有向无环图。

特点：

1. 只有一个入度为 0 的源点，表示工程开始。
2. 只有一个出度为 0 的汇点，表示工程结束。
3. 从源点到汇点的最长路径称为关键路径。

事件最早发生时间：

ve[j] = max(ve[i] + dur<i,j>)

事件最迟发生时间：

vl[i] = min(vl[j] - dur<i,j>)

活动最早开始时间：

e(i) = ve[活动起点]

活动最迟开始时间：

l(i) = vl[活动终点] - 活动持续时间

关键活动：

e(i) == l(i)

求关键路径步骤：

1. 拓扑排序，同时求各事件 ve。
2. 按拓扑逆序求各事件 vl。
3. 对每条边计算活动的 e(i) 和 l(i)。
4. e(i) == l(i) 的活动为关键活动。
5. 关键活动组成关键路径。

七、索引结构与散列技术

1. 索引结构基本概念

索引结构由两部分组成：

1. 索引表：记录关键字与存储位置之间的对应关系。
2. 数据表：真正存储记录信息的表，常见形式是线性表。

索引项的一般形式：

(关键字, 地址)

其中关键字用于唯一标识一个记录，地址用于指出记录在数据表中的位置。

索引结构分类：

1. 索引顺序结构：数据表中的记录按关键字顺序排列。
2. 索引非顺序结构：数据表中的记录未按关键字顺序排列。

线性索引：

1. 稠密索引：每个数据记录对应一个索引项，适合数据表无序的情况。
2. 稀疏索引：一组记录对应一个索引项，索引项地址通常指向该组记录的起始位置，要求数据表分组有序。

索引查找基本过程：

1. 先查索引表。
2. 若索引表中确定可能位置，再访问数据表。
3. 若索引表中无法定位，则数据表中不存在目标记录。

索引表通常有序，因此可在索引表上使用顺序查找或折半查找。

2. 分块查找

分块查找又称索引顺序查找，性能介于顺序查找和折半查找之间。

构造条件：

1. 将数据表 R[n] 分成若干块。
2. 块内记录可以无序。
3. 块间必须有序，即前一块的最大关键字小于后一块的最小关键字。
4. 为每一块建立索引项，保存该块最大关键字和该块起始地址。

索引项形式：

typedef struct {
    keytype key;  // 该块最大关键字
    int addr;     // 该块起始位置
} Idtable;

查找步骤：

1. 在索引表中查找第一个 key >= 目标值 x 的索引项，确定 x 可能所在块。
2. 在该块内部顺序查找 x。
3. 若块内找到则成功，否则失败。

平均查找长度：

ASL = 查索引表的平均查找长度 + 块内顺序查找的平均查找长度

易错点：

1. 分块查找要求“块间有序”，不要求“块内有序”。
2. 如果索引表用折半查找，索引表必须按块最大关键字递增。
3. 最后一块元素个数可以少于其他块。

3. 散列表基本概念

散列法又称关键字到地址转换法：

address = H(key)

相关概念：

1. 散列表：用散列法存储的线性表。
2. 散列函数：由关键字计算地址的函数 H(key)。
3. 散列地址：散列函数计算出的存储地址。
4. 冲突：不同关键字得到相同散列地址。
5. 同义词：发生冲突的不同关键字。
6. 装填因子：alpha = n / m，其中 n 为已存记录数，m 为散列表长度。

散列函数选择原则：

1. 计算尽可能简单。
2. 函数值必须落在表长范围内。
3. 尽可能均匀，减少冲突。

常见散列函数：除留余数法。

H(key) = key % p

其中 p 通常取不大于表长 m 的最大素数。例如表长为 13，则常取 p = 13。

4. 冲突处理

开放地址法：

发生冲突后，按照某种探查序列继续寻找下一个空位置。

线性探查法：

d = H(key)
di = (d + i) % m, 1 <= i <= m - 1

特点：

1. 实现简单。
2. 容易产生堆积现象，即冲突元素聚集在连续区域。

二次探查法：

d + 1^2, d - 1^2, d + 2^2, d - 2^2, ...

随机探查法：

di = (d + Ri) % m

其中 R1, R2, ..., Rm-1 是 1 到 m-1 的一个随机排列。

拉链法：

把散列地址相同的所有结点链接到同一个单链表中。

若散列函数值域为 0 到 m-1，可定义头指针数组：

HTP[0..m-1]

凡散列地址为 i 的结点，都插入到 HTP[i] 指向的链表中。

拉链法优点：

1. 不会产生开放地址法中的堆积现象。
2. 适合造表前无法准确确定表长的情况。
3. 删除结点较方便，只需在对应链表中删除。
4. 装填因子较大时，拉链法通常比开放地址法更稳定。

5. 散列表 ASL

查找成功 ASL：

ASLsucc = 每个已有关键字查找比较次数之和 / 关键字个数

拉链法中，若链表第一个结点查找需比较 1 次，第二个需比较 2 次，以此类推。

线性探查中，每个关键字的比较次数等于从其散列地址开始探查到该关键字所经历的单元数。

查找不成功 ASL：

ASLunsucc = 每个可能散列地址查找失败比较次数之和 / 散列函数可能地址数

易错点：

1. 成功 ASL 对已有关键字求平均。
2. 不成功 ASL 对可能散列地址求平均，不是对已有关键字求平均。
3. 同一个散列函数，冲突处理方法不同，ASL 可能不同。
4. 散列表平均查找长度主要与装填因子有关；alpha 越大，冲突可能越多，但 alpha 太小会浪费空间。

八、缩小规模算法

1. 递归与分治

递归算法是直接或间接调用自身的算法。适合两类问题：

1. 问题本身具有递归定义，如二叉树遍历。
2. 问题可分解为规模更小、形式相同的子问题。

分治法基本思想：

1. 分解：把规模为 n 的问题分解为若干规模较小的子问题。
2. 递归求解：分别求解子问题。
3. 合并：把子问题的解合并为原问题的解。

分治法适用条件：

1. 原问题可分解为若干相同类型的子问题。
2. 子问题相互独立。
3. 子问题的解可以合并成原问题的解。
4. 子问题规模足够小时可以直接求解。

2. 二分搜索

二分搜索适用于有序顺序表。

基本过程：

1. 令 low = 0，high = n - 1。
2. 取 mid = (low + high) / 2。
3. 若 R[mid] == x，查找成功。
4. 若 x < R[mid]，只在左半区间查找。
5. 若 x > R[mid]，只在右半区间查找。
6. 若 low > high，查找失败。

复杂度：

最坏比较次数：O(log2 n)

折半查找判定树：

1. 中间位置记录作为根。
2. 左子表和右子表分别构成左右子树。
3. 查找成功时的比较次数等于目标结点所在层数。
4. 成功比较次数最多不超过判定树深度。

平均查找长度近似：

ASLbin ≈ log2(n + 1) - 1

3. 归并排序

归并排序是典型分治算法。

基本思想：

1. 当待排序元素个数 n = 1 时，已有序。
2. 否则把待排序序列分成两个规模大致相同的子序列。
3. 分别对两个子序列归并排序。
4. 将两个有序子序列合并为一个有序序列。

二路归并排序：

初始时把 n 个记录看成 n 个长度为 1 的有序子表。
第一趟两两归并，得到长度为 2 的有序子表。
第二趟再两两归并，得到长度为 4 的有序子表。
重复直到得到长度为 n 的有序表。

复杂度：

时间复杂度：O(n log n)
辅助空间：O(n)

手算注意：

1. 每一趟归并后，有序段长度通常翻倍。
2. 最后一段长度可能不足当前归并长度。
3. 归并排序稳定，因为相等元素通常先取左段元素。

4. 快速排序

快速排序也是基于分治策略的排序算法。

一趟划分思想：

1. 取当前区间第一个元素作为基准 pivot。
2. 从右向左找第一个小于 pivot 的元素，放到左侧空位。
3. 从左向右找第一个大于 pivot 的元素，放到右侧空位。
4. 左右指针相遇时，把 pivot 放入最终位置。
5. pivot 左边元素不大于 pivot，右边元素不小于 pivot。

递归过程：

QuickSort(left, pivotPos - 1)
QuickSort(pivotPos + 1, right)

复杂度：

平均时间复杂度：O(n log n)
最好时间复杂度：O(n log n)
最坏时间复杂度：O(n^2)
辅助空间：平均 O(log n)，最坏 O(n)

易错点：

1. 快速排序通常不稳定。
2. 若每次基准都取到最小或最大元素，会退化为 O(n^2)。
3. 一趟划分结束后，只有基准元素到达最终位置，左右区间内部不一定完全有序。

5. 动态规划与备忘录

动态规划适合子问题不独立、存在重叠子问题的问题。

设计步骤：

1. 找出最优解的结构特征。
2. 递归定义最优值。
3. 自底向上计算最优值。
4. 根据记录的信息构造最优解。

两个基本要素：

1. 最优子结构：问题的最优解包含其子问题的最优解。
2. 重叠子问题：不同求解路径会反复遇到相同子问题。

备忘录方法：

自顶向下递归求解。
每个子问题设置记录项。
若记录项已有值，则直接返回；否则计算后存入记录项。

动态规划与备忘录比较：

方法	方向	特点
动态规划	自底向上	通常会填完整个状态表
备忘录	自顶向下	只计算递归实际遇到的子问题

矩阵连乘问题可用动态规划或备忘录方法在 O(n^3) 时间内求解。

6. 贪心算法

贪心算法基本思想：

每一步都做当前看来最好的选择，希望最终得到整体最优解。

适用条件：

1. 贪心选择性质：整体最优解可通过一系列局部最优选择得到。
2. 最优子结构：问题的最优解包含子问题的最优解。

贪心与动态规划区别：

1. 动态规划的选择依赖相关子问题的解。
2. 贪心选择只依赖当前状态和过去选择，不依赖未来子问题的解。

背包类问题：

1. 0-1 背包：每种物品只能装或不装，不能装一部分；不能简单使用单位价值贪心。
2. 分数背包：物品可以装一部分；可按单位重量价值 vi / wi 从大到小贪心选择。

分数背包贪心步骤：

1. 计算每种物品单位重量价值 vi / wi。
2. 按单位重量价值从大到小排序。
3. 优先装单位价值高的物品。
4. 若剩余容量不足以装完整件物品，则装入该物品的一部分。

九、算法复杂度速查表

内容	时间复杂度
顺序表按下标访问	O(1)
顺序表按值查找	O(n)
顺序表插入/删除	O(n)
单链表按序号/按值查找	O(n)
已知前驱结点的链表插入/删除	O(1)
顺序栈/链栈入栈出栈	O(1)
循环队列入队出队	O(1)
链队列入队出队	O(1)
朴素模式匹配最坏情况	O(nm)
稀疏矩阵普通三元组转置	O(n * t)
二叉树遍历	O(n)
二叉排序树查找平均	O(log n)
二叉排序树查找最坏	O(n)
邻接矩阵 DFS/BFS	O(n^2)
邻接表 DFS/BFS	O(n + e)
Prim	O(n^2)
Kruskal	O(e log e)
Dijkstra	O(n^2)
Floyd	O(n^3)
拓扑排序邻接表	O(n + e)
关键路径	O(n + e)
分块查找	O(查索引表 + 块内顺序查找)
散列查找平均	与装填因子 alpha 有关
折半查找	O(log n)
归并排序	O(n log n)
快速排序平均	O(n log n)
快速排序最坏	O(n^2)
矩阵连乘动态规划	O(n^3)
0-1 背包一维 DP	O(n * C)
分数背包贪心	O(n log n)

十、常考题型与答题模板

1. 概念判断题

重点判断：

1. 栈是后进先出，队列是先进先出。
2. 二叉树不是树的特殊情形，因为二叉树区分左右子树。
3. 完全二叉树适合顺序存储，一般二叉树更适合链式存储。
4. 无向图邻接矩阵一定对称。
5. AOV 网不能有有向环。
6. 哈夫曼树不一定唯一。
7. 分块查找要求块间有序，块内可以无序。
8. 散列函数相同但冲突处理方法不同，ASL 可能不同。
9. 分数背包可用贪心，0-1 背包不能直接用同样的贪心策略。

2. 手算题

常见手算：

1. 顺序表插入删除后的表状态。
2. 栈的入栈出栈序列。
3. 循环队列 front、rear 变化。
4. 二叉树遍历序列。
5. 根据先序+中序恢复二叉树。
6. 哈夫曼树构造和编码。
7. 图的 DFS/BFS 序列。
8. Prim/Kruskal 最小生成树。
9. Dijkstra 单源最短路径。
10. Floyd 距离矩阵更新。
11. 拓扑排序序列。
12. 关键路径、关键活动。
13. 分块查找确定目标所在块。
14. 线性探查或拉链法构造散列表，并计算成功/不成功 ASL。
15. 二分搜索比较过程和判定树。
16. 归并排序每一趟结果、快速排序一趟划分结果。

3. 算法设计题

答题结构：

1. 说明使用的数据结构。
2. 写出核心算法步骤。
3. 给出伪代码或 C 语言代码。
4. 分析时间复杂度和空间复杂度。

链表题注意：

先保存后继，再修改指针。
涉及删除必须 free。
带头结点时从 head->next 才是第一个有效结点。

树题注意：

递归出口通常是 p == NULL。
遍历题先明确访问根的位置。
层次遍历必须使用队列。

图题注意：

遍历前初始化 visited 数组。
非连通图需要从每个未访问顶点再次出发。
最短路径题要写清 D、p、s 数组含义。
拓扑排序要检查是否输出 n 个顶点。

排序、查找与算法设计题注意：

二分查找必须先确认顺序表有序。
快速排序一趟划分后，只有基准元素确定最终位置。
散列表题要写清散列函数、表长、冲突处理方法。
动态规划题先定义状态，再写状态转移。
贪心题要说明贪心选择依据，不能把 0-1 背包误写成分数背包。

十一、最后复习清单

必背公式

1. 顺序表长度：last + 1。
2. 循环队列队满：(rear + 1) % maxsize == front。
3. 循环队列长度：(rear - front + maxsize) % maxsize。
4. 二维数组行优先地址：Loc(aij) = Loc(a00) + (i * n + j) * d。
5. 对称矩阵压缩：k = i * (i + 1) / 2 + j，其中 i >= j。
6. 二叉树叶子数：n0 = n2 + 1。
7. 完全二叉树深度：floor(log2 n) + 1。
8. 哈夫曼树：WPL = sum(wi * li)。
9. 无向图度数和：2e。
10. Floyd：A[i][j] = min(A[i][j], A[i][k] + A[k][j])。
11. 关键活动：e(i) == l(i)。
12. 装填因子：alpha = n / m。
13. 除留余数法：H(key) = key % p。
14. 线性探查：di = (H(key) + i) % m。
15. 分数背包单位价值：vi / wi。

必会算法

1. 顺序表插入、删除。
2. 单链表头插、尾插、查找、插入、删除、合并。
3. 顺序栈和链栈的入栈、出栈。
4. 循环队列和链队列的入队、出队。
5. 朴素模式匹配。
6. 三元组稀疏矩阵转置。
7. 二叉树先序、中序、后序、层次遍历。
8. 由先序和中序恢复二叉树。
9. 哈夫曼树构造和编码。
10. 二叉排序树查找、插入、删除。
11. 图的 DFS 和 BFS。
12. Prim、Kruskal、Dijkstra、Floyd。
13. 拓扑排序和关键路径。
14. 分块查找、线性探查散列表、拉链法散列表。
15. 二分搜索、归并排序、快速排序。
16. 矩阵连乘、0-1 背包、分数背包。

三天冲刺建议

第一天：

线性表、栈、队列、串、数组。
重点练：指针操作、循环队列、数组地址、矩阵压缩。

第二天：

树和二叉树。
重点练：遍历、恢复二叉树、哈夫曼树、二叉排序树删除。

第三天：

图。
重点练：DFS/BFS、最小生成树、最短路径、拓扑排序、关键路径。

补充冲刺：

索引、散列、缩小规模算法。
重点练：分块查找、散列表 ASL、二分、归并、快排、动态规划和贪心区别。

十二、自测题

1. 顺序表和链表分别适合什么场景？为什么？
2. 带头结点单链表删除第 i 个结点，为什么要先找到第 i-1 个结点？
3. 循环队列为什么常常浪费一个存储单元？
4. 栈如何支持递归调用？
5. 给定一个二叉树，写出先序、中序、后序、层次遍历序列。
6. 为什么先序和中序可以唯一恢复二叉树？
7. 哈夫曼树构造时为什么每次选择两个最小权值？
8. 二叉排序树删除有两个孩子的结点时，为什么可用直接前驱或直接后继替代？
9. 邻接矩阵和邻接表分别适合什么图？
10. Prim 和 Kruskal 的区别是什么？
11. Dijkstra 中 D、p、s 数组分别表示什么？
12. 拓扑排序如何判断图中有环？
13. 关键路径中 ve、vl、e(i)、l(i) 的含义分别是什么？
14. 稠密索引和稀疏索引的区别是什么？
15. 分块查找为什么要求块间有序？
16. 线性探查法和拉链法分别如何解决冲突？
17. 散列表成功 ASL 和不成功 ASL 的平均对象有什么不同？
18. 归并排序和快速排序分别如何体现分治思想？
19. 动态规划和备忘录方法的求解方向有什么区别？
20. 为什么分数背包可以贪心，而 0-1 背包不能直接用同样方法？