导论与抽象数据类型

p1（6 分钟）、p2（13 分钟）

数据结构是什么#

正式定义：数据结构是在计算机中存储和组织数据、以使数据得以有效利用的一种方式。

核心命题：数据如何存储、组织、整合，决定了软件效率。机器算力再强，结构不对就不高效。

结论：不同种类的数据需要不同种类的结构来组织。

这条主线全课反复回扣。

1
① 作为数学 / 逻辑模型  →  只看抽象视角、高层特性和操作，不关心实现
2
                          →  这就是「抽象数据类型 ADT」
3
② 作为实现            →  具体类型；同一种语言可以有多种方式实现同一个 ADT

一个类比：电视机。抽象视图是「可开可关、能接收卫星信号并播放音视频的电子设备」，不必操心内部电路怎么嵌、哪家公司生产。

正式定义：对数据和操作的定义，但不存在实现。

也就是说，ADT 里没有任何实现细节。

定义一个叫「列表」的东西：

1
能存给定数据类型的元素
2
能按位置读取元素
3
能修改特定位置的元素

高级语言里的数组，已经是对这类 ADT 的具体实现。

1
① 研究逻辑视图
2
② 研究能做哪些操作
3
③ 研究这些操作的代价（主要从时间方面考量）
4
—— 然后才是语言中的实现

数组完全满足：int A[n]，元素是 A[0]、A[1]…（下标从 0 开始）。

1
① 空列表时称「空列表」，大小为 0
2
② 可向列表任意位置插入元素
3
③ 可从已有列表移除元素
4
④ 可统计元素数量
5
⑤ 可在特定位置读取并修改元素
6
⑥ 创建时可指定数据类型（整数列表 / 字符串 / 浮点…）

做法：

1
声明一个非常大的数组（定一个最大尺寸）
2
另设一个变量 N 标记「数组中列表的末尾」

为什么 N 初值是 −1：因为可能的最低索引是 0，所以 N = −1 时列表在任何时候都为空。

每次插入/删除后 N 都要调整。

演示序列：插入 2 → 插入 4 → 在末尾插入 5；再调用移除函数传索引 0 移除元素 2。

数组必须事先定最大尺寸，而「不存在合适的最大规模」——列表可能一直增长直到耗尽数组空间。

应对：数组满 → 新建一个更大的数组，把旧数组所有元素复制过去，然后释放旧数组内存。

无法扩展同一个数组，只能新建 + 复制。

扩容策略：新数组大小 = 旧数组的 2 倍。

至于为什么这是最佳策略，这一节没有讲。所以这里不要自作主张补「因为均摊 O(1)」——那是后面的内容。

操作	复杂度	理由
按索引读/写	O(1)	数组元素在连续内存中，用「内存块起始地址 + 元素索引」就能算出地址并直接访问
特定位置插入	O(n)	最坏情况在首位插入，要把所有元素向右移，时间与列表长度成正比
删除一个元素	O(n)	所花时间与列表当前规模成正比
末尾添加	不是 O(1)	未满时 O(1)；已满时 O(n)（建新数组并复制全部元素）→ 最坏情况下仍是 O(n)

最后一行容易记错：很多人以为「末尾追加是 O(1)」，其实最坏情况是 O(n)。

三条代价：

1
① 中间插入/删除代价高昂
2
② 列表频繁增大缩小 → 一再创建新数组、反复复制元素
3
③ 很多时候数组中有很大一部分未被使用，那里的内存毫无用处
4
   → 内存效率不高

第 ③ 条是引出链表的动机。注意动机是内存效率，不是访问速度——这个链条在 p2 结尾 → p3 故事 → p4 对比三集里是连贯的。

引子：「我们有一种能很好地利用内存的数据结构，就是链表。」