C++數(shù)據(jù)結(jié)構(gòu)與算法（第4版）

第1章 C++面向?qū)ο蟪绦蛟O(shè)計 1
1.1 抽象數(shù)據(jù)類型 1
1.2 封裝 1
1.3 繼承 5
1.4 指針 7
1.4.1 指針與數(shù)組 10
1.4.2 指針與復(fù)制構(gòu)造函數(shù) 12
1.4.3 指針與析構(gòu)函數(shù) 14
1.4.4 指針和引用變量 14
1.4.5 函數(shù)指針 17
1.5 多態(tài)性 18
1.6 C++和面向?qū)ο蟪绦蛟O(shè)計 20
1.7 標(biāo)準(zhǔn)模板庫 20
1.7.1 容器 21
1.7.2 迭代器 21
1.7.3 算法 21
1.7.4 函數(shù)對象 22
1.8 標(biāo)準(zhǔn)模板庫中的向量 24
1.9 數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶幊? 29
1.10 案例分析：隨機訪問文件 30
1.11 習(xí)題 38
1.12 編程練習(xí) 40
參考書目 42
第2章 復(fù)雜度分析 43
2.1 計算復(fù)雜度以及漸近復(fù)雜度 43
2.2 大O表示法 44
2.3 大O表示法的性質(zhì) 46
2.4 Ω表示法與Θ表示法 47
2.5 可能存在的問題 48
2.6 復(fù)雜度示例 49
2.7 確定漸近復(fù)雜度示例 50
2.8 最好、平均和最壞情況 51
2.9 攤銷復(fù)雜度(amortized complexity) 54
2.10 NP完整性 57
2.11 習(xí)題 59
參考書目 61
第3章 鏈表 63
3.1 單向鏈表 63
3.1.1 插入 68
3.1.2 刪除 70
3.1.3 查找 74
3.2 雙向鏈表 74
3.3 循環(huán)鏈表 78
3.4 跳躍鏈表(skip list) 79
3.5 自組織鏈表 83
3.6 稀疏表 87
3.7 標(biāo)準(zhǔn)模板庫中的鏈表 89
3.8 小結(jié) 92
3.9 案例分析：圖書館 93
3.10 習(xí)題 101
3.11 編程練習(xí) 102
參考書目 105
第4章 棧與隊列 107
4.1 棧 107
4.2 隊列 113
4.3 優(yōu)先隊列 119
4.4 標(biāo)準(zhǔn)模板庫中的棧 119
4.5 標(biāo)準(zhǔn)模板庫中的隊列 120
4.6 標(biāo)準(zhǔn)模板庫中的優(yōu)先隊列 121
4.7 標(biāo)準(zhǔn)模版庫中的雙端隊列 123
4.8 案例分析：迷宮問題 127
4.9 習(xí)題 131
4.10 編程練習(xí) 133
參考書目 134
第5章 遞歸 135
5.1 遞歸定義 135
5.2 函數(shù)調(diào)用與遞歸實現(xiàn) 137
5.3 分析遞歸調(diào)用 139
5.4 尾遞歸 142
5.5 非尾遞歸 142
5.6 間接遞歸 147
5.7 嵌套遞歸 148
5.8 不合理遞歸 149
5.9 回溯 152
5.10 小結(jié) 157
5.11 案例分析：遞歸下降解釋器 158
5.12 習(xí)題 165
5.13 編程練習(xí) 167
參考書目 169
第6章 二叉樹 171
6.1 樹、二叉樹和二叉查找樹 171
6.2 二叉樹的實現(xiàn) 174
6.3 二叉查找樹的查找 176
6.4 樹的遍歷 179
6.4.1 廣度優(yōu)先遍歷 179
6.4.2 深度優(yōu)先遍歷 180
6.4.3 不使用棧的深度優(yōu)先遍歷 186
6.5 插入 191
6.6 刪除 193
6.6.1 合并刪除 194
6.6.2 復(fù)制刪除 196
6.7 樹的平衡 198
6.7.1 DSW算法 200
6.7.2 AVL樹 202
6.8 自適應(yīng)樹(self-adjusting tree) 207
6.8.1 自重新構(gòu)造樹(self-restructuring tree) 207
6.8.2 “張開”策略(splaying) 208
6.9 堆 212
6.9.1 將堆作為優(yōu)先隊列 213
6.9.2 用數(shù)組實現(xiàn)堆 215
6.10 treap樹 218
6.11 k-d樹 221
6.12 波蘭表示法和表達式樹 225
6.13 案例分析：計算單詞出現(xiàn)的頻率 229
6.14 習(xí)題 235
6.15 編程練習(xí) 239
參考書目 242
第7章 多叉樹 245
7.1 B樹家族 245
7.1.1 B樹 247
7.1.2 B*樹 254
7.1.3 B+樹 255
7.1.4 前綴B+樹 257
7.1.5 k-d B樹 259
7.1.6 位樹 264
7.1.7 R樹 265
7.1.8 2-4樹 267
7.1.9 標(biāo)準(zhǔn)模板庫中的集合(set)以及多重集合(multiset) 278
7.1.10 標(biāo)準(zhǔn)模板庫中的映射(map)和多映射(multimap) 282
7.2 trie 286
7.3 小結(jié) 292
7.4 案例分析：拼寫檢查器 292
7.5 習(xí)題 300
7.6 編程練習(xí) 301
參考書目 304
第8章 圖 307
8.1 圖的表示法 308
8.2 圖的遍歷 309
8.3 最短路徑 312
8.4 環(huán)的檢測 319
8.5 生成樹 322
8.6 連通性 324
8.6.1 無向圖中的連通性 324
8.6.2 有向圖中的連通性 326
8.7 拓撲排序 328
8.8 網(wǎng)絡(luò) 329
8.8.1 最大流 329
8.8.2 成本最低的最大流 337
8.9 匹配 340
8.9.1 穩(wěn)定匹配問題 344
8.9.2 分配問題 346
8.9.3 非二分圖中的匹配集合 348
8.10 歐拉(Eulerian)圖與漢密爾頓 (Hamiltonian)圖 349
8.10.1 歐拉圖 349
8.10.2 漢密爾頓圖 352
8.11 圖的上色問題 356
8.12 圖論中的NP完整性問題 359
8.12.1 派系問題 359
8.12.2 三色問題 360
8.12.3 頂點覆蓋問題 361
8.12.4 漢密爾頓環(huán)問題 361
8.13 案例分析：唯一代表 363
8.14 習(xí)題 372
8.15 編程練習(xí) 376
參考書目 377
第9章 排序 381
9.1 基本的排序算法 382
9.1.1 插入排序 382
9.1.2 選擇排序 384
9.1.3 冒泡排序 386
9.1.4 梳排序 388
9.2 決策樹 389
9.3 高效排序算法 392
9.3.1 希爾排序 392
9.3.2 堆排序 395
9.3.3 快速排序 397
9.3.4 歸并排序 402
9.3.5 基數(shù)排序 405
9.3.6 計數(shù)排序 408
9.4 標(biāo)準(zhǔn)模板庫中的排序 410
9.5 小結(jié) 414
9.6 案例分析：多項式相加 414
9.7 習(xí)題 420
9.8 編程練習(xí) 422
參考書目 423
第10章 散列 427
10.1 散列函數(shù) 427
10.1.1 除余法 428
10.1.2 折疊法 428
10.1.3 平方取中法 429
10.1.4 提取法 429
10.1.5 基數(shù)轉(zhuǎn)換法 429
10.1.6 全域散列法 429
10.2 沖突解決方法 430
10.2.1 開放定址法 430
10.2.2 鏈接法 435
10.2.3 桶定址 436
10.3 刪除 437
10.4 理想散列函數(shù) 438
10.4.1 Cichelli方法 438
10.4.2 FHCD算法 440
10.5 再散列 442
10.6 可擴展文件的散列函數(shù) 444
10.6.1 可擴展散列 445
10.6.2 線性散列 446
10.7 案例分析：使用桶的散列 449
10.8 習(xí)題 456
10.9 編程練習(xí) 457
參考書目 458
第11章 數(shù)據(jù)壓縮 461
11.1 數(shù)據(jù)壓縮的條件 461
11.2 Huffman編碼 463
11.3 Run-Length編碼方式 473
11.4 Ziv-Lempel編碼方式 474
11.5 案例分析：Huffman方法和Run-Length編碼方式 476
11.6 習(xí)題 485
11.7 編程練習(xí) 486
參考書目 487
第12章 內(nèi)存管理 489
12.1 sequential-fit方法 490
12.2 nonsequential-fit方法 491
12.3 垃圾回收 497
12.3.1 標(biāo)記和清除 498
12.3.2 復(fù)制方法 504
12.3.3 遞增的垃圾回收 505
12.3.4 分代垃圾回收 510
12.4 小結(jié) 513
12.5 案例分析 514
12.6 習(xí)題 521
12.7 編程練習(xí) 522
參考書目 524
第13章 字符串匹配 527
13.1 字符串的精確匹配 527
13.1.1 簡單的算法 527
13.1.2 Knuth-Morris-Pratt算法 530
13.1.3 Boyer-Moore算法 536
13.1.4 多次搜索 545
13.1.5 面向位的方法 546
13.1.6 單詞集合的匹配 550
13.1.7 正則表達式的匹配 555
13.1.8 后綴trie和樹 558
13.1.9 后綴數(shù)組 563
13.2 字符串的模糊匹配 564
13.2.1 字符串的近似性 565
13.2.2 有k個錯誤的字符串匹配 570
13.3 案例分析：最長的共有子字符串 573
13.4 習(xí)題 580
13.5 編程練習(xí) 581
參考書目 582
附錄A 計算大O 585
附錄B 標(biāo)準(zhǔn)模板庫中的算法 591
附錄C NP完整性 599