# 数据结构：把不变式与操作成本讲清楚 — 学习任务单

[学习指南](https://unireadinglist.com/zh-cn/guides/data-structures/)

[课程专题: 数据结构](https://unireadinglist.com/zh-cn/subjects/computer-science/#course-data-structures)

来源确认日期: 2026-11-04

学习计划与例题由 University Reading List 编辑整理。

适合会循环、函数、数组和引用后的第二门计算机课程。Morin侧重数学分析，Goodrich要求阅读Java类与泛型，Wengrow先数步骤。以下均为虚构算法的精确计数，不是语言内置列表的实测。

## 选择你的起点

- [ ] 需要重视证明与分析的免费教材
  用Morin作者站的Java或伪代码版，先复习求和、对数与初等概率，把实现和界的论证对照读。

- [ ] 课程要求Java实现
  用Goodrich学习抽象数据类型、类与接口契约；核对教学API与作业实际接口的区别。

- [ ] 会写代码但不理解大O
  先用Wengrow数步骤和看图，再以Morin检验摊还论证；单次示例不是所有序列的证明。

## 三本书如何取舍

### Open Data Structures: An Introduction（开放数据结构导论）

Pat Morin · 2013
免费数据结构教材，侧重算法分析

什么情况下适合读: 能读循环和求和，想把表示方式连接到复杂度。
什么情况下选别本: 还需要第一门编程课，或分不清索引与存储值。
建议阅读范围: 作者Java／伪代码版先读数组列表，再读链表、选读散列表；2013纸版目录分别为2、3、5章。
局限与取舍: 作者在线正文与代码采用署名许可；AU Press PDF另有非商业、禁止改作条款。许可随具体版本区分。

#### 选书前试做

写n≤容量，并数十二次追加复制了多少元素。
检查标准: 同时说明索引访问有效的原因及扩容为何改变单次成本。

你的笔记:

________________________________

ISBN: 9781927356388

[官方免费阅读](https://opendatastructures.org/)

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/open-data-structures/)

### Data Structures and Algorithms in Java（Java数据结构与算法）

Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser · 6 · 2014
Java实现主线

什么情况下适合读: 需要设计类、前置条件和抽象数据类型。
什么情况下选别本: 不愿先理解引用、异常与泛型。
建议阅读范围: 第6版2014纸书ISBN 9781118771334，按标题选数组／列表、栈／队列及算法分析。
局限与取舍: 配套代码不等于商业全书免费；后来电子产品有不同编号。

#### 选书前试做

给队列写API，再用循环数组追踪入队、出队和空队列。
检查标准: FIFO是可见行为，回绕是内部实现；能区分满与空而不丢元素。

你的笔记:

________________________________

ISBN: 9781118771334

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/data-structures-and-algorithms-in-java/)

### A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills（数据结构与算法常识指南）

Jay Wengrow · 2 · 2020
直观计数配套

什么情况下适合读: 已有基础编程，需要先用具体步骤理解记号。
什么情况下选别本: 希望用图示替代最坏或概率界的论证。
建议阅读范围: 2020第2版ISBN 9781680507225，读数据结构的重要性、大O、栈／队列与节点结构。
局限与取舍: JavaScript、Python、Ruby示例不保证其库操作等于手工模型；公开摘录和代码不等于免费全书。

#### 选书前试做

比较删除数组首元素与沿已知链表头引用操作。
检查标准: 分开搬移与改链接；没给节点引用时还须计定位成本。

你的笔记:

________________________________

ISBN: 9781680507225

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/common-sense-guide-data-structures-algorithms-wengrow/)

## 开始前需要会什么

### 不变式是什么？

你的笔记:

________________________________

### 摊还是什么意思？

你的笔记:

________________________________

### 本题数什么？

你的笔记:

________________________________

## 六步学习计划

- [ ] 规定接口

建议阅读范围: 所选列表或队列引言。

要做的练习: 写允许操作、空满状态及调用者可见结果。

检查标准: 接口不强制数组或链式表示。

你的笔记:

________________________________

- [ ] 画表示

建议阅读范围: Morin数组列表或Goodrich相应讨论。

要做的练习: 画扩容前后n、容量、有效槽与下一插入位置。

检查标准: 旧元素各出现一次且次序不变，新值接在最后。

你的笔记:

________________________________

- [ ] 数完整序列

建议阅读范围: Wengrow计数与Morin扩容论证。

要做的练习: 列十二行追加账本，逐行记容量、复制、累计写入。

检查标准: 单次最坏与序列总成本分别报告。

你的笔记:

________________________________

- [ ] 换增长规则

建议阅读范围: 同一数组讨论。

要做的练习: 把翻倍改容量加2，再做账本。

