数据结构与算法复习

线性结构

1. 核心概念

• 逻辑结构：线性表的核心特征是数据元素之间存在一对一的线性关系。
  • 必须要掌握的两种基本实现方式：顺序表 和 链表。
  • 两种受限的线性表：
    • 栈：后进先出 (LIFO)，递归的基石。
    • 队列：先进先出 (FIFO)，广度优先搜索的基石。

2. 重点与难点 (Exam Focus)

• 指针操作：单链表的插入与删除 是必考点，注意指针赋值顺序。
• 索引计算：
  • 一维数组地址计算。
  • 矩阵压缩存储（对称矩阵、三对角矩阵的下标转换）。
• 溢出问题：
  • 理解 循环队列 如何解决C顺序队列的“假溢出”问题。
• 应用场景：
  • 栈的应用：表达式求值、迷宫求解。
  • 稀疏矩阵：三元组表与十字链表。

树与分治

1. 核心概念 (Core Concepts)

• 树的逻辑结构：一对多，层次结构。
• 二叉树 (Binary Tree)：最核心结构，区分左右子树。
  • 特例：满二叉树、完全二叉树。
  • 存储：顺序存储（适合完全二叉树）、链式存储（二叉链表）。
  • 操作：二叉树遍历（递归/非递归）、线索化（了解即可）。
• 树与森林 (Tree & Forest)
  • 转换：树/森林 $\leftrightarrow$ 二叉树（左孩子右兄弟表示法）。
  • 遍历：先根、后根遍历。
• 应用 (Applications)
  • 哈夫曼树 (Huffman Tree)：最优二叉树，用于数据压缩。
  • 二叉排序树 (BST)：查找效率 $O(\log n)$。
  • 堆 (Heap)：一种特殊的完全二叉树，用于 堆排序。
  • AVL 自平衡二叉树

2. 算法思想 (Algorithm Design)

• 分治法 (Divide and Conquer)
  • 核心：分解 (Divide) → 解决 (Conquer) → 合并 (Combine)。
  • 典型应用：归并排序、大整数乘法、Strassen矩阵乘法。
  • 复杂度分析：递归方程求解（代换法、递归树、主方法）。

图与贪心

1. 贪心算法 (Greedy Strategy)

• 核心思想：只看当下，局部最优 $\to$ 整体最优。
• 经典问题：
  • 活动安排问题：按结束时间排序。
  • 背包问题 (分数背包)：按性价比（价值/重量）排序。注意：0-1背包不能用贪心（需用动态规划）。
  • 多机调度问题：按作业时间排序。

2. 图论基础 (Graph Theory)

• 存储结构：
  • 图的存储：邻接矩阵（稠密图）、邻接表（稀疏图）、十字链表（有向图）、邻接多重表（无向图）。
• 遍历：
  • 图的遍历：DFS（递归/栈）、BFS（队列）。
• 核心算法 (Exam Focus)：
  • 最小生成树 (MST)：Prim算法、Kruskal算法。
  • 最短路径 (Shortest Path)：Dijkstra算法、Floyd算法。
  • 拓扑排序 (Topological Sort)：AOV网，检测环。
  • 关键路径 (Critical Path)：AOE网，工程工期。

查找与排序

1. 查找 (Search)

• 静态查找：表结构在查找过程中不改变。
  • 顺序查找：适合无序表，$O(n)$。
  • 折半查找 (Binary Search)：适合有序顺序表，$O(\log n)$。
  • 索引查找：分块查找，块间有序，块内无序。
• 动态查找：表结构动态调整（如BST，已在树章节复习）。
• 散列技术：
  • 哈希表 (Hash Table)：通过函数映射实现 $O(1)$ 查找。
  • 关键：哈希函数构造 + 冲突处理。

2. 排序 (Sort)

• 内部排序：数据在内存中。
  • 插入排序：直接插入（稳定）、希尔排序（不稳定）。
  • 交换排序：冒泡排序（稳定）、快速排序（不稳定，核心）。
  • 选择排序：简单选择（不稳定）、堆排序（不稳定，$O(n\log n)$）。
  • 归并排序：稳定，分治思想。
  • 基数排序：分配 + 收集，稳定。
