數(shù)據(jù)結(jié)構(gòu)與算法（C++版 第2版）

目錄
第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)的概念和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性1
1.2數(shù)據(jù)結(jié)構(gòu)的基本概念2
1.2.1數(shù)據(jù)2
1.2.2數(shù)據(jù)元素和數(shù)據(jù)項2
1.2.3數(shù)據(jù)結(jié)構(gòu)3
1.3抽象數(shù)據(jù)類型及其實現(xiàn)4
1.3.1數(shù)據(jù)類型4
1.3.2抽象數(shù)據(jù)類型4
1.4算法和算法分析4
1.4.1算法4
1.4.2算法分析5
1.5實例研究: 生命游戲7
1.6深入學(xué)習(xí)導(dǎo)讀13
1.7習(xí)題13

第2章線性表14
2.1線性表的邏輯結(jié)構(gòu)14
2.2線性表的順序存儲結(jié)構(gòu)16
2.3線性表的鏈式存儲結(jié)構(gòu)23
2.3.1單鏈表23
2.3.2循環(huán)鏈表32
2.3.3雙向鏈表35
2.3.4在鏈表結(jié)構(gòu)中保存當前位置和元素個數(shù)39
2.4實例研究: 計算任意大整數(shù)的階乘42
2.5深入學(xué)習(xí)導(dǎo)讀45
2.6習(xí)題45

第3章棧和隊列46
3.1棧46
3.1.1棧的基本概念46
3.1.2順序棧47
3.1.3鏈式棧52
3.2隊列59
3.2.1隊列的基本概念59
3.2.2鏈隊列60
3.2.3循環(huán)隊列——隊列的順序存儲結(jié)構(gòu)65
3.2.4隊列應(yīng)用——顯示二項式(a+b)i的系數(shù)70
3.3優(yōu)先隊列71
3.4實例研究: 表達式求值75
3.5深入學(xué)習(xí)導(dǎo)讀79
3.6習(xí)題79

第4章串80
4.1串類型的定義80
4.2字符串的實現(xiàn)81
4.3字符串模式匹配算法86
4.3.1簡單字符串模式匹配算法86
4.3.2首尾字符串模式匹配算法88
4.3.3KMP字符串模式匹配算法88
4.4實例研究: 文本編輯94
4.5深入學(xué)習(xí)導(dǎo)讀103
4.6習(xí)題103

第5章數(shù)組和廣義表105
5.1數(shù)組105
5.1.1數(shù)組的基本概念105
5.1.2數(shù)組的順序表105
5.1.3數(shù)組的類模板定義107
5.2矩陣111
5.2.1矩陣的定義和操作111
5.2.2特殊矩陣113
5.2.3稀疏矩陣118
5.3廣義表130
5.3.1基本概念130
5.3.2廣義表的存儲結(jié)構(gòu)132
5.4實例研究: 穩(wěn)定伴侶問題142
5.5深入學(xué)習(xí)導(dǎo)讀145
5.6習(xí)題146

第6章樹和二叉樹147
6.1樹的基本概念147
6.1.1樹的定義147
6.1.2基本術(shù)語147
6.2二叉樹149
6.2.1二叉樹的定義149
6.2.2二叉樹的性質(zhì)151
6.2.3二叉樹的存儲結(jié)構(gòu)153
6.3二叉樹遍歷162
6.3.1遍歷的定義162
6.3.2遍歷算法163
6.3.3二叉樹遍歷應(yīng)用舉例169
6.4線索二叉樹174
6.4.1線索的概念174
6.4.2線索二叉樹的實現(xiàn)176
6.5樹和森林的實現(xiàn)184
6.5.1樹的存儲表示184
6.5.2樹的顯示191
6.5.3森林的存儲表示192
6.5.4樹和森林的遍歷197
6.5.5將樹和森林與二叉樹相互轉(zhuǎn)換199
6.6哈夫曼樹與哈夫曼編碼202
6.6.1哈夫曼樹的基本概念202
6.6.2哈夫曼樹構(gòu)造算法203
6.6.3哈夫曼編碼204
6.6.4哈夫曼樹的實現(xiàn)205
6.7樹的計數(shù)209
6.8樹在等價關(guān)系上的應(yīng)用212
6.9實例研究: 哈夫曼壓縮算法216
6.10深入學(xué)習(xí)導(dǎo)讀221
6.11習(xí)題222

