數(shù)據(jù)結構與算法分析-C++語言描述（第2版）

第1章  軟件開發(fā)    1
1.1  問題分析和需求規(guī)格說明    3
1.2  設計    5
1.2.1  自頂向下設計    5
1.2.2  面向對象設計    7
1.2.3  小規(guī)模設計    9
1.3  編碼    15
1.4  測試、運行和調試    27
1.5  維護    34
1.6  本章小結    36
第2章  抽象數(shù)據(jù)類型入門    40
2.1  對ADT及其實現(xiàn)的第一瞥    40
2.2  C++的簡單數(shù)據(jù)類型    41
2.2.1  整型數(shù)據(jù)    42
2.2.2  實型數(shù)據(jù)    46
2.2.3  字符數(shù)據(jù)    49
2.4.4  布爾數(shù)據(jù)    50
2.3  程序員定義的數(shù)據(jù)類型    53
2.3.1  Typedefs    53
2.3.2  枚舉    53
2.3.3  類    55
2.4  指針    56
2.4.1  聲明和初始化指針    57
2.4.2  基本指針操作    60
2.4.3  動態(tài)內存分配——new操作    64
2.4.4  關于引用形參的注釋    65
2.5  本章小結    68
第3章  數(shù)據(jù)結構和抽象數(shù)據(jù)類型    73
3.1  數(shù)據(jù)結構，抽象數(shù)據(jù)類型和實現(xiàn)    73
3.2  靜態(tài)數(shù)組    77
3.2.1  一維靜態(tài)數(shù)組    78
3.2.2  下標運算    81
3.2.3  數(shù)組作為形參    82
3.2.4  越界錯誤    83
3.2.5  數(shù)組的問題    86
3.3  多維數(shù)組    88
3.3.1  二維數(shù)組    88
3.3.2  高維數(shù)組    89
3.3.3  數(shù)組的數(shù)組聲明    91
3.3.4  多維數(shù)組作函數(shù)參數(shù)    95
3.4  動態(tài)數(shù)組    97
3.4.1  new操作——動態(tài)數(shù)組    98
3.4.2  指針的其他用法    110
3.5  C風格結構（可選）    112
指向結構的指針    116
3.6  過程式編程    117
過程式編程的例子    118
3.7  本章小結    123
第4章  OOP和ADT進階——類    129
4.1  過程式編程vs.面向對象編程    129
4.2  類    130
4.2.1 “傳統(tǒng)的”（C）結構和OOP
（C++）結構以及類之間的
區(qū)別    131
4.2.2  類聲明    131
4.3  例子：用戶定義的Time類的
第一個版本    135
4.3.1  為什么不使所有成員都
公有化    137
4.3.2  實現(xiàn)一個類    138
4.3.3  一些現(xiàn)象    141
4.4  類構造函數(shù)    142
4.5  其他類操作    150
4.5.1  復制操作——初始化和
賦值    150
4.5.2  訪問函數(shù)和更動函數(shù)    151
4.5.3  重載運算符    153
4.5.4  重載輸入/輸出運算符    154
4.5.5  其他操作：前進和關系
操作    161
4.5.6  總結以及其他一些細節(jié)    163
4.5.7  指向類對象的指針    167
4.5.8  this指針    168
4.6  本章小結    171
第5章  標準C++輸入/輸出和字
符串類    176
5.1  C++標準I/O類    177
5.1.1  istream類    178
5.1.2  ostream類    182
5.1.3  文件I/O：ifstream和
ofstream類    186
5.1.4  I/O類層次    188
5.2  C++ String類型    192
5.2.1  C風格的字符串    193
5.2.2  一個字符串類    195
5.2.3  C++ String類    196
5.2.4  String流    204
5.3  案例學習：文本編輯    208
5.4  模式匹配介紹（可選）    216
5.5  數(shù)據(jù)加密介紹（可選）    219
5.5.1  數(shù)據(jù)加密標準（Data Encryption
Standard）    222
5.5.2  公共密鑰加密（Public-Key
Encryption）    222
5.6  本章小結    224
第6章  列表    228
6.1  作為ADT的列表    229
設計和創(chuàng)建一個列表類    230
6.2  基于數(shù)組的列表實現(xiàn)    231
6.2.1  選擇存儲結構    231
6.2.2  實現(xiàn)操作    232
6.2.3  一個使用靜態(tài)數(shù)組存儲的
列表類    234
6.3  使用動態(tài)分配的基于數(shù)組實現(xiàn)的
列表    242
6.3.1  類中的動態(tài)分配——析構函數(shù)、復制構造函數(shù)和賦值運算符    246
6.3.2  最后一點    253
6.4  對鏈表的介紹    257
6.4.1  它們是什么    257
6.4.2  實現(xiàn)基本列表操作    258
6.4.3  小結    262
6.5  在C++中基于指針來實現(xiàn)鏈表    264
6.5.1  節(jié)點結構    264
6.5.2  鏈表實現(xiàn)中的數(shù)據(jù)成員    266
6.5.3  鏈表實現(xiàn)中的函數(shù)成員    267
6.6  基于數(shù)組的鏈表實現(xiàn)    271
6.6.1  節(jié)點結構    272
6.6.2  存儲池管理    274
6.7  本章小結    276
第7章  棧    280
7.1  棧的介紹    281
7.2  設計和創(chuàng)建一個Stack類——
基于數(shù)組    285
7.2.1  選擇存儲結構    285
7.2.2  實現(xiàn)操作    288
7.2.3  實現(xiàn)pop操作的算法    290
7.2.4  完整的Stack類    290
7.2.5  使用動態(tài)數(shù)組存儲棧元素296
7.2.6  前瞻    309
7.3  鏈式棧    312
7.3.1  選擇存儲結構    313
7.3.2  實現(xiàn)操作    314
7.3.3  完整的Stack類：鏈表
版本    317
7.4  棧在函數(shù)調用中的使用    324
7.5  案例學習：后綴（RPN）表示329
7.5.1  計算后綴表達式    330
7.5.2  將中綴表達式轉換成后綴
表達式    331
7.6  本章小節(jié)    341
第8章  隊列    345
8.1  隊列入門    345
8.2  設計和創(chuàng)建一個Queue類——
基于數(shù)組    353
8.2.1  使用靜態(tài)數(shù)組存儲隊列
元素    356
8.2.2  使用動態(tài)數(shù)組存儲隊列
元素    361
8.3  鏈式隊列    365
8.3.1  一種自然的鏈表實現(xiàn)    365
8.3.2  使用循環(huán)鏈表    374
8.4  隊列的應用：緩沖區(qū)和調度376
8.5  案例學習：信息中心仿真    379
8.5.1  問題分析和需求規(guī)格說明380
8.5.2  創(chuàng)建一個Simulation類    380
8.5.3  Time類和Call類    389
8.6  本章小結    390
第9章  ADT實現(xiàn)：模板和標準容器393
9.1  介紹：可重用性和通用性的發(fā)展394
9.1.1  從算法到算法    394
9.1.2  從數(shù)據(jù)到容器    396
9.2  函數(shù)通用性——重載和模板396
9.2.1  重載    397
9.2.2  函數(shù)模板    399
9.2.3  另一個例子：顯示一個
數(shù)組    403
9.3  類通用性——模板    404
9.3.1  Typedef有什么錯    404
9.3.2  類模板    405
9.3.3  Stack類模板的另一個版本417
9.3.4  對標準C++容器類模板的
快速一瞥    418
9.4  vector容器    420
9.4.1  定義vector對象    421
9.4.2  一些vector操作    423
9.4.3  內部實現(xiàn)一瞥——增加
容量    427
9.4.4  對迭代器的第一次探討    430
9.4.5  一些牽涉到迭代器的vector
函數(shù)成員    433
9.4.6  綜合比較：vector對數(shù)組434
9.5  案例學習：計算機系統(tǒng)登錄統(tǒng)計438
9.6  多維vector（可選）    443
9.6.1  二維vector對象    443
9.6.2  二維vector操作    444
9.7  其他標準容器——deque、stack以及queue    447
9.7.1  STL的deque類模板    447
9.7.2  我們的stack類模板的一個
新（但是非必須的）版本    450
9.7.3  STL的stack適配器    452
9.7.4  STL的queue適配器    453
9.8  Bitset和Valarray（可選）454
9.8.1  Bitset    454
9.8.2  Valarray    456
9.8.3  Slics、Mask、以及間接
數(shù)組    458
9.9  本章小結    459
第10章  ADT實現(xiàn)--遞歸、算法分析
以及標準算法    464
10.1  遞歸    464
10.1.1  遞歸的例子    465
10.1.2  遞歸函數(shù)的編碼    466
10.1.3  糟糕遞歸的例子：Fibonacci
數(shù)字    468
10.1.4  例子：折半查找    470
10.1.5  例子：回文檢查程序    473
10.2  遞歸的例子：Hanoi塔；分析478
10.2.1  Hanoi塔    478
10.2.2  分析    481
10.3  實現(xiàn)遞歸    485
10.4  算法效率    489
10.5  C++中的標準算法    500
10.5.1  例：STL的sort算法    500
10.5.2  STL算法的例子    505
10.5.3  <numeric>庫中的算法    506
10.5.4  例：花樣滑冰評判    507
10.6  算法正確性證明(可選)    508
10.6.1  例：計算平均值    509
10.6.2  例：遞歸求冪函數(shù)    510
10.6.3  總結    511
10.7  本章小節(jié)    513
第11章  其他鏈表結構    519
11.1  單向鏈表的某些變種    519
11.1.1  帶頭節(jié)點的鏈表    519
11.1.2  循環(huán)鏈表    522
11.2  稀疏多項式的鏈式實現(xiàn)    526
11.3  雙向鏈表和標準C++list    534
11.3.1  雙向鏈表    534
11.3.2  標準list類模板    536
11.3.3  例：互聯(lián)網(wǎng)地址    542
11.3.4  對C++中l(wèi)ist的內部一瞥546
11.4  案例學習：長整數(shù)運算    551
11.4.1  問題    551
11.4.2  設計    551
11.4.3  實現(xiàn)    553
11.5  其他鏈列表    560
11.5.1  多序列表    560
11.5.2  稀疏矩陣    561
11.5.3  廣義表    563
11.6  本章小結    566
第12章  二叉樹和散列表    571
12.1  線性查找和折半查找的復習571
12.1.1  線性查找    572
12.1.2  折半查找    573
12.2  二叉樹的介紹    576
12.2.1  樹的定義    577
12.2.2  二叉樹的一些例子    578
12.2.3  二叉樹的數(shù)組表示    579
12.2.4  二叉樹的鏈表表示    581
12.3  作為遞歸數(shù)據(jù)結構的二叉樹583
12.4  二叉查找樹    589
12.4.1  BST的實現(xiàn)    590
12.4.2  遍歷BST    592
12.4.3  BST的查找    596
12.4.4  BST中的插入操作    599
12.4.5  從BST中刪除一個節(jié)點    602
12.4.6  不平衡（Lopsidedness）
問題    612
12.5  案例學習：計算機登錄驗證616
12.5.1  問題    616
12.5.2  設計    616
12.5.3  編碼    617
12.6  線索化二叉查找樹（可選）620
12.7  散列表    624
12.7.1  散列函數(shù)    625
12.7.2  沖突處理策略    626
12.7.3  改進    627
12.8  本章小結    631
第13章  排序    636
13.1  某些計算時間為O(n2)的排序
方法    637
13.1.1  選擇排序    637
13.1.2  交換排序    639
13.1.3  插入排序    641
13.1.4  排序算法的性能比較    643
13.1.5  間接排序    644
13.2  堆、堆排序和優(yōu)先隊列    647
13.2.1  堆    648
13.2.2  堆的基本操作    649
13.2.3  堆排序    652
13.2.4  STL中的堆算法    655
13.2.5  堆和優(yōu)先隊列    658
13.3  快速排序    662
13.3.1  拆分操作    663
13.3.2  快速排序    665
13.3.3  改進    668
13.4  歸并排序    670
13.4.1  歸并列表    670
13.4.2  折半歸并排序    672
13.4.3  自然歸并排序    674
13.5  基數(shù)排序（Radix Sort）677
13.6  本章小結    680
第14章  OOP和ADT    684
14.1  OOP和ADT的簡要歷史和概覽684
14.1.1  封裝性    685
14.1.2  繼承性    686
14.1.3  多態(tài)性和動態(tài)聯(lián)編    687
14.2  繼承和面向對象設計    688
14.2.1  第1個例子：許可證    689
14.2.2  公有、私有和保護域    693
14.2.3  派生類的形式    693
14.2.4  類之間的Is-a、Has-a和
Uses-a關系    694
14.3  創(chuàng)建派生類    696
14.3.1  派生類構造函數(shù)    697
14.3.2  訪問繼承的數(shù)據(jù)成員    697
14.3.3  復用操作    698
14.3.4  例子：棧和有限棧    700
14.4  案例學習：工資    703
14.4.1  問題    703
14.4.2  設計    703
14.5  多態(tài)性、虛函數(shù)和ADT    711
14.5.1  為什么需要多態(tài)性：聯(lián)編
問題    711
14.5.2  虛函數(shù)和動態(tài)聯(lián)編    713
14.5.3  例1：使用句柄    716
14.5.4  例2：棧和有限棧    717
14.5.5  純虛函數(shù)和抽象類    720
14.6  案例學習：異構數(shù)據(jù)結構722
14.6.1  虛函數(shù)的必要性    723
14.7  本章小結    726
第15章  樹    729
15.1  案例學習：哈夫曼編碼    729
15.1.1  變長碼    730
15.1.2  立刻可解碼性    730
15.1.3  哈夫曼編碼    731
15.2  平衡樹：AVL樹    735
15.2.1  例子：州簡稱的BST    735
15.2.2  基本的重新平衡旋轉
操作    743
15.3  2-3-4樹、紅-黑樹、B-樹和
其他樹    748
15.3.1  2-3-4樹    750
15.3.2  紅-黑樹    756
15.3.3  B-樹    760
15.3.4  用二叉樹來表示樹和
森林    761
15.4  STL中的關聯(lián)容器——
map（可選）    765
15.5  本章小結    771
第16章  圖和有向圖    773
16.1  有向圖    773
16.1.1  鄰接矩陣表示（Adjacency-
Matrix Representation）    775
16.1.2  鄰接表表示（Adjacency-
List Representation）    776
16.2  搜索和遍歷有向圖    781
16.2.1  深度優(yōu)先搜索    782
16.2.2  廣度優(yōu)先搜索    783
16.2.3  遍歷和最短路經(jīng)問題    785
16.2.4  NP完全性問題    794
16.3  圖    796
16.3.1  鄰接矩陣和鄰接表表示797
16.3.2  邊列表表示    798
16.3.3  連通性    799
16.4  本章小結    810
附錄A  ASCII字符集    812
附錄B  小測驗答案    814