• 外部排序：数据量大，需借助外存（如归并排序的变种）。

3. 核心考点 (Exam Focus)

• ASL 计算：查找成功与失败的平均查找长度。
• 排序过程模拟：给出一个序列，写出某算法（如快排、希尔）前几趟的结果。
• 算法性能对比：排序算法稳定性 与时间/空间复杂度表格。

---

考点速查表 (Complexity Table)

算法	平均时间	最坏时间	空间	稳定性	备注
直接插入	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	$n$ 小或基本有序时快
希尔	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	增量序列影响大
冒泡	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	可加 flag 优化
快排	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	综合性能最好
简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	移动次数少
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	适合 $n$ 大，不适合 $n$ 小
归并	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	需辅助空间

动态规划

1. 核心思想 (Core Philosophy)

• 定义：将待求解问题分解成若干个重叠子问题，通过保存子问题的解（备忘录）来避免重复计算。
• 与分治法的区别：
  • 分治法：子问题相互独立（如归并排序）。
  • 动态规划：子问题重叠（如斐波那契数列）。
• 基本要素 (必考概念)：
  1. 最优子结构：问题的最优解包含其子问题的最优解。
  2. 重叠子问题：递归求解时，相同的子问题被反复计算。
  3. 无后效性：某阶段的状态一旦确定，就不受后续决策影响（“未来与过去无关”）。

2. 经典模型 (Classic Problems)

• 线性模型：
  • 最长公共子序列 (LCS)：字符串相似度计算。
  • 0-1背包问题：资源分配问题（注意与贪心法的区别）。
• 区间模型：
  • 矩阵连乘问题：寻找最少乘法次数。
  • 凸多边形最优三角剖分：与矩阵连乘同构。
  • RNA第二结构预测：生物信息学应用。
• 其他应用：
  • 最短路径（Floyd算法，已在图论章节复习）。
  • 带权活动安排
  • 最长公共子序列

课后习题

第一章 绪论

1. 数据结构从逻辑结构（元素之间的关系）分为线性结构和非线性结构（一对多 or 一对一）
2. 算法分析是通过分析算法的时间复杂度、空间复杂度，评估其执行效率，从而优化算法性能。
3. 时间复杂度的增长速度：指数级 > 多项式级（高次幂 > 低次幂）> 对数级
4. 数据元素是构成数据的 基本 单位，数据项是构成数据的 最小 单位。

一、数据为什么需要结构？

核心目的：高效处理数据

1. 简化逻辑：通过结构（如数组、树）清晰表达数据间关系，降低理解与操作的复杂度；
2. 提升效率：合理结构（如哈希表）优化增删改查的时间/空间性能；
3. 节省空间：结构化存储（如链表）避免无结构数据的空间浪费；
4. 增强复用：通用结构（如栈、队列）是同类问题的“模板”，减少重复开发。

二、算法与程序的相同点和区别

维度	相同点	区别（算法 vs 程序）
核心属性	都是解决问题的步骤集合	算法是抽象逻辑思路；程序是算法的代码实现
特性要求	依赖清晰逻辑	算法必须“有穷、确定、可行”；程序可无限循环（如服务器）
表达载体	——	算法用自然语言/伪代码；程序用编程语言编写
关注重点	——	算法重“正确性”；程序重“可运行性”（需考虑语法/环境）

三、用抽象数据类型（ADT）定义矩阵类型

ADT是“数据+操作”的封装，定义矩阵需明确两部分：

1. 数据结构：

   • 稠密矩阵：用二维数组存储，记录行数rows、列数cols；
   • 稀疏矩阵：用三元组（行号、列号、元素值）存储非零元素。

2. 操作集合（以稠密矩阵为例）：

   • 初始化：InitMatrix(&M, rows, cols)
   • 元素访问：GetElement(M, i, j)、SetElement(&M, i, j, val)
   • 矩阵运算：AddMatrix(M1, M2)（求和）、MultiplyMatrix(M1, M2)（求积）、TransposeMatrix(M)（转置）

