|
|
本書為Goodrich與Tamassia累積多年經驗，根據JAVA5.0程式語言之需求，所撰寫關於資料結構與演算法之書籍。內容架構完整，鉅細 靡遺。並透過書中的圖片及教學網站的解說使讀者清楚了解資料結構與演算法的觀念。並附有精選習題，課後立即複習，加強實力。
本書特色
1.本書為Goodrich與Tamassia累積多年經驗，根據JAVA5.0程式語言之需求，所撰寫關於資料結構與演算法之書籍。
2.書中程式碼與例題均能將JAVA5.0版本之特色呈現出來。
3.透過書中的圖片及教學網站上的動畫清晰的解說資料結構與演算法的觀念。
4.藉由數百個精選的習題，以增強讀者暸解概念。
5.新增符合目前科技發展的專題研究題目。
第1章 基本Java程式設計
1.1 入門：類別、型別與物件
1.1.1 基本型別
1.1.2 物件
1.1.3 列舉 (Enum) 型別
1.2 方法
1.3 運算式
1.3.1 字面常數
1.3.2 運算子
1.3.3 運算式中的「轉型」與「自動裝箱／拆箱」
1.4 控制流
1.4.1 If及Switch述句
1.4.2 迴圈
1.4.3 顯式控制流述句
1.5 陣列
1.5.1 陣列的宣告
1.5.2 陣列物件
1.6 簡單輸入與輸出
1.7 範例程式
1.8 巢狀類別與套件
1.9 Java程式的撰寫
1.9.1 設計
1.9.2 虛擬碼
1.9.3 撰寫程式碼
1.9.4 測試及除錯
1.10 習題
第2章 物件導向設計
2.1 目標、法則與設計模式
2.1.1 物件導向設計的目標
2.1.1 物件導向設計法則
2.1.3 設計模式
2.2 繼承與多型
2.2.1 繼承
2.2.2 多型
2.2.3 使用Java繼承
2.3 例外
2.3.1 丟出例外
2.3.2 「接住」例外
2.4 介面及抽象類別
2.4.1 實作介面
2.4.2 介面中的多重繼承
2.4.3 抽象類別與強型別
2.5 轉型與泛型
2.5.1 轉型
2.5.2 泛型
2.6 習題
第3章 陣列、連結串鏈及遞迴
3.1 陣列的使用
3.1.1 在陣列存放遊戲條目
3.1.2 排序一個陣列
3.1.3 陣列和隨機數字的java.util方法
3.1.4 用字串和字元陣列的簡單密碼學
3.1.5 二維陣列和定位遊戲
3.2 單向連結串鏈
3.2.1 單向連結串鏈的插入
3.2.2 從一個單向連結串鏈移除元素
3.3 雙向連結串鏈
3.3.1 在雙向連結串鏈的中間作插入
3.3.2 在雙向連結串鏈的中間作移除
3.3.3 雙向連結串鏈的實作
3.4 循環連結串鏈和連結串鏈的排序
3.4.1 循環連結串鏈和抓鬼遊戲Duck, Duck, Goose
3.4.2 排序一個連結串鏈
3.5 遞迴
3.5.1 線性遞迴
3.5.2 二元遞迴
3.5.3 多元遞迴
3.6 習題
第4章 分析工具
4.1 在本書中用到的七個函數
4.1.1 常數函數
4.1.2 對數函數
4.1.3 線性函數
4.1.4 N-log-N函數
4.1.5 二次方函數
4.1.6 三次方函數及其它多項式
4.1.7 指數函數
4.1.8 比較成長率
4.2 演算法分析
4.2.1 實驗分析
4.2.2 原生指令
4.2.3 漸近符號
4.2.4 漸近分析
4.2.5 使用Big-Oh標記法
4.2.6 計算冪次的遞迴演算法
4.3 簡單的驗證技巧
4.3.1 實例證明
4.3.2 反向證明法
4.3.3 歸納法及迴圈不變量
4.4 習題
第5章 堆疊與佇列
5.1 堆疊
5.1.1 堆疊抽象資料型態
5.1.2 利用陣列完成的簡單堆疊實作
5.1.3 利用泛型連結串鏈完成的堆疊實作
5.1.4 用堆疊反轉一個陣列
5.1.5 括號及HTML標籤配對
5.2 佇列
5.2.1 佇列抽象資料型態
5.2.2 利用陣列完成的簡單佇列實作
5.2.3 使用泛型連結串鏈實作佇列
5.2.4 循環排程器
5.3 雙端佇列
5.3.1 雙端佇列抽象資料型態
5.3.2 Deque的實作
5.4 習題
第6章 串列與迭代器
6.1 陣列串列
6.1.1 陣列串列的抽象資料型態
6.1.2 轉接器模式
6.1.3 以陣列為基礎的簡單實作
6.1.4 一個簡單的介面與java.util.ArrayList類別
6.1.5 利用可延伸陣列實作陣列串列
6.2 節點串列
6.2.1 以節點為基礎的運算
6.2.2 位置
6.2.3 節點串列抽象資料型態
6.2.4 雙向連結串鏈實作
6.3 迭代器
6.3.1 迭代器與可迭代的抽象資料型態
6.3.2 Java的For-Each迴圈
6.3.3 實作迭代器
6.3.4 Java的串列迭代器
6.4 List ADTs以及Collections框架
6.4.1 Java的Collections框架
6.4.2 java.util.LinkedList類別
6.4.3 序列
6.5 案例研究：移至前端試探法
6.5.1 使用排序串列以及巢狀類別
6.5.2 以「移至前端試探法」使用串列
6.5.3 Favorites List的可能應用
6.6 習題
第7章 樹
7.1 一般樹
7.1.1 樹的定義及特性
7.1.2 樹抽象資料型態
7.1.3 樹的實作
7.2 樹的走訪演算法
7.2.1 深度和高度
7.2.2 前序走訪
7.2.3 後序走訪
7.3 二元樹
7.3.1 二元樹ADT
7.3.2 Java的二元樹介面
7.3.3 二元樹的性質
7.3.4 二元樹的鏈結結構
7.3.5 二元樹的陣列串列表示法
7.3.6 二元樹的走訪
7.3.7 樣版方法模式
7.4 習題
第8章 優先權佇列
8.1 優先權佇列抽象資料結構
8.1.1 鍵、優先權與全體順序關係
8.1.2 項目與比較子
8.1.3 優先權佇列ADT
8.1.4 以優先權佇列排序
8.2 使用串列實作優先權佇列
8.2.1 利用未排序串列來實作
8.2.2 利用已排序串列來實作
8.2.3 選擇排序及插入排序
8.3 堆積
8.3.1 堆積資料結構
8.3.2 完整二元樹及其表示法
8.3.3 使用堆積實作優先權佇列
8.3.4 Java堆積實作
8.3.5 堆積排序
8.3.6 由下到上建構堆積
8.4 可轉接的優先權佇列
8.4.1 可轉接優先權佇列之方法
8.4.2 定位感知項目
8.4.3 實作可轉接優先權佇列
8.5 習題
第9章 映射與字典
9.1 映射的抽象資型態集合
9.1.1 以串列為基礎的簡單映射實作
9.2 雜湊表
9.2.1 水桶陣列
9.2.2 雜湊函數
9.2.3 雜湊碼
9.2.4 壓縮函數
9.2.5 衝突處理方案
9.2.6 Java雜湊表實作
9.2.7 負載因數與再雜湊
9.2.8 應用：計算文字的頻率
9.3 字典抽象資料型態
9.3.1 以串列為基礎的字典與稽核紀錄
9.3.2 雜湊表的字典實作
9.3.3 有序查詢表與二元搜尋
9.4 跳躍串列
9.4.1 跳躍串列中的搜尋與更新運算
9.4.2 跳躍串列的機率分析
9.5 字典的延伸及應用
9.5.1 支援定位感知的字典項目
9.5.2 有序字典ADT
9.5.3 航班資料庫與最大值集合
9.6 習題
第10章 搜尋樹
10.1 二元搜尋樹
10.1.1 搜尋
10.1.2 更新運算
10.1.3 Java實作
10.2 AVL樹
10.2.1 更新運算
10.2.2 Java實作
10.3 外張樹
10.3.1 外張
10.3.2 何時外張
10.3.3 外張的攤銷分析
10.4 (2.4) 樹
10.4.1 多元搜尋樹
10.4.2 (2,4) 的更新運算
10.5 紅黑樹
10.5.1 更新運算
10.5.2 Java實作
10.6 習題
第11章 排序、集合與選擇
11.1 合併排序
11.1.1 各個擊破
11.1.2 合併陣列與串列
11.1.3 合併排序的執行時間
11.1.4 合併排序的Java實作
11.1.5 合併排序與遞迴方程式
11.2 快速排序
11.2.1 隨機快速排序
11.2.2 原位的快速排序
11.3 一個排序的下限
11.4 桶子排序與基底排序
11.4.1 桶子排序
11.4.2 基底排序
11.5 排序演算法的比較
11.6 集合抽象資料型態與Union/Find結構
11.6.1 一個簡單的集合實作
11.6.2 尋找聯集運算的分割
11.6.3 以樹實作分割
11.7 選擇
11.7.1 修剪與搜尋
11.7.2 隨機快速選擇
11.7.3 分析隨機快速選擇
11.8 習題
第12章 文字處理
12.1 字串運算
12.1.1 Java的String類別
12.1.2 Java的StringBuffer類別
12.2 樣式比對演算法
12.2.1 暴力法
12.2.2 Boyer-Moore演算法
12.2.3 Knuth-Morris-Pratt演算法
12.3 Trie樹
12.3.1 標準Trie樹
12.3.2 壓縮Tries
12.3.3 字尾Tries
12.3.4 搜尋引擎
12.4 文字壓縮
12.4.1 霍夫曼編碼演算法
12.4.2 貪婪演算法
12.5 文字相似性測試
12.5.1 最長共同子序列問題
12.5.2 動態規劃
12.5.3 運用動態規劃至LCS問題上
12.6 習題
第13章 圖
13.1 圖的抽象資料型態
13.1.1 圖的ADT
13.2 圖的資料結構
13.2.1 邊串列結構
13.2.2 鄰接串列結構
13.2.3 鄰接矩陣結構
13.3 圖形走訪
13.3.1 深度優先搜尋
13.3.2 深度優先搜尋的實作
13.3.3 廣度優先搜尋
13.4 有向圖
13.4.1 走訪有向圖
13.4.2 遞移包
13.4.3 無迴路的有向圖
13.5 有權重的圖
13.6 最短路徑
13.6.1 Dijkstra演算法
13.7 最小生成樹
13.7.1 Kruskal演算法
13.7.2 Prim-Jarnik演算法
13.8 習題
第14章 記憶體
14.1 記憶體管理
14.1.1 Java虛擬機器的堆疊結構
14.1.2 在記憶體堆積中配置空間
14.1.3 資源回收
14.2 外部記憶體及快取
14.2.1 記憶體階層
14.2.2 快取策略
14.3 外部搜尋及B-tree
14.3.1 (, ) 樹
14.3.2 B樹
14.4 外部記憶體排序
14.4.1 多路合併
14.5 習題
附錄A 常用的數學定理
參考文獻
