數(shù)據(jù)結(jié)構(gòu)

第一章緒論.1
1.1數(shù)據(jù)結(jié)構(gòu)概念1
1.2面向?qū)ο蟪绦蛟O(shè)計(jì)OOP與抽象數(shù)據(jù)類型ADT3
1.3算法概念和算法描述語(yǔ)言5
第二章算法分析基礎(chǔ)9
2.1引論9
2.2算法時(shí)間復(fù)雜性的分析方法11
2.3時(shí)間與空間分析15
習(xí)題16
第三章面向?qū)ο蟪绦蛟O(shè)計(jì)與C++語(yǔ)言18
3.1類和對(duì)象18
3.1.1類聲明18
3.1.2類實(shí)現(xiàn)19
3.1.3對(duì)象聲明20
3.2C++語(yǔ)言的基本操作21
3.2.1輸入輸出的C++實(shí)現(xiàn)21
3.2.2友元函數(shù)（friendfuntction）23
3.2.3參數(shù)傳遞24
3.2.4多態(tài)性25
3.2.5動(dòng)態(tài)存儲(chǔ)分配28
3.3模板29
3.3.1模板函數(shù)29
3.3.2模板類31
3.4繼承32
習(xí)題34
第四章線性表.堆棧.隊(duì)列35
4.1線性表的定義和基本操作35
4.2線性表的存儲(chǔ)結(jié)構(gòu)36
4.2.1順序存儲(chǔ)結(jié)構(gòu)36
4.2.2鏈接存儲(chǔ)結(jié)構(gòu)----單鏈表36
4.2.3循環(huán)鏈表47
4.2.4雙向循環(huán)鏈表49
4.3堆棧和隊(duì)列53
4.3.1定義和主要操作53
4.3.2順序存儲(chǔ)56
4.3.3鏈接存儲(chǔ)63
4.3.4應(yīng)用--算術(shù)表達(dá)式求值65
習(xí)題68
第五章數(shù)組字符串和集合類71
5.1數(shù)組71
5.1.1順序存儲(chǔ)的數(shù)組71
5.1.2靜態(tài)數(shù)組與動(dòng)態(tài)數(shù)組73
5.1.3稀疏矩陣77
5.2字符串84
5.2.1定義和主要操作84
5.2.2存儲(chǔ)方式85
5.2.3模式匹配算法*86
5.3整型集合90
習(xí)題94
第六章樹(shù)98
6.1基本概念98
6.2二叉樹(shù)99
6.2.1主要性質(zhì)和定義99
6.2.2二叉樹(shù)的實(shí)現(xiàn)102
6.2.3二叉樹(shù)的遍歷108
6.2.4復(fù)制二叉樹(shù)110
6.3線索二叉樹(shù)111
6.4樹(shù)與森林119
6.4.1樹(shù)的順序存儲(chǔ)結(jié)構(gòu)119
6.4.2樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu)121
6.4.3森林與二叉樹(shù)的轉(zhuǎn)換125
6.4.4樹(shù)和森林的遍歷126
6.5壓縮與哈夫曼樹(shù)131
習(xí)題135
第七章圖137
7.1概念和定義137
7.2圖的存儲(chǔ)結(jié)構(gòu)與類Graph139
7.2.1存儲(chǔ)結(jié)構(gòu)139
7.2.2Graph類141
7.3遍歷函數(shù)的實(shí)現(xiàn)153
7.3.1深度優(yōu)先遍歷153
7.3.2廣度優(yōu)先遍歷155
7.4拓?fù)渑判?56
7.5關(guān)鍵路徑159
7.6最短路徑問(wèn)題163
7.6.1無(wú)權(quán)最短路徑問(wèn)題163
7.6.2正權(quán)最短路徑問(wèn)題165
7.6.3負(fù)權(quán)最短路徑問(wèn)題*168
7.6.4每對(duì)頂點(diǎn)之間的最短路徑171
7.7最小支撐樹(shù)173
7.8應(yīng)用178
7.8.1可及性與Warshall算法178
7.8.2連通分量180
習(xí)題182
第八章遞歸..186
8.1什么是遞歸186
8.2基本遞歸過(guò)程188
8.3遞歸過(guò)程的實(shí)現(xiàn)：堆棧與遞歸191
8.4遞歸到非遞歸的轉(zhuǎn)換196
8.5遞歸的應(yīng)用203
8.5.1應(yīng)用實(shí)例1：算術(shù)表達(dá)式求值203
8.5.2應(yīng)用實(shí)例2：回溯205
習(xí)題210
第九章排序211
9.1插入排序212
9.2交換排序217
9.2.1冒泡排序217
9.2.2分劃交換排序222
9.3選擇排序231
9.3.1直接選擇排序231
9.3.2堆排序232
9.4合并排序238
9.5排序下界242
9.6分布排序*243
9.6.1基數(shù)分布244
9.6.2值分布247
9.7外排序*249
9.7.1外存儲(chǔ)器249
9.7.2磁帶排序250
9.7.3磁盤(pán)排序260
習(xí)題266
第十章查找與二叉查找樹(shù)269
10.1線性表查找269
10.1.1順序查找270
10.1.2有序表的查找271
10.2二叉查找樹(shù)278
10.2.1定義和基本操作278
10.2.2靜態(tài)樹(shù)281
10.2.3動(dòng)態(tài)樹(shù)289
10.3數(shù)字查找樹(shù)320
10.4雜湊322
10.4.1雜湊表的定義和主要操作322
10.4.2雜湊函數(shù)323
10.4.3沖突調(diào)節(jié)326
10.5(a,b)-樹(shù).B樹(shù)和B+樹(shù)*334
習(xí)題341
第十一章內(nèi)存管理344
11.1均勻大小記錄的管理和廢料收集方法344
11.1.1訪問(wèn)計(jì)數(shù)器法345
11.1.2廢料收集346
11.2不同大小記錄的查找分配和壓縮分配350
11.2.1查找分配351
11.2.2壓縮分配357
11.3伙伴系統(tǒng)362
11.4C++中的動(dòng)態(tài)內(nèi)存分配*368
習(xí)題369
第十二章復(fù)雜數(shù)據(jù)結(jié)構(gòu)371
12.1優(yōu)先級(jí)隊(duì)列371
12.1.1類聲明371
12.1.2優(yōu)先級(jí)隊(duì)列的應(yīng)用：長(zhǎng)歸并段372
12.2不相交集合類378
12.2.1等價(jià)關(guān)系378
12.2.2動(dòng)態(tài)等價(jià)379
12.2.3快速查找算法383
12.2.4快速合并算法384
12.2.5C++實(shí)現(xiàn)390
12.2.6最壞情況下的歸并和路徑壓縮391
第十三章文件393
13.1文件結(jié)構(gòu)概論393
13.2順序文件396
13.2.1串行處理文件396
13.2.2順序處理文件399
13.2.3增補(bǔ)文件400
13.3雜湊（散列）文件402
13.3.1雜湊文件的設(shè)計(jì)402
13.3.2可擴(kuò)充的雜湊文件405
13.4索引文件410
13.4.1動(dòng)態(tài)索引結(jié)構(gòu)和靜態(tài)索引結(jié)構(gòu)414
13.4.2索引順序文件B+414
13.4.3B+索引文件418
13.5倒排文件和多重鏈表文件422
習(xí)題430
第十四章應(yīng)用*432
14.1事件驅(qū)動(dòng)模擬432
14.1.1模擬設(shè)計(jì)432
14.1.2模擬建立436
14.1.3運(yùn)行模擬437
14.2在線等價(jià)類443
14.2.1樹(shù)形描述443
14.2.2操作444
14.2.3性能評(píng)價(jià)445
14.2.4性能改進(jìn)445
14.3殘缺棋盤(pán)451
14.4圖像壓縮454
參考文獻(xiàn)...461