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

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

第2章線性表15
2.1線性表的概念和基本操作15
2.1.1線性表的定義15
2.1.2線性表的基本操作17
2.2線性表的順序存儲(chǔ)結(jié)構(gòu)18
2.2.1數(shù)組——線性表的順序存儲(chǔ)結(jié)構(gòu)18
2.2.2數(shù)組中基本操作的實(shí)現(xiàn)19
2.2.3操作的時(shí)間分析22
2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)23
2.3.1單鏈表和指針23
2.3.2單鏈表的基本操作25
2.3.3鏈表的實(shí)現(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章堆棧和隊(duì)列43
3.1堆棧的概念及操作43
3.1.1堆棧的定義43
3.1.2堆棧的有關(guān)操作44
3.2堆棧的順序存儲(chǔ)結(jié)構(gòu)45
3.3堆棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)47
3.4堆棧的應(yīng)用舉例49
3.4.1算術(shù)表達(dá)式的求值49
3.4.2在遞歸問(wèn)題中的應(yīng)用51
3.5隊(duì)列的概念及操作52
3.5.1隊(duì)列的定義52
3.5.2隊(duì)列的有關(guān)操作53
3.6隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)53
3.7隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)57
3.8綜合實(shí)例——算符優(yōu)先算法59
習(xí)題63

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

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

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

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

第8章圖131
8.1圖的基本概念131
8.1.1圖的定義131
8.1.2圖的基本術(shù)語(yǔ)132
8.1.3圖的基本操作135
8.2圖的存儲(chǔ)結(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)的最小生成樹(shù)*151
8.5最短路徑*154
8.6拓?fù)渑判?56
習(xí)題160

第9章查找165
9.1順序查找165
9.2二分查找167
9.3分塊查找170
9.4樹(shù)表的查找*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

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

參考文獻(xiàn)212