数据结构：从概念到算法

块1：数据结构、数据类型与抽象数据类型

数据结构研究的是数据元素之间的逻辑关系、存储方式以及可以进行的操作。常见逻辑关系有线性关系、一对多层次关系和多对多网状关系。

块2：算法与复杂度

算法是解决问题的有限步骤。分析时重点看输入规模 n 增大后，基本操作次数如何增长。

空间复杂度统计额外使用的存储；递归算法还要计算调用栈。

块1：顺序表

顺序表把逻辑相邻元素放在物理相邻的存储单元中。第一个元素地址为 base，每个元素占 sizeof(E)，则 LOC(A[i]) = base + i·sizeof(E)（下标从0开始）。

访问 O(1)，按位置插入/删除平均 O(n)，尾部插入若有空位可为 O(1)。

块2：链表、循环链表与双向链表

链表用结点的指针把不连续的存储单元串成逻辑序列。插入删除的关键是先保存后继，再修改指针；链表随机访问慢，因为必须从头逐结点走。

循环链表把尾结点指回头结点；双向链表每个结点有 prior 和 next，牺牲空间换取向前移动和删除时的便利。

块3：线性表应用

有序表合并利用两个指针分别扫描两个有序序列，每次取较小者，时间 O(m+n)。稀疏数据可用链式结构避免大量空位置；多项式相加本质上是按指数归并。

块1：栈与递归

栈只允许在一端操作，后进先出（LIFO）。递归调用时，系统栈保存当前函数的参数、局部变量和返回位置，因此递归天然可以模拟“回到最近未完成任务”。

把递归改成非递归，通常就是把“系统调用栈”显式换成一个栈。括号匹配、表达式求值、深度优先搜索都利用这一点。

块2：队列与循环队列

队列先进先出（FIFO）：队尾入队，队头出队。顺序队列中即使前面有空位，尾指针到数组末尾也可能无法继续入队，这叫假溢出。循环队列用取模让下标绕回开头。

牺牲一个存储单元时，用 (rear+1)%M == front 判断队满，空队列和满队列就可以只靠 front、rear 区分。

块3：栈和队列的应用

块1：串、模式匹配与 KMP

串是字符序列。朴素匹配失配后把模式串右移一位；KMP利用已经匹配的前缀信息，让模式串跳到不必重比的位置。

next[j]记录模式串前 j 个字符的最长相等真前缀和真后缀长度；nextval进一步跳过与失配字符相同的无效位置。

块2：数组与特殊矩阵

多维数组按某种主序连续存放。二维数组按行优先时，元素 A[i][j] 的地址要先跳过前面完整的行，再跳过当前行前面的列。

对称矩阵、三角矩阵、对角矩阵和稀疏矩阵可以压缩存储。压缩的关键是建立“二维下标 → 一维下标”的映射。

块3：广义表

广义表的元素可以是原子，也可以是另一个表。表结点通常保存 hp（表头）和 tp（表尾）两个指针；原子结点保存数据。

块1：树与二叉树基础

树中每个结点（除根外）有且只有一个双亲；二叉树不仅限制每个结点最多两个孩子，还区分左子树和右子树。

度是孩子数；叶子度为0；树的深度是最大层数。二叉树的结构递归地由根、左子树、右子树构成。

块2：二叉树性质与存储

第 i 层最多有 2^(i-1) 个结点，深度为 h 的二叉树最多有 2^h-1 个结点。顺序存储中，根下标为1时，左孩子 2i，右孩子 2i+1。

完全二叉树适合顺序存储；一般二叉树用二叉链表，每个结点有 left、right 两个指针。

块3：遍历与线索二叉树

先序 DLR、中序 LDR、后序 LRD。层序遍历使用队列；递归遍历的本质是系统栈保存尚未完成的子树。

线索二叉树把空指针改存遍历序列中的前驱或后继，用 LTag/RTag 区分真实孩子和线索，于是中序遍历可以不使用递归栈。

