数据结构与算法

围绕数据结构与算法建立可解释、可验证的知识主线。

阅读起点

学习前先阅读：计算思维学习路线。

全书顺序

本书按知识依赖组织。主线先建立可运行的共同模型，再进入机制、工程边界和生产约束；维护与前沿内容明确标注，不改变主线的学习顺序。

第1章｜问题建模与复杂度分析

理解本章问题建模与复杂度分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 问题建模：从需求到状态、操作与目标：理解问题建模：从需求到状态、操作与目标的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 时间复杂度：渐进上界、最坏情况与输入规模：理解时间复杂度：渐进上界、最坏情况与输入规模的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 空间复杂度：辅助空间、递归栈与原地算法：理解空间复杂度：辅助空间、递归栈与原地算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 摊销分析：动态数组扩容与势能方法：理解摊销分析：动态数组扩容与势能方法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 正确性证明：循环不变量与归纳法：理解正确性证明：循环不变量与归纳法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 复杂度与工程约束：数据规模、内存与响应时间：理解复杂度与工程约束：数据规模、内存与响应时间的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第2章｜数组、链表与线性结构

理解本章数组、链表与线性结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 数组与连续内存：随机访问、扩容与缓存局部性：理解数组与连续内存：随机访问、扩容与缓存局部性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 动态数组：容量、扩容策略与摊销成本：理解动态数组：容量、扩容策略与摊销成本的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 链表：单链表、双链表、快慢指针与环检测：理解链表：单链表、双链表、快慢指针与环检测的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 双指针与滑动窗口：降低枚举复杂度：理解双指针与滑动窗口：降低枚举复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 前缀和与差分：区间查询与区间更新：理解前缀和与差分：区间查询与区间更新的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 栈与队列：后进先出与先进先出：理解栈与队列：后进先出与先进先出的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第3章｜哈希表、集合与树结构

理解本章哈希表、集合与树结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 哈希表：哈希函数、冲突、负载因子与扩容：理解哈希表：哈希函数、冲突、负载因子与扩容的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 集合与判重：去重、成员测试与频次统计：理解集合与判重：去重、成员测试与频次统计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 树的术语与遍历：根、叶、深度与前中后序：理解树的术语与遍历：根、叶、深度与前中后序的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 二叉搜索树：有序性、查找、插入与删除：理解二叉搜索树：有序性、查找、插入与删除的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 平衡树：AVL、红黑树与复杂度保证：理解平衡树：AVL、红黑树与复杂度保证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 堆与优先队列：上浮下沉、建堆与 Top K：理解堆与优先队列：上浮下沉、建堆与 Top K的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
7. 多路树与外存索引：B 树、B+ 树与磁盘页：理解多路树与外存索引：B 树、B+ 树与磁盘页的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第4章｜图、搜索与路径算法

理解本章图、搜索与路径算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 图的表示：邻接矩阵、邻接表与稀疏图：理解图的表示：邻接矩阵、邻接表与稀疏图的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 深度与广度优先：DFS、BFS 与连通分量：理解深度与广度优先：DFS、BFS 与连通分量的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 拓扑排序：入度法、环检测与任务依赖：理解拓扑排序：入度法、环检测与任务依赖的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 最短路径：BFS、Dijkstra 与 Bellman-Ford：理解最短路径：BFS、Dijkstra 与 Bellman-Ford的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 最小生成树：Kruskal、Prim 与并查集：理解最小生成树：Kruskal、Prim 与并查集的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 网络流与匹配：最大流最小割与二分图：理解网络流与匹配：最大流最小割与二分图的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第5章｜排序、二分与递归分治

理解本章排序、二分与递归分治的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 比较排序：归并、快速、堆排序与稳定性：理解比较排序：归并、快速、堆排序与稳定性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 非比较排序：计数、桶、基数排序与值域假设：理解非比较排序：计数、桶、基数排序与值域假设的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 二分搜索：有序性、边界模板与答案空间：理解二分搜索：有序性、边界模板与答案空间的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 递归与分治：递归树、主定理与子问题重叠：理解递归与分治：递归树、主定理与子问题重叠的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 选择算法：快速选择与 Top K：理解选择算法：快速选择与 Top K的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第6章｜贪心、动态规划与回溯

