第1章 C++麵嚮對象程序設計 1
1.1 抽象數據類型 1
1.2 封裝 1
1.3 繼承 5
1.4 指針 7
1.4.1 指針與數組 10
1.4.2 指針與復製構造函數 12
1.4.3 指針與析構函數 14
1.4.4 指針和引用變量 14
1.4.5 函數指針 17
1.5 多態性 18
1.6 C++和麵嚮對象程序設計 20
1.7 標準模闆庫 20
1.7.1 容器 21
1.7.2 迭代器 21
1.7.3 算法 21
1.7.4 函數對象 22
1.8 標準模闆庫中的嚮量 24
1.9 數據結構與麵嚮對象編程 29
1.10 案例分析：隨機訪問文件 30
1.11 習題 38
1.12 編程練習 40
參考書目 42
第2章 復雜度分析 43
2.1 計算復雜度以及漸近復雜度 43
2.2 大O錶示法 44
2.3 大O錶示法的性質 46
2.4 Ω錶示法與Θ錶示法 47
2.5 可能存在的問題 48
2.6 復雜度示例 49
2.7 確定漸近復雜度示例 50
2.8 最好、平均和最壞情況 51
2.9 攤銷復雜度(amortized complexity) 54
2.10 NP完整性 57
2.11 習題 59
參考書目 61
第3章 鏈錶 63
3.1 單嚮鏈錶 63
3.1.1 插入 68
3.1.2 刪除 70
3.1.3 查找 74
3.2 雙嚮鏈錶 74
3.3 循環鏈錶 78
3.4 跳躍鏈錶(skip list) 79
3.5 自組織鏈錶 83
3.6 稀疏錶 87
3.7 標準模闆庫中的鏈錶 89
3.8 小結 92
3.9 案例分析：圖書館 93
3.10 習題 101
3.11 編程練習 102
參考書目 105
第4章 棧與隊列 107
4.1 棧 107
4.2 隊列 113
4.3 優先隊列 119
4.4 標準模闆庫中的棧 119
4.5 標準模闆庫中的隊列 120
4.6 標準模闆庫中的優先隊列 121
4.7 標準模版庫中的雙端隊列 123
4.8 案例分析：迷宮問題 127
4.9 習題 131
4.10 編程練習 133
參考書目 134
第5章 遞歸 135
5.1 遞歸定義 135
5.2 函數調用與遞歸實現 137
5.3 分析遞歸調用 139
5.4 尾遞歸 142
5.5 非尾遞歸 142
5.6 間接遞歸 147
5.7 嵌套遞歸 148
5.8 不閤理遞歸 149
5.9 迴溯 152
5.10 小結 157
5.11 案例分析：遞歸下降解釋器 158
5.12 習題 165
5.13 編程練習 167
參考書目 169
第6章 二叉樹 171
6.1 樹、二叉樹和二叉查找樹 171
6.2 二叉樹的實現 174
6.3 二叉查找樹的查找 176
6.4 樹的遍曆 179
6.4.1 廣度優先遍曆 179
6.4.2 深度優先遍曆 180
6.4.3 不使用棧的深度優先遍曆 186
6.5 插入 191
6.6 刪除 193
6.6.1 閤並刪除 194
6.6.2 復製刪除 196
6.7 樹的平衡 198
6.7.1 DSW算法 200
6.7.2 AVL樹 202
6.8 自適應樹(self-adjusting tree) 207
6.8.1 自重新構造樹(self-restructuring tree) 207
6.8.2 “張開”策略(splaying) 208
6.9 堆 212
6.9.1 將堆作為優先隊列 213
6.9.2 用數組實現堆 215
6.10 treap樹 218
6.11 k-d樹 221
6.12 波蘭錶示法和錶達式樹 225
6.13 案例分析：計算單詞齣現的頻率 229
6.14 習題 235
6.15 編程練習 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 標準模闆庫中的集閤(set)以及多重集閤(multiset) 278
7.1.10 標準模闆庫中的映射(map)和多映射(multimap) 282
7.2 trie 286
7.3 小結 292
7.4 案例分析：拼寫檢查器 292
7.5 習題 300
7.6 編程練習 301
參考書目 304
第8章 圖 307
8.1 圖的錶示法 308
8.2 圖的遍曆 309
8.3 最短路徑 312
8.4 環的檢測 319
8.5 生成樹 322
8.6 連通性 324
8.6.1 無嚮圖中的連通性 324
8.6.2 有嚮圖中的連通性 326
8.7 拓撲排序 328
8.8 網絡 329
8.8.1 最大流 329
8.8.2 成本最低的最大流 337
8.9 匹配 340
8.9.1 穩定匹配問題 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 漢密爾頓環問題 361
8.13 案例分析：唯一代錶 363
8.14 習題 372
8.15 編程練習 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 基數排序 405
9.3.6 計數排序 408
9.4 標準模闆庫中的排序 410
9.5 小結 414
9.6 案例分析：多項式相加 414
9.7 習題 420
9.8 編程練習 422
參考書目 423
第10章 散列 427
10.1 散列函數 427
10.1.1 除餘法 428
10.1.2 摺疊法 428
10.1.3 平方取中法 429
10.1.4 提取法 429
10.1.5 基數轉換法 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 理想散列函數 438
10.4.1 Cichelli方法 438
10.4.2 FHCD算法 440
10.5 再散列 442
10.6 可擴展文件的散列函數 444
10.6.1 可擴展散列 445
10.6.2 綫性散列 446
10.7 案例分析：使用桶的散列 449
10.8 習題 456
10.9 編程練習 457
參考書目 458
第11章 數據壓縮 461
11.1 數據壓縮的條件 461
11.2 Huffman編碼 463
11.3 Run-Length編碼方式 473
11.4 Ziv-Lempel編碼方式 474
11.5 案例分析：Huffman方法和Run-Length編碼方式 476
11.6 習題 485
11.7 編程練習 486
參考書目 487
第12章 內存管理 489
12.1 sequential-fit方法 490
12.2 nonsequential-fit方法 491
12.3 垃圾迴收 497
12.3.1 標記和清除 498
12.3.2 復製方法 504
12.3.3 遞增的垃圾迴收 505
12.3.4 分代垃圾迴收 510
12.4 小結 513
12.5 案例分析 514
12.6 習題 521
12.7 編程練習 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 後綴數組 563
13.2 字符串的模糊匹配 564
13.2.1 字符串的近似性 565
13.2.2 有k個錯誤的字符串匹配 570
13.3 案例分析：最長的共有子字符串 573
13.4 習題 580
13.5 編程練習 581
參考書目 582
附錄A 計算大O 585
附錄B 標準模闆庫中的算法 591
附錄C NP完整性 599
· · · · · · (收起)