Skip to content
第1章

1.1 这门课解决什么问题,要学什么 ​

本节问题
数据结构这门课到底在研究什么?学完应该会什么?

数据结构这门课回答一个问题:程序里的数据该怎么组织,才能让管理和操作它更高效。

这个问题没有统一答案,因为数据不同、要做的事不同。一个单行编辑器里的字符排成一串,用户要在中间插入、删除;手机的拦截名单只需判断一个号码在不在;文件系统里的文件夹层层嵌套;地图上的路口四通八达。组织方式跟着数据的关系和要做的操作走:字符要排成序列,名单只要能快速查有没有,文件夹要能层层展开,路口要能找出一条路来。

所以这门课真正教的是一套分析方法,四步:

  1. 看数据之间是什么关系(1.2);
  2. 确定要对数据做哪些操作,关系加操作合起来叫抽象数据类型(1.3);
  3. 决定怎么放进内存(1.4);
  4. 用一把统一的尺子量效率,看这个选择对不对(1.5)。

每一种具体的结构——顺序表、链表、树、散列表——都是这套方法在某类问题上的答案。学会的是方法,具体的结构就不必背,遇到新问题也能自己推出来。

本书的取舍也由此而来。不把所有结构罗列一遍,每种结构只在一个真实问题需要它的时候出场;不把重点放在语言细节上,代码是把分析落地的工具;每一章围绕一个任务,读者要亲手把它做出来。第2章就从上面那个单行编辑器开始。

到这里你有了
这门课的问题和四步方法,后面四节逐一展开。
练一练
(1)想一个你每天用的软件(微信、日历、音乐播放器),它处理的数据是什么?你对这些数据做的最常见的三个操作是什么?(2)同样是"一堆联系人",通讯录和拦截名单要做的操作有什么不同?这会不会影响它们该怎么存?
选中正文里的任意文字,就可以针对它发表评论