主题
第八章 数据结构比较与工程实践
1. 最后一章为什么不再讲新结构
如果学到最后还只是“又记住了几个结构名字”，那这门课其实没有学成。真正成熟的数据结构能力，表现为你能面对一个问题时快速判断：
- 数据关系是什么。
- 主操作是什么。
- 哪个结构最匹配。
- 复杂度和工程代价分别来自哪里。
因此，最后一章不再引入新名词，而是把前面七章拉回到统一框架下，做课程级整合。
2. 一张总表看主要结构
| 结构 | 核心优势 | 主要代价 | 典型场景 |
|---|---|---|---|
| 数组 / 切片 | 随机访问快，局部性好 | 中间插删代价高 | 顺序存储、批量扫描、堆底层 |
| 链表 | 局部改链灵活 | 随机访问慢，缓存差 | 频繁局部插删、节点稳定引用 |
| 栈 | O(1) 栈顶操作 | 只能访问一端 | 回溯、调用栈、表达式处理 |
| 队列 | O(1) 头尾操作 | 不适合中间访问 | 调度、缓冲、BFS |
| BST / 平衡树 | 有序查找与动态更新 | 实现复杂，维护旋转代价 | 有序集合、范围查询 |
| 堆 | 快速取最值 | 不适合任意键查找 | 优先队列、调度、Dijkstra |
| 哈希表 | 平均快速查找 | 不保序，冲突影响性能 | 集合、字典、去重 |
| 并查集 | 高效维护连通性 | 只适合特定问题 | 连通分量、集合归并 |
| 图邻接表 | 表达复杂连接关系 | 算法多样、实现复杂 | 路网、依赖、社交图 |
这张表最重要的意义不是方便背诵，而是帮你建立“每个结构都是为某类主操作服务”的意识。