第二章 线性结构

• 装填因子 ($\alpha$)：$\alpha =\text{填入表中的元素个数}/\text{哈希表长度}$。

  • $\alpha$ 越大，发生冲突的可能性越大。

• 冲突处理：

  1. 开放定址法：$H_i=(H(key)+d_i)(\mathrm{mod}m)$
     • 线性探测：$d_i=1,2,3,\dots$ (易产生“堆积”现象)。
     • 二次探测：$d_i=1^2,-1^2,2^2,-2^2,\dots$
  2. 链地址法 (Chaining)：冲突元素挂在链表中 (无堆积现象，平均查找长度较短)。

• 排序方法：

  1. 直接插入：把当前元素插入到前面已排好序的序列中，直到所有元素有序。
     • 稳定（相等元素相对位置不变）；
     • 趟数固定为n-1，与原序列无关。
  2. 冒泡：每趟从左到右比较相邻元素，把大的元素 “冒泡” 到右侧（或小的到左侧），直到无交换。
     • 趟数由原序列有序程度决定（越有序，趟数越少）。
  3. 简单选择：每趟找到 “未排序部分的最小元素”，放到已排序部分的末尾。
     • 不稳定（如原序列的两个 2，交换后相对位置改变）；
     • 趟数固定为n-1，与原序列无关。
  4. 快速：选一个 “基准元素”，把序列分成 “比基准小” 和 “比基准大” 的两部分（分区），再对两部分递归排序。
     • 不稳定（分区时相等元素的相对位置可能被打乱）；
     • 效率高，但最坏情况（原序列有序）效率低。
  5. 希尔：按 “增量” 分组，对每组做直接插入排序；逐步减小增量，直到增量为 1（此时就是直接插入排序）。
     • 不稳定（分组排序时相等元素会跨组移动）；
     • 趟数由增量序列决定，与原序列无关。

线性表存储结构：顺序、链式

线性表的链式存储结构主要包括 单链表、循环链表 和 双向链表 三种形式，其中最基本的形式是 单链表。

线性表操作次数：

1. 插入操作 (Insertion)
   • 插入位置：共 $n+1$ 个（含队尾）。
   • 最大移动：插在第 1 位，移动 $n$ 次。
   • 最小移动：插在最后，移动 $0$ 次。
   • 平均移动：$\frac{0+n}{2}=\frac{n}{2}$
2. 删除操作 (Deletion)
   • 删除位置：共 $n$ 个。
   • 最大移动：删第 1 位，移动 $n-1$ 次。
   • 最小移动：删最后一位，移动 $0$ 次。
   • 平均移动：$\frac{0+(n-1)}{2}=\frac{n-1}{2}$

在三对角矩阵中，只有主对角线及其相邻的两条对角线上有非零元素。对于一个 $n\times n$ 的三对角矩阵 $A$，其非零元素的分布特征是：当且仅当 $|i-j|\le 1$ 时，$a_{ij}$ 是非零元素。

对于元素 $a_{ijk}$，其跳过的元素个数公式为： $N=k\times (m\times n)+j\times m+i$ (注：如果题目是“行优先”，公式则反过来：$N=i\times (n\times p)+j\times p+k$)

线性表的 逻辑长度 与 物理长度 总是一致的。

岗哨：在查找之前，将待查找的关键字 $K$ 存入 $R[0]$。这样做的好处是：在 while 循环中不需要判断下标是否越界，因为最坏情况下一定会在 $R[0]$ 处找到 $K$。

在索引表中，每个索引项至少包含有 关键字 域和 地址 域这两项。

在采用链地址法解决冲突时，平均查找长度（ASL）主要取决于哈希表的装填因子（Load Factor），计算公式如下：

• 装填因子 $\alpha$：$\alpha =\frac{n}{m}$ （其中 $n$ 是数据个数，$m$ 是哈希表长度）。
• 平均查找长度（成功）：$AS{L}_{成功}\approx 1+\frac{\alpha }{2}$
• 平均查找长度（不成功）：$AS{L}_{不成功}\approx \alpha +e^{-\alpha }$ （或者简单近似为 $\alpha$）

