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

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