演演算法分析與設計

典型問題的Java應用示例分佈在不同的章節中。此外，書中以大量圖例說明演演算法的工作過程，使演演算法更加易於理解和掌握。

本書適合作為高等院校計算機專業本科生和研究生演演算法設計課程的教材，也可作為從事軟體開發和工程設計的專業人員的參考書。此外，演演算法愛好者和參加各種程序設計大賽的選手也可把本書作為參考用書。

Michael T.Goodrich，1987年從普度大學獲得計算機科學博士學位，目前是加州大學（歐文分校）信息和計算機科學學院計算機系教授。此前，他曾擔任約翰·霍普金斯大學計算機科學系的教授，同時擔任該校演演算法工程中心主任。Goodrich教授的主要研究方向是高性能演演算法設計、數據結構求解的大規模問題、網際網路、信息可視化和幾何計算等。

第一部分 基礎工具

第1章 演演算法分析

1.1演演算法的分析方法學

1.1.1偽代碼

1.1.2隨機存取機(RAM)模型

1.1.3統計基本操作的數量

1.1.4遞歸演演算法分析

1.2漸近符號

1.2.1大O符號

1.2.2與大“O”相關的漸近符號

1.2.3漸近表示的重要性

1.3數學概覽

1.3.1求和

1.3.2對數和指數

1.3.3簡單證明技術

1.3.4概率基礎

1.4演演算法分析案例研究

1.4.1二次時間前綴平均值演演算法

1.4.2線性時間前綴平均值演演算法

1.5平攤方法

1.5.1平攤技術

1.5.2擴展數組實現分析

1.6實驗

1.6.1實驗組織

1.6.2數據分析和可視化

1.7習題

基礎題

創新題

程序設計

1.8本章註記

第2章 基本數據結構

2.1棧和隊列

2.1.1棧

2.1.2隊列

2.2向量、表和序列

2.2.1向量

2.2.2表

2.2.3序列

2.3樹

2.3.1樹抽象數據類型

2.3.2樹的遍歷

2.3.3二叉樹

2.3.4表示樹的數據結構

2.4優先隊列和堆

2.4.1優先隊列抽象數據類型

2.4.2PQ排序、選擇排序和插入排序

2.4.3堆數據結構

2.4.4堆排序

2.5字典與散列表

2.5.1無序字典ADT

2.5.2散列表

2.5.3散列函數

2.5.4壓縮映射

2.5.5衝突處理模式

2.5.6通用散列

2.6Java示例：堆

2.7習題

基礎題

創新題

程序設計

2.8本章註記

第3章 查找樹和跳躍表

3.1有序字典和二叉查找樹

3.1.1有序表

3.1.2二叉查找樹

3.1.3二叉查找樹中的查找

3.1.4二叉查找樹中的插入

3.1.5二叉查找樹中的刪除

3.1.6二叉查找樹的性能

3.2AVL樹

3.2.1更新操作

3.2.2性能

3.3深度有界查找樹

3.3.1多路查找樹

3.3.2(2,4)樹

3.3.3紅黑樹

3.4伸展樹

3.4.1伸展

3.4.2伸展過程的平攤分析

3.5跳躍表

3.5.1查找

3.5.2更新操作

3.5.3跳躍表的概率分析

3.6Java示例：AVL樹和紅黑樹

3.6.1AVL樹的Java實現

3.6.2紅黑樹的Java實現

3.7習題

基礎題

創新題

程序設計

3.8本章註記

第4章　排序、集合和選擇

4.1歸併排序

4.1.1分治法

4.1.2歸併排序和遞歸方程

4.2集合抽象數據類型

4.2.1簡單的集合實現

4.2.2具有union-find操作的劃分

4.2.3基於樹的劃分實現

4.3快速排序

4.4基於比較的排序下界

4.5桶排序和基數排序

4.5.1桶排序

4.5.2基數排序

4.6比較排序演演算法

4.7選擇

4.7.1剪枝-查找法

4.7.2隨機化快速選擇

4.7.3隨機化快速選擇分析

4.8Java示例：原位快速排序

4.9習題

基礎題

創新題

程序設計

4.10本章註記

第5章 基本技術

5.1貪心法

5.1.1背包問題

5.1.2任務調度

5.2分治法

5.2.1分治遞歸方程

5.2.2整數相乘

5.2.3矩陣相乘

5.3動態規劃

5.3.1矩陣鏈乘

5.3.2一般技術

5.3.30-1背包問題

5.4習題