若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据的排序

哈希表（Hash Table，也称散列表）是一种通过建立键（Key）与存储地址（Address）之间直接映射关系来实现高效查找的数据结构。

• 访问速度快
• 数据无序
• 冲突必然性
• 存储空间与时间的平衡

第三章 递归与分治

汉诺塔问题：

• 移动 $n$ 个盘子的总步数 $H(n)$ 的递推公式为： $H(n)=2\times H(n-1)+1$
• 通项公式计算：$H(n)=2^n-1$

分形是基于自然界图形的 自相似 特点

• Koch 曲线、康托尔集、曼德博集合

递归算法的计算过程是从大到小，而迭代算法的计算过程是从小到大

系统用于保存递归函数调用信息的堆栈叫调用栈

针对分治问题（Divide and Conquer）的复杂度计算，最核心且常用的方法有以下三种

• 主定理
• 递归树
• 代入法

可以使用分治策略的问题通常需要满足以下四个特征：

• 可分性：原问题可以分解为若干个规模较小的相同子问题。
• 子问题独立性：各个子问题之间相互独立，即子问题之间不包含公共的子子问题（这是分治与动态规划的主要区别）。
• 递归出口：子问题规模足够小时可以很容易地直接求解。
• 合并性：利用子问题的解可以合并出原问题的解。

树

在任何一棵二叉树中，叶子结点（度为 0 的结点）与度为 2 的结点之间存在如下关系：$n_0=n_2+1$- $n_0$：叶子结点的个数（度为 0）

• $n_2$：度为 2 的结点个数

完全二叉树：除了最后一层外，其他各层都是满的，且最后一层的结点都集中在左侧。

哈夫曼树是通过不断“合并”节点构建出来的：

1. 初始状态：我们有 $n$ 个叶子结点，它们各自都是一棵独立的树（此时有 $n$ 个连通分量）。
2. 合并规则：每次从所有树中选出根结点权值最小的两棵，合并成一棵新树。
3. 关键动作：每次合并，都会消耗掉 2 个旧的根结点，并生成 1 个新的分支结点（作为这两个结点的父结点）。
4. 终止状态：直到最后只剩下一棵树为止。

树转换为二叉树（孩子-兄弟表示法）：

1. 将所有孩子连起来
2. 断开除最左孩子外，其他孩子与父节点的连线
3. 将其他孩子移为最左孩子的右子树

在数据结构中，堆通常是指完全二叉树。它分为两种：

• 大根堆：任何一个父结点的值都大于或等于它的左、右孩子结点。
• 小根堆：任何一个父结点的值都小于或等于它的左、右孩子结点。 从序列上看，如果一个序列是堆，必须满足：

1. 它的左孩子是第 $2i$ 个元素。
2. 它的右孩子是第 $2i+1$ 个元素。
3. 必须满足：$A[i]\ge A[2i]$ 且 $A[i]\ge A[2i+1]$（大根堆）

2-3 树是一种非常特殊的自平衡搜索树。你可以把它看作是普通二叉搜索树的“升级版”。它的名字“2-3”来源于它节点的分叉（孩子）数量。

哈夫曼树 WPL 的计算有两种方法：

• 方法 A（定义法）： $\sum (叶子权值\times 路径长度)$。
• 方法 B（求和法，更简单）： 所有非叶子结点的权值之和。

二叉树的先序遍历、中序遍历和后序遍历的共同特征是 遍历左子树先于右子树

在结点数为 $n$ 的红黑树中，插入、删除、查找结点的复杂度分别为：$O(\log n)$、$O(\log n)$、$O(\log n)$。

图

• 最大边数但仍可能不连通： 若无向图有 $n$ 个顶点，能构成的最大非连通图的边数是： $e_{max\_non\_connected}=\frac{(n-1)(n-2)}{2}$

  （即 $n-1$ 个点全连接，1 个点孤立）

• 保证连通的最小边数： 若要 $n$ 个顶点的无向图一定连通，所需的最小边数是： $e_{min\_must\_connected}=\frac{(n-1)(n-2)}{2}+1$