C++數(shù)據(jù)結(jié)構(gòu)導引（國外經(jīng)典教材計算機科學與技術）

第1章 軟件開發(fā) 1
1.1 問題分析和需求規(guī)格說明 1
1.2 設計 3
1.2.1 對象 3
1.2.2 操作 4
1.2.3 算法 5
1.2.4 函數(shù)YearSum()的設計 5
1.2.5 函數(shù)DisplayTable()的設計 6
1.2.6 關于算法的一些最后說明 7
1.3 編碼 10
1.4 測試、執(zhí)行和調(diào)試 14
1.5 維護 18
1.5.1 小測驗 18
1.5.2 練習 19
第2章 數(shù)據(jù)結(jié)構(gòu)入門和抽象數(shù)據(jù)類型——C風格類型 21
2.1 數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型和實現(xiàn) 21
2.2 簡單數(shù)據(jù)類型 24
2.2.1 Boolean數(shù)據(jù) 24
2.2.2 Character數(shù)據(jù) 25
2.2.3 整型數(shù)據(jù) 26
2.2.4 實數(shù)數(shù)據(jù) 28
2.2.5 小結(jié) 30
2.2.6 小測驗 31
2.2.7 練習 31
2.3 數(shù)組 32
2.3.1 一維數(shù)組 33
2.3.2 下標運算 35
2.3.3 數(shù)組作為形參 35
2.3.4 越界錯誤 37
2.3.5 數(shù)組的問題 37
2.3.6 多維數(shù)組 38
2.3.7 小測驗 44
2.3.8 練習 45
2.4 結(jié)構(gòu) 46
2.4.1 為什么需要結(jié)構(gòu) 46
2.4.2 C風格結(jié)構(gòu) 47
2.4.3 結(jié)構(gòu)的運算 49
2.4.4 聯(lián)合 50
2.4.5 內(nèi)存中的結(jié)構(gòu) 52
2.4.6 小測驗 53
2.4.7 練習 53
2.5 過程式編程 55
2.5.1 例子：一個時間數(shù)據(jù)類型 55
2.5.2 PP對OOP 59
第3章 數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)結(jié)構(gòu)進階——C++類型 64
3.1 類 64
3.1.1 “傳統(tǒng)的”（C）結(jié)構(gòu)，OOP（C++）結(jié)構(gòu)以及類之間的區(qū)別 65
3.1.2 類聲明 65
3.1.3 例子：C++標準I/O類 66
3.2 用戶定義類型的例子：一個Time類67
3.2.1 實現(xiàn)一個類 68
3.2.2 一些現(xiàn)象 70
3.2.3 類構(gòu)造函數(shù) 72
3.2.4 復制操作——初始化和賦值 76
3.2.5 訪問函數(shù) 77
3.2.6 輸入/輸出——重載運算符——友元函數(shù) 78
3.2.7 其他操作：關系操作和前進 83
3.2.8 總結(jié)以及其他一些細節(jié) 85
3.2.9 小測驗 87
3.2.10 練習 87
3.3 作為ADT的串 88
3.3.1 串的C風格實現(xiàn) 89
3.3.2 一個串類 90
3.3.3 練習 93
3.4 C++串類型 93
3.4.1 定義和構(gòu)造函數(shù) 94
3.4.2 存儲 94
3.4.3 輸入/輸出 94
3.4.4 string流 96
3.4.5 修改符 97
3.4.6 復制符 97
3.4.7 訪問單獨的字符 98
3.4.8 查找操作 98
3.4.9 比較 99
3.4.10 string和C風格串 100
3.4.11 小測驗 100
3.4.12 練習 101
3.5 一個例子：文本編輯 101
3.5.1 對象 102
3.5.2 操作 102
3.5.3 文本編輯算法 102
3.6 數(shù)據(jù)加密（可選） 105
3.6.1 數(shù)據(jù)加密標準 107
3.6.2 公共密鑰加密 110
3.6.3 練習 113
3.7 模式匹配（可選） 114
第4章 棧 128
4.1 棧的介紹 128
4.2 設計和創(chuàng)建一個Stack類 132
4.2.1 設計一個Stack類 132
4.2.2 實現(xiàn)一個棧類 132
4.2.3 選擇數(shù)據(jù)成員 133
4.2.4 函數(shù)成員 135
4.2.5 前瞻 142
4.2.6 小測驗 142
4.2.7 練習 143
4.3 棧的兩個應用：函數(shù)調(diào)用，逆波蘭表示 144
4.3.1 在函數(shù)調(diào)用中使用棧 144
4.3.2 逆波蘭表示中棧的應用 145
4.3.3 小測驗 153
4.3.4 練習 153
第5章 隊列 158
5.1 隊列入門 158
5.1.1 例子：訓練和實踐問題 159
5.1.2 調(diào)度隊列的例子 163
5.2 基于數(shù)組的隊列實現(xiàn) 165
5.2.1 小測驗 168
5.2.2 練習 169
5.3 隊列的應用：信息中心仿真 170
5.3.1 問題分析和需求規(guī)格說明 171
5.3.2 設計 171
5.3.3 編碼和執(zhí)行 174
第6章 改進ADT——第1部分： 模板和標準容器 181
6.1 介紹：可重用性和通用性的發(fā)展 181
6.1.1 從算法到算法 182
6.1.2 從數(shù)據(jù)到容器 183
6.2 函數(shù)通用性——重載和模板 183
6.2.1 重載 184
6.2.2 函數(shù)模板 186
6.2.3 例子：顯示一個數(shù)組 189
6.3 類通用性——模板 190
6.3.1 Typedef有什么錯 190
6.3.2 類模板 190
6.3.3 一個Stack類模板 192
6.3.4 Stack類模板的另一個版本 196
6.3.5 標準C++的容器類模板 197
6.3.6 小測驗 198
6.3.7 練習 198
6.4 vector容器 198
6.4.1 定義vector對象 199
6.4.2 一些vector操作 200
6.4.3 例子：登錄計數(shù) 204
6.4.4 內(nèi)部實現(xiàn)一瞥——增加容量 207
6.4.5 對迭代器的第一次探討 209
6.4.6 一些涉及到迭代器的vector函數(shù)成員 212
6.4.7 綜合比較：vector對數(shù)組 212
6.4.8 小測驗 213
6.4.9 練習 214
6.5 多維向量 215
6.5.1 二維vector對象 216
6.5.2 二維vector操作 216
6.5.3 練習 218
6.6 其他標準容器——deque、stack和queue 218
6.6.1 STL的deque類模板 219
6.6.2 Stack類模板的一個新（但是非必需的）版本 221
6.6.3 STL的stack適配器 222
6.6.4 STL的queue適配器 224
6.6.5 小測驗 224
6.7 bitsets（可選） 224
6.7.1 bitset對象的聲明 224
6.7.2 bitset操作 225
6.7.3 使用bitset實現(xiàn)集合 226
6.7.4 例子：使用埃拉托色尼（Eratoshenes）篩尋找素數(shù) 228
6.7.5 練習 230
6.8 valarrays（可選） 230
6.8.1 valarray對象的聲明 231
6.8.2 valarray操作 231
6.8.3 slices、masks以及間接數(shù)組 232
6.8.4 練習 233
第7章 改進ADT——第2部分：遞歸，算法分析，以及標準算法 238
7.1 遞歸 238
7.1.1 例子：遞歸的求冪和求階乘函數(shù)238
7.1.2 糟糕遞歸的例子：Fibonacci數(shù)字242
7.1.3 例子：折半搜索 245
7.1.4 例子：回文檢查程序 246
7.1.5 小測驗 248
7.1.6 練習 248
7.2 遞歸的例子：Hanoi塔；分析 251
7.2.1 Hanoi塔 251
7.2.2 分析 253
7.2.3 練習 258
7.3 實現(xiàn)遞歸 259
7.4 算法效率 261
7.4.1 小測驗 271
7.4.2 練習 271
7.5 C++中的標準算法 272
7.5.1 例子：STL的sort算法 272
7.5.2 STL算法的例子 275
7.5.3 <numeric>庫中的算法 276
7.5.4 例子：花樣滑冰評判 277
7.5.5 小測驗 278
7.6 算法正確性證明 278
7.6.1 例子：計算平均值 278
7.6.2 例子：遞歸求冪函數(shù) 280
7.6.3 總結(jié) 280
7.6.4 練習 281
第8章 列表 287
8.1 列表的順序存儲實現(xiàn) 287
8.1.1 存儲結(jié)構(gòu) 287
8.1.2 操作的實現(xiàn) 288
8.1.3 小測驗 290
8.1.4 練習 290
8.2 對鏈表的介紹 290
8.2.1 它們是什么 291
8.2.2 實現(xiàn)基本列表操作 291
8.2.3 小結(jié) 294
8.2.4 小測驗 295
8.2.5 練習 295
8.3 基于數(shù)組的鏈表實現(xiàn) 296
8.3.1 節(jié)點結(jié)構(gòu) 296
8.3.2 存儲池管理 298
8.3.3 練習 300
8.4 C++中的指針 301
8.4.1 指針 301
8.4.2 基本指針操作 303
8.4.3 指針的其他用法 309
8.4.4 小測驗 310
8.4.5 練習 310
8.5 運行時分配和釋放 311
8.5.1 New操作——運行時數(shù)組 312
8.5.2 delete操作 314
8.5.3 類中的運行時分配——析構(gòu)函數(shù)、復制構(gòu)造函數(shù)和賦值操作符 317
8.5.4 最后一點 325
8.5.5 小測驗 327
8.5.6 練習 328
8.6 在C++中基于指針來實現(xiàn)鏈表 328
8.6.1 節(jié)點結(jié)構(gòu) 329
8.6.2 LinkedList的數(shù)據(jù)成員 330
8.6.3 LinkedList的函數(shù)成員 330
8.6.4 練習 331
8.7 標準list類模板 334
8.7.1 List與其他容器類的比較 334
8.7.2 迭代器 334
8.7.3 基本list操作 334
8.7.4 例子：互聯(lián)網(wǎng)地址 338
8.7.5 小測驗 340
8.7.6 練習 340
第9章 其他鏈表結(jié)構(gòu) 346
9.1 單向鏈表的某些變種 346
9.1.1 鏈式棧和鏈式隊列 346
9.1.2 帶頭節(jié)點或尾節(jié)點的鏈表 347
9.1.3 循環(huán)鏈表 348
9.1.4 小測驗 350
9.1.5 練習 350
9.2 稀疏矩陣的鏈式實現(xiàn) 351
練習 355
9.3 哈希表 356
9.3.1 哈希函數(shù) 356
9.3.2 沖突處理策略 356
9.3.3 改進 357
9.3.4 小測驗 358
9.3.5 練習 359
9.4 雙向鏈表和標準的C++鏈表 359
9.4.1 雙向鏈表 359
9.4.2 對C++中列表的內(nèi)部一瞥 360
9.4.3 應用：長整數(shù)運算 363
9.4.4 練習 367
9.5 其他多鏈列表 368
9.5.1 多序列表 368
9.5.2 稀疏矩陣 368
9.5.3 廣義表 370
9.5.4 練習 372
第10章 二叉樹 377
10.1 線性查找和折半查找的復習 377
10.1.1 線性查找 377
10.1.2 折半查找 378
10.1.3 練習 380
10.2 二叉樹的介紹 381
10.2.1 樹的定義和例子 381
10.2.2 二叉樹的數(shù)組表示 382
10.2.3 二叉樹的鏈表表示 383
10.3 二叉查找樹 385
10.3.1 對BST的查找 385
10.3.2 在BST中插入項 386
10.3.3 例子：計算機登錄驗證 388
10.3.4 不平衡（Lopsidedness）問題391
10.3.5 小測驗 392
10.3.6 練習 392
10.4 作為遞歸數(shù)據(jù)結(jié)構(gòu)的二叉樹 392
10.4.1 遍歷 393
10.4.2 遞歸查找 396
10.4.3 遞歸插入 397
10.4.4 刪除 397
10.4.5 小測驗 402
10.4.6 練習 402
10.5 二叉樹的應用：哈夫曼編碼 404
10.5.1 變長碼 404
10.5.2 立刻可解碼性 405
10.5.3 哈夫曼編碼 405
10.5.4 練習 412
第11章 排序 417
11.1 某些計算時間為O(n2)的排序方法 417
11.1.1 選擇排序 417
11.1.2 交換排序 419
11.1.3 排序算法的性能比較 423
11.1.4 間接排序 424
11.1.5 小測驗 424
11.1.6 練習 424
11.2 堆和堆排序 426
11.2.1 堆 426
11.2.2 堆的基本操作 427
11.2.3 STL中的堆算法 430
11.2.4 堆和優(yōu)先級隊列 432
11.2.5 小測驗 434
11.2.6 練習 434
11.3 快速排序 436
11.3.1 拆分操作 436
11.3.2 快速排序 438
11.3.3 改進 441
11.3.4 小測驗 441
11.3.5 練習 441
11.4 歸并排序 442
11.4.1 歸并列表 443
11.4.2 折半歸并排序 444
11.4.3 自然歸并排序 445
11.4.4 小測驗 447
11.4.5 練習 448
第12章 OOP和ADT 452
12.1 OOP和ADTs的簡要歷史和概覽 452
12.1.1 封裝性 452
12.1.2 繼承性 453
12.1.3 多態(tài)性和動態(tài)聯(lián)編 453
12.1.4 小測驗 454
12.2 繼承和面向?qū)ο笤O計 454
12.2.1 從OCD到OOD 454
12.2.2 OOD的第1個例子：許可證455
12.2.3 類之間的is-a、has-a和uses-a關系 459
12.2.4 OOD的第2個例子：工資 461
12.2.5 派生類中的操作 463
12.2.6 派生類中的構(gòu)造函數(shù) 463
12.2.7 OOD的第3個例子：有限棧 465
12.2.8 OOD的第4個例子：scrolls468
12.2.9 小測驗 469
12.2.10 練習 469
12.3 多態(tài)性、虛擬函數(shù)和ADTs 470
12.3.1 聯(lián)編問題 470
12.3.2 虛擬函數(shù)和動態(tài)聯(lián)編 472
12.3.3 例子：棧、有限棧和Scroll 473
12.3.4 純虛擬函數(shù)和抽象類 476
12.3.5 小測驗 478
12.3.6 練習 478
12.4 異構(gòu)數(shù)據(jù)結(jié)構(gòu) 478
12.4.1 構(gòu)建異構(gòu)數(shù)據(jù)結(jié)構(gòu) 479
12.4.2 虛擬函數(shù)的必要性 480
第13章 樹 483
13.1 線索化二叉查找樹 483
13.1.1 小測驗 485
13.1.2 練習 486
13.2 平衡樹：AVL樹 486
13.2.1 例子：州簡稱的BST 487
13.2.2 基本的重新平衡旋轉(zhuǎn)操作 491
13.2.3 小測驗 493
13.2.4 練習 494
13.3 2-3-4樹、紅—黑樹、B-樹和其他樹494
13.3.1 2-3-4樹 495
13.3.2 紅—黑樹 498
13.3.3 B-樹 501
13.3.4 用二叉樹來表示樹和森林 502
13.3.5 小測驗 503
13.3.6 練習 503
13.4 STL中的關聯(lián)容器——map（可選） 504
小測驗 507
第14章 圖和有向圖 509
14.1 有向圖 509
14.1.1 鄰接矩陣表示 510
14.1.2 鄰接表表示 511
14.1.3 小測驗 512
14.1.4 練習 513
14.2 搜索和遍歷有向圖 515
14.2.1 深度優(yōu)先搜索 516
14.2.2 廣度優(yōu)先搜索 516
14.2.3 遍歷和最短路徑問題 517
14.2.4 NP完全性問題 523
14.2.5 小測驗 524
14.2.6 練習 524
14.3 圖 525
14.3.1 鄰接矩陣和鄰接表表示 526
14.3.2 邊列表表示 526
14.3.3 連通性 527
14.3.4 小測驗 531
14.3.5 練習 532
附錄A ASCII字符集 536
附錄B 數(shù)制系統(tǒng) 538
練習 539
附錄C 基本C++ 542
C1 C++程序結(jié)構(gòu) 542
C2 編譯器命令 542
C3 標準庫 543
C4 注釋 545
C5 標識符和關鍵字 545
C6 基本數(shù)據(jù)類型 547
C7 常量 548
C8 聲明 548
C9 運算符和表達式 548
C10 控制結(jié)構(gòu) 552
C11 函數(shù) 556
C12 對象的生命周期、作用域和名字空間 560
C13 文件 562
附錄D 其他C++特性 566
D1 數(shù)組、結(jié)構(gòu)和聯(lián)合 566
D2 流操作 567
D3 串操作 570
D4 異常 575
D5 關于函數(shù)模板的更多信息 577
D6 指針的其他應用 578
附錄E 小測驗答案 583
索引 594