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

第1章緒論1
1.1基本術(shù)語1
1.2算法的概念4
1.3算法描述6
1.4算法分析7
1.4.1時間復(fù)雜度8
1.4.2空間復(fù)雜度11
1.5算法設(shè)計的基本步驟11
習(xí)題12

第2章線性表15
2.1線性表的概念和基本操作15
2.1.1線性表的定義15
2.1.2線性表的基本操作17
2.2線性表的順序存儲結(jié)構(gòu)18
2.2.1數(shù)組——線性表的順序存儲結(jié)構(gòu)18
2.2.2數(shù)組中基本操作的實現(xiàn)19
2.2.3操作的時間分析22
2.3線性表的鏈式存儲結(jié)構(gòu)23
2.3.1單鏈表和指針23
2.3.2單鏈表的基本操作25
2.3.3鏈表的實現(xiàn)30
2.3.4單鏈表的其他操作31
2.4循環(huán)鏈表及其操作33
2.5雙向鏈表及其操作36
2.5.1雙向鏈表的構(gòu)造36
2.5.2雙向鏈表的插入與刪除算法37
習(xí)題39

第3章堆棧和隊列43
3.1堆棧的概念及操作43
3.1.1堆棧的定義43
3.1.2堆棧的有關(guān)操作44
3.2堆棧的順序存儲結(jié)構(gòu)45
3.3堆棧的鏈式存儲結(jié)構(gòu)47
3.4堆棧的應(yīng)用舉例49
3.4.1算術(shù)表達式的求值49
3.4.2在遞歸問題中的應(yīng)用51
3.5隊列的概念及操作52
3.5.1隊列的定義52
3.5.2隊列的有關(guān)操作53
3.6隊列的順序存儲結(jié)構(gòu)53
3.7隊列的鏈式存儲結(jié)構(gòu)57
3.8綜合實例——算符優(yōu)先算法59
習(xí)題63

第4章數(shù)組65
4.1數(shù)組的定義和操作65
4.2數(shù)組的順序存儲結(jié)構(gòu)66
4.3特殊矩陣的壓縮存儲68
4.3.1對稱矩陣的壓縮存儲68
4.3.2對角矩陣的壓縮存儲69
4.4稀疏矩陣的表示法70
4.4.1三元組表示法70
4.1.2稀疏矩陣的順序存儲71
4.1.3稀疏矩陣的鏈式存儲71
4.1.4稀疏矩陣的運算*73
習(xí)題76

第5章字符串77
5.1字符串的概念和基本操作77
5.1.1字符串的定義77
5.1.2字符串的基本操作78
5.2字符串的存儲結(jié)構(gòu)79
5.2.1字符串的順序存儲結(jié)構(gòu)80
5.2.2字符串的鏈式存儲結(jié)構(gòu)81
5.3字符串操作的實現(xiàn)82
習(xí)題84

第6章廣義表85
6.1廣義表的定義85
6.2廣義表的存儲結(jié)構(gòu)87
6.3廣義表的操作88
習(xí)題89

第7章樹與二叉樹91
7.1樹的概念91
7.1.1樹的定義91
7.1.2樹的邏輯表示法93
7.1.3樹的基本術(shù)語94
7.1.4樹的基本操作95
7.2二叉樹96
7.2.1二叉樹的定義96
7.2.2二叉樹的基本操作97
7.2.3二叉樹的性質(zhì)98
7.3二叉樹的存儲結(jié)構(gòu)101
7.3.1二叉樹的順序存儲結(jié)構(gòu)101
7.3.2二叉樹的鏈式存儲結(jié)構(gòu)102
7.4二叉樹的遍歷104
7.4.1遍歷的概念104
7.4.2遍歷的算法106
7.5線索二叉樹*108
7.5.1二叉樹的線索化108
7.5.2利用線索進行遍歷111
7.6二叉排序樹112
7.6.1二叉排序樹的定義112
7.6.2二叉排序樹的查找113
7.6.3二叉排序樹的插入和生成114
7.6.4二叉排序樹中結(jié)點的刪除117
7.7哈夫曼樹120
7.7.1哈夫曼樹的基本術(shù)語120
7.7.2哈夫曼樹的構(gòu)造121
7.7.3哈夫曼編碼122
7.8樹和森林123
7.8.1樹的存儲結(jié)構(gòu)124
7.8.2二叉樹與樹.森林之間的轉(zhuǎn)換126
習(xí)題127

第8章圖131
8.1圖的基本概念131
8.1.1圖的定義131
8.1.2圖的基本術(shù)語132
8.1.3圖的基本操作135
8.2圖的存儲結(jié)構(gòu)136
8.2.1鄰接矩陣（數(shù)組）136
8.2.2鄰接表137
8.2.3鄰接多重表138
8.2.4鄰接表的生成算法140
8.3圖的遍歷140
8.3.1DFS和BFS的基本思想141
8.3.2DFS和BFS算法142
8.3.3非連通圖的遍歷148
8.3.4DFS和BFS算法的應(yīng)用149
8.4網(wǎng)的最小生成樹*151
8.5最短路徑*154
8.6拓撲排序156
習(xí)題160

第9章查找165
9.1順序查找165
9.2二分查找167
9.3分塊查找170
9.4樹表的查找*173
9.5哈希表查找180
9.5.1哈希表180
9.5.2哈希函數(shù)的構(gòu)造方法181
9.5.3沖突解決的方法183
習(xí)題186

第10章排序189
10.1排序的概念189
10.2插入排序190
10.3快速排序191
10.4選擇排序197
10.5歸并排序202
10.6小結(jié)203
習(xí)題204

實驗指導(dǎo)書207
實驗一順序表的插入與刪除207
實驗二單鏈表的插入與刪除208
實驗三堆棧的操作208
實驗四二叉排序樹的構(gòu)造與查找209
實驗五冒泡排序210
實驗六快速排序211

參考文獻212