數(shù)據(jù)結構：C++版

目錄數(shù)據(jù)結構(C++版)第1章緒論11.1數(shù)據(jù)結構的重要性1
1.2面向對象程序設計2
1.2.1面向對象程序設計方法2
1.2.2C++的特征及基本概念3
1.3基本術語4
1.4抽象數(shù)據(jù)類型6
1.5數(shù)據(jù)結構的概念8
1.6數(shù)據(jù)的邏輯結構10
1.7數(shù)據(jù)的存儲結構11
1.8數(shù)據(jù)的運算13
1.9數(shù)據(jù)的邏輯結構、存儲結構及數(shù)據(jù)的運算的關系14
1.10算法的描述14
小結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
小結28
習題28
第3章線性表30
3.1線性表及其抽象數(shù)據(jù)類型說明30
3.1.1線性表及其邏輯結構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線性鏈表的存儲結構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ù)結構(C++版)[]
3.5鏈式存儲結構的應用55
3.5.1約瑟夫問題55
3.5.2一元多項式求和56
小結60
習題60
第4章棧和隊列63
4.1棧63
4.1.1棧的定義63
4.1.2棧的順序存儲結構66
4.1.3棧的鏈式存儲結構69
4.1.4順序棧和鏈式棧的比較72
4.2棧的應用72
4.2.1迷宮問題72
4.2.2表達式求值75
4.2.3漢諾塔問題78
4.2.4數(shù)制轉換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解決設備速度不匹配問題97
4.4.2舞伴問題97
4.4.3火車車廂重排99
小結101
習題101
第5章串105
5.1C++語言的字符和字符串105
5.2串的基本概念106
5.3串的存儲結構107
5.3.1串的順序存儲結構107
5.3.2串的鏈式存儲結構109
5.3.3串的索引存儲結構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
小結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ù)組的順序存儲結構132
6.3矩陣的壓縮存儲133
6.3.1特殊矩陣的壓縮存儲134
6.3.2稀疏矩陣的壓縮存儲136
6.4廣義表的概念143
6.5廣義表的存儲結構表示144
6.6廣義表的運算146
小結153
習題153
第7章樹157
7.1樹的基本概念157
7.1.1樹的定義157
7.1.2樹的表示形式158
7.1.3樹的常用術語159
7.1.4樹的基本操作159
7.1.5一個樹的接口160
7.1.6樹的基本算法161
7.2二叉樹162
7.2.1二叉樹的定義162
7.2.2二叉樹的性質164
7.2.3二叉樹的接口166
7.2.4二叉樹的存儲結構167
7.2.5二叉樹的遍歷175
7.2.6二叉樹遍歷的應用178
7.3線索二叉樹179
7.3.1線索二叉樹的類定義179
7.3.2中序線索二叉樹183
7.4樹、森林和二叉樹的關系186
7.4.1樹的存儲結構186
7.4.2森林與二叉樹的轉換189
7.4.3樹和森林的遍歷192
7.5霍夫曼樹及其應用194
7.5.1霍夫曼樹的定義194
7.5.2霍夫曼樹的構造195
7.5.3霍夫曼樹在編碼問題中的應用198
小結200
習題200
第8章圖204
8.1圖的基本概念204
8.1.1圖的定義及基本概念204
8.1.2圖的抽象數(shù)據(jù)類型208
8.2圖的存儲結構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關鍵路徑247
小結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構造哈希表的基本方法284
9.4.3解決沖突的方法286
9.4.4哈希表的查找方法289
9.5各種查找方法的比較290
小結291
習題291
第10章排序295
10.1基本概念295
10.2內部排序298
10.2.1插入排序298
10.2.2交換排序303
10.2.3選擇排序307
10.2.4歸并排序315
10.2.5基數(shù)排序319
10.3內部排序方法比較323
10.4外部排序簡介325
小結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
小結345
習題346
第12章文件348
12.1外存儲器的介紹348
12.2磁盤349
12.3有關文件的概念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多關鍵字文件362
12.5外部排序365
12.5.1外部排序的簡單方法365
12.5.2兩路歸并365
12.5.3多路歸并368
12.6文件的索引結構369
12.6.1索引向量369
12.6.2樹形索引結構370
小結370
習題370
參考文獻372
C++C++