第7章圖223
7.1圖的定義和術(shù)語223
7.2圖的存儲表示227
7.2.1鄰接矩陣227
7.2.2鄰接表232
7.3圖的遍歷240
7.3.1深度優(yōu)先搜索240
7.3.2廣度優(yōu)先搜索242
7.4連通無向網(wǎng)的最小代價生成樹244
7.4.1Prim算法244
7.4.2Kruskal算法247
7.5有向無環(huán)圖及應(yīng)用250
7.5.1拓撲排序251
7.5.2關(guān)鍵路徑253
7.6最短路徑257
7.6.1單源點最短路徑問題258
7.6.2所有頂點之間的最短路徑261
7.7實例研究: 周游世界問題——哈密頓圈263
7.8深入學(xué)習(xí)導(dǎo)讀265
7.9習(xí)題265

第8章查找267
8.1查找的基本概念267
8.2靜態(tài)表的查找267
8.2.1順序查找267
8.2.2有序表的查找268
8.3動態(tài)查找表272
8.3.1二叉排序樹272
8.3.2平衡二叉樹282
8.3.3B樹和B+樹306
8.4哈希表309
8.4.1哈希表的概念309
8.4.2構(gòu)造哈希函數(shù)的方法309
8.4.3處理沖突的方法309
8.4.4哈希表的實現(xiàn)311
8.5實例研究: 查找3個數(shù)組的最小共同元素316
8.6深入學(xué)習(xí)導(dǎo)讀317
8.7習(xí)題317

第9章排序319
9.1概述319
9.2插入排序320
9.2.1直接插入排序320
9.2.2Shell排序321
9.3交換排序323
9.3.1冒泡排序323
9.3.2快速排序324
9.4選擇排序327
9.4.1簡單選擇排序327
9.4.2堆排序328
9.5歸并排序332
9.6基數(shù)排序336
9.6.1多關(guān)鍵字排序336
9.6.2基數(shù)排序337
9.7各種內(nèi)部排序方法討論339
9.8外部排序341
9.8.1外部排序基礎(chǔ)341
9.8.2外部排序的方法342
9.9實例研究: 用堆實現(xiàn)優(yōu)先隊列343
9.10深入學(xué)習(xí)導(dǎo)讀346
9.11習(xí)題346

第10章文件348
10.1主存儲器和輔助存儲器348
10.2各種常用文件結(jié)構(gòu)348
10.2.1順序文件348
10.2.2索引文件349
10.2.3哈希文件350
10.3實例研究350
10.3.1VSAM文件350
10.3.2多關(guān)鍵字文件351
10.4深入學(xué)習(xí)導(dǎo)讀353
10.5習(xí)題353

第11章算法設(shè)計與分析354
11.1算法設(shè)計354
11.1.1遞歸算法354
11.1.2分治算法356
11.1.3動態(tài)規(guī)劃算法357
11.1.4貪婪算法358
11.1.5回溯法359
11.1.6分支限界法361
11.2算法分析363
11.2.1遞歸分析363
11.2.2利用生成函數(shù)進行分析364
11.3實例研究: 圖著色問題366
11.4深入學(xué)習(xí)導(dǎo)讀368
11.5習(xí)題368

參考文獻370

附錄A調(diào)和級數(shù)371

附錄B泊松分布372

附錄C配套軟件包文件索引373

附錄D主流C++開發(fā)環(huán)境的使用方法379