第1章 引論. 1
1.1 本書討論的內容
1.2 數學知識復習
1.2.1 指數 2
1.2.2 對數 2
1.2.3 級數 3
1.2.4 模運算 4
1.2.5 證明方法 4
1.3 遞歸的簡單介紹 6
1.4 C++類
1.4.1 基本class語法 9
1.4.2 特別的構造函數語法與訪問函數 10
1.4.3 接口與實現的分離 11
1.4.4 vector和string
1.5 C++細節(jié)
1.5.1 指針 14
1.5.2 參數傳遞 15
1.5.3 返回值傳遞 16
1.5.4 引用變量 16
1.5.5 三大函數：析構函數. 復制構造函數和operator= 17
1.5.6 C風格的數組和字符串
1.6 模板
1.6.1 函數模板
1.6.2 類模板 22
1.6.3 Object. Comparable和例子
1.6.4 函數對象
1.6.5 類模板的分離編譯
1.7 使用矩陣
1.7.1 數據成員. 構造函數和基本訪問函數 27
1.7.2 operator[] 28
1.7.3 析構函數. 復制賦值和復制構造函數 29
小結 29
練習 29
參考文獻 30
第2章 算法分析 32
2.1 數學基礎 32
2.2 模型 34
2.3 要分析的問題 34
2.4 運行時間計算 36
2.4.1 一個簡單的例子 37
2.4.2 一般法則 37
2.4.3 最大子序列和問題的解 39
2.4.4 運行時間中的對數 44
2.4.5 檢驗你的分析 46
2.4.6 分析結果的準確性 47
小結 48
練習 48
參考文獻 52
第3章 表. 棧和隊列 53
3.1 抽象數據類型（ADT） 53
3.2 表ADT 53
3.2.1 表的簡單數組實現 54
3.2.2 簡單鏈表 54
3.3 STL中的向量和表 55
3.3.1 迭代器 56
3.3.2 示例：對表使用erase 57
3.3.3 const_iterator 58
3.4 向量的實現 59
3.5 表的實現 63
3.6 棧ADT 71
3.6.1 棧模型 71
3.6.2 棧的實現 72
3.6.3 應用 72
3.7 隊列ADT 78
3.7.1 隊列模型 78
3.7.2 隊列的數組實現 78
3.7.3 隊列的應用 80
小結 81
練習 81
第4章 樹 85
4.1 預備知識 85
4.1.1 樹的實現 86
4.1.2 樹的遍歷及應用 87
4.2 二叉樹 90
4.2.1 實現 90
4.2.2 一個例子——表達式樹 91
4.3 查找樹ADT——二叉查找樹 93
4.3.1 contains 94
4.3.2 findMin和findMax 96
4.3.3 insert 97
4.3.4 remove 98
4.3.5 析構函數和復制賦值操作符 99
4.3.6 平均情況分析 99
4.4 AVL樹 102
4.4.1 單旋轉 104
4.4.2 雙旋轉 106
4.5 伸展樹 111
4.5.1 一個簡單的想法（不能直接使用） 112
4.5.2 伸展 113
4.6 樹的遍歷 118
4.7 B樹 119
4.8 標準庫中的set和map 123
4.8.1 set 123
4.8.2 map 124
4.8.3 set和map的實現 125
4.8.4 使用幾個map的例子 126
小結 130
練習 130
參考文獻 135
第5章 散列 137
5.1 基本思想 137
5.2 散列函數 137
5.3 分離鏈接法 139
5.4 不使用鏈表的散列表 142
5.4.1 線性探測 142
5.4.2 平方探測 144
5.4.3 雙散列 148
5.5 再散列 148
5.6 標準庫中的散列表 150
5.7 可擴散列 151
小結 153
練習 154
參考文獻 156
第6章 優(yōu)先隊列（堆） 158
6.1 模型 158
6.2 一些簡單的實現 159
6.3 二叉堆 159
6.3.1 結構性質 159
6.3.2 堆序性質 160
6.3.3 基本的堆操作 161
6.3.4 堆的其他操作 164
6.4 優(yōu)先隊列的應用 167
6.4.1 選擇問題 167
6.4.2 事件模擬 168
6.5 d堆 169
6.6 左式堆 170
6.6.1 左式堆性質.. 170
6.6.2 左式堆操作 171
6.7 斜堆 175
6.8 二項隊列 177
6.8.1 二項隊列結構 177
6.8.2 二項隊列操作 178
6.8.3 二項隊列的實現 180
6.9 標準庫中的優(yōu)先隊列 183
小結 185
練習 185
參考文獻 189
第7章 排序 191
7.1 預備知識 191
7.2 插入排序 192
7.2.1 算法 192
7.2.2 插入排序的STL實現 192
7.2.3 插入排序的分析 194
7.3 一些簡單排序算法的下界 194
7.4 謝爾排序 195
7.5 堆排序 198
7.6 歸并排序 200
7.7 快速排序 204
7.7.1 選取樞紐元 206
7.7.2 分割策略 206
7.7.3 小數組 208
7.7.4 實際的快速排序例程 208
7.7.5 快速排序的分析 209
7.7.6 選擇問題的線性期望時間算法 213
7.8 間接排序 213
7.8.1 vector＜Comparable*＞不運行 215
7.8.2 智能指針類 216
7.8.3 重載operator＜ 217
7.8.4 使用“*”解引用指針 217
7.8.5 重載類型轉換操作符 217
7.8.6 隨處可見的隱式類型轉換 217
7.8.7 雙向隱式類型轉換會導致歧義 218
7.8.8 指針減法是合法的 218
7.9 排序算法的一般下界 218
7.10 桶排序 220
7.11 外部排序 220
7.11.1 為什么需要新算法 220
7.11.2 外部排序模型 221
7.11.3 簡單算法 221
7.11.4 多路合并 222
7.11.5 多相合并 223
7.11.6 替換選擇 223
小結 224
練習 225
參考文獻 229
第8章 不相交集類 231
8.1 等價關系 231
8.2 動態(tài)等價性問題 231
8.3 基本數據結構 233
8.4 靈巧求并算法 235
8.5 路徑壓縮 237
8.6 按秩求并和路徑壓縮的最壞情形 239
8.7 一個應用 243
小結 245
練習 245
參考文獻 246
第9章 圖論算法 248
9.1 若干定義 248
9.2 拓撲排序 250
9.3 最短路徑算法 252
9.3.1 無權最短路徑 254
9.3.2 Dijkstra算法 257
9.3.3 具有負邊值的圖 262
9.3.4 無環(huán)圖 263
9.3.5 所有頂點對的最短路徑 265
9.3.6 最短路徑舉例 266
9.4 網絡流問題 267
9.5 最小生成樹 271
9.5.1 Prim算法 272
9.5.2 Kruskal算法 273
9.6 深度優(yōu)先搜索的應用 275
9.6.1 無向圖 276
9.6.2 雙連通性 276
9.6.3 歐拉回路 279
9.6.4 有向圖 282
9.6.5 查找強分支 283
9.7 NP完全性介紹 284
9.7.1 難與易 285
9.7.2 NP類 286
9.7.3 NP完全問題 286
小結 288
練習 288
參考文獻 293
第10章 算法設計技巧 296
10.1 貪心算法 296
10.1.1 一個簡單的調度問題 297
10.1.2 赫夫曼編碼 299
10.1.3 近似裝箱問題 303
10.2 分治算法 310
10.2.1 分治算法的運行時間 310
10.2.2 最近點問題 312
10.2.3 選擇問題 315
10.2.4 一些算術問題的理論改進 317
10.3 動態(tài)規(guī)劃 320
10.3.1 用表代替遞歸 320
10.3.2 矩陣乘法的順序安排 322
10.3.3 最優(yōu)二叉查找樹 325
10.3.4 所有點對最短路徑 327
10.4 隨機化算法 329
10.4.1 隨機數生成器 330
10.4.2 跳躍表 333
10.4.3 素性測試 335
10.5 回溯算法 337
10.5.1 公路收費點重建問題 337
10.5.2 博弈 341
小結 346
練習 346
參考文獻 351
第11章 攤還分析 355
11.1 一個無關的智力問題 355
11.2 二項隊列 356
11.3 斜堆 359
11.4 斐波那契堆 361
11.4.1 切除左式堆中的結點 362
11.4.2 二項隊列的懶惰合并 364
11.4.3 斐波那契堆操作 366
11.4.4 時間界的證明 367
11.5 伸展樹 368
小結 371
練習 371
參考文獻 372
第12章 高級數據結構及其實現 374
12.1 自頂向下伸展樹 374
12.2 紅黑樹 379
12.2.1 自底向上插入 380
12.2.2 自頂向下紅黑樹 381
12.2.3 自頂向下刪除 385
12.3 確定性跳躍表 387
12.4 AA樹 392
12.5 treap樹 396
12.6 k-d樹 399
12.7 配對堆 401
小結 405
練習 406
參考文獻 408
附錄 類模板的分離編譯 411
索引... 414
鄂公網安備 42010302001612號 