算法與數據結構

本書共分12章，涵蓋了數據結構的數組與鏈表、散列表與關聯數組、排序與選擇、優先隊列、有序序列、圖的表示、圖的遍歷、最短路徑、最小生成樹與優化。第1章作為一個引子，作者以讀者熟悉的整數乘法為核心，介紹了大數乘法算法，以此激發讀者對算法的興趣。第2章介紹了本書算法所需的基礎知識--漸近表示法、術語、機器模型、高級偽代碼表、複雜度、平均情況分析、隨機算法、圖的基礎、複雜性類P和NP，同時還給出了本書的第一個綜合性示例--有序數組的二分查找。第3～11章是數據結構課程必須學習的內容，其與其他教科書的不同之處在於：作者獨具匠心的從問題域到解域的思考方法，這種學習思想是非常棒的。在第12章中，以揹包問題為主線，介紹了7種遺傳方法：黑盒求解器、貪婪算法、線性規劃、動態規劃、系統搜索、局部搜索和進化算法。 ^[1] 

第1章 開胃菜： 整數運算1

1.1 加法2

1.2 乘法： 學校方法2

1.3 結果檢查5

1.4 遞歸版的學校方法6

1.5 Karatsuba乘法7

1.6 算法工程9

1.7 程序10

1.8 引理1.5和定理1.7的證明13

1.9 實現提示14

1.9.1 C++14

1.9.2 Java14

1.10 歷史註釋與進一步的讀物15

第2章 概述16

2.1 漸近表示法16

2.2 機器模型19

2.2.1 外部存儲器20

2.2.2 並行處理21

2.3 偽代碼21

2.3.1 變量和基本數據類型21

2.3.2 語句23

2.3.3 過程與函數23

2.3.4 面向對象25

2.4 設計正確的算法和程序25

2.4.1 斷言和不變量26

2.4.2 循環不變量26

2.4.3 數據結構不變量27

2.4.4 驗證算法27

2.5 一個示例： 二分查找27

2.6 基本算法分析29

2.6.1 求和29

2.6.2 遞推30

2.6.3 全局參數33

2.7 平均情況分析33

2.7.1 遞增計數器33

2.7.2 從左到右的最大值34

2.7.3 線性搜索35

2.8 隨機算法36

2.8.1 形式模型37

2.8.2 Las Vegas和Monte Carlo算法38

2.9 圖39

2.9.1 第一個圖算法41

2.9.2 樹41

2.9.3 有序樹42

2.10 P與NP43

2.11 實現提示45

2.11.1 C++45

2.11.2 Java46

2.12 歷史註釋與進一步的讀物46

第3章 用數組與鏈表表示序列47

3.1 鏈表48

3.1.1 雙鏈表48

3.1.2 單鏈表51

3.2 無界數組52

3.2.1 無界數組的平攤分析： 全局參數53

3.2.2 無界數組的平攤分析： 局部參數55

3.2.3 二進制計數器的平攤分析55

3.3* 平攤分析56

3.3.1 平攤分析： 勢能方法或銀行賬户方法57

3.3.2 勢能方法的普遍性58

3.4 棧與隊列58

3.5 鏈表與數組60

3.6 實現提示61

3.6.1 C++61

3.6.2 Java62

3.7 歷史註釋與進一步的讀物62

第4章 散列表與關聯數組64

4.1 鏈接法散列66

4.2 通用散列67

4.3 線性探測散列71

4.4 鏈接法與線性探測法72

4.5 *完全散列73

4.6 實現提示75

4.6.1 C++76

4.6.2 Java76

4.7 歷史註釋與進一步的讀物76

第5章 排序與選擇78

5.1 簡單排序80

5.2 歸併排序--O(nlogn)的排序算法81

5.3 下界83

5.4 快速排序85

5.4.1 分析85

5.4.2 細化87

5.5 選擇89

5.6 打破下界91

5.7 外部排序93

5.7.1 多路歸併94

5.7.2 採樣排序94

5.8 實現提示96

5.8.1 C/C++97

5.8.2 Java97

5.9 歷史註釋與進一步的讀物97

第6章 優先級隊列99

6.1 二叉堆100

6.2 可尋址的優先級隊列104

6.2.1 配對堆104

6.2.2 斐波那契堆106

6.3 外部存儲器109

6.4 實現提示110

6.4.1 C++110

6.4.2 Java110

6.5 歷史註釋與進一步的讀物111

第7章 有序序列112

7.1 二叉搜索樹113

7.2 (a,b)-樹與紅黑樹115

7.3 更多的操作121

7.3.1 連接121

7.3.2 拆分122

7.4 更新操作的平攤分析123

7.5 增強搜索樹124

7.5.1 父指針125

7.5.2 子樹大小125

7.6 實現提示126

7.6.1 C++127

7.6.2 Java127

7.7 歷史註釋與進一步的讀物128

第8章 圖的表示130

8.1 無序的邊序列131

8.2 鄰接數組--靜態圖132

8.3 鄰接表--動態圖132

8.4 鄰接矩陣表示133

8.5 隱式表示134

8.6 實現提示134

8.6.1 C++135

8.6.2 Java135

8.7 歷史註釋與進一步的讀物135

第9章 圖的遍歷137

9.1 廣度優先搜索137

9.2 深度優先搜索139

9.2.1 DFS編號、完成時間和拓撲排序140

9.2.2 強連通分量142

9.3 實現提示147

9.3.1 C++147

9.3.2 Java148

9.4 歷史註釋與進一步的讀物148

第10章 最短路徑149

10.1 從基本概念到遺傳算法150

10.2 有向無環圖153

10.3 非負邊代價(Dijkstra算法)153

10.4 *Dijkstra算法的平均情況分析156

10.5 單調整數優先級隊列157

10.5.1 桶隊列157

10.5.2 *基數堆158

10.6 任意邊代價(Bellman-Ford算法)161

10.7 所有點對最短路徑和節點的勢162

10.8 最短路徑查詢163

10.8.1 目標定向搜索164

10.8.2 等級166

10.8.3 中轉節點路線166

10.9 實現提示167

10.9.1 C++167

10.9.2 Java167

10.10 歷史註釋與進一步的讀物168

第11章 最小生成樹169

11.1 割和環的性質170

11.2 Jarník-Prim算法171

11.3 Kruskal算法172

11.4 並-查數據結構173

11.5 *外部存儲器176

11.5.1 Semiexternal的Kruskal算法176

11.5.2 邊收縮176

11.5.3 Sibeyn算法176

11.6 應用程序178

11.6.1 Steiner樹問題178

11.6.2 旅行推銷員之旅179

11.7 實現提示180

11.7.1 C++180

11.7.2 Java180

11.8 歷史註釋與進一步的讀物180

第12章 遺傳方法優化182

12.1 線性規劃： 黑盒求解器183

12.1.1 整數線性規劃185

12.2 貪婪算法： 永不回頭186

12.3 動態規劃： 子問題的構建189

12.4 系統搜索： 有疑問，用蠻力192

12.4.1 求解整數線性規劃194

12.5 局部搜索： 全局思考，局部行動194

12.5.1 爬山195

12.5.2 模擬退火： 從自然中學習196

12.5.3 局部搜索的優化201

12.6 進化算法201

12.7 實現提示203

12.8 歷史註釋與進一步的讀物204

附錄A205

A.1 數學符號205

A.2 數學概念206

A.3 概率論基礎207

A.4 有用的公式210

A.4.1 證明211

參考文獻213 ^[2]