外观
1.6 怎么学这门课,以及本书的组织
本节问题这些方法怎么学才学得会?
数据结构不是看会的。读懂一段链表代码和自己写出一个链表之间,隔着所有的坑:指针改错顺序、边界漏掉一个、内存忘了释放。这些坑只有亲手踩过才记得住。Andrej Karpathy——特斯拉前AI负责人、OpenAI创始成员——教神经网络时的做法是从零把一个最小的版本做出来,在做的过程中理解每一个部件为什么在那里。本书用同样的方式教数据结构。
具体到每一章:围绕一个真实任务展开,比如第2章的单行编辑器。每一节提出一个具体的问题,先分析、再引入需要的概念、然后动手解决、最后运行验证。每节结尾有三样东西:这一节你做出了什么,几道先预测再运行的变式题,以及下一节要解决的问题。读完一章,任务就做出来了,而途中引入的每一种结构、每一个概念,都是因为任务需要它。
逻辑结构 → 抽象数据类型 → 存储结构 → 算法
逻辑结构描述数据之间的关系,抽象数据类型在关系上加操作集,存储结构把ADT映射到内存,算法在存储结构上实现操作并用复杂度衡量。后面每一章都在回答同一个问题:某种逻辑关系上的某个抽象数据类型,用什么存储结构实现,效率如何。
本书的组织
| 章 | 任务 | 逻辑关系 | 抽象数据类型 | 存储结构 | 效率上的主要问题 |
|---|---|---|---|---|---|
| 2 线性表 | 单行编辑器 | 线性 | 线性表 | 数组、单链表、双向链表 | 插入删除与按位置存取的取舍;接口怎么影响效率 |
| 3 栈和队列 | 线性 | 栈、队列 | 数组、链表 | 限制操作集后两种存储都能做到O(1) | |
| 4 树 | 树形 | 树、二叉树 | 孩子指针、数组 | 层级关系的表示与遍历 | |
| 5 集合与查找 | 集合 | 集合、字典 | 有序数组→二叉搜索树→平衡树→散列表 | 查找从O(n)到O(log n)到O(1) | |
| 6 优先队列 | 集合 | 优先队列 | 堆 | 反复取最值的代价 | |
| 7 图 | 图 | 图 | 邻接矩阵、邻接表 | 遍历、最短路径、最小生成树 | |
| 8 排序 | 线性 | — | 数组为主 | 用前面的结构改进算法 |
第2、3章讲线性关系。线性表是最基本的ADT,两种存储方式的取舍在这里第一次完整呈现;栈和队列展示限制操作集之后实现可以变得多简单。第4章讲树形关系,除了表示层级数据,树更重要的用途是把查找加速。第5、6章回到集合关系:"判断元素在不在"这一个操作,实现方式从有序数组的二分查找到二叉搜索树、平衡树、散列表,效率从O(n)逐步压到O(log n)和O(1),这是全书最能体现"操作集决定存储选择"的部分;优先队列是集合关系上另一个操作集不同的ADT。第7章讲图,最一般的关系——多对多,线性关系和树形关系都是它的特例。第8章讲排序,不是新的关系,而是把前面学过的结构用起来。
全书读完,回头看1.1提出的问题——数据该怎么组织才高效——答案就是这张表:先弄清数据之间的关系,再根据需要的操作定义ADT,然后在顺序和链式两种基本手段中选择或组合出存储结构,最后用复杂度分析验证这个选择是否达到了目的。
现在开始第一个任务:做一个单行编辑器。
到这里你有了本书的学法、四层框架和全书路线图。下一步第2章,单行编辑器。