資料結構：把不變式與操作成本講清楚
資料結構既規定行為，也在特定操作和成本模型下承諾效率。本路線分開介面、表示不變式與成本，用動態陣列說明一次昂貴操作如何與低序列平均成本並存。選一本主線，另兩本用於解決具體理解或實現障礙。
學習計畫與例題由 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版的計數、圖示和多語言示例構成直觀路線；數字賬本為原創。
這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。