譯者序
前言
第一部分 基礎知識
第1章 引言 1
1.1 算法 1
1.2 典型問題—連通性 2
1.3 閤並－查找算法 5
1.4 展望 12
1.5 主題概述 13
第2章 算法分析的原理 15
2.1 實現和經驗分析 15
2.2 算法分析 17
2.3 函數的增長 19
2.4 大O符號 23
2.5 基本遞歸方程 27
2.6 算法分析示例 29
2.7 保證、預測及局限性 33
第二部分 數據結構
第3章 基本數據結構 37
3.1 構建組件 37
3.2 數組 44
3.3 鏈錶 49
3.4 鏈錶的基本處理操作 54
3.5 鏈錶的內存分配 60
3.6 字符串 63
3.7 復閤數據結構 66
第4章 抽象數據類型 74
4.1 抽象對象和對象集 76
4.2 下推棧ADT 78
4.3 棧ADT客戶示例 79
4.4 棧ADT的實現 84
4.5 創建一個新ADT 87
4.6 FIFO隊列和廣義隊列 90
4.7 復製和索引項 95
4.8 一級ADT 99
4.9 基於應用的ADT示例 106
4.10 展望 110
第5章 遞歸與樹 111
5.1 遞歸算法 111
5.2 分治法 116
5.3 動態規劃 127
5.4 樹 133
5.5 樹的數學性質 138
5.6 樹的遍曆 140
5.7 遞歸二叉樹算法 145
5.8 圖的遍曆 149
5.9 綜述 155
第三部分 排序
第6章 基本排序方法 157
6.1 遊戲規則 158
6.2 選擇排序 161
6.3 插入排序 162
6.4 冒泡排序 164
6.5 基本排序方法的性能特徵 166
6.6 希爾排序 171
6.7 對其他類型的數據進行排序 177
6.8 索引和指針排序 180
6.9 鏈錶排序 185
6.10 關鍵字索引統計 188
第7章 快速排序 191
7.1 基本算法 191
7.2 快速排序算法的性能特徵 195
7.3 棧大小 198
7.4 小的子文件 201
7.5 三者取中劃分.. 203
7.6 重復關鍵字 206
7.7 字符串和嚮量 209
7.8 選擇 210
第8章 歸並與歸並排序 213
8.1 兩路歸並 213
8.2 抽象原位歸並 215
8.3 自頂嚮下的歸並排序 216
8.4 基本算法的改進 219
8.5 自底嚮上的歸並排序 220
8.6 歸並排序的性能特徵 223
8.7 歸並排序的鏈錶實現 225
8.8 改進的遞歸過程 227
第9章 優先隊列和堆排序 229
9.1 基本操作的實現 231
9.2 堆數據結構 233
9.3 基於堆的算法 235
9.4 堆排序 240
9.5 優先隊列ADT 244
9.6 索引數據項的優先隊列 247
9.7 二項隊列 250
第10章 基數排序 258
10.1 位、字節和字 259
10.2 二進製快速排序 261
10.3 MSD基數排序 265
10.4 三路基數快速排序 271
10.5 LSD基數排序 274
10.6 基數排序的性能特徵 278
10.7 亞綫性時間排序 280
第11章 特殊用途的排序方法 284
11.1 Batcher奇偶歸並排序 284
11.2 排序網 289
11.3 外部排序 295
11.4 排序－歸並的實現 299
11.5 並行排序/歸並 303
第四部分 搜索
第12章 符號錶和二叉搜索樹 307
12.1 符號錶抽象數據類型 308
12.2 關鍵字索引搜索 311
12.3 順序搜索 313
12.4 二分搜索 318
12.5 二叉搜索樹 321
12.6 BST的性能特徵 327
12.7 符號錶的索引實現 329
12.8 在BST的根節點插入 332
12.9 其他ADT函數的BST實現 336
第13章 平衡樹 343
13.1 隨機化BST 345
13.2 伸展BST 350
13.3 自頂嚮下2-3-4樹 355
13.4 紅黑樹 360
13.5 跳躍錶 368
13.6 性能特徵 374
第14章 散列 377
14.1 散列函數 377
14.2 鏈地址法 385
14.3 綫性探測法 388
14.4 雙重散列錶 392
14.5 動態散列錶 396
14.6 綜述 399
第15章 基數搜索 402
15.1 數字搜索樹 402
15.2 綫索 406
15.3 帕氏綫索 413
15.4 多路綫索和TST 419
15.5 文本字符串索引算法 430
第16章 外部搜索 434
16.1 遊戲規則 435
16.2 索引順序訪問 436
16.3 B樹 438
16.4 可擴展散列 447
16.5 綜述 455
· · · · · · (收起)