数据结构与算法(C 语言)

这门课的讲义坚持一件事:每个结论都尽量配一次真实测量。链表理论上是插入王,实测输给数组百倍(第 2 章),原因在缓存行;快排平均最快,不随机化在有序数据上当场退化(第 8 章);哈希表平均 O(1),装载因子 0.9 时照样悬崖(第 7 章)。算法课最怕学成背诵,而它明明是个实验学科,每章末尾的动手题都是可以真跑的。

全部用 C 实现,和 C 指针课程共用一套内存语言,第 12 章把全课的抽象拉回内存字节层面收账:

• 第 1 章 · 复杂度分析——用真实跑分建立大 O 的直觉,摊还分析
• 第 2 章 · 线性表——顺序表 vs 链表的实测对决、快慢指针
• 第 3 章 · 栈与队列——循环队列、括号匹配、表达式求值
• 第 4 章 · 串与数组——KMP 的「不回退」思想、矩阵压缩
• 第 5 章 · 树与二叉树——四种遍历、BST、AVL 旋转、堆
• 第 6 章 · 图——存图选型、DFS/BFS、最小生成树、最短路
• 第 7 章 · 查找——二分的边界艺术、哈希表、装载因子悬崖
• 第 8 章 · 排序——比较排序的下限、快归堆三方对峙、稳定性
• 第 9 章 · 递归与分治——栈帧成本、递推式、Karatsuba
• 第 10 章 · 动态规划与贪心——背包的倒序之谜、LCS 填表、贪心要证明
• 第 11 章 · 高级结构——并查集、跳表、Trie、B+ 树
• 第 12 章 · 内存视角——指针税与缓存行,全课收账

先修:会 C 的基本语法;指针细节随用随查 C 指针课程。教材配合:OI Wiki(算法竞赛视角)、VisuAlgo(动画演示, AVL 旋转和图算法强烈建议拖一遍)。