数据结构代码板子
写法：C 风格，可以用 C++ 的
&引用和bool；不用 STL，不写头文件和main，数组下标从 0 开始。完整约定见 结构体定义与写法约定。 分级：★★★ 闭眼手写 · ★★ 能写出来 · ★ 会手算就行。〔年份〕表示 408 真题算法题的出处，打勾表示已经写好。
0. 基础部分
1. 顺序表 / 数组
- 区间逆置与循环左移 ★★★ 〔2010〕
- 删除所有值为 x 的元素 ★★★
- 有序表去重与合并 ★★★
- 二分查找 ★★★
- 辅助数组计数与标记 ★★★ 〔2018〕
- 主元素：摩尔投票 ★★ 〔2013〕
- 两个等长升序序列的中位数 ★★ 〔2011〕
- 三元组最小距离 ★★ 〔2020〕
2. 链表
- 建表（头插法、尾插法）与插入删除 ★★★
- 链表就地逆置 ★★★
- 删除值为 x 的结点 ★★★
- 快慢指针：中点、倒数第 k 个、判环 ★★★ 〔2009〕
- 合并两个有序链表 ★★★
- 两个链表的公共结点 ★★ 〔2012〕
- 链表按绝对值去重 ★★ 〔2015〕
- 链表重排 ★★ 〔2019〕
3. 栈、队列、串
- 括号匹配 ★★
- 中缀转后缀与后缀求值 ★
- KMP 的 next 与 nextval ★（手算见 速查：KMP 的 next 与 nextval）
4. 树与二叉树
- 前序、中序、后序递归遍历 ★★★
- 层序遍历与按层处理 ★★★
- 非递归遍历：中序 ★★★；前序、后序 ★★
- 靠递归返回值的题：树高、结点数、叶子数、各种度的结点数、第 k 层结点数 ★★★
- 带深度参数的递归：WPL ★★★ 〔2014〕
- 表达式树转中缀表达式 ★★★ 〔2017〕
- 判断二叉排序树 ★★ 〔2022〕
- 判断完全二叉树与平衡二叉树 ★★
- 找祖先与最近公共祖先 ★★
- 用前序 + 中序建树 ★★
- 并查集（路径压缩） ★★
- 中序线索化 ★；BST 删除、AVL 旋转 ★ 只考手算，见 BST 删除、AVL 四种旋转
5. 图
- DFS 与 BFS（邻接矩阵版 + 邻接表版） ★★★
- 邻接矩阵上统计度数 ★★★ 〔2021、2023〕
- 拓扑排序与唯一性判断 ★★★ 〔2024〕
- BFS 求无权图单源最短路 ★★
- 判断路径、判断有环、判断树 ★★
- Floyd ★★
- Prim 与 Dijkstra、Kruskal ★
6. 查找
- BST 的查找和插入 ★★
- 散列表线性探测 ★
7. 排序
- 快速排序（教材版 Partition）、partition 的应用：第 k 小、按条件划分 ★★★ 〔2016〕
- 直接插入排序、冒泡排序、简单选择排序 ★★★
- 堆排序 ★★★
- 归并排序 ★★★
- 折半插入排序、希尔排序、计数排序 ★★
- 基数排序 ★
通用思路
双指针 · 三次逆置 · 快慢指针 · 头插法逆置 · 辅助数组计数 · partition · 递归返回子树信息 · BFS 按层处理
边界
- 这里只放考场手写的板子。真正的脚本仍放在 80-Automation/scripts（本地资料）。
链接
- 返回数据结构附录
- 附录规范（本地资料）
- Appendix 模板（本地资料）