基礎題

創新題

程序設計

5.5本章註記

第二部分　圖演演算法

第6章　圖

6.1圖抽象數據類型

6.2圖的數據結構

6.2.1邊表結構

6.2.2鄰接表結構

6.2.3鄰接矩陣結構

6.3圖的遍歷

6.3.1深度優先查找

6.3.2雙連通分量

6.3.3廣度優先查找

6.4有向圖

6.4.1遍歷有向圖

6.4.2傳遞閉包

6.4.3DFS和垃圾收集

6.4.4有向無環圖

6.5Java示例：深度優先查找

6.5.1修飾模式

6.5.2DFS引擎

6.5.3模板方法設計模式

6.6習題

基礎題

創新題

程序設計

6.7本章註記

第7章 加權圖

7.1單源點最短路徑

7.1.1Dijkstra演演算法

7.1.2Bellman-Ford最短路徑演演算法

7.1.3有向無環圖中的最短路徑

7.2所有頂點對之間的最短路徑

7.2.1動態規劃最短路徑演演算法

7.2.2利用矩陣相乘計算最短路徑

7.3最小生成樹

7.3.1Kruskal演演算法

7.3.2Prim-Jarník演演算法

7.3.3Bar?vka演演算法

7.3.4MST演演算法比較

7.4Java示例：Dijkstra演演算法

7.5習題

基礎題

創新題

程序設計

7.6本章註記

第8章 網路流和匹配

8.1流和割

8.1.1流網路

8.1.2割

8.2最大流

8.2.1剩餘容量和增大路徑

8.2.2Ford-Fulkerson演演算法

8.2.3Ford-Fulkerson演演算法分析

8.2.4Edmonds-Karp演演算法

8.3最大二分匹配

8.4最小代價流

8.4.1增大迴路

8.4.2連續最短路徑

8.4.3修改權值

8.5Java示例：最小代價流

8.6習題

基礎題

創新題

程序設計

8.7本章註記

第三部分 網際網路演演算法

第9章 文本處理

9.1串和模式匹配演演算法

9.1.1串操作

9.1.2蠻力模式匹配

9.1.3Boyer-Moore演演算法

9.1.4Knuth-Morris-Pratt演演算法

9.2trie

9.2.1標準trie

9.2.2壓縮trie

9.2.3後綴trie

9.2.4搜索引擎

9.3文本壓縮

9.3.1赫夫曼編碼演演算法

9.3.2修正貪心法

9.4文本相似性測試

9.4.1最長公共子序列問題

9.4.2應用動態規劃求解LCS問題

9.5習題

基礎題

創新題

程序設計

9.6本章註記

第10章數論和密碼學

10.1與數有關的基本演演算法

10.1.1基本數論的一些事實

10.1.2歐幾里得GCD演演算法

10.1.3模運算

10.1.4模指數運算

10.1.5模乘法逆元

10.1.6素性測試

10.2密碼計算

10.2.1對稱加密模式

10.2.2公鑰密碼系統

10.2.3RSA密碼系統

10.2.4ElGamal密碼系統

10.3信息安全演演算法和協議

10.3.1單向散列函數

10.3.2時間戳和認證字典

10.3.3硬幣拋擲和比特承諾

10.3.4安全電子傳輸(SET)協議

10.3.5密鑰分發和交換

10.4快速傅里葉變換

10.4.1本原單位根

10.4.2離散傅里葉變換

10.4.3快速傅里葉變換演演算法

10.4.4大整數相乘

10.5Java示例：FFT

10.6習題

基礎題

創新題

程序設計

10.7本章註記

第11章 網路演演算法

11.1複雜性測度和模型

11.1.1網路協議棧

11.1.2消息傳遞模型

11.1.3網路演演算法的複雜性測度

11.2基本分散式演演算法

11.2.1環網上的領導人選舉

11.2.2樹網上的領導人選舉

11.2.3廣度優先查找

11.2.4最小生成樹

11.3廣播路由和單播路由

11.3.1廣播路由的洪泛演演算法

11.3.2單播路由的距離矢量演演算法

11.3.3單播路由的鏈路-狀態演演算法

11.4多播路由

11.4.1逆向路徑轉發

11.4.2中心樹

11.4.3Steiner樹

11.5習題

基礎題

創新題

程序設計

11.6本章註記

第四部分 其他主題

第12章 計算幾何

12.1範圍樹

12.1.1一維範圍查找

12.1.2二維範圍查找

12.2優先查找樹

..