數(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ù)項(xiàng)2
1.2.3數(shù)據(jù)結(jié)構(gòu)3
1.3抽象數(shù)據(jù)類(lèi)型及其實(shí)現(xiàn)4
1.3.1數(shù)據(jù)類(lèi)型4
1.3.2抽象數(shù)據(jù)類(lèi)型4
1.4算法和算法分析4
1.4.1算法4
1.4.2算法分析5
1.5實(shí)例研究: 生命游戲7
1.6深入學(xué)習(xí)導(dǎo)讀13
1.7習(xí)題13

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

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

第4章串80
4.1串類(lèi)型的定義80
4.2字符串的實(shí)現(xiàn)81
4.3字符串模式匹配算法86
4.3.1簡(jiǎn)單字符串模式匹配算法86
4.3.2首尾字符串模式匹配算法88
4.3.3KMP字符串模式匹配算法88
4.4實(shí)例研究: 文本編輯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ù)組的類(lèi)模板定義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廣義表的存儲(chǔ)結(jié)構(gòu)132
5.4實(shí)例研究: 穩(wěn)定伴侶問(wèn)題142
5.5深入學(xué)習(xí)導(dǎo)讀145
5.6習(xí)題146

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

第7章圖223
7.1圖的定義和術(shù)語(yǔ)223
7.2圖的存儲(chǔ)表示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ú)向網(wǎng)的最小代價(jià)生成樹(shù)244
7.4.1Prim算法244
7.4.2Kruskal算法247
7.5有向無(wú)環(huán)圖及應(yīng)用250
7.5.1拓?fù)渑判?51
7.5.2關(guān)鍵路徑253
7.6最短路徑257
7.6.1單源點(diǎn)最短路徑問(wèn)題258
7.6.2所有頂點(diǎn)之間的最短路徑261
7.7實(shí)例研究: 周游世界問(wèn)題——哈密頓圈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動(dòng)態(tài)查找表272
8.3.1二叉排序樹(shù)272
8.3.2平衡二叉樹(shù)282
8.3.3B樹(shù)和B+樹(shù)306
8.4哈希表309
8.4.1哈希表的概念309
8.4.2構(gòu)造哈希函數(shù)的方法309
8.4.3處理沖突的方法309
8.4.4哈希表的實(shí)現(xiàn)311
8.5實(shí)例研究: 查找3個(gè)數(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簡(jiǎn)單選擇排序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實(shí)例研究: 用堆實(shí)現(xiàn)優(yōu)先隊(duì)列343
9.10深入學(xué)習(xí)導(dǎo)讀346
9.11習(xí)題346

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

第11章算法設(shè)計(jì)與分析354
11.1算法設(shè)計(jì)354
11.1.1遞歸算法354
11.1.2分治算法356
11.1.3動(dòng)態(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ù)進(jìn)行分析364
11.3實(shí)例研究: 圖著色問(wèn)題366
11.4深入學(xué)習(xí)導(dǎo)讀368
11.5習(xí)題368

參考文獻(xiàn)370

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

附錄B泊松分布372

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

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