数据结构：把不变式与操作成本讲清楚
数据结构既规定行为，也在特定操作和成本模型下承诺效率。本路线分开接口、表示不变式与成本，用动态数组说明一次昂贵操作如何与低序列平均成本并存。选一本主线，另两本用于解决具体理解或实现障碍。
学习计划与例题由 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≤容量，并数十二次追加复制了多少元素。
检查标准: 同时说明索引访问有效的原因及扩容为何改变单次成本。
Data Structures and Algorithms in Java（Java数据结构与算法）
Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser · 版次: 6 · 2014
Java实现主线
- 什么情况下适合读
- 需要设计类、前置条件和抽象数据类型。
- 什么情况下选别本
- 不愿先理解引用、异常与泛型。
- 建议阅读范围
- 第6版2014纸书ISBN 9781118771334，按标题选数组／列表、栈／队列及算法分析。
- 局限与取舍
- 配套代码不等于商业全书免费；后来电子产品有不同编号。
选书前试做
给队列写API，再用循环数组追踪入队、出队和空队列。
检查标准: FIFO是可见行为，回绕是内部实现；能区分满与空而不丢元素。
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示例不保证其库操作等于手工模型；公开摘录和代码不等于免费全书。
选书前试做
比较删除数组首元素与沿已知链表头引用操作。
检查标准: 分开搬移与改链接；没给节点引用时还须计定位成本。
开始前需要会什么
不变式是什么？
例如0≤n≤容量，元素占据0…n−1，且每次合法操作前后都成立。它不是运行时间。
摊还是什么意思？
对整个操作序列的总成本给界，再分摊到操作；并非每次都快，也不要求随机输入。
本题数什么？
每次写新元素或搬移旧元素记一次写入；不计分配、读取、清零、释放或删除槽清理。改变计数模型要重算。
六步学习计划
已完成步骤: 0 / 6
勾选用于自我记录，不是成绩评定；标记不会发送给本站。
-
规定接口
建议阅读范围: 所选列表或队列引言。
要做的练习: 写允许操作、空满状态及调用者可见结果。
检查标准: 接口不强制数组或链式表示。
-
画表示
建议阅读范围: Morin数组列表或Goodrich相应讨论。
要做的练习: 画扩容前后n、容量、有效槽与下一插入位置。
检查标准: 旧元素各出现一次且次序不变，新值接在最后。
-
数完整序列
建议阅读范围: Wengrow计数与Morin扩容论证。
要做的练习: 列十二行追加账本，逐行记容量、复制、累计写入。
检查标准: 单次最坏与序列总成本分别报告。
-
换增长规则
建议阅读范围: 同一数组讨论。
要做的练习: 把翻倍改容量加2，再做账本。
检查标准: 说明递增复制量的算术和为何改变总界。
-
检验缩容间隔
建议阅读范围: 数组扩缩容及下方变式。
要做的练习: 用两个精确阈值追踪四轮追加／弹出。
检查标准: 增长与缩容阈值拉开可防本题来回搬移，不代表永不复制。
-
给出选择理由
建议阅读范围: 列表与队列选读。
要做的练习: 为随机索引和首端删除负载各写建议，说明引用是否已知。
检查标准: 列负载、不变式、成本及未计开销，不能只报结构名称。
原创例题与解析
原创扩容账本：平均便宜仍会突然变贵
空数组初始容量2，追加十二个元素；遇满才翻倍扩容。求元素写入次数与最终容量，再比较每次只加2的规则。
前提假设
元素占0…n−1；扩容复制全部n个旧值，再写新值。初始容量不计成本，不计分配、读取、清零及删除清理，全程不删除。
- 翻倍在第3、5、9次追加复制2、4、8个值，共14；加十二次新写入得26，最终大小12、容量16。
- 第9次单独需要8次搬移加1次新写入，共9。平均26/12=13/6不能当每次操作的上界。
- 每次加2则复制2+4+6+8+10=30，加十二次写入共42，最终大小与容量都是12。少留空间付出了更多复制。
- 翻倍复制量构成几何和，加常量构成算术和，支持本模型中总搬移的线性与二次增长区别，不是墙钟测速。
答案与解释
翻倍26次写、容量16；加2共42次写、容量12。翻倍的第9次仍有9次写入尖峰。
检验结果
列所有扩容事件。8→16时旧新数组暂时共分配24槽，峰值分配不等于最后空闲容量。
改变假设，再做一题
改变阈值：缩容可能反复抵消扩容
改从大小8、容量8开始，不计建造成本。做四轮先追加一个再弹出；满时翻倍。H规则弹出后若n≤容量/2便减半，Q改为n≤容量/4；最低容量2。只数追加和搬移写入。
- H每轮追加复制8并扩为16，弹出剩8立即减为8再复制8。四轮复制64，加四次追加共68。
- Q只在首次追加复制8；弹出后大小8、容量16，高于四分之一阈值4，不缩容。总共8+4=12次写入。
- 两者最终大小8，H容量8、Q容量16。Q保留空间来避免本序列震荡，不计删除槽清理。
答案与解释
同样八个操作，H写68次，Q写12次；保留容量不同。
检验结果
逐个列八次操作后的大小／容量，不能加入题设排除的初始建造或删除清理成本。
常见误区
混淆最坏与摊还
一次昂贵追加否定单次常数界，不否定常数摊还界。
漏算定位
已知节点后的改链接与找到节点是两项成本。
暗换成本模型
真实程序的分配、缓存与内存保留重要，但本题未提供其测量。
进入下一阶段之前
- 能说明不变式并在操作后恢复它。
- 能复算两种追加账本和缩容轨迹。
- 能按负载选结构，不把数学计数当实测耗时。
参考来源与版本
来源确认日期:
- Morin: free online editions, source code and licence
作者免费版将实现与分析配读，仍要求基础编程和数学记号。
- AU Press: selected 2013 print identity and contents
2013纸版目录与书号不等同在线迭代版及其许可。
- Wiley: Java sixth edition and product formats
第6版纸书的Java与API侧重构成实现路线。
- Pragmatic Bookshelf: second-edition contents and practice
第2版的计数、图示和多语言示例构成直观路线；数字账本为原创。
这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。