第1章 数据结构绪论

从数据、元素、数据项和数据对象建立精确术语，分离逻辑结构与物理结构，并以可替换的C线性表实现验证抽象数据类型契约。

从“把学生信息存进电脑”开始

“数据结构”不是先选数组还是链表，而是先回答三个问题：问题中哪些事实要被计算机表示；这些事实之间有什么关系；哪些操作必须高效且正确。若需求是按学号查学生，学生可以是数据元素，学号/姓名/成绩是数据项，全班是数据对象；若需求变成分析每门课的选课网络，课程与学生可能都成为图的顶点，原来的“字段”也可能升级为独立元素。

先预测：把学生按录入顺序存入数组，业务逻辑就一定是线性关系吗？把树结点放在连续数组中，树就变成线性结构了吗？答案都是否定的。内存布局与业务关系是两个观察层次。

只有附带type、domain、unit、encoding和missing policy后，才成为可验证输入。

数据结构起源：规模变化迫使表示与算法一起设计

早期程序常围绕数值计算展开，输入规模小，程序员可以把注意力集中在公式本身。信息系统、编译器、操作系统和网络应用出现后，计算对象变成大量记录、符号、层次和关系；同一批数据既要查询，又要插入、删除、排序和遍历。只选择正确公式已不够，必须同时设计数据的组织方式。这就是数据结构起源所揭示的问题：计算成本不仅由“做什么运算”决定，也由“数据以什么关系和表示等待运算”决定。

例如保存一百万个学生记录：若唯一需求是按固定序号批量扫描，连续数组能利用局部性；若记录频繁在中间增删且已有目标位置，链式结构避免移动长后缀；若主要按学号查找，单纯数组或链表都未必合适，排序索引、二叉搜索结构或散列表可能更符合操作分布。结构选择不是给数据贴标签，而是把业务频率、规模和资源限制翻译成可测成本。

这也解释了为什么本章必须同时学习“数据、数据元素、数据项、数据对象”“逻辑结构与物理结构”“数据类型与抽象数据类型”。第一组确定问题粒度，第二组分离关系与存储，第三组分离公开语义与内部实现。三层若混在一起，需求一变化就只能连接口、算法和存储一起推翻。

一个可审查的建模记录至少回答以下问题：

  1. Universe：所有候选数据来自哪里，哪些值合法，规模上限是多少。
  2. Element identity：两个元素何时是同一个，重复项允许还是合并。
  3. Relation：顺序、父子、邻接、权值或无额外关系中，哪一个是业务事实。
  4. Operations：读取、定位、插入、删除、遍历、合并的实际频率和延迟目标。
  5. Representation：连续、链式、索引或散列如何实现关系，谁拥有内存。
  6. Evidence：哪些不变量、契约测试和规模实验证明设计没有偷换语义。

假设“经常查找”却不记录是精确key查询、范围查询还是按插入顺序扫描，会选错结构；只写平均复杂度却不记录最坏输入、内存上限和缓存局部性，也无法解释线上表现。第2章会正式推导时间与空间复杂度，本章先固定分析对象：操作必须作用在一个定义清楚的ADT和输入模型上。

从现实对象到可执行模型的四次收缩

第一次收缩从现实世界选择数据：学生有无数属性，成绩系统只保存被授权且与目标有关的字段。第二次收缩定义元素与数据项：学号是identity还是可变属性，分数是否允许缺失。第三次收缩定义逻辑关系：成绩榜是有序序列，班级成员也可作为集合。第四次收缩选择物理表示：数组、链表、树或散列，并明确表示失败不会改变外部语义。

每次收缩都可能丢失信息，因此要把丢失写成契约。按总分排序后，原始录入次序是否还要保留；姓名规范化是否改变显示值；删除学生是物理删除还是保留审计记录；这些都不是某个容器自动回答的问题。好的数据结构设计让丢失与取舍可见，而不是让实现细节悄悄决定业务事实。

先做小规模oracle，再做大规模实验。对十个元素，可以用最直接的reference model验证结果；对百万元素，再测吞吐、峰值内存和尾延迟。若两个实现结果不同，先修语义；若语义一致但成本不同，才根据操作分布选择representation。这条顺序能避免用“跑得快”掩盖“不再做同一件事”。

数据、数据元素、数据项与数据对象

不是语言中的某个固定类型。一个元素可以由多个数据项组成，也可以只是一个整数。

仍需明确范围。例如“年龄是int”没有说明负数、未知值和上限；“距离是double”没有说明单位和无穷值。

可对应一张表、一个图的顶点集合或一次查询结果。对象边界决定谁负责验证、存储和释放。

#include <stdbool.h>
#include <stddef.h>
 
