2.1 抽象数据类型与操作契约
学习目标
学完这一节，你能：
- 解释什么是抽象数据类型
- 区分"接口"和"实现"
- 把一个真实任务改写成操作需求表
- 说明为什么数据结构选择必须依赖操作频率和规模
- 要求 agent 先分析操作契约，再生成代码
从"存学生名单"开始
假设老师说：
帮我写一个学生名单管理功能。
如果只听到"名单"，你可能会想到 Python 列表：
students = ["Alice", "Bob", "Chen"]但这还不是数据结构选择。真正的问题是：这个名单要支持什么操作？
不同场景答案完全不同：
| 场景 | 高频操作 | 可能的结构 |
|---|---|---|
| 按座位号查看第 k 个学生 | 随机访问 | 数组或 Python list |
| 按姓名判断是否在班里 | 成员查询 | set |
| 按学号找到学生信息 | 键值查询 | dict |
| 按报名顺序处理申请 | 先进先出 | 队列 |
| 支持撤销上一步修改 | 后进先出 | 栈 |
| 反复取最高分学生 | 取最大或最小 | 优先队列 |
同样叫"学生名单"，背后的操作契约不同，数据结构就不同。
抽象数据类型：先说能做什么
抽象数据类型，也叫 ADT，可以先理解成：
只规定一组数据支持哪些操作，以及这些操作应该有什么行为；暂时不规定底层怎么存。
例如，一个"集合"的抽象接口可以写成：
add(x)：加入元素 x
contains(x)：判断 x 是否存在
remove(x)：删除 x
size()：返回元素数量这个接口没有说底层一定要用数组、链表还是哈希表。它只规定调用者能做什么。
实现可以有很多种：
| 实现方式 | contains(x) | add(x) | 适合场景 |
|---|---|---|---|
| 无序列表 | Θ(n) | 末尾追加通常很快 | 数据很小，代码简单 |
| 有序列表 | Θ(log n) 查找位置，但插入要移动元素 | Θ(n) | 查找多、更新少 |
| 哈希表 | 期望 Θ(1) | 期望 Θ(1) | 大量查询、去重、映射 |
抽象接口让我们先讨论"问题需要什么能力"，实现让我们再讨论"怎样把能力做快"。
一个 ADT 要回答的四件事
专业地描述一个数据结构，不能只说"它很快"。至少要回答四件事：
| 维度 | 要回答的问题 | 例子 |
|---|---|---|
| 数据集合 | 它保存的对象是什么？ | 学生、课程、文章 id、任务 |
| 操作接口 | 外部能调用哪些操作？ | add、remove、contains、get |
| 操作语义 | 每个操作应该产生什么结果？ | 重复添加是否允许？不存在时返回什么？ |
| 成本模型 | 每个操作的时间和空间成本如何增长？ | contains 是 Θ(n) 还是期望 Θ(1) |
这四件事合起来，才是一个完整的"操作契约"。
例如，"收藏文章集合"可以写成：
数据：文章 id 的集合
add(article_id)：收藏文章；如果已收藏，不重复增加
remove(article_id)：取消收藏；如果不存在，可以静默忽略或报错，需要约定
contains(article_id)：判断是否已收藏
size()：返回收藏数量注意这里还没有选择 list、set 或数据库索引。先写契约，是为了防止实现反过来限制问题定义。
表示和不变量
数据结构除了接口，还要有表示。表示就是你在程序里实际保存了什么。
例如前面的收藏功能，如果只用一个集合：
favorite_ids = set()它能快速判断是否收藏，却不能直接按收藏时间展示。于是我们可能组合两个结构：
favorite_ids = set()
favorite_order = []一旦组合多个结构，就必须维护表示不变量：
favorite_ids 中的每个 id，都应该出现在 favorite_order 中。
favorite_order 中不能出现 favorite_ids 没有的 id。
favorite_order 中同一个 id 不能重复出现。不变量是数据结构正确性的骨架。代码的每次更新都必须保持它。
def add_favorite(article_id):
if article_id in favorite_ids:
return
favorite_ids.add(article_id)
favorite_order.append(article_id)
def remove_favorite(article_id):
if article_id not in favorite_ids:
return
favorite_ids.remove(article_id)
favorite_order.remove(article_id) # 这里是 Θ(n)，后面还要审查这段代码看起来维护了不变量，但 favorite_order.remove(article_id) 是线性查找和移动。对于收藏数量很小的应用可以接受；如果收藏很多、取消频繁，就要重新设计。
这就是专业教材必须反复强调的点：正确性不变量和复杂度成本要同时看。
接口和实现要分开想
很多 agent 生成代码时会直接跳到实现：
students = []但你应该先问：
这个结构需要支持哪些操作？
每种操作调用多少次？
哪种操作必须快？
是否需要保持顺序？
是否允许重复？
是否需要按优先级取出？这一步叫做操作建模。它比"用什么结构"更早。
例如"收藏文章"功能：
| 操作 | 频率 | 约束 |
|---|---|---|
| 收藏一篇文章 | 很高 | 不能重复收藏 |
| 判断某篇文章是否已收藏 | 很高 | 页面打开时要快速显示状态 |
| 按收藏时间倒序展示 | 中等 | 需要顺序 |
| 取消收藏 | 中等 | 要能快速删除 |
只用列表能做，但判断是否收藏会慢；只用集合能快速判断，但不能直接保存展示顺序。真实实现可能要组合：
favorite_ids = set()
favorite_order = []或者使用数据库索引。数据结构选择不是只能选一个名字，而是围绕操作契约组织数据。
操作需求表：从需求到结构的桥
实际工程里，数据结构选择通常从一张操作需求表开始。
| 操作 | 输入 | 输出 | 频率 | 目标复杂度 | 备注 |
|---|---|---|---|---|---|
enroll(student, course) | 学生、课程 | 是否成功 | 高 | 期望 Θ(1) | 不能重复报名 |
drop(student, course) | 学生、课程 | 是否成功 | 中 | 期望 Θ(1) | 不存在时如何处理 |
is_enrolled(student, course) | 学生、课程 | 布尔值 | 很高 | 期望 Θ(1) | 页面展示会频繁调用 |
list_students(course) | 课程 | 学生列表 | 中 | Θ(k) | k 是该课程人数 |
list_courses(student) | 学生 | 课程列表 | 中 | Θ(k) | k 是该学生课程数 |
从这张表可以自然推出一种组合结构：
courses_by_student = {} # student -> set(course)
students_by_course = {} # course -> set(student)这不是为了炫技，而是因为两个方向都要查。如果只保存一个方向，另一个方向就会变慢。
同时，这个组合结构也带来新的不变量：
如果 course 在 courses_by_student[student] 中，
那么 student 必须在 students_by_course[course] 中。Agent 很容易只写出一个字典，漏掉另一个方向。你要能从操作需求表看出这个遗漏。
用本节知识解决：课堂互动系统的第一张卡
回到本章的贯穿案例。现在还不急着写代码，我们先写操作契约。
任务：在线课堂互动系统
数据：
- 学生
- 问题
- 问题状态：普通、紧急、已处理、已撤回
核心操作：
1. join(student_id)：学生加入课堂
2. ask(student_id, question_text)：学生提交问题
3. undo_last_question(student_id)：学生撤回自己最近一次问题
4. next_question()：老师取出下一个要处理的问题
5. mark_urgent(question_id)：把问题标为紧急
6. count_questions(student_id)：查询某学生提交了多少问题
7. export_questions()：按提交顺序导出记录先看这张契约，就能发现：单个列表不可能优雅地满足所有操作。
join需要判断学生是否已经在课堂里。count_questions需要按学生快速查计数。undo_last_question需要记住每个学生最近提交的问题。next_question既可能按提交顺序，也可能按紧急程度。export_questions需要保留完整顺序记录。
这一步的收获不是"答案是哪个结构"，而是把一个产品功能拆成了多个结构信号。
如果你现在让 agent 写代码，提示词不应该是：
帮我实现在线课堂互动系统。
而应该是：
请先根据以下操作契约，列出每个操作的高频程度、目标复杂度和候选数据结构。
暂时不要写实现代码。这就是操作契约的价值：它让 agent 先分析问题，而不是直接把需求压扁成一段看起来能跑的代码。
Python 里的接口感
Python 里常见结构可以先按接口理解：
| Python 结构 | 更像什么接口 | 常用操作 |
|---|---|---|
list | 动态数组 | 按下标访问、末尾追加、顺序遍历 |
collections.deque | 双端队列 | 头尾快速加入和移除 |
set | 集合 | 去重、判断是否存在 |
dict | 字典或符号表 | 按 key 找 value |
heapq + list | 优先队列 | 反复取最小优先级元素 |
注意这里说的是"更像"。Python 的实现有具体细节，但初学时先抓住接口和复杂度，比记住底层所有实现细节更重要。
让 agent 先做操作分析
不要这样问：
帮我写一个学生名单管理功能。
更好的问法是：
下面是一个功能需求。请先不要写代码。
任务：学生名单管理。
已知规模：最多 10 万名学生。
可能操作：
1. 按学号查询学生信息
2. 判断某个姓名是否存在
3. 按加入时间展示前 50 名
4. 更新学生信息
请输出：
1. 操作需求表
2. 每个操作的期望复杂度
3. 候选数据结构
4. 推荐方案和放弃其他方案的理由
5. 仍需澄清的问题这个提示词把 agent 拉回了数据结构选择的核心：操作、规模、约束、取舍。
审查 agent 输出
假设 agent 这样回答：
使用列表保存所有学生。查询时遍历列表即可。因为列表简单，所以是最好的结构。
你应该审查：
- "最好"是相对什么操作说的？
- 10 万名学生按学号查询时，遍历是否可接受？
- 如果查询远多于插入，是否应该按学号建立
dict？ - 如果还要保持加入顺序，是否需要额外结构？
- agent 是否说明了放弃其他结构的理由？
合理的改进可能是：
students_by_id = {}
join_order = []用 dict 支持按学号查询，用列表保存加入顺序。这个方案的代价是额外空间和维护一致性的责任。
本节要点
- 数据结构先是操作契约，再是具体实现。
- 不同操作需求会导向不同结构。
- 只说"保存一组数据"还不够，必须说清查找、插入、删除、遍历、取最值等操作。
- Python 的
list、dict、set、deque、heapq可以先按接口理解。 - 与 agent 协作时，先让它列操作表，再让它推荐结构和写代码。
课堂练习
把下面需求改写成操作需求表：
做一个课程报名系统。学生可以报名课程、退课、查看自己已报名课程，老师可以查看某门课的报名名单。
要求：
- 写出至少 4 个操作。
- 为每个操作估计频率：高、中、低。
- 写出每个操作希望达到的复杂度。
- 给出至少 2 种候选数据结构组合。
- 说明你会让 agent 帮你检查什么。
课后测验
📝 课后测验
上一节：第2章导入
下一节：2.2 数组与动态数组