第二卷：数据结构与算法

数组、哈希表和树各有擅长的操作。本卷用不变量检查正确性，用复杂度比较成本。十个元素时大家跑得都挺快，数据再加几个零，区别就出来了。

先修知识

• 能用一种语言写循环、函数和递归，并能读懂数组访问；有缺口时回到编程基础。
• 理解对数、求和与简单归纳推理；证明方法可以按需查数学基础。

覆盖内容

第 1 章先约定如何分析成本，第 2 至 8 章学习数据结构与图，第 9 至 14 章比较算法，第 15 章补充按特定查询需求设计的结构。

第 1 章

• 1.1 复杂度是什么
• 1.2 常见复杂度分析
• 1.3 渐近界、递推式与摊还分析

第 2 章

• 2.1 数组
• 2.2 链表
• 2.3 数组与链表：如何选择

第 3 章

• 3.1 栈：后进先出
• 3.2 队列：先进先出
• 3.3 双端队列：两端操作与滑动窗口

第 4 章

• 4.1 哈希表基础
• 4.2 哈希冲突与扩容

第 5 章

• 5.1 二叉树的结构与递归
• 5.2 二叉搜索树的增删查
• 5.3 树的遍历：递归、栈与队列

第 6 章

• 6.1 AVL 树与旋转
• 6.2 红黑树

第 7 章

• 7.1 堆
• 7.2 优先队列

第 8 章

• 8.1 图的表示：先把顶点和边放进内存
• 8.2 图搜索：从一条网络路径走到整张网络
• 8.3 加权最短路径：路少，不等于路程短

第 9 章

• 9.1 初级排序：冒泡、选择、插入
• 9.2 高级排序：希尔、归并与分治

第 10 章

• 10.1 快速、堆与非比较排序
• 10.2 排序对比：从约束到选择

第 11 章

• 11.1 二分搜索与边界
• 11.2 字符串匹配

第 12 章

• 12.1 分治
• 12.2 回溯

第 13 章

• 13.1 动态规划入门
• 13.2 经典动态规划问题

第 14 章

• 14.1 贪心算法
• 14.2 补充：NP 完全性与归约
• 14.3 补充：摊还分析

第 15 章

• 15.1 高级数据结构导览
• 15.2 布隆过滤器
• 15.3 并查集
• 15.4 线段树

学完能做什么

• 为查找、插入、排序或路径问题选一种实现，并说明输入规模与空间限制。
• 用循环不变量、归纳或交换论证解释正确性，再用边界输入找反例。
• 区分最坏、平均与摊还成本；解释一次基准结果能支持多大的结论。

怎样使用这份目录

初学时先读复杂度和线性结构，再学习树、图与算法。复习某个算法时，把一个正常输入和一个边界输入手算出来，再运行实现核对；时间复杂度写对了，数组下标仍然可能越界。