數(shù)據(jù)結(jié)構(gòu)（C語言版）

第1章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 1
1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念 1
1.1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容 2
1.1.2 基本概念和術(shù)語 4
1.1.3 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 7
1.2 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 8
1.2.1 數(shù)據(jù)類型 8
1.2.2 抽象數(shù)據(jù)類型 8
1.3 算法和算法分析 10
1.3.1 算法特性 10
1.3.2 算法描述 11
1.3.3 算法性能分析 12
1.4 本章小結(jié) 15
　　習題 15
上機編程 17
第2章 線性表 18
2.1 線性表的定義 18
2.1.1 線性表的邏輯結(jié)構(gòu) 18
2.1.2 線性表的抽象數(shù)據(jù)類型定義 19
2.2 線性表的順序存儲及實現(xiàn) 20
2.2.1 順序表 20
2.2.2 順序表的基本運算 22
2.3 線性表的鏈式存儲及實現(xiàn) 27
2.3.1 單鏈表 27
2.3.2 單鏈表的基本運算 29
2.3.3 循環(huán)鏈表 34
2.3.4 雙向鏈表 35
2.3.5 靜態(tài)鏈表 37
2.3.6 單鏈表應(yīng)用舉例 39
2.4 順序表與鏈表的比較 41
2.5 本章小結(jié) 42
　　習題 42
上機編程 44
第3章 棧和隊列 46
3.1 棧 46
3.1.1 棧的定義 46
3.1.2 棧的表示和實現(xiàn) 48
3.2 棧的應(yīng)用 53
3.2.1 數(shù)制轉(zhuǎn)換問題 53
3.2.2 括號匹配檢驗 55
3.2.3 表達式求值 56
3.2.4 棧與遞歸 59
3.3 隊列 62
3.3.1 隊列的定義 62
3.3.2 隊列的表示和實現(xiàn) 64
3.4 隊列的應(yīng)用 69
3.5 本章小結(jié) 72
　　習題 72
上機編程 74
第4章 串 78
4.1 串的定義和基本運算 78
4.1.1 串的定義 78
4.1.2 串的基本操作 79
4.2 串的存儲結(jié)構(gòu) 80
4.2.1 定長順序存儲 80
4.2.2 鏈式存儲 81
4.2.3 堆存儲 82
4.3 串的運算實現(xiàn) 83
4.4 串的模式匹配 88
4.4.1 子串的定位 88
4.4.2 KMP算法 89
4.5 本章小結(jié) 92
　　習題 92
上機編程 95
第5章 數(shù)組和廣義表 98
5.1 數(shù)組的定義及存儲 98
5.1.1 數(shù)組的定義 98
5.1.2 數(shù)組的基本操作 99
5.1.3 數(shù)組的順序存儲 99
5.2 特殊矩陣的壓縮存儲 100
5.2.1 對稱矩陣 101
5.2.2 三角矩陣 102
5.2.3 對角矩陣 103
5.3 稀疏矩陣 103
5.3.1 順序存儲 104
5.3.2 鏈式存儲 107
5.4 廣義表 108
5.4.1 廣義表的定義 108
5.4.2 廣義表的存儲結(jié)構(gòu) 110
5.4.3 廣義表的遞歸算法 112
5.5 本章小結(jié) 113
　　習題 113
上機編程 114
第6章 樹和二叉樹 117
6.1 樹的定義與基本術(shù)語 117
6.1.1 樹的定義 117
6.1.2 樹的基本術(shù)語 120
6.2 二叉樹 121
6.2.1 二叉樹的定義 121
6.2.2 二叉樹的性質(zhì) 124
6.2.3 二叉樹的存儲實現(xiàn) 126
6.3 遍歷二叉樹 128
6.3.1 遍歷二叉樹的遞歸實現(xiàn) 129
6.3.2 遍歷二叉樹的非遞歸實現(xiàn) 131
6.3.3 遍歷算法的應(yīng)用 134
6.4 線索二叉樹 137
6.4.1 線索二叉樹的基本概念 137
6.4.2 線索二叉樹的運算實現(xiàn) 139
6.5 樹和森林 143
6.5.1 樹的存儲結(jié)構(gòu) 143
6.5.2 樹、森林與二叉樹的轉(zhuǎn)換 145
6.5.3 樹和森林的遍歷 148
6.6 哈夫曼樹及其應(yīng)用 149
6.6.1 哈夫曼樹的基本概念 149
6.6.2 構(gòu)造哈夫曼樹 150
6.6.3 哈夫曼編碼 152
6.7 本章小結(jié) 155
　　習題 155
上機編程 157
第7章 圖 161
7.1 圖的定義與基本術(shù)語 161
7.1.1 圖的定義 161
7.1.2 基本術(shù)語 163
7.2 圖的存儲結(jié)構(gòu) 166
7.2.1 鄰接矩陣 166
7.2.2 鄰接鏈表 168
7.2.3 十字鏈表 170
7.2.4 鄰接多重表 171
7.3 圖的遍歷 173
7.3.1 深度優(yōu)先搜索 173
7.3.2 廣度優(yōu)先搜索 175
7.4 圖的應(yīng)用 177
7.4.1 最小生成樹 177
7.4.2 最短路徑問題 184
7.4.3 AOV網(wǎng)與拓撲排序 188
7.4.4 AOE網(wǎng)與關(guān)鍵路徑 192
7.5 本章小結(jié) 197
　　習題 197
上機編程 199
第8章 查找 203
8.1 查找的基本概念 203
8.2 線性表的查找 204
8.2.1 順序查找 204
8.2.2 折半查找 205
8.2.3 分塊查找 209
8.3 樹表的查找 210
8.3.1 二叉排序樹 210
8.3.2 平衡二叉樹 216
8.3.3 B樹 220
8.4 散列表的查找 227
8.4.1 散列表的基本概念 227
8.4.2 散列函數(shù)的構(gòu)造方法 228
8.4.3 處理沖突的方法 230
8.4.4 散列表的查找 233
8.5 本章小結(jié) 234
　　習題 235
上機編程 237
第9章 排序 240
9.1 排序的基本概念 240
9.1.1 什么是排序 240
9.1.2 排序的實現(xiàn) 241
9.2 插入排序 242
9.2.1 直接插入排序 242
9.2.2 折半插入排序 244
9.2.3 希爾排序 245
9.3 交換排序 246
9.3.1 冒泡排序 247
9.3.2 快速排序 248
9.4 選擇排序 251
9.4.1 簡單選擇排序 251
9.4.2 堆排序 253
9.5 歸并排序 258
9.6 基數(shù)排序 260
9.6.1 多關(guān)鍵字排序 260
9.6.2 鏈式基數(shù)排序 260
9.7 本章小結(jié) 264
　　習題 265
上機編程 266
第10章 文件 269
10.1 文件的基本概念 269
10.2 順序文件 270
10.3 索引文件 272
10.4 索引順序文件 274
10.4.1 ISAM文件 274
10.4.2 VSAM文件 275
10.5 散列文件 276
10.6 本章小結(jié) 278
　　習題 278