數(shù)據(jù)結(jié)構(gòu)與算法分析-C++語(yǔ)言描述（第2版）

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