# 資料結構：把不變式與操作成本講清楚 — 學習任務單 [學習指南](https://unireadinglist.com/zh-tw/guides/data-structures/) [課程主題: 資料結構](https://unireadinglist.com/zh-tw/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-tw/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-tw/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-tw/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-tw/editorial/)