块4：树、森林与转换

孩子—兄弟表示中，左指针指向第一个孩子，右指针指向下一个兄弟。普通树先根遍历对应二叉树先序遍历，普通树后根遍历对应二叉树中序遍历。

森林转换为二叉树：第一棵树的根作为二叉树根；第一棵树根的孩子森林转为左子树；剩余树的森林转为右子树。

块5：哈夫曼树

哈夫曼树让叶子带权路径长度之和 WPL 最小。每次从当前森林选取权值最小的两棵树合并，直到只剩一棵。

左边记0、右边记1，根到叶子的路径就是编码。字符只在叶子上，因此编码具有前缀性，不会出现解码歧义。

块6：并查集

并查集维护若干互不相交的集合，支持 Find（查找代表元）和 Union（合并集合）。双亲数组中，根结点的 parent 通常指向自己或用特殊负值表示集合大小。

路径压缩把查找路径上的结点直接挂到根；按秩/按大小合并让树保持矮。两者结合后，单次操作的摊销复杂度接近 O(α(n))。

块1：图的概念与存储

图由顶点和边组成。边可有向、无向、带权；顶点的度、入度、出度描述与它相连的边数。

邻接矩阵用二维数组表示边，查询 O(1) 但空间 O(V²)；邻接表只保存存在的边，空间 O(V+E)，适合稀疏图。

块2：DFS与BFS

DFS沿一条路径尽量深入，使用递归或栈；BFS按层扩展，使用队列。无权图中，BFS第一次到达某顶点时得到的边数最少。

块3：最小生成树

生成树连接所有顶点且无环；最小生成树（MST）使边权总和最小。Kruskal按边权排序并用并查集防止成环；Prim从一个顶点出发，每次加入连接已选集合的最小边。

块4：最短路径

Dijkstra适合非负权图：每次确定当前距离最小且未确定的顶点，并松弛其邻边。Floyd用动态规划处理所有点对最短路，时间 O(V³)。

块5：拓扑排序与关键路径

拓扑排序只适用于有向无环图（DAG），每次取入度为0的顶点。若最后仍有顶点，说明图中有环。关键路径用于工程进度，关键活动的总时差为0。

块1：线性查找与折半查找

顺序查找不要求有序，最坏 O(n)。折半查找要求有序，每次比较中间元素并排除一半，时间 O(log n)。

块2：二叉排序树与平衡树

二叉排序树满足左子树关键字小于根、右子树关键字大于根，中序遍历得到有序序列。普通 BST 可能退化成链表；AVL 通过旋转保持平衡，红黑树用颜色约束保证 O(log n) 高度。

块3：B树、B+树与散列

B树和B+树适合外存，结点大、树高低，以减少磁盘I/O。B+树的记录通常只在叶子，叶子之间有链，适合范围查询。

散列表通过哈希函数把关键字映射到地址。冲突可用开放定址或拉链法处理；装填因子越大，冲突通常越多。

块1：排序概念与插入排序

稳定排序保持相等关键字原有相对次序；原地排序只需 O(1) 或 O(log n) 额外空间。直接插入排序把当前元素插入前面已经有序的部分，最好 O(n)，最坏 O(n²)。

块2：交换与选择排序

冒泡排序不断交换相邻逆序元素；快速排序选择枢轴分割，平均 O(n log n)，最坏 O(n²)。简单选择排序每轮选择最小值放到前面；堆排序利用堆，时间 O(n log n) 且原地。

块3：归并与基数排序

归并排序把序列分成两半递归排序，再线性合并，稳定且 O(n log n)，但通常需要 O(n) 辅助空间。基数排序按低位到高位或高位到低位处理多关键字，依赖稳定的子排序。

块4：外部排序

数据无法一次装入内存时，先生成有序归并段，再进行多路归并。最佳归并树让总的外存读写量尽量小；核心成本不是比较本身，而是磁盘I/O。