數(shù)據(jù)結(jié)構(gòu)與問題求解（C++版）

第一部分 對象和C++
第1章 數(shù)組、指針和結(jié)構(gòu) 1
1.1 什么是指針、數(shù)組和結(jié)構(gòu) 1
1.2 數(shù)組和字符串 2
1.2.1 頭等對象與次等對象的對比 2
1.2.2 使用Vector 3
1.2.3 調(diào)整Vector大小 5
1.2.4 push_back大小與容量 7
1.2.5 參數(shù)傳遞機制 7
1.2.6 常量基元數(shù)組 9
1.2.7 多維數(shù)組 9
1.2.8 標(biāo)準(zhǔn)庫類型string 9
1.3 C++中的指針語法 10
1.4 動態(tài)內(nèi)存管理 14
1.4.1 new運算符 15
1.4.2 垃圾收集與delete 15
1.4.3 過期指針、雙重刪除及其他 16
1.5 引用變量 17
1.6 結(jié)構(gòu) 19
1.6.1 指向結(jié)構(gòu)的指針 21
1.6.2 外部數(shù)據(jù)與內(nèi)部數(shù)據(jù)、深復(fù)制與淺復(fù)制 21
1.6.3 非鄰接鏈表：鏈表 23
小結(jié) 24
學(xué)習(xí)目標(biāo) 24
常見錯誤 25
網(wǎng)上資源 26
練習(xí) 26
簡答題 26
實踐題 28
編程項目 28
參考文獻(xiàn) 28
第2章 對象和類 30
2.1 什么是面向?qū)ο缶幊?30
2.2 類的基本語法 31
2.2.1 類成員 31
2.2.2 附加的構(gòu)造函數(shù)語法和訪問函數(shù) 33
2.2.3 接口和實現(xiàn)的分離 35
2.2.4 析構(gòu)函數(shù)、復(fù)制構(gòu)造函數(shù)和賦值運算符（=） 38
2.2.5 默認(rèn)的構(gòu)造函數(shù) 43
2.3 附加的C++類特性 43
2.3.1 調(diào)整后的構(gòu)造函數(shù)中的初始化與賦值 47
2.3.2 類型轉(zhuǎn)換 48
2.3.3 運算符重載 49
2.3.4 輸入、輸出和友元 52
2.4 一些常用術(shù)語 54
2.4.1 避免使用友元 54
2.4.2 靜態(tài)類成員 55
2.4.3 整型類常量的陷阱 55
2.5 異常 56
2.6 String類 57
2.7 要點重述：進(jìn)行了哪些調(diào)用？
哪些采用了默認(rèn)行為 65
2.8 組合 66
小結(jié) 67
學(xué)習(xí)目標(biāo) 68
常見錯誤 69
Internet資源 70
練習(xí) 70
簡答題 70
理論題 71
編程項目 72
參考文獻(xiàn) 75
第3章 模板 76
3.1 模板的概念 76
3.2 函數(shù)模板 76
3.3 排序函數(shù)模板 78
3.4 類模板 81
3.4.1 MemoryCell模板 81
3.4.2 實現(xiàn)vector類模板 85
3.5 模板的模板：matrix類 87
3.5.1 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本附件 88
3.5.2 operator [ ] 89
3.5.3 析構(gòu)函數(shù)、復(fù)制賦值和復(fù)制構(gòu)造函數(shù) 89
3.6 Fancy模板 89
3.6.1 多平臺參數(shù) 89
3.6.2 默認(rèn)的模板參數(shù) 90
3.6.3 保留字typename 90
3.7 與模板有關(guān)的bug 90
3.7.1 錯誤消息和改變的規(guī)則 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套類 91
3.7.4 類模板中的靜態(tài)成員 91
小結(jié) 91
學(xué)習(xí)目標(biāo) 91
常見錯誤 92
Internet資源 92
練習(xí) 93
簡答題 93
實踐題 93
編程項目 93
第4章 繼承 94
4.1 什么是繼承 94
4.2 繼承的基本知識 97
4.2.1 可視性規(guī)則 98
4.2.2 構(gòu)造函數(shù)和基類初始化 98
4.2.3 添加成員 99
4.2.4 覆蓋方法 101
4.2.5 靜態(tài)綁定和動態(tài)綁定 101
4.2.6 默認(rèn)的構(gòu)造函數(shù)、復(fù)制構(gòu)造函數(shù)、復(fù)制賦值運算符和析構(gòu)函數(shù) 103
4.2.7 構(gòu)造函數(shù)和析構(gòu)函數(shù)virtual或非virtual 104
4.2.8 抽象方法和抽象類 105
4.3 例子：擴(kuò)展Shape類 108
4.4 微妙的C++細(xì)節(jié) 112
4.4.1 參數(shù)的靜態(tài)綁定 113
4.4.2 默認(rèn)參數(shù) 114
4.4.3 派生類方法隱藏基類方法 114
4.4.4 覆蓋方法的兼容返回類型 115
4.4.5 私有繼承 116
4.4.6 友元 116
4.4.7 值調(diào)用與多態(tài)并不混淆 117
4.5 多重繼承 117
小結(jié) 118
學(xué)習(xí)目標(biāo) 119
常見錯誤 119
Internet資源 120
練習(xí) 120
簡答題 120
實踐題 122
編程項目 122
參考文獻(xiàn) 122
第5章 設(shè)計模式 123
5.1 模式的概念 123
5.2 Functor（函數(shù)對象） 124
5.3 適配器和包裝器 129
5.3.1 指針包裝器 129
5.3.2 常數(shù)引用包裝器 134
5.3.3 適配器更改接口 135
5.4 迭代器 136
5.4.1 迭代器設(shè)計1 137
5.4.2 迭代器設(shè)計2 139
5.4.3 基于繼承的迭代器和
factory 139
5.5 合成（對） 144
5.6 觀察者 144
小結(jié) 148
學(xué)習(xí)目標(biāo) 148
常見錯誤 149
Internet資源 149
練習(xí) 150
簡答題 150
理論題 150
實踐題 150
編程項目 152
參考文獻(xiàn) 152
第二部分 算法和構(gòu)建代碼塊
第6章 算法分析 153
6.1 什么是算法分析 153
6.2 算法運行時間的例子 156
6.3 最大連續(xù)子數(shù)列和問題 157
6.3.1 直觀的O(N3)算法 158
6.3.2 改進(jìn)的O(N2)算法 160
6.3.3 線性算法 161
6.4 一般的Big-Oh規(guī)則 164
6.5 對數(shù) 167
6.6 靜態(tài)查找問題 169
6.6.1 順序查找 169
6.6.2 折半查找 169
6.6.3 插值查找 172
6.7 算法分析的檢驗 173
6.8 Big-Oh分析的限制 174
小結(jié) 174
學(xué)習(xí)目標(biāo) 174
常見錯誤 175
Internet資源 175
練習(xí) 176
簡答題 176
理論題 177
實踐題 179
編程項目 179
參考文獻(xiàn) 180
第7章 標(biāo)準(zhǔn)模板庫 182
7.1 簡介 182
7.2 堆棧和隊列 183
7.2.1 堆棧 184
7.2.2 堆棧和計算機語言 185
7.2.3 隊列 186
7.3 容器和迭代器 187
7.3.1 容器 187
7.3.2 迭代器 188
7.4 STL算法 189
7.4.1 STL函數(shù)對象 189
7.4.2 二分查找法 191
7.4.3 排序 193
7.5 實現(xiàn)帶有迭代器的vector 193
7.6 順序表和鏈表 195
7.6.1 list類 195
7.6.2 堆棧和隊列 196
7.7 集合 197
7.8 映射 199
7.9 優(yōu)先隊列 200
小結(jié) 203
學(xué)習(xí)目標(biāo) 204
常見錯誤 204
Internet資源 205
練習(xí) 205
簡答題 205
理論題 205
實踐題 206
編程項目 206
參考文獻(xiàn) 208
第8章 遞歸 209
8.1 遞歸的概念 209
8.2 背景知識：數(shù)學(xué)歸納法 210
8.3 基本遞歸 212
8.3.1 以任意基數(shù)打印數(shù)字 213
8.3.2 遞歸算法有效的原因 215
8.3.3 遞歸算法的作用原理 216
8.3.4 遞歸不宜太多 217
8.3.5 樹 218
8.3.6 附加例子 219
8.4 數(shù)值應(yīng)用 223
8.4.1 模運算 223
8.4.2 模冪運算 224
8.4.3 最大公約數(shù)和乘法逆元素 225
8.4.4 RSA密碼系統(tǒng) 228
8.5 分治算法 230
8.5.1 最大鄰近子序列和問題 230
8.5.2 基本分治遞歸分析 233
8.5.3 分治法運行時間的一般上限 235
8.6 動態(tài)規(guī)劃 237
8.7 回溯法 241
小結(jié) 244
學(xué)習(xí)目標(biāo) 244
常見錯誤 245
Internet資源 245
練習(xí) 246
簡答題 246
理論題 246
實踐題 247
編程項目 248
參考文獻(xiàn) 249
第9章 排序算法 250
9.1 排序為何重要 250
9.2 預(yù)備知識 251
9.3 插入排序和其他簡單排序的分析 252
9.4 希爾排序 254
9.5 歸并排序 257
9.5.1 排過序的數(shù)組的線性時間合并 257
9.5.2 歸并排序算法 259
9.6 快速排序 261
9.6.1 快速排序算法 261
9.6.2 快速排序的分析 263
9.6.3 支點的選擇 265
9.6.4 分組策略 267
9.6.5 同支點相等的鍵 268
9.6.6 中值劃分 269
9.6.7 小數(shù)組 270
9.6.8 C++快速排序例程 270
9.7 排序選擇 272
9.8 排序的下限 274
9.9 間接排序 275
9.9.1 使用指針將Comparable
副本數(shù)減少為2N 275
9.9.2 避免附加數(shù)組 276
小結(jié) 278
學(xué)習(xí)目標(biāo) 279
常見錯誤 279
Internet資源 279
練習(xí) 280
簡答題 280
理論題 280
實踐題 281
編程項目 282
參考文獻(xiàn) 283
第10章 隨機 285
10.1 為什么我們需要隨機數(shù) 285
10.2 隨機數(shù)生成器 286
10.3 非均勻隨機數(shù) 290
10.4 生成隨機排列 291
10.5 隨機算法 293
10.6 隨機素數(shù)測試 295
小結(jié) 298
學(xué)習(xí)目標(biāo) 298
常見錯誤 298
Internet資源 299
練習(xí) 299
簡答題 299
理論題 299
實踐題 300
編程項目 300
參考文獻(xiàn) 301
第三部分 應(yīng)用程序
第11章 娛樂與游戲 302
11.1 單詞查找拼圖 302
11.1.1 理論 303
11.1.2 C++實現(xiàn) 304
11.2 Tic-Tac-Toe游戲 309
11.2.1 a- b修剪 309
11.2.2 變換表 312
11.2.3 計算機國際象棋 316
小結(jié) 316
學(xué)習(xí)目標(biāo) 317
常見錯誤 317
Internet資源 317
練習(xí) 317
簡答題 317
理論題 317
實踐題 318
編程項目 318
參考文獻(xiàn) 319
第12章 堆棧和編譯器 320
12.1 對稱符號檢查器 320
12.1.1 基本算法 320
12.1.2 實現(xiàn) 321
12.2 簡單計算器 330
12.2.1 后綴自動機 330
12.2.2 中綴到后綴的轉(zhuǎn)換 332
12.2.3 實現(xiàn) 333
12.2.4 表達(dá)式樹 341
小結(jié) 343
學(xué)習(xí)目標(biāo) 343
常見錯誤 343
Internet資源 343
練習(xí) 344
簡答題 344
理論題 344
實踐題 344
編程項目 345
參考文獻(xiàn) 345
第13章 實用工具 346
13.1 文件壓縮 346
13.1.1 前綴碼 347
13.1.2 霍夫曼算法 348
13.1.3 實現(xiàn) 350
13.2 交叉引用生成程序 366
13.2.1 基本概念 366
13.2.2 C++實現(xiàn) 366
小結(jié) 370
學(xué)習(xí)目標(biāo) 370
常見錯誤 371
Internet資源 371
練習(xí) 371
簡答題 371
理論題 371
實踐題 372
編程項目 372
參考文獻(xiàn) 373
第14章 仿真 375
14.1 Josephus問題 375
14.1.1 簡單的解決方案 376
14.1.2 一個更有效的算法 376
14.2 事件驅(qū)動仿真 380
14.2.1 基本思想 380
14.2.2 實例：調(diào)制解調(diào)器
庫仿真 381
小結(jié) 388
學(xué)習(xí)目標(biāo) 388
常見錯誤 389
Internet資源 389
練習(xí) 389
簡答題 389
理論題 389
實踐題 390
編程項目 390
第15章 圖和路徑 391
15.1 定義 391
15.2 無權(quán)最短路徑問題 403
15.2.1 理論 403
15.2.2 C++實現(xiàn) 406
15.3 正的有權(quán)最短路徑問題 407
15.3.1 理論：迪杰斯特拉算法 407
15.3.2 C++實現(xiàn) 410
15.4 負(fù)的有權(quán)最短路徑問題 412
15.4.1 理論 412
15.4.2 C++實現(xiàn) 413
15.5 無環(huán)圖的路徑問題 414
15.5.1 拓?fù)渑判?415
15.5.2 無環(huán)最短路徑算法的理論 416
15.5.3 C++實現(xiàn) 417
15.5.4 應(yīng)用：關(guān)鍵路徑分析 419
小結(jié) 421
學(xué)習(xí)目標(biāo) 422
常見錯誤 422
Internet資源 423
練習(xí) 423
簡答題 423
理論證明 423
實踐題 424
編程項目 425
參考文獻(xiàn) 426
第四部分 實現(xiàn)
第16章 堆棧和隊列 427
16.1 動態(tài)數(shù)組實現(xiàn) 427
16.1.1 堆棧 427
16.1.2 隊列 431
16.2 鏈表實現(xiàn) 436
16.2.1 堆棧 436
16.2.2 隊列 441
16.3 兩種方法的比較 444
16.4 STL堆棧和隊列適配器 445
16.5 雙頭隊列 446
小結(jié) 447
學(xué)習(xí)目標(biāo) 447
常見錯誤 448
Internet資源 448
練習(xí) 448
簡答題 448
實踐題 449
編程項目 449
第17章 鏈表 450
17.1 基本概念 450
17.1.1 header節(jié)點 452
17.1.2 迭代器類 453
17.2 C++實現(xiàn) 454
17.3 雙鏈表和循環(huán)鏈表 462
17.4 排序鏈表 464
17.5 實現(xiàn)STL鏈表類 466
小結(jié) 479
學(xué)習(xí)目標(biāo) 480
常見錯誤 480
Internet資源 480
練習(xí) 481
簡答題 481
理論題 481
實踐題 482
編程項目 483
第18章 樹 485
18.1 一般樹 485
18.1.1 定義 485
18.1.2 實現(xiàn) 486
18.1.3 應(yīng)用：文件系統(tǒng) 487
18.2 二叉樹 490
18.3 遞歸和樹 496
18.4 樹遍歷：迭代器類 499
18.4.1 后序遍歷 502
18.4.2 中序遍歷 506
18.4.3 前序遍歷 508
18.4.4 層序遍歷 509
小結(jié) 511
學(xué)習(xí)目標(biāo) 512
常見錯誤 512
Internet資源 512
練習(xí) 513
簡答題 513
理論題 514
實踐題 514
編程項目 514
第19章 二叉查找樹 516
19.1 基本概念 516
19.1.1 操作 517
19.1.2 C++實現(xiàn) 518
19.2 順序統(tǒng)計C++實現(xiàn) 526
19.3 分析二叉查找樹操作 530
19.4 AVL樹 533
19.4.1 屬性 534
19.4.2 單旋轉(zhuǎn) 536
19.4.3 雙旋轉(zhuǎn) 538
19.4.4 AVL插入總結(jié) 540
19.5 紅-黑樹 541
19.5.1 自底向上插入 541
19.5.2 自頂向下紅-黑樹 543
19.5.3 C++實現(xiàn) 545
19.5.4 自頂往下刪除 551
19.6 AA-樹 553
19.6.1 插入 554
19.6.2 刪除 556
19.6.3 C++實現(xiàn) 557
19.7 實現(xiàn)STL set類和map類 561
19.8 B樹 575
小結(jié) 580
學(xué)習(xí)目標(biāo) 581
常見錯誤 581
Internet資源 582
練習(xí) 582
簡答題 582
理論題 583
實踐題 583
編程項目 584
參考文獻(xiàn) 584
第20章 散列表 587
20.1 基本概念 587
20.2 散列函數(shù) 588
20.3 線形探測法 590
20.3.1 線性探測法的簡單
分析（naive analysis） 591
20.3.2 實際情況：原始集聚 592
20.3.3 查找運算分析 593
20.4 二次探測法 594
20.4.1 C++實現(xiàn) 598
20.4.2 二次探測法分析 603
20.5 分離鏈接法 603
20.6 散列表與二叉查找樹 604
20.7 散列化應(yīng)用程序 604
小結(jié) 605
學(xué)習(xí)目標(biāo) 605
常見錯誤 606
Internet資源 606
練習(xí) 606
簡答題 606
實踐題 607
編程項目 608
參考文獻(xiàn) 608
第21章 優(yōu)先級隊列：二叉堆 610
21.1 基本思想 610
21.1.1 結(jié)構(gòu)屬性 611
21.1.2 堆順序?qū)傩?612
21.1.3 允許的操作 613
21.2 基本操作的實現(xiàn) 615
21.2.1 insert操作 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：線性時間的堆構(gòu)造函數(shù) 619
21.4 STL priority_queue實現(xiàn) 622
21.5 高級操作：decreaseKey和merge 625
21.6 內(nèi)部排序：堆排序 625
21.7 外部排序 628
21.7.1 我們?yōu)槭裁葱枰碌乃惴?628
21.7.2 外部排序模型 628
21.7.3 簡單的算法 629
21.7.4 多路歸并 630
21.7.5 多相歸并 631
21.7.6 置換選擇 632
小結(jié) 634
學(xué)習(xí)目標(biāo) 634
常見錯誤 635
Internet資源 635
練習(xí) 635
簡答題 635
理論題 635
實踐題 637
編程項目 637
參考文獻(xiàn) 638
第五部分 高級數(shù)據(jù)結(jié)構(gòu)
第22章 伸展樹 639
22.1 自我調(diào)整和攤銷分析 639
22.1.1 攤銷時間限制 640
22.1.2 簡單的自我調(diào)整策略 641
22.2 基本的自底往上伸展樹 642
22.3 基本伸展樹操作 644
22.4 自底往上伸展樹分析 645
22.5 自頂往下伸展樹 649
22.6 實現(xiàn)自頂往下伸展樹 652
22.7 伸展樹與其他查找樹的比較 657
小結(jié) 658
學(xué)習(xí)目標(biāo) 658
常見錯誤 658
Internet資源 659
練習(xí) 659
簡答題 659
理論題 659
實踐題 660
編程項目 660
參考文獻(xiàn) 660
第23章 合并優(yōu)先級隊列 661
23.1 偏斜堆 661
23.1.1 合并是基礎(chǔ) 661
23.1.2 簡化的堆排序樹合并 662
23.1.3 偏斜堆：簡單修改 662
23.1.4 偏斜堆分析 663
23.2 對偶堆 665
23.2.1 對偶堆的操作 666
23.2.2 對偶堆的實現(xiàn) 668
23.2.3 應(yīng)用：Dijkstra最短加權(quán)
路徑算法 674
小結(jié) 676
學(xué)習(xí)目標(biāo) 676
常見錯誤 676
Internet資源 677
練習(xí) 677
簡答題 677
理論題 677
實踐題 678
編程項目 678
參考文獻(xiàn) 678
第24章 不相交集類 680
24.1 等價關(guān)系 680
24.2 動態(tài)等價和兩個應(yīng)用 680
24.2.1 應(yīng)用：生成迷宮 681
24.2.2 應(yīng)用：最小伸展樹 684
24.2.3 應(yīng)用：最近共同祖先問題 686
24.3 快速查找算法 689
24.4 快速合并算法 690
24.4.1 巧妙的合并算法 691
24.4.2 路徑壓縮 693
24.5 C++實現(xiàn) 694
24.6 針對按秩合并與路徑壓縮的
最壞情形 695
合并/查找算法分析 696
小結(jié) 701
學(xué)習(xí)目標(biāo) 701
常見錯誤 702
Internet資源 702
練習(xí) 702
簡答題 702
理論題 703
實踐題 703
編程項目 703
參考文獻(xiàn) 704
附 錄
附錄A C++相關(guān)信息 706
A.1 沒有編譯器實現(xiàn)該標(biāo)準(zhǔn) 706
A.2 不常見的C++運算符 706
A.2.1 自增運算符與自減運算符 706
A.2.2 類型轉(zhuǎn)換 707
A.2.3 按位運算符 708
A.2.4 條件運算符 710
A.3 命令參數(shù) 710
A.4 輸入和輸出 710
A.4.1 基本的流操作 711
A.4.2 順序文件 714
A.4.3 字符串流 714
A.5 名字空間 716
A.6 C++新特性 717
常見錯誤 717
附錄B 運算符 719
附錄C 某些庫例程 720
C.1 <ctype.h>和<cctype>中聲明的例程 720
C.2 <limits.h>和<climits>中聲明的常量 720
C.3 <math.h>和<cmath>中聲明的例程 721
C.4 <stdlib.h>和<cstdlib>中聲明的例程 721
附錄D C++中的基元數(shù)組 723
D.1 基元數(shù)組 723
D.1.1 C++實現(xiàn)：數(shù)組名稱是一個指針 723
D.1.2 多維數(shù)組 726
D.1.3 char * 類型、const指針和常量字符串 726
D.2 動態(tài)數(shù)組分配：new [ ]和delete [ ] 729
D.3 指針?biāo)阈g(shù)運算、指針跳和基本迭代 733
D.3.1 *、&和[ ]優(yōu)先級的含意 734
D.3.2 指針?biāo)阈g(shù)的含意 734
D.3.3 指針跳例子 736
D.3.4 使用指針跳的意義 737
常見錯誤 738
Internet資源 738