Classic Data Structures in Java
暫譯: Java 中的經典資料結構

描述
本書由 Tim Budd 撰寫，探討資料結構，提供關於抽象資料型別 (ADT) 的堅實基礎，並在可能的情況下使用 Java 中的圖形元素。
前幾章提供了所有其他內容的基礎。這些章節定義了抽象資料型別 (ADT) 的基本概念，並描述了用於評估和分析資料結構的工具。本書接著詳細描述了兩個最重要的基本資料抽象：向量和鏈結串列，並解釋了一些這些基本概念的常見變體。
接下來的內容考慮了適用於值的添加順序對集合重要的問題的資料結構，然後考慮了二元樹在資料結構創建中的各種不同用法。最後幾章考慮了一系列更高級的資料結構。大多數是建立在早期抽象之上的適配器。哈希表首先作為實現簡單集合的技術引入，然後作為開發高效映射的工具。最後，考慮圖形資料型別。在這裡，有幾種常用的替代資料結構表示，這一章的重點更多在於有用演算法的開發和分析，而不是任何特定的資料結構。

適合的課程
Java 資料結構 / CS2。

特點
- 整體應用物件導向思維。
- 強調 ADT (介面) 與實作之間的明確區分。
- 鼓勵嚴謹的開發方法，提供開發程式正式證明的技術，並在文本中出現程式的證明。
- 提供工具以便輕鬆創建執行時間的視覺記錄，鼓勵探索和視覺化的方法，幫助觀察從程式碼中可能不明顯的執行方面。
- 突出重要的軟體模式，並從一開始就強調模式的使用。
- 使用圖形元素，選擇最小化不必要的細節並強調 Java 的重要教訓，以激發學生對材料的興趣。
- 在整本書中包含 側邊欄，讓讀者可以根據自己的選擇瀏覽額外資訊。
- 章節結尾 的材料旨在幫助學生理解剛剛呈現的內容，包括：章節摘要、關鍵術語詞彙表、眾多基本學習問題、一系列引人深思的練習和一系列程式設計專案。
- 附錄中提供 Java 語法概述，使本書適合沒有 Java 背景的讀者。
- 由 Tim Budd 撰寫，他是多本成功著作的作者，包括 C++ 中的經典資料結構、使用 STL 的 C++ 資料結構、物件導向程式設計導論 和 為 Java 程式設計師準備的 C++。

目錄
（所有章節結尾均包含「章節摘要」、「進一步資訊」、「學習問題」、「練習」和「程式設計專案」。）
1. 複雜性的管理。
複雜性的控制。
抽象、資訊隱藏和分層。
分割成部分。
封裝和可互換性。
介面和實作。
服務視圖。
重複和遞迴。
組合。
專業化層次。
多重視圖。
模式。
2. 抽象資料型別。
什麼是型別？
類別。
介面和多型性。
抽象資料型別。
基本 ADT。
集合。
背包。
集合。
排序、比較器和可比較。
堆疊、佇列和雙端佇列。
FindMin 和 FindNth。
索引集合和排序演算法。
映射。
矩陣。
3. 演算法。
演算法的特徵。
食譜作為演算法。
分析計算機演算法。
輸入的規範。
結果的描述。
指令精確度。
執行時間。
空間利用。
遞迴演算法。
4. 執行時間測量。
演算法分析和大 O 符號。
程式構造的執行時間。
常數時間。
簡單迴圈。
嵌套迴圈。
While 迴圈。
函數呼叫。
總結演算法執行時間。
快速演算法的重要性。
基準測試和實際執行時間。
5. 增加正確性的信心。
程式證明。
不變式。
分析迴圈。
斷言結果正確。
朝向目標的進展。
操作未命名的數量。
函數呼叫。
遞迴演算法。
程式測試。
6. 向量。
向量資料結構。
列舉。
應用—愚蠢的句子。
應用—記憶遊戲。
應用—外殼排序。
視覺向量。
7. 排序向量。
分而治之。
二元搜尋。
排序向量。
合併排序。
分割。
樞紐演算法。
尋找 第 n 個元素。
快速排序。
8. 鏈結串列。
鏈結串列的變體。
LISP 風格的串列。
LinkedList 抽象。
應用—小行星遊戲。
應用—無限精度整數。
9. 串列變體。
排序串列。
快速合併。
合併操作的執行時間。
自我組織串列。
跳躍串列。
10. 堆疊。
堆疊 ADT。
檢查平衡括號。
河內塔，重訪。
四功能計算器。
一個接龍程式。
堆疊抽象的實作。
11. 雙端佇列。
一個分形雪花。
深度優先和廣度優先搜尋。
一個實作：IndexedDeque。
12. 佇列。
佇列 ADT。
毛毛蟲遊戲。
一個糕點工廠模擬。
佇列抽象的實作。
基於向量的佇列。
環形緩衝佇列。
管道輸入/輸出流。
13. 樹。
二元樹。
向量實作。
動態記憶體實作。
應用—猜動物遊戲。
樹的遍歷。
後序樹遍歷。
前序樹遍歷。
中序樹遍歷。
層序樹遍歷。
歐拉巡迴。
一般樹的二元樹表示。
14. 二元搜尋樹。
平衡的重要性。
AVL 樹。
應用—樹排序。
15. 優先佇列。
優先佇列 ADT。
堆。
偏斜堆。
應用—離散事件驅動模擬。
模擬框架。
冰淇淋店模擬。
16. 哈希表。
哈希函數。
Java 標準庫中的哈希函數。
碰撞解決。
哈希表排序演算法。
計數排序。
基數排序。
開放地址哈希。
哈希表資料型別。
應用—撲克牌手牌排名。
17. 映射。
範例程式。
愚蠢句子生成，重訪。
地址資料庫。
一個索引。
一個實作。
搜尋問題和映射。
18. 集合。
將背包轉換為集合。
集合的聯集、交集和差集。
排序串列集合。
應用—拼字檢查器。
聯集-查找問題。
BitSet 抽象。
應用—質數篩。
19. 矩陣。
Java 矩陣。
應用—雨水遊戲。
二元矩陣。
應用—生命遊戲。
稀疏向量。
應用—(幾乎) 無限大的哈希表。
稀疏矩陣。
非整數鍵。
20. 圖形。
鄰接矩陣表示。
邊列表表示。
加權圖表示。
加權鄰接矩陣。
Floyd 演算法。
加權邊列表表示。
Dijkstra 演算法。
其他圖形問題。
拓撲排序。
深度優先搜尋生成樹。
問題—旅行推銷員。
附錄 A. Java 語法。
程式結構。
套件。
匯入聲明。
類別聲明。
介面聲明。
方法聲明。
建構子。
資料欄位聲明。
陳述句。
聲明陳述句。
指派陳述句。
程序呼叫。
If 陳述句。
Switch 陳述句。
While 陳述句。
For 陳述句。
Return 陳述句。
Throw 陳述句。
Try 陳述句。
表達式。
字面量。
變數。
資料欄位和方法存取。
運算子。
物件創建。
陣列。
檔案。
附錄 B. 匯入函式庫。