C++數據結構導引（國外經典教材計算機科學與技術）

第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 函數YearSum()的設計 5
1.2.5 函數DisplayTable()的設計 6
1.2.6 關于算法的一些最后說明 7
1.3 編碼 10
1.4 測試、執(zhí)行和調試 14
1.5 維護 18
1.5.1 小測驗 18
1.5.2 練習 19
第2章 數據結構入門和抽象數據類型——C風格類型 21
2.1 數據結構、抽象數據類型和實現 21
2.2 簡單數據類型 24
2.2.1 Boolean數據 24
2.2.2 Character數據 25
2.2.3 整型數據 26
2.2.4 實數數據 28
2.2.5 小結 30
2.2.6 小測驗 31
2.2.7 練習 31
2.3 數組 32
2.3.1 一維數組 33
2.3.2 下標運算 35
2.3.3 數組作為形參 35
2.3.4 越界錯誤 37
2.3.5 數組的問題 37
2.3.6 多維數組 38
2.3.7 小測驗 44
2.3.8 練習 45
2.4 結構 46
2.4.1 為什么需要結構 46
2.4.2 C風格結構 47
2.4.3 結構的運算 49
2.4.4 聯合 50
2.4.5 內存中的結構 52
2.4.6 小測驗 53
2.4.7 練習 53
2.5 過程式編程 55
2.5.1 例子：一個時間數據類型 55
2.5.2 PP對OOP 59
第3章 數據結構和抽象數據結構進階——C++類型 64
3.1 類 64
3.1.1 “傳統(tǒng)的”（C）結構，OOP（C++）結構以及類之間的區(qū)別 65
3.1.2 類聲明 65
3.1.3 例子：C++標準I/O類 66
3.2 用戶定義類型的例子：一個Time類67
3.2.1 實現一個類 68
3.2.2 一些現象 70
3.2.3 類構造函數 72
3.2.4 復制操作——初始化和賦值 76
3.2.5 訪問函數 77
3.2.6 輸入/輸出——重載運算符——友元函數 78
3.2.7 其他操作：關系操作和前進 83
3.2.8 總結以及其他一些細節(jié) 85
3.2.9 小測驗 87
3.2.10 練習 87
3.3 作為ADT的串 88
3.3.1 串的C風格實現 89
3.3.2 一個串類 90
3.3.3 練習 93
3.4 C++串類型 93
3.4.1 定義和構造函數 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 數據加密（可選） 105
3.6.1 數據加密標準 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 實現一個棧類 132
4.2.3 選擇數據成員 133
4.2.4 函數成員 135
4.2.5 前瞻 142
4.2.6 小測驗 142
4.2.7 練習 143
4.3 棧的兩個應用：函數調用，逆波蘭表示 144
4.3.1 在函數調用中使用棧 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 調度隊列的例子 163
5.2 基于數組的隊列實現 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 從數據到容器 183
6.2 函數通用性——重載和模板 183
6.2.1 重載 184
6.2.2 函數模板 186
6.2.3 例子：顯示一個數組 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 例子：登錄計數 204
6.4.4 內部實現一瞥——增加容量 207
6.4.5 對迭代器的第一次探討 209
6.4.6 一些涉及到迭代器的vector函數成員 212
6.4.7 綜合比較：vector對數組 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實現集合 226
6.7.4 例子：使用埃拉托色尼（Eratoshenes）篩尋找素數 228
6.7.5 練習 230
6.8 valarrays（可選） 230
6.8.1 valarray對象的聲明 231
6.8.2 valarray操作 231
6.8.3 slices、masks以及間接數組 232
6.8.4 練習 233
第7章 改進ADT——第2部分：遞歸，算法分析，以及標準算法 238
7.1 遞歸 238
7.1.1 例子：遞歸的求冪和求階乘函數238
7.1.2 糟糕遞歸的例子：Fibonacci數字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 實現遞歸 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 例子：遞歸求冪函數 280
7.6.3 總結 280
7.6.4 練習 281
第8章 列表 287
8.1 列表的順序存儲實現 287
8.1.1 存儲結構 287
8.1.2 操作的實現 288
8.1.3 小測驗 290
8.1.4 練習 290
8.2 對鏈表的介紹 290
8.2.1 它們是什么 291
8.2.2 實現基本列表操作 291
8.2.3 小結 294
8.2.4 小測驗 295
8.2.5 練習 295
8.3 基于數組的鏈表實現 296
8.3.1 節(jié)點結構 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操作——運行時數組 312
8.5.2 delete操作 314
8.5.3 類中的運行時分配——析構函數、復制構造函數和賦值操作符 317
8.5.4 最后一點 325
8.5.5 小測驗 327
8.5.6 練習 328
8.6 在C++中基于指針來實現鏈表 328
8.6.1 節(jié)點結構 329
8.6.2 LinkedList的數據成員 330
8.6.3 LinkedList的函數成員 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 例子：互聯網地址 338
8.7.5 小測驗 340
8.7.6 練習 340
第9章 其他鏈表結構 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 稀疏矩陣的鏈式實現 351
練習 355
9.3 哈希表 356
9.3.1 哈希函數 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++中列表的內部一瞥 360
9.4.3 應用：長整數運算 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 二叉樹的數組表示 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 作為遞歸數據結構的二叉樹 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)聯編 453
12.1.4 小測驗 454
12.2 繼承和面向對象設計 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 派生類中的構造函數 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)性、虛擬函數和ADTs 470
12.3.1 聯編問題 470
12.3.2 虛擬函數和動態(tài)聯編 472
12.3.3 例子：棧、有限棧和Scroll 473
12.3.4 純虛擬函數和抽象類 476
12.3.5 小測驗 478
12.3.6 練習 478
12.4 異構數據結構 478
12.4.1 構建異構數據結構 479
12.4.2 虛擬函數的必要性 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 基本的重新平衡旋轉操作 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中的關聯容器——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 數制系統(tǒng) 538
練習 539
附錄C 基本C++ 542
C1 C++程序結構 542
C2 編譯器命令 542
C3 標準庫 543
C4 注釋 545
C5 標識符和關鍵字 545
C6 基本數據類型 547
C7 常量 548
C8 聲明 548
C9 運算符和表達式 548
C10 控制結構 552
C11 函數 556
C12 對象的生命周期、作用域和名字空間 560
C13 文件 562
附錄D 其他C++特性 566
D1 數組、結構和聯合 566
D2 流操作 567
D3 串操作 570
D4 異常 575
D5 關于函數模板的更多信息 577
D6 指針的其他應用 578
附錄E 小測驗答案 583
索引 594