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

第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1
1.2抽象數(shù)據(jù)類型和軟件構(gòu)造方法4
1.3算法和算法的時(shí)間復(fù)雜度5
1.3.1算法5
1.3.2算法設(shè)計(jì)的目標(biāo)7
1.3.3算法時(shí)間效率的度量7
1.4算法設(shè)計(jì)11
1.5算法書寫規(guī)范14
1.6本課程內(nèi)容概述14
習(xí)題一15

第2章線性表17
2.1線性表的抽象數(shù)據(jù)類型17
2.2線性表的順序表示和實(shí)現(xiàn)18
2.2.1順序表的存儲(chǔ)結(jié)構(gòu)18
2.2.2順序表的操作實(shí)現(xiàn)19
2.2.3順序表操作的效?
2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)26
2.3.1單鏈表的存儲(chǔ)結(jié)構(gòu)26
2.3.2單鏈表的操作實(shí)現(xiàn)29
2.3.3單鏈表操作的效率分析34
2.3.4單鏈表應(yīng)用舉例35
2.3.5循環(huán)單鏈表36
2.3.6雙向鏈表37
2.4設(shè)計(jì)舉例40
2.5本章小結(jié)46
習(xí)題二47

第3章堆棧和隊(duì)列49
3.1堆棧49
3.1.1堆棧和堆棧的抽象數(shù)據(jù)類型49
3.1.2堆棧的順序表示和實(shí)現(xiàn)50
3.1.3堆棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)53
*3.2堆棧應(yīng)用--表達(dá)式計(jì)算58
3.3隊(duì)列61
3.3.1隊(duì)列和隊(duì)列抽象數(shù)據(jù)類型61
3.3.2順序隊(duì)列62
3.3.3順序循環(huán)隊(duì)列的表示和實(shí)現(xiàn)63
3.3.4鏈?zhǔn)疥?duì)列66
3.3.5隊(duì)列的應(yīng)用69
*3.4優(yōu)先級隊(duì)列71
3.4.1順序優(yōu)先級隊(duì)列的設(shè)計(jì)和實(shí)現(xiàn)71
3.4.2優(yōu)先級隊(duì)列的應(yīng)用74
3.5本章小結(jié)75
習(xí)題三76

第4章串79
4.1串79
4.1.1串及其基本概念79
4.1.2串的抽象數(shù)據(jù)類型80
4.1.3C語言的串函數(shù)81
4.2串的存儲(chǔ)結(jié)構(gòu)83
4.2.1串的順序存儲(chǔ)結(jié)構(gòu)83
4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)84
4.3串基本操作的實(shí)現(xiàn)算法85
4.4串的模式匹配算法90
4.4.1BruteForce算法90
4.4.2KMP算法92
4.4.3BruteForce算法和KMP算法的比較96
4.5本章小結(jié)98
習(xí)題四99

第5章數(shù)組101
5.1數(shù)組的實(shí)現(xiàn)機(jī)制101
5.2動(dòng)態(tài)數(shù)組的設(shè)計(jì)方法102
5.3特殊矩陣的壓縮存儲(chǔ)105
5.4稀疏矩陣的壓縮存儲(chǔ)106
5.4.1稀疏矩陣的三元組順序表106
5.4.2稀疏矩陣的三元組鏈表110
5.5本章小結(jié)111
習(xí)題五112

第6章遞歸114
6.1遞歸的概念114
6.2遞歸算法的執(zhí)行過程115
6.3遞歸算法的設(shè)計(jì)方法118
6.4遞歸過程和運(yùn)行時(shí)棧120
6.5遞歸算法的效率分析122
*6.6遞歸算法到非遞歸算法的轉(zhuǎn)換123
6.7設(shè)計(jì)舉例126
6.7.1一般遞歸算法設(shè)計(jì)舉例126
*6.7.2回溯法及設(shè)計(jì)舉例129
6.8本章小結(jié)133
習(xí)題六134

第7章樹和二叉樹137
7.1樹137
7.1.1樹的定義137
7.1.2樹的表示方法138
7.1.3樹的抽象數(shù)據(jù)類型139
7.2二叉樹140
7.2.1二叉樹的定義140
7.2.2二叉樹抽象數(shù)據(jù)類型141
7.2.3二叉樹的性質(zhì)141
7.3二叉樹的設(shè)計(jì)和實(shí)現(xiàn)143
7.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)143
7.3.2二叉鏈存儲(chǔ)結(jié)構(gòu)下二叉樹的操作實(shí)現(xiàn)145
7.3.3二叉樹的遍歷及其實(shí)現(xiàn)147
7.4線索二叉樹151
7.5哈夫曼樹153
7.5.1哈夫曼樹的基本概念153
7.5.2哈夫曼編碼問題155
*7.5.3哈夫曼編碼問題設(shè)計(jì)和實(shí)現(xiàn)156
7.6樹的存儲(chǔ)結(jié)構(gòu).轉(zhuǎn)換和遍歷160
7.6.1樹的存儲(chǔ)結(jié)構(gòu)160
7.6.2樹與二叉樹的轉(zhuǎn)換162
7.6.3樹的遍歷163
7.7本章小結(jié)164
習(xí)題七165

第8章圖168
8.1圖的基本概念168
8.1.1圖的基本概念168
8.1.2圖的抽象數(shù)據(jù)類型170
8.2圖的設(shè)計(jì)和實(shí)現(xiàn)171
8.2.1圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)171
8.2.2圖的鄰接表存儲(chǔ)結(jié)構(gòu)172
8.2.3鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的操作實(shí)現(xiàn)173
8.3圖的遍歷177
8.3.1圖的深度和廣度優(yōu)先遍歷算法177
8.3.2圖的深度和廣度優(yōu)先遍歷算法設(shè)計(jì)和實(shí)現(xiàn)178
8.4最小生成樹181
8.4.1最小生成樹的基本概念181
8.4.2普里姆算法182
*8.4.3普里姆函數(shù)設(shè)計(jì)和實(shí)現(xiàn)183
8.4.4克魯斯卡爾算法186
8.5最短路徑187
8.5.1最短路徑的基本概念187
8.5.2從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑188
*8.5.3狄克斯特拉算法設(shè)計(jì)和實(shí)現(xiàn)189
8.6本章小結(jié)192
習(xí)題八192

第9章排序195
9.1排序的基本概念195
9.2插入排序197
9.2.1直接插入排序197
9.2.2希爾排序199
9.3選擇排序201
9.3.1直接選擇排序201
9.3.2堆排序202
9.4交換排序207
9.4.1冒泡排序207
9.4.2快速排序209
*9.5歸并排序211
9.6綜合應(yīng)用舉例214
9.7本章小結(jié)215
習(xí)題九216

第10章查找218
10.1查找的基本概念218
10.2靜態(tài)查找表219
10.2.1順序表219
10.2.2有序順序表220
10.2.3索引順序表222
10.3動(dòng)態(tài)查找表224
10.3.1二叉排序樹224
10.3.2B-樹231
10.4哈希表235
10.4.1哈希表的基本概念235
10.4.2哈希函數(shù)構(gòu)造方法237
10.4.3哈希沖突解決方法238
10.4.4哈希表設(shè)計(jì)舉例239
10.5本章小結(jié)243
習(xí)題十244
附錄A上機(jī)實(shí)習(xí)內(nèi)容規(guī)范245
附錄B上機(jī)實(shí)習(xí)范例246
參考文獻(xiàn)257