理解本章贪心、动态规划与回溯的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 贪心策略：局部最优、交换论证与反例：理解贪心策略：局部最优、交换论证与反例的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 动态规划建模：状态、决策、转移与边界：理解动态规划建模：状态、决策、转移与边界的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 线性与背包 DP：序列、路径与状态压缩：理解线性与背包 DP：序列、路径与状态压缩的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 区间与树形 DP：区间分割与树上子问题：理解区间与树形 DP：区间分割与树上子问题的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 回溯与剪枝：选择、约束、撤销与搜索树：理解回溯与剪枝：选择、约束、撤销与搜索树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 记忆化与搜索结合：缓存状态与启发式：理解记忆化与搜索结合：缓存状态与启发式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第7章｜字符串与高级数据结构

理解本章字符串与高级数据结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. KMP 与 Z 算法：前缀函数与线性匹配：理解KMP 与 Z 算法：前缀函数与线性匹配的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. Trie 与多模式匹配：前缀树与词典查询：理解Trie 与多模式匹配：前缀树与词典查询的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 并查集：路径压缩、按秩合并与连通性：理解并查集：路径压缩、按秩合并与连通性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 线段树与树状数组：区间查询与懒标记：理解线段树与树状数组：区间查询与懒标记的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 稀疏表与倍增：静态查询与 LCA：理解稀疏表与倍增：静态查询与 LCA的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 布隆过滤器：位图、误判率与近似统计：理解布隆过滤器：位图、误判率与近似统计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第8章｜工程验证与性能分析（第1段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 在线与流式算法：滑动窗口与流式统计：理解在线与流式算法：滑动窗口与流式统计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 外存与大数据：外部排序、分块与磁盘 I/O：理解外存与大数据：外部排序、分块与磁盘 I/O的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 并行与分布式：任务拆分、通信与负载均衡：理解并行与分布式：任务拆分、通信与负载均衡的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 基准与性能验证：代表性输入、热身与尾延迟：理解基准与性能验证：代表性输入、热身与尾延迟的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 边界与恶意输入：溢出、递归深度与退化树：理解边界与恶意输入：溢出、递归深度与退化树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 渐进分析：理解渐进分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第9章｜工程验证与性能分析（第2段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 摊销分析：理解摊销分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 动态数组扩容：理解动态数组扩容的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 链表指针操作：理解链表指针操作的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 滑动窗口降复杂度：理解滑动窗口降复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 哈希冲突与负载因子：理解哈希冲突与负载因子的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 平衡树旋转：理解平衡树旋转的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第10章｜工程验证与性能分析（第3段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 堆的上浮下沉：理解堆的上浮下沉的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 比较排序的最坏情况：理解比较排序的最坏情况的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 二分搜索的单调性：理解二分搜索的单调性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 递归树与主定理：理解递归树与主定理的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 图的稀疏与稠密：理解图的稀疏与稠密的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 最短路径的负权边：理解最短路径的负权边的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第11章｜工程验证与性能分析（第4段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 交换论证：理解交换论证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 状态转移：理解状态转移的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 记忆化：理解记忆化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 回溯剪枝：理解回溯剪枝的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 搜索空间估算：理解搜索空间估算的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 外部排序：理解外部排序的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第12章｜工程验证与性能分析（第5段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 流式处理：理解流式处理的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 任务拆分与通信：理解任务拆分与通信的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 基准测试：理解基准测试的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 恶意输入：理解恶意输入的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. KMP 的前缀函数：理解KMP 的前缀函数的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. Trie 的前缀树：理解Trie 的前缀树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第13章｜工程验证与性能分析（第6段）

理解本章工程验证与性能分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 并查集：理解并查集的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 线段树：理解线段树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 路径压缩：理解路径压缩的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 懒标记：理解懒标记的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

阅读边界

本页是学习路线和专题入口，不替代专题笔记中的机制解释、可运行示例和练习。笔记尚未完成的专题会先显示为占位页；已有经验的读者可以跳到具体章节，再按前置关系回补。

路线状态

本路线的目录已完成本轮架构审查；专题笔记的内容质量和来源审查另行进行。