0.1 数据结构基本概念

§ 0.1.1 为什么要研究数据结构#

程序面对的往往不是一个孤立数值，而是一组相互关联的数据：通讯录中的记录有先后顺序，文件系统中的目录具有层次，城市与道路形成网络。若只决定“每个值用什么类型保存”，还没有回答以下问题：

• 关系怎样表达：谁在谁前面，谁属于谁，哪些对象彼此相连。

• 数据放在哪里：元素是否连续存放，关系由下标、指针还是映射函数表示。

• 操作如何完成：怎样查找、插入、删除、遍历或更新，并维持原有关系。

• 代价是否可接受：操作需要多少时间、额外空间和数据移动。

• 因此，数据结构不是某一段代码或某一种容器，而是数据元素、元素关系以及作用于这些元素的操作所形成的整体

  • 存储实现是这个整体落到计算机上的具体方式。

§ 0.1.2 从数据到数据对象#

一、基本术语#

这些术语描述的是观察粒度，而不是固定的物理大小：

• 在“学生表”问题中，一条学生记录是数据元素。
• 在“按字符匹配姓名”问题中，姓名又可以成为一个串，其中单个字符是元素。
• 是否继续细分，取决于当前操作需要观察到哪一层。

二、值、关键字与记录#

• 记录：由若干相关数据项组成的复合数据元素，例如 {学号, 姓名, 专业}。
• 关键字：能够参与识别或查找记录的数据项。
  • 主关键字能够在当前数据对象中唯一标识记录，例如唯一学号。
  • 次关键字可能对应多条记录，例如专业名称。
• 值域：某个数据项允许出现的值的集合，例如成绩位于 $[0,100]$。

这些概念会在 查找基本概念 和 散列表 中继续使用。

§ 0.1.3 数据结构的三个观察层次#

一、逻辑结构：元素之间是什么关系#

逻辑结构只描述元素及其关系，不规定它们在内存中的位置。常见关系可以概括为：

• 集合结构：元素同属一个集合，除此之外没有显式次序。
  • 例如并查集关注元素属于哪个不相交集合。
• 线性结构：除边界元素外，每个元素至多有一个直接前驱和一个直接后继。
  • 例如线性表、栈、队列和串。
• 树形结构：结点形成层次关系；除根外，每个结点有唯一直接前驱，可以有多个直接后继。
  • 例如二叉树、堆和目录树。
• 图结构：元素之间可以形成多对多的任意连接。
  • 例如道路网、依赖网和社交关系。

二、存储结构：逻辑关系怎样落到机器中#

存储结构也称物理结构，是数据元素及其关系在存储器中的表示。四类基本思想可以组合使用：

• 顺序存储：用一段连续地址保存元素，逻辑位置通常映射为数组下标。
  • 优势：能够依据下标直接计算地址，缓存局部性通常较好。
  • 代价：需要连续空间；中间插入、删除通常伴随元素移动；静态容量可能不足或浪费。
• 链式存储：结点可以分散放置，用指针或引用显式保存关系。
  • 优势：不要求所有结点连续；已知修改位置时，局部链接调整不需要移动大量元素。
  • 代价：关系字段占额外空间；按位访问需要沿链接逐个前进；局部性通常较弱。
• 索引存储：在数据之外建立“关键字或逻辑位置 → 数据位置”的索引。
  • 优势：可以减少定位数据所需的访问次数，并支持多种查询顺序。
  • 代价：索引占空间，数据变化时必须同步维护。
• 散列存储：用散列函数把关键字映射到候选位置，再处理冲突。
  • 优势：在装填因子和冲突分布合适时，查找、插入和删除的期望时间可接近 $O(1)$。
  • 代价：最坏情况仍可能退化到 $O(n)$；通常不保留关键字的全序关系。

三、数据运算：结构允许做什么#

数据运算需要区分两个层次：

• 操作定义回答“做什么”。
  • 例如在线性表的第 $i$ 个位置插入元素，或查找关键字等于 key 的记录。
  • 它描述输入、输出、前置条件和操作后的逻辑结果。
• 操作实现回答“怎样做”。
  • 顺序表插入需要移动数组元素。
  • 单链表插入需要找到前驱并修改链接。
  • 二者实现不同，但可以满足相同的线性表接口。

