Skip to content
第1章

1.6 怎么学这门课,以及本书的组织 ​

本节问题
这些方法怎么学才学得会?

数据结构不是看会的。读懂一段链表代码和自己写出一个链表之间,隔着所有的坑:指针改错顺序、边界漏掉一个、内存忘了释放。这些坑只有亲手踩过才记得住。Andrej Karpathy——特斯拉前AI负责人、OpenAI创始成员——教神经网络时的做法是从零把一个最小的版本做出来,在做的过程中理解每一个部件为什么在那里。本书用同样的方式教数据结构。

具体到每一章:围绕一个真实任务展开,比如第2章的单行编辑器。每一节提出一个具体的问题,先分析、再引入需要的概念、然后动手解决、最后运行验证。每节结尾有三样东西:这一节你做出了什么,几道先预测再运行的变式题,以及下一节要解决的问题。读完一章,任务就做出来了,而途中引入的每一种结构、每一个概念,都是因为任务需要它。

四层框架。 1.1到1.5说的四步,就是全书的骨架:

逻辑结构 → 抽象数据类型 → 存储结构 → 算法

逻辑结构描述数据之间的关系,抽象数据类型在关系上加操作集,存储结构把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章,单行编辑器。
选中正文里的任意文字,就可以针对它发表评论