數(shù)據(jù)抽象和問題求解：C++語(yǔ)言描述（第四版）

第1部分 問題解決技術(shù)
第1章 編程原理與軟件工程 3
1.1 問題求解與軟件工程 3
1.1.1 問題求解的含義 3
1.1.2 軟件的生命周期 4
1.1.3 優(yōu)秀解決方案的含義 10
1.2 模塊化設(shè)計(jì) 11
1.2.1 抽象與信息隱藏 11
1.2.2 面向?qū)ο蟮脑O(shè)計(jì) 13
1.2.3 自上而下的設(shè)計(jì) 14
1.2.4 一般設(shè)計(jì)原則 15
1.2.5 使用UML為面向?qū)ο蟮脑O(shè)計(jì)
建模 15
1.2.6 面向?qū)ο蠓绞降膬?yōu)點(diǎn) 17
1.3 關(guān)鍵編程問題 18
1.3.1 模塊化 18
1.3.2 可修改 19
1.3.3 易用 21
1.3.4 防故障編程 21
1.3.5 風(fēng)格 25
1.3.6 調(diào)試 30
1.4 小結(jié) 31
1.5 提示 32
1.6 自我測(cè)試題 32
1.7 練習(xí)題 33
1.8 編程問題 35
第2章 遞歸：鏡子 37
2.1 遞歸解決方案 37
2.1.1 遞歸值函數(shù)：n的階乘 39
2.1.2 遞歸void函數(shù)：逆置字符串 43
2.2 計(jì)數(shù) 52
2.2.1 兔子繁殖(Fibonacci序列) 52
2.2.2 組織游行隊(duì)伍 53
2.2.3 Spock的困惑 56
2.3 數(shù)組查找 57
2.3.1 查找數(shù)組的最大項(xiàng) 58
2.3.2 折半查找 59
2.3.3 查找數(shù)組中的第k個(gè)最小項(xiàng) 62
2.4 組織數(shù)據(jù) 64
2.5 遞歸與效率 69
2.6 小結(jié) 72
2.7 提示 72
2.8 自我測(cè)試題 73
2.9 練習(xí)題 73
2.10 編程問題 79
第3章 數(shù)據(jù)抽象：墻 80
3.1 抽象數(shù)據(jù)類型 80
3.2 指定ADT 83
3.2.1 ADT列表 84
3.2.2 ADT有序表 88
3.2.3 設(shè)計(jì)ADT 89
3.2.4 公理 92
3.3 實(shí)現(xiàn)ADT 94
3.3.1 C++類 95
3.3.2 C++命名空間 102
3.3.3 基于數(shù)組的ADT列表實(shí)現(xiàn) 104
3.3.4 C++異常 109
3.3.5 使用異常的ADT列表實(shí)現(xiàn) 110
3.4 小結(jié) 112
3.5 提示 113
3.6 自我測(cè)試題 113
3.7 練習(xí)題 114
3.8 編程問題 116第4章 鏈表 117
4.1 預(yù)備知識(shí) 117
4.1.1 指針 118
4.1.2 數(shù)組的動(dòng)態(tài)分配 123
4.1.3 基于指針的鏈表 124
4.2 鏈表編程 125
4.2.1 顯示鏈表的內(nèi)容 126
4.2.2 從鏈表中刪除指定的節(jié)點(diǎn) 127
4.2.3 在鏈表的指定位置插入節(jié)點(diǎn) 129
4.2.4 ADT列表的基于指針的實(shí)現(xiàn) 133
4.2.5 比較基于數(shù)組的實(shí)現(xiàn)和基于
引用的實(shí)現(xiàn) 139
4.2.6 使用文件存儲(chǔ)和恢復(fù)鏈表 140
4.2.7 將鏈表傳給函數(shù) 143
4.2.8 遞歸地處理鏈表 144
4.2.9 把對(duì)象作為鏈表的數(shù)據(jù) 148
4.3 鏈表的各種變化 148
4.3.1 循環(huán)鏈表 148
4.3.2 虛擬頭節(jié)點(diǎn) 150
4.3.3 雙向鏈表 150
4.4 清單應(yīng)用程序 152
4.5 C++標(biāo)準(zhǔn)模板庫(kù) 156
4.5.1 容器 157
4.5.2 迭代器 157
4.5.3 標(biāo)準(zhǔn)模板庫(kù)類list 158
4.6 小結(jié) 162
4.7 提示 164
4.8 自我測(cè)試題 165
4.9 練習(xí)題 167
4.10 編程問題 169
第5章 遞歸問題解決技術(shù) 172
5.1 回溯 172
5.1.1 八皇后問題 172
5.1.2 使用STL類vector解決八皇后
問題 174
5.2 定義語(yǔ)言 178
5.2.1 語(yǔ)法知識(shí)基礎(chǔ) 179
5.2.2 兩種簡(jiǎn)單語(yǔ)言 180
5.2.3 代數(shù)表達(dá)式 182
5.3 遞歸和數(shù)學(xué)歸納法的關(guān)系 189
5.3.1 factorial遞歸算法的正確性 189
5.3.2 Hanoi塔的成本 190
5.4 小結(jié) 191
5.5 提示 192
5.6 自我測(cè)試題 192
5.7 練習(xí)題 192
5.8 編程問題 195第2部分 使用抽象數(shù)據(jù)類型
解決問題
第6章 棧 201
6.1 抽象數(shù)據(jù)類型 201
6.2 ADT棧的簡(jiǎn)單應(yīng)用 206
6.2.1 檢查括號(hào)匹配 206
6.2.2 識(shí)別語(yǔ)言中的字符串 208
6.3 ADT棧的實(shí)現(xiàn) 209
6.3.1 ADT棧的基本數(shù)組的實(shí)現(xiàn) 209
6.3.2 ADT棧的基于指針的實(shí)現(xiàn) 213
6.3.3 使用ADT列表的實(shí)現(xiàn) 217
6.3.4 各種實(shí)現(xiàn)方式的比較 221
6.3.5 標(biāo)準(zhǔn)模板庫(kù)類stack 221
6.4 應(yīng)用：代數(shù)表達(dá)式 223
6.4.1 計(jì)算后綴表達(dá)式 223
6.4.2 中綴表達(dá)式與后綴表達(dá)式的
等價(jià)轉(zhuǎn)換 224
6.5 應(yīng)用：查找問題 227
6.5.1 使用棧的非遞歸解決方案 228
6.5.2 遞歸解決方案 234
6.6 棧和遞歸的關(guān)系 236
6.7 小結(jié) 238
6.8 提示 238
6.9 自我測(cè)試題 238
6.10 練習(xí)題 239
6.11 編程問題 242
第7章 隊(duì)列 247
7.1 ADT隊(duì)列 247
7.2 ADT隊(duì)列的簡(jiǎn)單應(yīng)用 249
7.2.1 讀取字符串 249
7.2.2 識(shí)別回文 250
7.3 實(shí)現(xiàn)ADT隊(duì)列 251
7.3.1 基于指針的實(shí)現(xiàn) 251
7.3.2 基于數(shù)組的實(shí)現(xiàn) 256
7.3.3 使用ADT列表的實(shí)現(xiàn) 261
7.3.4 標(biāo)準(zhǔn)模板庫(kù)類queue 263
7.3.5 實(shí)現(xiàn)的比較 266
7.4 基于位置的ADT總覽 266
7.5 模擬應(yīng)用 267
7.6 小結(jié) 275
7.7 提示 275
7.8 自我測(cè)試題 275
7.9 練習(xí)題 276
7.10 編程問題 278
第8章 類關(guān)系 282
8.1 繼承 282
8.1.1 公有、私有和受保護(hù)的繼承 287
8.1.2 is-a、has-a和As-a關(guān)系 288
8.2 虛函數(shù)和后期綁定 290
8.3 友元 297
8.4 ADT列表和有序表 299
8.5 類模板 304
8.6 重載運(yùn)算符 310
8.7 迭代器 313
8.8 小結(jié) 318
8.9 提示 319
8.10 自我測(cè)試題 319
8.11 練習(xí)題 319
8.12 編程問題 323
第9章 算法效率和排序 325
9.1 確定算法效率 325
9.1.1 算法的執(zhí)行時(shí)間 326
9.1.2 算法增率 327
9.1.3 數(shù)量階分析和大O表示法 328
9.1.4 正確分析問題 331
9.1.5 查找算法的效率 332
9.2 排序算法及其效率 333
9.2.1 選擇排序 333
9.2.2 起泡排序 336
9.2.3 插入排序 337
9.2.4 歸并排序 339
9.2.5 快速排序 344
9.2.6 基數(shù)排序 352
9.2.7 各種排序算法的比較 354
9.2.8 標(biāo)準(zhǔn)模板庫(kù)排序算法 355
9.3 小結(jié) 359
9.4 提示 360
9.5 自我測(cè)試題 360
9.6 練習(xí)題 361
9.7 編程問題 363
第10章 樹 366
10.1 術(shù)語(yǔ) 366
10.2 ADT二叉樹 372
10.2.1 二叉樹的遍歷 375
10.2.2 二叉樹的表示 378
10.2.3 ADT二叉樹的基于指針的
實(shí)現(xiàn) 381
10.3 ADT二叉查找樹 393
10.3.1 ADT二叉查找樹操作的
算法 397
10.3.2 ADT二叉查找樹的基于指針
的實(shí)現(xiàn) 408
10.3.3 二叉查找樹操作的效率 416
10.3.4 樹排序 419
10.3.5 將二叉查找樹保存到文件 419
10.3.6 STL查找算法 422
10.4 一般樹 424
10.5 小結(jié) 426
10.6 提示 426
10.7 自我測(cè)試題 427
10.8 練習(xí)題 428
10.9 編程問題 433
第11章 表和優(yōu)先隊(duì)列 435
11.1 ADT表 435
11.1.1 選擇實(shí)現(xiàn) 439
11.1.2 ADT表的基于數(shù)組的有序
實(shí)現(xiàn) 444
11.1.3 ADT表的二叉查找樹實(shí)現(xiàn) 448
11.2 ADT優(yōu)先隊(duì)列：ADT表的
變體 451
11.2.1 堆 454
11.2.2 ADT優(yōu)先隊(duì)列的堆實(shí)現(xiàn) 462
11.2.3 堆排序 464
11.3 STL中的表和優(yōu)先隊(duì)列 466
11.3.1 STL關(guān)聯(lián)容器 466
11.3.2 STL的priority_queue類和
堆算法 474
11.3 小結(jié) 477
11.4 提示 478
11.5 自我測(cè)試題 478
11.6 練習(xí)題 479
11.7 編程問題 481
第12章 表的高級(jí)實(shí)現(xiàn) 483
12.1 平衡查找樹 483
12.1.1 2-3樹 484
12.1.2 2-3-4樹 499
12.1.3 紅-黑樹 504
12.1.4 AVL樹 506
12.2 散列 510
12.2.1 散列函數(shù) 513
12.2.2 解決沖突 515
12.2.3 散列的效率 521
12.2.4 如何確立散列函數(shù) 523
12.2.5 表遍歷：散列的低效操作 525
12.2.6 使用STL實(shí)現(xiàn)
HashMap類 525
12.3 按多種形式組織數(shù)據(jù) 528
12.4 小結(jié) 531
12.5 提示 532
12.6 自我測(cè)試題 532
12.7 練習(xí)題 533
12.8 編程問題 535
第13章 圖 536
13.1 術(shù)語(yǔ) 536
13.2 將圖作為ADT 538
13.2.1 實(shí)現(xiàn)圖 539
13.2.2 使用STL實(shí)現(xiàn)Graph類 541
13.3 圖的遍歷 544
13.3.1 深度優(yōu)先查找 545
13.3.2 廣度優(yōu)先查找 546
13.3.3 使用STL實(shí)現(xiàn)BFS類 548
13.4 圖的應(yīng)用 550
13.4.1 拓?fù)渑判?550
13.4.2 生成樹 552
13.4.3 最小生成樹 555
13.4.4 最短路徑 556
13.4.5 回路 560
13.4.6 一些復(fù)雜問題 563
13.5 小結(jié) 563
13.6 提示 564
13.7 自我測(cè)試題 564
13.8 練習(xí)題 565
13.9 編程問題 567
第14章 外部方法 569
14.1 了解外部存儲(chǔ) 569
14.2 排序外部文件的數(shù)據(jù) 571
14.3 外部表 577
14.3.1 確定外部文件的索引 579
14.3.2 外部散列 582
14.3.3 B-樹 584
14.3.4 遍歷 590
14.3.5 多索引 593
14.4 小結(jié) 594
14.5 提示 594
14.6 自我測(cè)試題 595
14.7 練習(xí)題 595
14.8 編程問題 597
附錄A C++基礎(chǔ) 599
附錄B ASCII字符代碼 653
附錄C C++頭文件和標(biāo)準(zhǔn)函數(shù) 655
附錄D 數(shù)學(xué)歸納法 659
附錄E 標(biāo)準(zhǔn)模板庫(kù) 663
術(shù)語(yǔ)表 673
自我測(cè)試題答案 690