因此应把完整关系记成：

读图说明：

1. 从顶部的实际问题与 ADT 契约开始，先明确输入、输出、元素关系和允许的操作。
2. 中间三栏分别观察逻辑关系、机器表示和操作算法；它们是同一实现的三个视角，不是三套彼此独立的知识。
3. 三栏共同落到具体实现：例如同一个 List ADT 可以形成顺序表或链表。
4. 底部再分别验证正确性和效率。只满足逻辑结果却越界，或运行很快却破坏链接，都不能算正确实现。

§ 0.1.4 抽象数据类型 ADT#

一、ADT 解决什么问题#

抽象数据类型（Abstract Data Type，ADT）由以下两部分构成：

• 值的集合及其逻辑关系：例如栈是一段有次序的元素序列。

• 允许的操作及其语义：例如 Push、Pop、Top 和 IsEmpty。

• ADT 不规定内部必须使用数组还是链表。

  • 使用者依赖接口语义，实现者可以在不破坏接口契约的前提下更换存储方式。

以栈为例：

Stack<T>
数据：有限元素序列 (a1, a2, ..., an)，an 为栈顶
操作：
    Init()        创建空栈
    Push(x)       将 x 放到栈顶
    Pop()         删除并返回栈顶元素
    Top()         返回但不删除栈顶元素
    IsEmpty()     判断栈是否为空

这个描述规定了后进先出语义，却没有暴露 top 是数组下标还是结点指针。

二、数据类型、ADT、数据结构与算法#

§ 0.1.5 完整示例：同一个 List ADT 的两种实现#

假设 List ADT 保存序列 (A, B, C, D)，现在要在第 3 个逻辑位置插入 X。

下标       0   1   2   3
元素       A   B   C   D
逻辑位序   1   2   3   4

head -> A -> B -> C -> D -> NULL

这个例子说明：

• 两种实现保持了相同逻辑结果和 List ADT 契约。
• 顺序表的主要代价是移动后缀元素；链表的主要代价通常是定位前驱。
• “链表插入是 $O(1)$”必须附带“已经持有正确前驱结点”的条件。

§ 0.1.6 怎样选择数据结构#

选择不是找一个在所有维度都最优的结构，而是根据工作负载做权衡：

1. 关系形态：数据天然是线性、层次、集合还是网络关系。
2. 主要操作：随机访问、范围查询、按关键字查找、插入删除或优先级访问，哪个最频繁。
3. 规模与变化：元素数量是否已知，是否频繁扩缩，是否允许重新分配。
4. 顺序要求：是否必须维持插入顺序、关键字顺序或稳定性。
5. 资源环境：内存是否连续、缓存是否重要、数据是否位于磁盘或网络。
6. 最坏保证：能否接受偶发退化，还是需要严格的时间上界。

§ 0.1.7 常见误解与边界#

• 逻辑结构不会唯一决定存储结构。
  • 线性表可以用连续数组，也可以用链接结点实现。
• 复杂度属于“操作 + 表示 + 条件”，不只属于结构名称。
  • 链表已知前驱时插入可为 $O(1)$；按位寻找插入位置仍为 $O(n)$。
• 散列表不是所有输入下都为 $O(1)$。
  • 常数期望依赖散列函数、装填因子和冲突策略；最坏情况可以退化。
• 树的形状相同不代表操作语义相同。
  • 普通二叉树与二叉排序树可能恰好具有同一组指针，但后者还必须维护关键字次序。
• 数据结构不是“数组和链表的别名”。
  • 数组、链接、索引和映射是基本表示手段，实际结构会组合它们并附加不变量。

总结#

• 数据结构的完整实现由逻辑结构、存储表示和操作算法共同决定；数据、数据对象、数据元素与数据项的粒度取决于当前问题。
• 抽象数据类型规定取值范围、逻辑关系与操作契约，不绑定具体内存布局；同一个 ADT 可以有多种实现。
• 结构选择应从主要操作、规模、空间限制和失败路径出发；复杂度必须连同具体操作、存储表示与前置条件一起判断。

← 本章第一篇 | 00-数据结构 | 0.2 算法和算法评价 →