數(shù)據(jù)結(jié)構(gòu)：C++版

目錄數(shù)據(jù)結(jié)構(gòu)(C++版)第1章緒論11.1數(shù)據(jù)結(jié)構(gòu)的重要性1
1.2面向?qū)ο蟪绦蛟O(shè)計2
1.2.1面向?qū)ο蟪绦蛟O(shè)計方法2
1.2.2C++的特征及基本概念3
1.3基本術(shù)語4
1.4抽象數(shù)據(jù)類型6
1.5數(shù)據(jù)結(jié)構(gòu)的概念8
1.6數(shù)據(jù)的邏輯結(jié)構(gòu)10
1.7數(shù)據(jù)的存儲結(jié)構(gòu)11
1.8數(shù)據(jù)的運算13
1.9數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運算的關(guān)系14
1.10算法的描述14
小結(jié)15
習題15
第2章算法分析16
2.1算法分析的概念16
2.2算法運行時間舉例18
2.3最大連續(xù)子序列之和問題18
2.3.1簡單易懂的O(n3)算法19
2.3.2一個改進的O(n2)算法20
2.3.3一個線性算法21
2.4靜態(tài)搜索問題23
2.4.1順序搜索23
2.4.2二分搜索24
2.4.3插值搜索26
2.5檢驗一個算法分析26
2.6Big\|Oh分析法的限制27
小結(jié)28
習題28
第3章線性表30
3.1線性表及其抽象數(shù)據(jù)類型說明30
3.1.1線性表及其邏輯結(jié)構(gòu)30
3.1.2線性表的抽象數(shù)據(jù)類型描述34
3.2線性表的順序存儲35
3.2.1順序存儲35
3.2.2順序表類的定義36
3.2.3順序表類的實現(xiàn)36
3.3線性表的鏈式存儲40
3.3.1線性鏈表的存儲結(jié)構(gòu)40
3.3.2線性鏈表類的定義41
3.3.3線性鏈表類的實現(xiàn)43
3.3.4循環(huán)鏈表47
3.3.5循環(huán)鏈表類的實現(xiàn)48
3.3.6雙向鏈表49
3.3.7可利用空間表51
3.3.8表遍歷器52
3.4線性表的順序存儲和鏈式存儲的比較54
[2][2]目錄[][][2]數(shù)據(jù)結(jié)構(gòu)(C++版)[]
3.5鏈式存儲結(jié)構(gòu)的應用55
3.5.1約瑟夫問題55
3.5.2一元多項式求和56
小結(jié)60
習題60
第4章棧和隊列63
4.1棧63
4.1.1棧的定義63
4.1.2棧的順序存儲結(jié)構(gòu)66
4.1.3棧的鏈式存儲結(jié)構(gòu)69
4.1.4順序棧和鏈式棧的比較72
4.2棧的應用72
4.2.1迷宮問題72
4.2.2表達式求值75
4.2.3漢諾塔問題78
4.2.4數(shù)制轉(zhuǎn)換80
4.2.5行編輯81
4.3隊列82
4.3.1隊列的定義82
4.3.2隊列的順序存儲85
4.3.3隊列的鏈式存儲92
4.3.4順序隊列與鏈式隊列的比較96
4.3.5優(yōu)先隊列96
4.4隊列的應用97
4.4.1解決設(shè)備速度不匹配問題97
4.4.2舞伴問題97
4.4.3火車車廂重排99
小結(jié)101
習題101
第5章串105
5.1C++語言的字符和字符串105
5.2串的基本概念106
5.3串的存儲結(jié)構(gòu)107
5.3.1串的順序存儲結(jié)構(gòu)107
5.3.2串的鏈式存儲結(jié)構(gòu)109
5.3.3串的索引存儲結(jié)構(gòu)110
5.4串的操作111
5.4.1常用的C++字符串函數(shù)111
5.4.2串的抽象數(shù)據(jù)類型的描述112
5.4.3串的類定義113
5.4.4部分成員函數(shù)的實現(xiàn)114
5.5串的基本運算與實現(xiàn)117
5.5.1串插入117
5.5.2串刪除118
5.6模式匹配120
5.6.1模式匹配的BF算法120
5.6.2模式匹配的KMP算法122
5.7串在文本編輯中的應用126
小結(jié)128
習題128
第6章數(shù)組和廣義表130
6.1C++中數(shù)組的定義及抽象數(shù)據(jù)類型表示130
6.1.1C++中數(shù)組的定義130
6.1.2數(shù)組的抽象數(shù)據(jù)類型表示131
6.2數(shù)組的順序存儲結(jié)構(gòu)132
6.3矩陣的壓縮存儲133
6.3.1特殊矩陣的壓縮存儲134
6.3.2稀疏矩陣的壓縮存儲136
6.4廣義表的概念143
6.5廣義表的存儲結(jié)構(gòu)表示144
6.6廣義表的運算146
小結(jié)153
習題153
第7章樹157
7.1樹的基本概念157
7.1.1樹的定義157
7.1.2樹的表示形式158
7.1.3樹的常用術(shù)語159
7.1.4樹的基本操作159
7.1.5一個樹的接口160
7.1.6樹的基本算法161
7.2二叉樹162
7.2.1二叉樹的定義162
7.2.2二叉樹的性質(zhì)164
7.2.3二叉樹的接口166
7.2.4二叉樹的存儲結(jié)構(gòu)167
7.2.5二叉樹的遍歷175
7.2.6二叉樹遍歷的應用178
7.3線索二叉樹179
7.3.1線索二叉樹的類定義179
7.3.2中序線索二叉樹183
7.4樹、森林和二叉樹的關(guān)系186
7.4.1樹的存儲結(jié)構(gòu)186
7.4.2森林與二叉樹的轉(zhuǎn)換189
7.4.3樹和森林的遍歷192
7.5霍夫曼樹及其應用194
7.5.1霍夫曼樹的定義194
7.5.2霍夫曼樹的構(gòu)造195
7.5.3霍夫曼樹在編碼問題中的應用198
小結(jié)200
習題200
第8章圖204
8.1圖的基本概念204
8.1.1圖的定義及基本概念204
8.1.2圖的抽象數(shù)據(jù)類型208
8.2圖的存儲結(jié)構(gòu)209
8.2.1鄰接矩陣表示法210
8.2.2鄰接表215
8.2.3十字鏈表221
8.2.4鄰接多重表223
8.3圖的遍歷225
8.3.1深度優(yōu)先搜索225
8.3.2廣度優(yōu)先搜索227
8.3.3歐拉回路228
8.4圖的連通性230
8.4.1連通分量230
8.4.2重連通分量232
8.5生成樹233
8.5.1普里姆算法234
8.5.2克魯斯卡爾算法237
8.6最短路徑239
8.6.1單源最短路徑240
8.6.2求每一對頂點之間的最短路徑242
8.7拓撲排序243
8.8關(guān)鍵路徑247
小結(jié)253
習題254
第9章查找258
9.1基本概念258
9.2線性表的查找259
9.2.1順序查找259
9.2.2折半查找261
9.2.3索引查找263
9.2.4分塊查找267
9.3樹表查找269
9.3.1二叉查找樹270
9.3.2平衡二叉樹276
9.3.3B-樹281
9.4哈希表的查找283
9.4.1哈希表283
9.4.2構(gòu)造哈希表的基本方法284
9.4.3解決沖突的方法286
9.4.4哈希表的查找方法289
9.5各種查找方法的比較290
小結(jié)291
習題291
第10章排序295
10.1基本概念295
10.2內(nèi)部排序298
10.2.1插入排序298
10.2.2交換排序303
10.2.3選擇排序307
10.2.4歸并排序315
10.2.5基數(shù)排序319
10.3內(nèi)部排序方法比較323
10.4外部排序簡介325
小結(jié)325
習題326
第11章遞歸330
11.1遞歸的定義330
11.2常見遞歸問題331
11.2.1漢諾塔問題331
11.2.2八皇后問題332
11.2.3表達式樹335
11.3遞歸的實現(xiàn)337
11.4消除遞歸340
11.4.1尾遞歸和單向遞歸的消除340
11.4.2用棧模擬系統(tǒng)運行時的棧341
11.5遞歸的評估344
小結(jié)345
習題346
第12章文件348
12.1外存儲器的介紹348
12.2磁盤349
12.3有關(guān)文件的概念350
12.3.1文件及其類別351
12.3.2文件的操作352
12.4文件的組織353
12.4.1順序文件354
12.4.2索引文件355
12.4.3散列文件361
12.4.4多關(guān)鍵字文件362
12.5外部排序365
12.5.1外部排序的簡單方法365
12.5.2兩路歸并365
12.5.3多路歸并368
12.6文件的索引結(jié)構(gòu)369
12.6.1索引向量369
12.6.2樹形索引結(jié)構(gòu)370
小結(jié)370
習題370
參考文獻372
C++C++