數據結構與抽象(Java版)(第3版)

第1章 袋子
袋子
袋子的行為
袋子的規格說明
接口
ADT袋子的使用
像使用自動售貨機一樣使用ADT
Java類庫： 接口Set
第2章 使用數組實現袋子
使用固定大小的數組實現ADT袋子
一個類比
一組核心方法
核心方法的實現
核心方法的測試
更多方法的實現
刪除物品的方法
使用可變大小的數組實現ADT袋子
調整數組的大小
袋子的一種新的實現
使用數組實現ADT袋子的優缺點
第3章 使用鏈表實現袋子
鏈表
通過添加節點到表頭來創建鏈表
ADT袋子的鏈表實現
私有的類Node
類LinkedBag的概要
一些核心方法的定義
核心方法的測試
方法getFrequencyOf
方法contains
從鏈表中刪除物品
方法remove和clear
具有方法set和get的類Node
使用鏈表實現ADT袋子的優缺點
第4章 算法的效率
動機
算法效率的度量
基本操作次數的統計
ZUI好、 最壞和平均情況
大O表示法
程序結構的復雜度
效率的圖形化表示
ADT袋子不同實現的效率
基於數組的實現
基於鏈表的實現
兩種實現方法的比較
第5章 棧
ADT棧的規格說明
利用棧處理代數表達式
應用問題： 中綴代數表達式中括號平衡的
檢查
應用問題： 中綴表達式向后綴表達式的
轉換
應用問題： 后綴表達式的求值
應用問題： 中綴表達式的求值
程序棧
Java類庫： 類Stack
第6章 棧的實現
基於鏈表的實現
基於數組的實現
基於向量的實現
Java類庫： Vector類
使用向量實現ADT棧
第7章 遞歸
什麼是遞歸
跟蹤一個遞歸方法
有返回值的遞歸方法
遞歸地處理一個數組
遞歸地處理一個鏈表
遞歸方法的時間效率
countDown的時間效率
計算xn的時間效率
一個復雜問題的簡單解決方案
一個簡單問題的拙劣解決方案
尾遞歸
間接遞歸
使用棧代替遞歸
第8章 排序引論
組織Java對數組排序的方法
選擇排序
迭代選擇排序
遞歸選擇排序
選擇排序的效率
插入排序
迭代插入排序
遞歸插入排序
插入排序的效率
鏈表的插入排序
希爾排序
Java代碼
希爾排序的效率
算法比較
第9章 快速排序方法
歸並排序
數組的歸並
遞歸的歸並排序
歸並排序的效率
迭代的歸並排序
Java類庫中的歸並排序
快速排序
快速排序的效率
創建划分
快速排序的Java代碼
Java類庫中的快速排序
基數排序
基數排序的偽代碼
基數排序的效率
算法比較
第10章 隊列、 雙端隊列和優先隊列
ADT隊列
解決問題： 模擬排隊
解決問題： 計算出售股票時的資本
增益（一）
Java類庫： 接口Queue
ADT雙端隊列
解決問題： 計算出售股票時的資本
增益（二）
Java類庫： 接口Deque
Java類庫： ArrayDeque類
ADT優先隊列
解決問題： 跟蹤你的作業
Java類庫： 類PriorityQueue
第11章 隊列、 雙端隊列和優先隊列的
實現
基於鏈表隊列的實現
基於數組隊列的實現
循環數組
有一個未使用存儲單元的循環數組
基於向量隊列的實現
基於循環鏈表隊列的實現
由兩部分構成的循環鏈表
Java類庫： 類AbstractQueue
基於雙向鏈表雙端隊列的實現
實現優先隊列的可用方法
第12章 線性表
ADT線性表的規格說明
使用ADT線性表
Java類庫： List接口
Jave類庫： ArraryList類
第13章 用數組實現線性表
用數組實現ADT線性表
一個類比
Java實現
用數組實現ADT線性表的效率
用Vector實現ADT線性表
第14章 用鏈表實現線性表
操作鏈表節點
在多種位置加入節點
在多種位置刪除節點
私有方法getNodeAt
開始實現
數據域和構造函數
在列表結尾加入
在列表給定位置加入
方法isEmpty和toArray
測試核心方法
繼續實現
一個更好的實現
尾引用
用鏈表實現ADT列表的效率
Java類庫： 類LinkedList
第15章 迭代器
迭代器是什麼
Iterator接口
使用Iterator接口
獨立類迭代器
內部類迭代器
基於鏈表實現
基於數組實現
為什麼迭代器方法在它們自己的
類中
ListIterator接口
使用ListIterator接口
ListIterator接口基於數組的實現
內部類
Java類庫： Iterable接口
Iterable和for-each循環
修改版接口List
第16章 有序表
ADT有序表的規格說明
使用ADT有序表
鏈表實現
方法add
鏈表實現的效率
使用ADT線性表的實現
效率問題
第17章 繼承及線性表
使用繼承實現有序表
設計一個基類
創建一個抽象基類
有序表的一種高效實現
方法add
第18章 查找
問題引入
查找無序數組
無序數組的迭代式順序查找
無序數組的遞歸式順序查找
順序查找數組的效率
查找有序數組
有序數組的順序查找
有序數組的二分查找
Java類庫: 方法binarySearch
二分查找數組的效率
查找無序鏈表
無序鏈表的迭代式順序查找
無序鏈表的遞歸式順序查找
順序查找鏈表的效率
查找有序鏈表
有序鏈表的順序查找
二分查找有序鏈表
查找方法的選擇
第19章 詞典
ADT詞典規格說明
Java接口
迭代器
使用ADT詞典
問題解決： 電話號碼本
問題解決： 詞頻
問題解決： 詞的索引
Java類庫： Map接口
第20章 詞典的實現
基於數組的實現
一個無序數組詞典
一個有序數組詞典
基於向量的實例
鏈式實例
一個無序鏈式詞典
一個有序鏈式詞典
第21章 散列概述
散列是什麼
散列函數
計算散列碼
將散列碼壓縮成散列表的索引
處理沖突
用線性探測實現開放尋址
用二次探測實現開放尋址
用雙重散列實現開放尋址
開放尋址的潛在問題
鏈地址
第22章 用散列實現詞典
散列的效率
容載分析
開放尋址消耗分析
鏈地址消耗分析
再散列
不同沖突解決方案的對比
用散列實現詞典的實例
散列表中的條目
數據域和構造函數
getValue， remove和add方法
迭代器
Java類庫： HashMap類
Java類庫： HashSet類
第23章 樹
樹的概念
層次化的數據組織
樹的術語
樹的遍歷
遍歷二叉樹
一般樹的遍歷
樹的Java接口
樹的通用接口
二叉樹的接口
二叉樹的例子
表達式樹
決策樹
二叉查找樹
堆
一般樹的例子
語法分析樹
游戲樹
第24章 樹的實現
二叉樹的節點
節點的接口
二叉樹節點的實現
ADT二叉樹的實現
創建基本二叉樹
privateSetTree方法
訪問器與更改器方法
計算高度和節點數
遍歷
表達式樹的實現
一般樹
一般樹的節點
用二叉樹表示一般樹
第25章 二叉查找樹的實現
開始
二叉查找樹接口
重復的條目
開始類定義
查找和檢索
遍歷
添加條目
遞歸實現
迭代實現
刪除條目
刪除一個葉子節點的條目
刪除節點有一個孩子的條目
刪除節點有兩個孩子的條目
刪除為根的條目
遞歸實現
迭代實現
操作的效率
平衡的重要性
節點添加的順序
ADT詞典實現
第26章 堆的實現
再論ADT堆
用數組表示堆
插入條目
刪除根
創建堆
堆排序
第27章 平衡查找樹
AVL樹
單旋轉
雙旋轉
實現細節
2-3樹
查找2-3樹
添加條目至2-3樹
添加時分裂節點
2-4樹
添加條目至2-4樹
比較AVL， 2-3和2-4樹
紅黑樹
紅黑樹的性質
添加條目到紅黑樹
Java類庫： TreeMap類
B樹
第28章 圖
一些示例和術語
公路線路圖
航空線路圖
迷宮
樹
遍歷
廣度優先遍歷
深度優先遍歷
拓撲排序
路徑
尋找路徑
無權圖的最短路徑算法
加權圖中的最短路徑
ADT圖的Java接口
第29章 圖的實現
兩種實現的概述
鄰接矩陣
鄰接表
頂點和邊
類Vertex的規格說明
內部類Edge
實現Vertex類
ADT圖的實現
基本操作
圖算法在 線 部 分
第30章 可變的、 不可變的和可復制的對象（英文版本）
附錄A Java基礎
附錄B Java類
附錄C 從已有類創建新類
附錄D 類的設計
附錄E 異常處理
附錄F 文件輸入與輸出
附錄G 文檔與程序設計風格