數(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è)計(jì)2
1.2.1面向?qū)ο蟪绦蛟O(shè)計(jì)方法2
1.2.2C++的特征及基本概念3
1.3基本術(shù)語(yǔ)4
1.4抽象數(shù)據(jù)類(lèi)型6
1.5數(shù)據(jù)結(jié)構(gòu)的概念8
1.6數(shù)據(jù)的邏輯結(jié)構(gòu)10
1.7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)11
1.8數(shù)據(jù)的運(yùn)算13
1.9數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算的關(guān)系14
1.10算法的描述14
小結(jié)15
習(xí)題15
第2章算法分析16
2.1算法分析的概念16
2.2算法運(yùn)行時(shí)間舉例18
2.3最大連續(xù)子序列之和問(wèn)題18
2.3.1簡(jiǎn)單易懂的O(n3)算法19
2.3.2一個(gè)改進(jìn)的O(n2)算法20
2.3.3一個(gè)線性算法21
2.4靜態(tài)搜索問(wèn)題23
2.4.1順序搜索23
2.4.2二分搜索24
2.4.3插值搜索26
2.5檢驗(yàn)一個(gè)算法分析26
2.6Big\|Oh分析法的限制27
小結(jié)28
習(xí)題28
第3章線性表30
3.1線性表及其抽象數(shù)據(jù)類(lèi)型說(shuō)明30
3.1.1線性表及其邏輯結(jié)構(gòu)30
3.1.2線性表的抽象數(shù)據(jù)類(lèi)型描述34
3.2線性表的順序存儲(chǔ)35
3.2.1順序存儲(chǔ)35
3.2.2順序表類(lèi)的定義36
3.2.3順序表類(lèi)的實(shí)現(xiàn)36
3.3線性表的鏈?zhǔn)酱鎯?chǔ)40
3.3.1線性鏈表的存儲(chǔ)結(jié)構(gòu)40
3.3.2線性鏈表類(lèi)的定義41
3.3.3線性鏈表類(lèi)的實(shí)現(xiàn)43
3.3.4循環(huán)鏈表47
3.3.5循環(huán)鏈表類(lèi)的實(shí)現(xiàn)48
3.3.6雙向鏈表49
3.3.7可利用空間表51
3.3.8表遍歷器52
3.4線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的比較54
[2][2]目錄[][][2]數(shù)據(jù)結(jié)構(gòu)(C++版)[]
3.5鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的應(yīng)用55
3.5.1約瑟夫問(wèn)題55
3.5.2一元多項(xiàng)式求和56
小結(jié)60
習(xí)題60
第4章棧和隊(duì)列63
4.1棧63
4.1.1棧的定義63
4.1.2棧的順序存儲(chǔ)結(jié)構(gòu)66
4.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)69
4.1.4順序棧和鏈?zhǔn)綏５谋容^72
4.2棧的應(yīng)用72
4.2.1迷宮問(wèn)題72
4.2.2表達(dá)式求值75
4.2.3漢諾塔問(wèn)題78
4.2.4數(shù)制轉(zhuǎn)換80
4.2.5行編輯81
4.3隊(duì)列82
4.3.1隊(duì)列的定義82
4.3.2隊(duì)列的順序存儲(chǔ)85
4.3.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)92
4.3.4順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較96
4.3.5優(yōu)先隊(duì)列96
4.4隊(duì)列的應(yīng)用97
4.4.1解決設(shè)備速度不匹配問(wèn)題97
4.4.2舞伴問(wèn)題97
4.4.3火車(chē)車(chē)廂重排99
小結(jié)101
習(xí)題101
第5章串105
5.1C++語(yǔ)言的字符和字符串105
5.2串的基本概念106
5.3串的存儲(chǔ)結(jié)構(gòu)107
5.3.1串的順序存儲(chǔ)結(jié)構(gòu)107
5.3.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)109
5.3.3串的索引存儲(chǔ)結(jié)構(gòu)110
5.4串的操作111
5.4.1常用的C++字符串函數(shù)111
5.4.2串的抽象數(shù)據(jù)類(lèi)型的描述112
5.4.3串的類(lèi)定義113
5.4.4部分成員函數(shù)的實(shí)現(xiàn)114
5.5串的基本運(yùn)算與實(shí)現(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串在文本編輯中的應(yīng)用126
小結(jié)128
習(xí)題128
第6章數(shù)組和廣義表130
6.1C++中數(shù)組的定義及抽象數(shù)據(jù)類(lèi)型表示130
6.1.1C++中數(shù)組的定義130
6.1.2數(shù)組的抽象數(shù)據(jù)類(lèi)型表示131
6.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)132
6.3矩陣的壓縮存儲(chǔ)133
6.3.1特殊矩陣的壓縮存儲(chǔ)134
6.3.2稀疏矩陣的壓縮存儲(chǔ)136
6.4廣義表的概念143
6.5廣義表的存儲(chǔ)結(jié)構(gòu)表示144
6.6廣義表的運(yùn)算146
小結(jié)153
習(xí)題153
第7章樹(shù)157
7.1樹(shù)的基本概念157
7.1.1樹(shù)的定義157
7.1.2樹(shù)的表示形式158
7.1.3樹(shù)的常用術(shù)語(yǔ)159
7.1.4樹(shù)的基本操作159
7.1.5一個(gè)樹(shù)的接口160
7.1.6樹(shù)的基本算法161
7.2二叉樹(shù)162
7.2.1二叉樹(shù)的定義162
7.2.2二叉樹(shù)的性質(zhì)164
7.2.3二叉樹(shù)的接口166
7.2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)167
7.2.5二叉樹(shù)的遍歷175
7.2.6二叉樹(shù)遍歷的應(yīng)用178
7.3線索二叉樹(shù)179
7.3.1線索二叉樹(shù)的類(lèi)定義179
7.3.2中序線索二叉樹(shù)183
7.4樹(shù)、森林和二叉樹(shù)的關(guān)系186
7.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)186
7.4.2森林與二叉樹(shù)的轉(zhuǎn)換189
7.4.3樹(shù)和森林的遍歷192
7.5霍夫曼樹(shù)及其應(yīng)用194
7.5.1霍夫曼樹(shù)的定義194
7.5.2霍夫曼樹(shù)的構(gòu)造195
7.5.3霍夫曼樹(shù)在編碼問(wèn)題中的應(yīng)用198
小結(jié)200
習(xí)題200
第8章圖204
8.1圖的基本概念204
8.1.1圖的定義及基本概念204
8.1.2圖的抽象數(shù)據(jù)類(lèi)型208
8.2圖的存儲(chǔ)結(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生成樹(shù)233
8.5.1普里姆算法234
8.5.2克魯斯卡爾算法237
8.6最短路徑239
8.6.1單源最短路徑240
8.6.2求每一對(duì)頂點(diǎn)之間的最短路徑242
8.7拓?fù)渑判?43
8.8關(guān)鍵路徑247
小結(jié)253
習(xí)題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樹(shù)表查找269
9.3.1二叉查找樹(shù)270
9.3.2平衡二叉樹(shù)276
9.3.3B-樹(shù)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
習(xí)題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外部排序簡(jiǎn)介325
小結(jié)325
習(xí)題326
第11章遞歸330
11.1遞歸的定義330
11.2常見(jiàn)遞歸問(wèn)題331
11.2.1漢諾塔問(wèn)題331
11.2.2八皇后問(wèn)題332
11.2.3表達(dá)式樹(shù)335
11.3遞歸的實(shí)現(xiàn)337
11.4消除遞歸340
11.4.1尾遞歸和單向遞歸的消除340
11.4.2用棧模擬系統(tǒng)運(yùn)行時(shí)的棧341
11.5遞歸的評(píng)估344
小結(jié)345
習(xí)題346
第12章文件348
12.1外存儲(chǔ)器的介紹348
12.2磁盤(pán)349
12.3有關(guān)文件的概念350
12.3.1文件及其類(lèi)別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外部排序的簡(jiǎn)單方法365
12.5.2兩路歸并365
12.5.3多路歸并368
12.6文件的索引結(jié)構(gòu)369
12.6.1索引向量369
12.6.2樹(shù)形索引結(jié)構(gòu)370
小結(jié)370
習(xí)題370
參考文獻(xiàn)372
C++C++