数据结构
全书精读
按考研 408 数据结构大纲编排。复杂度必须写清最好 / 平均 / 最坏与前提。可以少讲，不写错；数值例题已手算。
绪论与复杂度
LEVEL 1数据结构管的是数据对象、关系、操作。算法分析先钉死渐进记号，再谈哪一种输入。
1.1抽象与记号
抽象数据类型（ADT）规定数据对象、逻辑关系和基本操作，不规定顺序/链式等存储实现。大 O 描述上界，Ω 下界，Θ 同阶。平时说「O(n)」默认是渐进上界，不要把它写成精确步数。
1.2最好 / 平均 / 最坏
同一算法三条曲线可以不同。平均必须带分布前提：随机排列、随机插入、均匀散列等。「平均 O(log n)」若省略前提，在退化输入上是错的。
线性表
LEVEL 2线性表是同一类型元素的有限序列。实现分顺序与链式。关系约束是「相邻」，比树、图更紧。
2.1顺序表
随机访问下标 O(1)。在第 i 个位置插入或删除，平均要移动约一半元素，时间 O(n)。表尾操作才是 O(1)。
2.2单链表与前驱
按位查找、按值查找都是 O(n)。单链表按位定位 O(n)；已定位到相关前驱结点后，插入/删除的改链操作 O(1)。只握着待删结点本身，单链表找不到前驱，不能 O(1) 删除（除非用后继覆盖再删后继这种特殊手法，题面要写明）。
双链表在已知结点上插入删除都可以 O(1) 改链。循环链表、头结点是实现细节，判空看头指针与头结点约定。
栈与队列
LEVEL 23.1栈
后进先出。共享栈把两个栈从数组两端往中间长，栈满当两顶相邻。括号匹配、表达式求值、递归消除、迷宫回溯是典型应用，不是四种新结构。
3.2循环队列
教材常用：front 指向队头元素，rear 指向下一个可插入位置。空：front == rear。满：(rear+1) mod M == front（浪费一个单元）。也可用计数或标志位区分空满，题面以约定为准。
串
LEVEL 34.1朴素匹配
主串长 n、模式长 m。设 1≤m≤n。最坏比较次数 Θ((n−m+1)m)，上界常简写 O(nm)。最好成功匹配情形：第一次对齐即匹配，比较 Θ(m)。
4.2KMP 与 next
失配时模式向右滑到「已匹配前缀」允许的位置，主串指针不回退。采用严蔚敏口径：1 下标，next[1]=0。
P a b a a b c
next 0 1 1 2 2 3
失配于 j 时改与 P[next[j]] 比。next[1]=0 表示模式整体右移一格、主串进一。
构造 next 本身是 O(m)。匹配 O(n)。不要把 nextval 优化和 next 混成一张表还不声明。
树与二叉树
LEVEL 35.1性质与遍历
约定根为第 1 层。二叉树第 i 层最多 2i−1 个结点；高 h 最多 2h−1。非空二叉树满足 n0 = n2 + 1。先序 / 中序 / 后序是三种遍历次序，不是三种树。层序用队列。
完全二叉树可用数组下标父子：1 下标时，若 2i≤n 则左孩子为 2i，若 2i+1≤n 则右孩子为 2i+1。满二叉树与完全二叉树不要混称。
5.2线索 · 并查集
线索二叉树用空指针穿到前驱后继，方便中序走访。并查集维护不相交集合：查找根、合并两棵树；路径压缩与按秩合并是实现优化。Kruskal 用它判回路。
查找树与哈夫曼
LEVEL 46.1BST / AVL
BST 查找 O(h)。随机插入形成的 BST，期望高度 O(log n)；按有序序列插入会退化成链，最坏 O(n)。AVL 要求平衡因子 ∈ {−1,0,1}，用单旋 / 双旋恢复，查找 O(log n)。红黑树只要求「近似平衡」的概念，408 不把旋转细则当必答题。
6.2B / B+ · 哈夫曼
m 阶 B 树：根若非叶至少 2 叉，非根内部结点至少 ⌈m/2⌉ 叉，所有叶在同一层（非空单结点 B 树的根可为叶）。B+ 树记录/数据只存叶，内部结点只存索引关键字，分隔关键字可在上层重复；叶常串成链表。二者都是多路平衡树，适合外存块访问——这里只写结构，不写操作系统页置换。
深度：A=1，B=2，C=D=3。
WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35。
哈夫曼树不唯一（并列权值时合并顺序可变），WPL 最小这一点不变。编码是前缀码。
图
LEVEL 47.1存储与遍历
邻接矩阵边查询 O(1)，空间 Θ(V²)。邻接表适合稀疏图。邻接表上 BFS、DFS 都是 O(V+E)。BFS 用队列，得到无权图最短路；DFS 用栈 / 递归，不保证最短。
7.2最短路 · MST
Dijkstra：每次取未确定点中距离最小者做松弛，边权必须非负。矩阵实现常见 O(V²)。负权边不要套它。Floyd：三重循环 O(V³)，允许负权，不允许负权环。Bellman-Ford 能检负环，但标准单源版本只能检出从源点可达的负权环；408 点到前提即可。
最小生成树：Prim 长树，Kruskal 按边权排序再并查集。无向连通带权图。两种算法得到的树可能不同，权值和相同（边权互异时树唯一）。
7.3拓扑 · 关键路径
拓扑排序只对有向无环图。关键路径在 AOE 网：事件最早 / 最迟发生时间，活动最早 / 最迟开始时间，松弛为 0 的活动在关键路径上。
查找
LEVEL 3顺序查找 O(n)。折半查找要求有序的顺序表，比较次数 O(log n)；链表上不能按中点下标折半。分块查找：块间有序、块内任意，先定块再块内扫，介于二者之间。
动态查找表见 BST / AVL / B 树（第 06 章）。静态表用折半或索引。
散列
LEVEL 3散列函数把关键字映射到槽。除留余数法 h(k)=k mod p，p 常取不大于表长的素数。冲突不可避免。平均查找在均匀假设下接近 O(1)；全部撞车时最坏 O(n)。
拉链：同槽做成链表。开放定址：线性探查 h+i，二次探查约定 h+i²，再散列。装载因子 α = n/m；同一散列/探查方式与均匀假设下，α 越大期望探查越长。开放定址还要求 α<1。删除常用墓碑标记，直接清空会截断探查链。
19→8。30→8 冲突，线性探查 → 9。41→8、9 已占 → 10。
二次探查：30→8+1²=9；41→8+2²=12≡1 (mod 11)。
排序
LEVEL 410.1八大内排
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 折半插入 | O(n log n) 比较 | 移动仍 Θ(n²) | 同左 | O(1) | 是 |
| 希尔 | 与增量有关 | 与增量有关 | 可达 O(n²) | O(1) | 否 |
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快速 | O(n log n) | O(n log n) | O(n²) | 平均 O(log n) | 否* |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | 否* |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否* |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 基数 | O(d(n+r)) | 同左 | 同左 | O(n+r) | 是† |
* 教材默认实现通常不稳定；「可以改成稳定」不当作默认结论。† 每一位必须用稳定的桶/计数排序。建堆是 O(n)，不是 O(n log n)。快排最坏出现在每次枢轴极偏（如已序且取端点）。
10.2外排概念
数据在外存。先生成初始归并段，再多路归并。败者树减少比较次数。这里只要求概念，不编造某次 I/O 次数。