这是一门完整开设的数据结构与算法课程，不是刷题指南，也不是知识点罗列。
它按美国研究型大学计算机系核心课（MIT 6.006 / 6.046、Princeton COS 226、Stanford CS 161 的合集）的标准组织：每一讲都给出数据结构的不变式、算法的正确性论证和复杂度的推导过程，而不只是告诉你"这个是 O(n log n)"。
课程信息
| 项目 | 内容 |
|---|---|
| 课程编号 | CS 261 — Data Structures and Algorithms |
| 课程层次 | 本科二/三年级核心课，研究生补修可用 |
| 教材 | Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th Edition（CLRS）Sedgewick & Wayne, Algorithms, 4th Edition（实现视角补充） |
| 先修 | 一门编程语言（能独立写 300 行以上程序）、离散数学（归纳法、集合、图的基本概念）、基础概率 |
| 代码语言 | Go——所有数据结构与算法都给出可直接运行的 Go 实现，而非伪代码 |
| 组织方式 | 每个数据结构先问"它维护什么不变式"，每个算法先问"为什么它是对的"，最后才问"它有多快" |
这门课想教会你三件事
第一，把问题化归为已知结构。 真实工作里几乎没有"请你实现红黑树"，只有"这个接口 P99 延迟太高"。区别在于你能不能看出：这是一个带优先级的调度问题（堆）、一个可达性问题（BFS）、一个带约束的最优选择问题（DP 或贪心）。
第二，为你的选择给出论证。 说"哈希表更快"是不够的。要能说出：期望 O(1) 的前提是简单均匀散列假设，最坏情况仍是 O(n)，如果攻击者能控制键就会退化成拒绝服务——所以 Python 3.3 之后要给字符串散列加随机盐。每个结论都带前提，这是课程和"背结论"的分界线。
第三，知道什么时候该放弃。 课程最后讲 NP 完全性，不是为了让你证明定理，而是为了让你在遇到一个问题时能判断：继续找多项式算法是浪费时间，该转向近似、启发式还是放宽约束。
课程结构
课程分为七个单元，共 34 讲。
Unit 1 · 分析工具（第 1–4 讲）
在写任何数据结构之前，先建立度量的语言：计算模型、渐近记号、递归式求解、摊还分析。
Unit 2 · 线性结构与散列（第 5–8 讲）
- 第 5 讲：序列 ADT——数组、动态数组与链表
- 第 6 讲：栈、队列与双端队列
- 第 7 讲：散列表 I——散列函数、链地址法与全域散列
- 第 8 讲：散列表 II——开放寻址、Cuckoo、一致性散列与布隆过滤器
Unit 3 · 排序与选择（第 9–13 讲）
排序是算法课的"标准模型"：几乎所有分析技巧都能在这里练一遍。
Unit 4 · 二分与搜索树（第 14–20 讲）
从"有序"这一个需求出发：先是数组上的静态二分，再看它如何被逼出旋转、平衡与增强。
- 第 14 讲：二分查找与二分答案
- 第 15 讲：二叉搜索树
- 第 16 讲：AVL 树与旋转
- 第 17 讲：红黑树与 2-3-4 树
- 第 18 讲：B 树与外存数据结构
- 第 19 讲：随机化平衡——跳表与 Treap
- 第 20 讲：数据结构的增强——顺序统计树与区间树
Unit 5 · 图算法（第 21–27 讲）
- 第 21 讲：图的表示与广度优先搜索
- 第 22 讲：深度优先搜索、拓扑排序与强连通分量
- 第 23 讲：并查集与不相交集合
- 第 24 讲：最小生成树——Kruskal 与 Prim
- 第 25 讲：单源最短路径——Dijkstra 与 Bellman-Ford
- 第 26 讲：全源最短路径——Floyd-Warshall 与 Johnson
- 第 27 讲：网络流——最大流最小割与二分匹配
Unit 6 · 算法设计范式（第 28–33 讲）
四种范式其实是同一棵解空间树的三个切面：回溯走遍全树（靠剪枝），贪心只走一条枝，DP 走遍但记住重复的子树。
- 第 28 讲：分治法
- 第 29 讲：回溯与穷举搜索
- 第 30 讲：贪心算法与交换论证
- 第 31 讲：动态规划 I——原理与经典问题
- 第 32 讲：动态规划 II——进阶模型与优化
- 第 33 讲：字符串算法——KMP、Rabin-Karp、Trie 与后缀结构
Unit 7 · 计算复杂性（第 34 讲）
习题
每套习题都含完整参考答案，并混合三类题：手算追踪（保证你真的懂机制）、证明题（保证你能论证）、实现题（保证你写得出来）。
- Problem Set 1：分析工具与线性结构（第 1–8 讲）
- Problem Set 2：排序与选择（第 9–13 讲）
- Problem Set 3：二分与搜索树（第 14–20 讲）
- Problem Set 4：图算法（第 21–27 讲）
- Problem Set 5：算法设计范式与复杂性（第 28–34 讲）
工具书
怎么用这门课
如果你是在自学： 按讲次顺序读。Unit 1 看起来枯燥但不能跳——后面每一讲的复杂度论证都建立在它上面。每讲末尾有「随堂自测」，答不上来就回去重读那一节。
如果你在准备面试： 第 7、8、10、11、14、20、21、29、30 讲覆盖了绝大多数题目。但真正拉开差距的是第 4 讲（摊还分析）和第 30 讲（交换论证）——它们决定你能不能证明自己的解法是对的。
如果你只想搞懂某个具体结构： 用术语表反查，用复杂度速查表对比选型。
本课程内容基于公开教材与公开课程材料整理，用于学习与普及。课程编号为教学设计示例，不对应任何真实院校的具体开课记录。