typedef struct {
    unsigned id;       /* identity: non-zero and unique in one class */
    char name[32];     /* UTF-8 bytes with explicit capacity policy */
    unsigned score;    /* domain: 0..100 */
} Student;
 
bool student_valid(const Student *student) {
    return student != NULL
        && student->id != 0
        && student->name[0] != '\0'
        && student->score <= 100;
}

这段struct只描述一个候选representation，不能独自证明“学生数据类型”正确。还要检查ID唯一、名字编码与截断、对象集合容量和修改规则。同时包含关系与操作，不等于一段字段声明。

逻辑结构：先描述关系

逻辑结构忽略具体地址，只讨论元素之间的抽象关系。集合结构只要求同属一个集合；线性结构形成有先后次序的一对一关系；树形结构表达层次性一对多关系；图状结构表达任意多对多关系。选择结构的依据是业务不变量，而不是某个API看起来方便。

决定操作语义。例如线性表的第i个元素有明确次序，而集合不承诺顺序。

物理结构：把关系映射到内存

物理结构也称存储结构，回答数据元素和关系如何落到存储介质。顺序存储把逻辑相邻元素放在地址相邻的单元中，借索引隐含关系；链式存储允许地址分散，用指针/索引显式连接。还可使用索引、散列等辅助表示。

决定局部性、分配、访问和更新成本，但不应改变公开ADT语义。

#include <stddef.h>
 
enum { LIST_CAPACITY = 64 };
 
typedef struct {
    Student items[LIST_CAPACITY];
    size_t length;
} SeqList;
 
typedef struct StudentNode {
    Student value;
    struct StudentNode *next;
} StudentNode;
 
typedef struct {
    StudentNode *head;
    size_t length;
} LinkList;

两种表示都可实现“有限学生序列”。顺序表的第i项可常数时间定位，但中间插入要移动后缀且受固定/扩容策略影响；链表定位第i项要逐结点走，但已持有前驱时链接更新为常数次。链表每个结点多一个指针且局部性更差，不能笼统称为“插入总是更快”。

数据类型与抽象数据类型

数据类型定义一组值及允许的操作。C的int包含某个实现范围的整数及算术/比较；自定义结构若只暴露字段，会让调用者绕开约束。抽象数据类型（ADT）进一步把“值的逻辑模型 + 操作集合”作为接口，隐藏具体表示。

既约束能表示什么，也约束允许怎样操作。使同一算法可在不同representation上保持语义。

一个线性表ADT至少声明：元素形成有限有序序列；size返回长度；get(i)只接受有效位置；insert(i,x)在位置前插入并保持其余相对顺序；erase(i)返回被删除元素；失败不得部分修改结构。Representation invariant则分别约束顺序表和链表内部状态。

typedef enum {
    LIST_OK,
    LIST_BAD_POSITION,
    LIST_FULL,
    LIST_NO_MEMORY
} ListStatus;
 
typedef struct List List;
 
size_t list_size(const List *list);
ListStatus list_get(const List *list, size_t index, Student *out);
ListStatus list_insert(List *list, size_t index, Student value);
ListStatus list_erase(List *list, size_t index, Student *removed);
bool list_invariant(const List *list);
 
/* Contract test sketch: implementation-independent. */
void assert_empty_insert(List *list, Student value) {
    assert(list_invariant(list));
    assert(list_size(list) == 0);
    assert(list_insert(list, 0, value) == LIST_OK);
    assert(list_size(list) == 1);
    assert(list_invariant(list));
}

接口用status区分位置错误、容量不足和分配失败；out只在成功时写入。契约测试不访问内部字段，才能替换表示。实现还需定义ownership：Student中的名字是内嵌字节、借用指针还是深复制；销毁List时谁释放元素资源。

从绪论到后续八章

第2章给出评价ADT实现的时间/空间工具；第3-5章分别研究线性表、受限线性结构和串；第6-7章扩展到树与图；第8章把不同结构用于查找；第9章比较排序算法。每章都重复同一方法：先写逻辑关系和操作，再选物理表示，最后用不变量、测试和复杂度证明选择。

本章回顾：先定语义，再定表示

  1. 数据、数据元素、数据项和数据对象的粒度由问题决定，必须附带domain、identity和边界。
  2. 数据结构组织元素与关系，同时服务一组操作；struct本身不构成完整设计。
  3. 集合、线性、树形、图状是逻辑结构；顺序、链式等是物理结构，两层可独立组合。
  4. 数据类型定义值与操作；ADT隐藏representation并公开前置条件、结果、错误和状态变化。
  5. SeqList与LinkList应通过同一契约测试，但它们的局部性、定位、更新和资源成本不同。

术语表

复习本章（2 题）

讨论

评论区加载中…