數(shù)據(jù)結構

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

第2章線性表15
2.1線性表的概念和基本操作15
2.1.1線性表的定義15
2.1.2線性表的基本操作17
2.2線性表的順序存儲結構18
2.2.1數(shù)組——線性表的順序存儲結構18
2.2.2數(shù)組中基本操作的實現(xiàn)19
2.2.3操作的時間分析22
2.3線性表的鏈式存儲結構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雙向鏈表的構造36
2.5.2雙向鏈表的插入與刪除算法37
習題39

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

第4章數(shù)組65
4.1數(shù)組的定義和操作65
4.2數(shù)組的順序存儲結構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
習題76

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

第6章廣義表85
6.1廣義表的定義85
6.2廣義表的存儲結構87
6.3廣義表的操作88
習題89

第7章樹與二叉樹91
7.1樹的概念91
7.1.1樹的定義91
7.1.2樹的邏輯表示法93
7.1.3樹的基本術語94
7.1.4樹的基本操作95
7.2二叉樹96
7.2.1二叉樹的定義96
7.2.2二叉樹的基本操作97
7.2.3二叉樹的性質(zhì)98
7.3二叉樹的存儲結構101
7.3.1二叉樹的順序存儲結構101
7.3.2二叉樹的鏈式存儲結構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二叉排序樹中結點的刪除117
7.7哈夫曼樹120
7.7.1哈夫曼樹的基本術語120
7.7.2哈夫曼樹的構造121
7.7.3哈夫曼編碼122
7.8樹和森林123
7.8.1樹的存儲結構124
7.8.2二叉樹與樹.森林之間的轉換126
習題127

第8章圖131
8.1圖的基本概念131
8.1.1圖的定義131
8.1.2圖的基本術語132
8.1.3圖的基本操作135
8.2圖的存儲結構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算法的應用149
8.4網(wǎng)的最小生成樹*151
8.5最短路徑*154
8.6拓撲排序156
習題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ù)的構造方法181
9.5.3沖突解決的方法183
習題186

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

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

參考文獻212