数据结构复习最容易变成“记住定义”，却无法在代码中做选择。更有效的路线是先明确抽象和复杂度，再沿着数据结构之间的转换关系学习，最后用边界条件和实现约束检验理解。
本文是历史课程笔记的重组与阅读路线，不是对任何单篇原题的替代。算法题的输入约束不同，复杂度和实现细节也应以题目要求为准。
先问三个问题
面对一道题或一个工程问题，先回答：
- 输入和输出是什么？ 规模、是否有序、是否允许修改、是否需要稳定。
- 操作频率是什么？ 主要是查询、插入、删除、遍历、合并，还是最短路。
- 约束在哪里？ 内存、递归深度、比较代价、整数范围和实时性。
没有这些信息，直接说“用红黑树”或“用快排”都没有意义。
推荐路线
第一阶段：复杂度与基础存储
从 数组 和 线性表 开始，掌握连续存储与链式存储的取舍。复杂度分析要同时看时间、空间和常数项，尤其是数组搬移、扩容和缓存局部性。
第二阶段：线性约束
栈与队列 适合从表达式、括号匹配、调用栈和 BFS/DFS 的辅助结构入手。重点不是记 API，而是理解“后进先出”和“先进先出”如何改变问题的处理顺序。
第三阶段：树与查找
树与二叉树 先覆盖遍历、线索化、树与二叉树的转换，再进入平衡树、BST 和堆。继续阅读 查找 时，把“查找路径长度”看作数据结构设计的一部分，而不只是最后计算的结果。
第四阶段：图与高阶应用
图 的核心是存储方式和遍历能力：邻接矩阵适合稠密图，邻接表适合稀疏图。之后再学习最小生成树、最短路径、拓扑排序和关键路径。工程中还要记住：递归深度、不可达节点、负权、浮点距离和大规模图的栈/堆开销。
第五阶段：排序
排序 建议用“比较次数、移动次数、稳定性、原地性、是否适用于链表”五个维度整理，而不是只背复杂度。可以用下表作为第一轮速查：
| 关注点 | 典型选择 | 需要验证的问题 |
|---|---|---|
| 通用原地排序 | 快速排序、堆排序 | 枢轴选择、递归深度、稳定性 |
| 稳定排序 | 归并排序、基数排序 | 辅助空间、比较/移动成本 |
| 接近有序 | 插入排序、Timsort 类策略 | 逆序对、是否需要稳定 |
| 极值统计 | 选择排序、堆 | 数据量和选择次数 |
从“会写”到“可靠实现”
每个算法至少做四组实验：
- 空输入和单元素输入；
- 重复值、负数或极大值；
- 已经有序、逆序和随机数据；
- 资源不足、递归过深或输入不可达时。
实现代码时优先保证边界行为清晰，再优化常数。笔记中的练习可以先写成可读的伪代码，再实现 C++；不要用未验证的指针运算掩盖算法的核心逻辑。
一个可复用的复习卡片
问题模型：
候选结构：
核心不变量：
时间复杂度：
空间复杂度：
边界条件：
实现风险：
测试样例：
高质量的算法笔记最终应该能回答“为什么这个结构适合这个操作，以及它在什么条件下会失效”。这也是把课程知识迁移到后端代码、日志分析、任务调度和性能优化的起点。