检查标准: 说明递增复制量的算术和为何改变总界。

你的笔记:

________________________________

- [ ] 检验缩容间隔

建议阅读范围: 数组扩缩容及下方变式。

要做的练习: 用两个精确阈值追踪四轮追加／弹出。

检查标准: 增长与缩容阈值拉开可防本题来回搬移，不代表永不复制。

你的笔记:

________________________________

- [ ] 给出选择理由

建议阅读范围: 列表与队列选读。

要做的练习: 为随机索引和首端删除负载各写建议，说明引用是否已知。

检查标准: 列负载、不变式、成本及未计开销，不能只报结构名称。

你的笔记:

________________________________

## 原创例题与解析: 原创扩容账本：平均便宜仍会突然变贵

空数组初始容量2，追加十二个元素；遇满才翻倍扩容。求元素写入次数与最终容量，再比较每次只加2的规则。

前提假设: 元素占0…n−1；扩容复制全部n个旧值，再写新值。初始容量不计成本，不计分配、读取、清零及删除清理，全程不删除。

你的笔记:

________________________________

## 改变假设，再做一题: 改变阈值：缩容可能反复抵消扩容

改从大小8、容量8开始，不计建造成本。做四轮先追加一个再弹出；满时翻倍。H规则弹出后若n≤容量/2便减半，Q改为n≤容量/4；最低容量2。只数追加和搬移写入。

你的笔记:

________________________________

## 进入下一阶段之前

- 能说明不变式并在操作后恢复它。
- 能复算两种追加账本和缩容轨迹。
- 能按负载选结构，不把数学计数当实测耗时。

## 答案与解释

### 不变式是什么？

例如0≤n≤容量，元素占据0…n−1，且每次合法操作前后都成立。它不是运行时间。

### 摊还是什么意思？

对整个操作序列的总成本给界，再分摊到操作；并非每次都快，也不要求随机输入。

### 本题数什么？

每次写新元素或搬移旧元素记一次写入；不计分配、读取、清零、释放或删除槽清理。改变计数模型要重算。

### 原创扩容账本：平均便宜仍会突然变贵

1. 翻倍在第3、5、9次追加复制2、4、8个值，共14；加十二次新写入得26，最终大小12、容量16。
2. 第9次单独需要8次搬移加1次新写入，共9。平均26/12=13/6不能当每次操作的上界。
3. 每次加2则复制2+4+6+8+10=30，加十二次写入共42，最终大小与容量都是12。少留空间付出了更多复制。
4. 翻倍复制量构成几何和，加常量构成算术和，支持本模型中总搬移的线性与二次增长区别，不是墙钟测速。

翻倍26次写、容量16；加2共42次写、容量12。翻倍的第9次仍有9次写入尖峰。

检验结果: 列所有扩容事件。8→16时旧新数组暂时共分配24槽，峰值分配不等于最后空闲容量。

### 改变假设，再做一题: 改变阈值：缩容可能反复抵消扩容

1. H每轮追加复制8并扩为16，弹出剩8立即减为8再复制8。四轮复制64，加四次追加共68。
2. Q只在首次追加复制8；弹出后大小8、容量16，高于四分之一阈值4，不缩容。总共8+4=12次写入。
3. 两者最终大小8，H容量8、Q容量16。Q保留空间来避免本序列震荡，不计删除槽清理。

同样八个操作，H写68次，Q写12次；保留容量不同。

检验结果: 逐个列八次操作后的大小／容量，不能加入题设排除的初始建造或删除清理成本。

## 常见误区

### 混淆最坏与摊还

一次昂贵追加否定单次常数界，不否定常数摊还界。

### 漏算定位

已知节点后的改链接与找到节点是两项成本。

### 暗换成本模型

真实程序的分配、缓存与内存保留重要，但本题未提供其测量。

## 参考来源与版本

- [Morin: free online editions, source code and licence](https://opendatastructures.org/)
  作者免费版将实现与分析配读，仍要求基础编程和数学记号。

- [AU Press: selected 2013 print identity and contents](https://www.aupress.ca/books/120226-open-data-structures/)
  2013纸版目录与书号不等同在线迭代版及其许可。

- [Wiley: Java sixth edition and product formats](https://www.wiley.com/en-br/data-structures-and-algorithms-in-java-6th-edition-p-9781118771334)
  第6版纸书的Java与API侧重构成实现路线。

- [Pragmatic Bookshelf: second-edition contents and practice](https://pragprog.com/titles/jwdsal2/a-common-sense-guide-to-data-structures-and-algorithms-second-edition/)
  第2版的计数、图示和多语言示例构成直观路线；数字账本为原创。

这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。

[编辑与选书方法](https://unireadinglist.com/zh-cn/editorial/)