齣版者的話
譯者序
前言
第一部分　預備知識
第1章　C++迴顧 2
1.1　引言 2
1.2　函數與參數 3
1.2.1　傳值參數 3
1.2.2　模闆函數 4
1.2.3　引用參數 4
1.2.4　常量引用參數 5
1.2.5　返迴值 5
1.2.6　重載函數 6
1.3　異常 7
1.3.1　拋齣異常 7
1.3.2　處理異常 7
1.4　動態存儲空間分配 9
1.4.1　操作符new 9
1.4.2　一維數組 9
1.4.3　異常處理 9
1.4.4　操作符delete 10
1.4.5　二維數組 10
1.5　自有數據類型 12
1.5.1　類currency 12
1.5.2　一種不同的描述方法 18
1.5.3　操作符重載 20
1.5.4　友元和保護性類成員 22
1.5.5　增加#ifndef、#define和#endif語句 23
1.6　異常類illegalParameterValue 24
1.7　遞歸函數 25
1.7.1　遞歸的數學函數 25
1.7.2　歸納 25
1.7.3　C++遞歸函數 26
1.8　標準模闆庫 30
1.9　測試與調試 32
1.9.1　什麼是測試 32
1.9.2　測試數據的設計 34
1.9.3　調試 36
1.10　參考及推薦讀物 37
第2章　程序性能分析 38
2.1　什麼是程序性能 38
2.2　空間復雜度 39
2.2.1　空間復雜度的組成 39
2.2.2　舉例 42
2.3　時間復雜度 44
2.3.1　時間復雜度的組成 44
2.3.2　操作計數 45
2.3.3　最好、最壞和平均操作計數 48
2.3.4　步數 53
第3章　漸近記法 64
3.1　引言 64
3.2　漸近記法 65
3.2.1　大Ο記法 65
3.2.2　漸近記法Ω和Θ 67
3.3　漸近數學（可選） 69
3.3.1　大O記法 69
3.3.2　Ω記法 71
3.3.3　Θ記法 72
3.3.4　小ο記法 73
3.3.5　特性 73
3.4　復雜度分析舉例 75
3.5　實際復雜度 78
3.6　參考及推薦讀物 80
第4章　性能測量 81
4.1　引言 81
4.2　選擇實例的大小 82
4.3　設計測試數據 82
4.4　實驗設計 82
4.5　高速緩存 87
4.5.1　簡單計算機模型 87
4.5.2　緩存未命中對運行時間的影響 87
4.5.3　矩陣乘法 88
4.6　參考及推薦讀物 90
第二部分　數據結構
第5章　綫性錶——數組描述 92
5.1　數據對象和數據結構 92
5.2　綫性錶數據結構 93
5.2.1　抽象數據類型linearList 94
5.2.2　抽象類linearList 94
5.3　數組描述 95
5.3.1　描述 95
5.3.2　變長一維數組 96
5.3.3　類arrayList 97
5.3.4　C++迭代器 102
5.3.5　arrayList的一個迭代器 103
5.4　vector的描述 107
5.5　在一個數組中實現的多重錶 109
5.6　性能測量 111
5.7　參考及推薦讀物 112
第6章　綫性錶——鏈式描述 113
6.1　單嚮鏈錶 113
6.1.1　描述 113
6.1.2　結構chainNode 114
6.1.3　類chain 115
6.1.4　抽象數據類型linearList的擴充 121
6.1.5　類extendedChain 121
6.1.6　性能測量 122
6.2　循環鏈錶和頭節點 126
6.3　雙嚮鏈錶 128
6.4　鏈錶用到的詞匯錶 129
6.5　應用 130
6.5.1　箱子排序 130
6.5.2　基數排序 134
6.5.3　凸包 135
6.5.4　並查集 137
第7章　數組和矩陣 146
7.1　數組 146
7.1.1　抽象數據類型 146
7.1.2　C++數組的索引 147
7.1.3　行主映射和列主映射 147
7.1.4　用數組的數組來描述 148
7.1.5　行主描述和列主描述 149
7.1.6　不規則二維數組 149
7.2　矩陣 151
7.2.1　定義和操作 151
7.2.2　類matrix 152
7.3　特殊矩陣 157
7.3.1　定義和應用 157
7.3.2　對角矩陣 158
7.3.3　三對角矩陣 159
7.3.4　三角矩陣 160
7.3.5　對稱矩陣 161
7.4　稀疏矩陣 164
7.4.1　基本概念 164
7.4.2　用單個綫性錶描述 165
7.4.3　用多個綫性錶描述 170
7.4.4　性能測量 172
第8章　棧 175
8.1　定義和應用 175
8.2　抽象數據類型 177
8.3　數組描述 178
8.3.1　作為一個派生類實現 178
8.3.2　類arrayStack 179
8.3.3　性能測量 181
8.4　鏈錶描述 182
8.4.1　類derivedLinkedStack 182
8.4.2　類linkedStack 183
8.4.3　性能測量 184
8.5　應用 184
8.5.1　括號匹配 184
8.5.2　漢諾塔 185
8.5.3　列車車廂重排 187
8.5.4　開關盒布綫 191
8.5.5　離綫等價類問題 193
8.5.6　迷宮老鼠 196
8.6　參考及推薦讀物 204
第9章　隊列 205
9.1　定義和應用 205
9.2　抽象數據類型 206
9.3　數組描述 207
9.3.1　描述 207
9.3.2　類arrayQueue 209
9.4　鏈錶描述 212
9.5　應用 214
9.5.1　列車車廂重排 214
9.5.2　電路布綫 217
9.5.3　圖元識彆 219
9.5.4　工廠仿真 222
9.6　參考及推薦讀物 234
第10章　跳錶和散列 235
10.1　字典 235
10.2　抽象數據類型 236
10.3　綫性錶描述 237
10.4　跳錶錶示（可選） 239
10.4.1　理想情況 239
10.4.2　插入和刪除 241
10.4.3　級的分配 241
10.4.4　結構skipNode 242
10.4.5　類skipList 242
10.4.6　skipList方法的復雜度 246
10.5　散列錶描述 246
10.5.1　理想散列 246
10.5.2　散列函數和散列錶 248
10.5.3　綫性探查 250
10.5.4　鏈式散列 255
10.6　一個應用——文本壓縮 260
10.6.1　LZW壓縮 260
10.6.2　LZW壓縮的實現 261
10.6.3　LZW解壓縮 264
10.6.4　LZW解壓縮的實現 265
10.6.5　性能評價 268
10.7　參考及推薦讀物 269
第11章　二叉樹和其他樹 270
11.1　樹 270
11.2　二叉樹 273
11.3　二叉樹的特性 274
11.4　二叉樹的描述 275
11.4.1　數組描述 275
11.4.2　鏈錶描述 276
11.5　二叉樹常用操作 277
11.6　二叉樹遍曆 277
11.7　抽象數據類型BinaryTree 281
11.8　類linkedBinaryTree 282
11.9　應用 285
11.9.1　設置信號放大器 285
11.9.2　並查集 288
11.10　參考及推薦讀物 296
第12章　優先級隊列 297
12.1　定義和應用 297
12.2　抽象數據類型 298
12.3　綫性錶 299
12.4　堆 299
12.4.1　定義 299
12.4.2　大根堆的插入 300
12.4.3　大根堆的刪除 301
12.4.4　大根堆的初始化 301
12.4.5　類maxHeap 302
12.4.6　堆和STL 305
12.5　左高樹 306
12.5.1　高度優先與寬度優先的最大及最小左高樹 306
12.5.2　最大HBLT的插入 308
12.5.3　最大HBLT的刪除 308
12.5.4　兩棵最大HBLT的閤並 308
12.5.5　初始化 309
12.5.6　類maxHblt 310
12.6　應用 313
12.6.1　堆排序 313
12.6.2　機器調度 314
12.6.3　霍夫曼編碼 317
12.7　參考及推薦讀物 322
第13章　競賽樹 323
13.1　贏者樹和應用 323
13.2　抽象數據類型WinnerTree 326
13.3　贏者樹的實現 327
13.3.1　錶示 327
13.3.2　贏者樹的初始化 328
13.3.3　重新組織比賽 328
13.3.4　類completeWinnerTree 328
13.4　輸者樹 329
13.5　應用 331
13.5.1　用最先適配法求解箱子裝載問題 331
13.5.2　用相鄰適配法求解箱子裝載問題 335
13.6　參考及推薦讀物 337
第14章　搜索樹 338
14.1　定義 338
14.1.1　二叉搜索樹 338
14.1.2　索引二叉搜索樹 340
14.2　抽象數據類型 340
14.3　二叉搜索樹的操作和實現 341
14.3.1　類binarySearchTree 341
14.3.2　搜索 342
14.3.3　插入 342
14.3.4　刪除 343
14.3.5　二叉搜索樹的高度 346
14.4　帶有相同關鍵字元素的二叉搜索樹 347
14.5　索引二叉搜索樹 348
14.6　應用 349
14.6.1　直方圖 349
14.6.2　箱子裝載問題的最優匹配法 351
14.6.3　交叉分布 353
第15章　平衡搜索樹 359
15.1　AVL樹 360
15.1.1　定義 360
15.1.2　AVL樹的高度 361
15.1.3　AVL樹的描述 361
15.1.4　AVL搜索樹的搜索 361
15.1.5　AVL搜索樹的插入 361
15.1.6　AVL搜索樹的刪除 364
15.2　紅-黑樹 367
15.2.1　基本概念 367
15.2.2　紅-黑樹的描述 368
15.2.3　紅-黑樹的搜索 368
15.2.4　紅-黑樹的插入 368
15.2.5　紅-黑樹的刪除 371
15.2.6　實現細節的考慮及復雜性分析 374
15.3　分裂樹 376
15.3.1　介紹 376
15.3.2　分裂樹的操作 376
15.3.3　摺算復雜性 378
15.4　B-樹 379
15.4.1　索引順序訪問方法 379
15.4.2　m叉搜索樹 380
15.4.3　m階B-樹 381
15.4.4　B-樹的高度 382
15.4.5　B-樹的搜索 382
15.4.6　B-樹的插入 382
15.4.7　B-樹的刪除 384
15.4.8　節點結構 387
15.5　參考及推薦讀物 389
第16章　圖 390
16.1　基本概念 390
16.2　應用和更多的概念 391
16.3　特性 394
16.4　抽象數據類型graph 395
16.5　無權圖的描述 396
16.5.1　鄰接矩陣 396
16.5.2　鄰接鏈錶 397
16.5.3　鄰接數組 398
16.6　加權圖的描述 400
16.7　類實現 400
16.7.1　不同的類 400
16.7.2　鄰接矩陣類 401
16.7.3　擴充chain類 405
16.7.4　鏈錶類 405
16.8　圖的遍曆 407
16.8.1　廣度優先搜索 407
16.8.2　廣度優先搜索的實現 408
16.8.3　方法graph::bfs的復雜性分析 409
16.8.4　深度優先搜索 410
16.8.5　深度優先搜索的實現 411
16.8.6　方法graph::dfs的復雜性分析 412
16.9　應用 412
16.9.1　尋找一條路徑 412
16.9.2　連通圖及其構成 414
16.9.3　生成樹 415
第三部分　算法設計方法
第17章　貪婪算法 420
17.1　最優化問題 420
17.2　貪婪算法思想 421
17.3　應用 424
17.3.1　貨箱裝載 424
17.3.2　0/1背包問題 425
17.3.3　拓撲排序 427
17.3.4　二分覆蓋 430
17.3.5　單源最短路徑 433
17.3.6　最小成本生成樹 436
17.4　參考及推薦讀物 445
第18章　分而治之 446
18.1　算法思想 446
18.2　應用 453
18.2.1　殘缺棋盤 453
18.2.2　歸並排序 455
18.2.3　快速排序 459
18.2.4　選擇 464
18.2.5　相距最近的點對 466
18.3　解遞歸方程 474
18.4　復雜度的下限 475
18.4.1　最小最大問題的下限 476
18.4.2　排序算法的下限 477
第19章　動態規劃 479
19.1　算法思想 479
19.2　應用 481
19.2.1　0/1背包問題 481
19.2.2　矩陣乘法鏈 484
19.2.3　所有頂點對之間的最短路徑 489
19.2.4　帶有負值的單源最短路徑 492
19.2.5　網組的無交叉子集 496
19.3　參考及推薦讀物 501
第20章　迴溯法 502
20.1　算法思想 502
20.2　應用 506
20.2.1　貨箱裝載 506
20.2.2　0/1背包問題 512
20.2.3　最大完備子圖 515
20.2.4　旅行商問題 517
20.2.5　電路闆排列 519
第21章　分支定界 525
21.1　算法思想 525
21.2　應用 528
21.2.1　貨箱裝載 528
21.2.2　0/1背包問題 535
21.2.3　最大完備子圖 536
21.2.4　旅行商問題 538
21.2.5　電路闆排列 541
· · · · · · (收起)