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

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