第1 章 數(shù)據(jù)結構基礎 .................................................................................... 1
1.1 數(shù)據(jù)結構的基本概念 .................................................................................................... 2
1.1.1 數(shù)據(jù)結構的研究內容 ......................................................................................... 2
1.1.2 基本概念和術語 ................................................................................................. 5
1.1.3 數(shù)據(jù)結構課程的內容 ......................................................................................... 8
1.2 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 ............................................................................................ 9
1.2.1 數(shù)據(jù)類型 ............................................................................................................. 9
1.2.2 抽象數(shù)據(jù)類型 ..................................................................................................... 9
1.3 算法和算法分析 .......................................................................................................... 10
1.3.1 算法特性 ........................................................................................................... 11
1.3.2 算法描述 ........................................................................................................... 12
1.3.3 算法性能分析 ................................................................................................... 12
1.4 本章小結 ...................................................................................................................... 15
習題 ....................................................................................................................................... 16
編程實例 ............................................................................................................................... 18
第2 章 線性表 ............................................................................................. 19
2.1 線性表的定義 .............................................................................................................. 20
2.1.1 線性表的邏輯結構 ........................................................................................... 20
2.1.2 線性表的抽象數(shù)據(jù)類型 ................................................................................... 20
2.2 線性表的順序存儲及實現(xiàn) .......................................................................................... 22
2.2.1 順序表 ............................................................................................................... 22
2.2.2 順序表的基本運算 ........................................................................................... 23
2.3 線性表的鏈式存儲及實現(xiàn) .......................................................................................... 28
vi | 數(shù)據(jù)結構案例教程（C 語言版）
2.3.1 單鏈表 ............................................................................................................... 29
2.3.2 單鏈表的基本運算 ........................................................................................... 30
2.3.3 循環(huán)鏈表 ........................................................................................................... 36
2.3.4 雙向鏈表 ........................................................................................................... 37
2.3.5 靜態(tài)鏈表 ........................................................................................................... 39
2.3.6 單鏈表應用舉例 ............................................................................................... 40
2.4 順序表與鏈表的比較 .................................................................................................. 43
2.5 本章小結 ...................................................................................................................... 44
習題 ....................................................................................................................................... 44
編程實例 ............................................................................................................................... 46
第3 章 棧和隊列 ......................................................................................... 48
3.1 棧 .................................................................................................................................. 49
3.1.1 棧的定義 ........................................................................................................... 49
3.1.2 棧的表示和實現(xiàn) ............................................................................................... 50
3.2 棧的應用 ...................................................................................................................... 55
3.2.1 數(shù)制轉換問題 ................................................................................................... 56
3.2.2 括號匹配檢驗 ................................................................................................... 57
3.2.3 表達式求值 ....................................................................................................... 58
3.2.4 棧與遞歸 ........................................................................................................... 61
3.3 隊列 .............................................................................................................................. 64
3.3.1 隊列的定義 ....................................................................................................... 64
3.3.2 隊列的表示和實現(xiàn) ........................................................................................... 65
3.4 隊列的應用 .................................................................................................................. 71
3.5 本章小結 ...................................................................................................................... 73
習題 ....................................................................................................................................... 74
編程實例 ............................................................................................................................... 75
第4 章 串 .................................................................................................... 79
4.1 串的定義和基本運算 .................................................................................................. 80
4.1.1 串的定義 ........................................................................................................... 80
4.1.2 串的基本操作 ................................................................................................... 81
4.2 串的存儲結構 .............................................................................................................. 82
4.2.1 定長順序存儲 ................................................................................................... 82
4.2.2 堆存儲 ............................................................................................................... 83
目 錄 | vii
4.2.3 鏈式存儲 ........................................................................................................... 85
4.3 串的運算實現(xiàn) .............................................................................................................. 86
4.4 串的模式匹配 .............................................................................................................. 90
4.4.1 BF 算法 ............................................................................................................. 90
4.4.2 KMP 算法 ......................................................................................................... 92
4.5 本章小結 ...................................................................................................................... 95
習題 ....................................................................................................................................... 96
編程實例 ............................................................................................................................... 99
第5 章 數(shù)組和廣義表 ................................................................................ 103
5.1 數(shù)組的定義及存儲 .................................................................................................... 104
5.1.1 數(shù)組的定義 ..................................................................................................... 104
5.1.2 數(shù)組的基本操作 ............................................................................................. 105
5.1.3 數(shù)組的順序存儲 ............................................................................................. 105
5.2 特殊矩陣的壓縮存儲 ................................................................................................ 107
5.2.1 對稱矩陣 ......................................................................................................... 108
5.2.2 三角矩陣 ......................................................................................................... 109
5.2.3 對角矩陣 ......................................................................................................... 110
5.3 稀疏矩陣 ..................................................................................................................... 111
5.3.1 稀疏矩陣的三元組表存儲 .............................................................................. 111
5.3.2 稀疏矩陣的十字鏈表存儲 ............................................................................. 115
5.4 廣義表 ........................................................................................................................ 117
5.4.1 廣義表的定義 ................................................................................................. 117
5.4.2 廣義表的存儲結構 ......................................................................................... 119
5.4.3 廣義表的基本操作實現(xiàn) ................................................................................. 121
5.5 本章小結 .................................................................................................................... 122
習題 ..................................................................................................................................... 123
編程實例 ............................................................................................................................. 124
第6 章 樹和二叉樹 .................................................................................... 127
6.1 樹的定義與基本術語 ................................................................................................ 128
6.1.1 樹的定義 ......................................................................................................... 128
6.1.2 樹的基本術語 ................................................................................................. 131
6.2 二叉樹 ........................................................................................................................ 131
6.2.1 二叉樹的定義 ................................................................................................. 131
viii | 數(shù)據(jù)結構案例教程（C 語言版）
6.2.2 二叉樹的性質 ................................................................................................. 134
6.2.3 二叉樹的存儲實現(xiàn) ......................................................................................... 136
6.3 遍歷二叉樹 ................................................................................................................ 139
6.3.1 遍歷二叉樹的遞歸實現(xiàn) ................................................................................. 139
6.3.2 遍歷二叉樹的非遞歸實現(xiàn) ............................................................................. 141
6.3.3 遍歷算法的應用 ............................................................................................. 145
6.4 線索二叉樹 ................................................................................................................ 148
6.4.1 線索二叉樹的基本概念 ................................................................................. 148
6.4.2 線索二叉樹的運算實現(xiàn) ................................................................................. 150
6.5 樹和森林 .................................................................................................................... 153
6.5.1 樹的存儲結構 ................................................................................................. 153
6.5.2 樹、森林與二叉樹的轉換 ............................................................................. 156
6.5.3 樹和森林的遍歷 ............................................................................................. 158
6.6 哈夫曼樹及其應用 .................................................................................................... 159
6.6.1 哈夫曼樹的基本概念 ..................................................................................... 159
6.6.2 構造哈夫曼樹 ................................................................................................. 161
6.6.3 哈夫曼編碼 ..................................................................................................... 163
6.7 本章小結 .................................................................................................................... 165
習題 ..................................................................................................................................... 166
編程實例 ............................................................................................................................. 168
第7 章 圖 .................................................................................................. 172
7.1 圖的定義與基本術語 ................................................................................................ 173
7.1.1 圖的定義 ......................................................................................................... 173
7.1.2 基本術語 ......................................................................................................... 175
7.2 圖的存儲結構 ............................................................................................................ 177
7.2.1 鄰接矩陣 ......................................................................................................... 177
7.2.2 鄰接鏈表 ......................................................................................................... 179
7.2.3 十字鏈表 ......................................................................................................... 182
7.2.4 鄰接多重表 ..................................................................................................... 183
7.3 圖的遍歷 .................................................................................................................... 184
7.3.1 深度優(yōu)先搜索 ................................................................................................. 185
7.3.2 廣度優(yōu)先搜索 ................................................................................................. 187
7.4 圖的應用 .................................................................................................................... 189
7.4.1 最小生成樹 ..................................................................................................... 189
目 錄 | ix
7.4.2 最短路徑問題 ................................................................................................. 195
7.4.3 AOV 網(wǎng)與拓撲排序 ....................................................................................... 200
7.4.4 AOE 網(wǎng)與關鍵路徑 ........................................................................................ 203
7.5 本章小結 .................................................................................................................... 208
習題 ..................................................................................................................................... 209
編程實例 ............................................................................................................................. 211
第8 章 查找 ............................................................................................... 216
8.1 查找的基本概念 ........................................................................................................ 217
8.2 線性表的查找 ............................................................................................................ 218
8.2.1 順序查找 ......................................................................................................... 218
8.2.2 折半查找 ......................................................................................................... 219
8.2.3 分塊查找 ......................................................................................................... 222
8.3 樹表的查找 ................................................................................................................ 223
8.3.1 二叉排序樹 ..................................................................................................... 223
8.3.2 平衡二叉樹 ..................................................................................................... 229
8.3.3 B 樹.................................................................................................................. 234
8.4 散列表的查找 ............................................................................................................ 241
8.4.1 散列表的基本概念 ......................................................................................... 241
8.4.2 散列函數(shù)的構造方法 ..................................................................................... 242
8.4.3 處理沖突的方法 ............................................................................................. 244
8.4.4 散列表的查找 ................................................................................................. 247
8.5 本章小結 .................................................................................................................... 248
習題 ..................................................................................................................................... 249
編程實例 ............................................................................................................................. 251
第9 章 排序 ............................................................................................... 254
9.1 排序的基本概念 ........................................................................................................ 255
9.1.1 什么是排序 ..................................................................................................... 255
9.1.2 排序的實現(xiàn) ..................................................................................................... 256
9.2 插入排序 .................................................................................................................... 257
9.2.1 直接插入排序 ................................................................................................. 257
9.2.2 折半插入排序 ................................................................................................. 259
9.2.3 希爾排序 ......................................................................................................... 260
9.3 交換排序 .................................................................................................................... 261
x | 數(shù)據(jù)結構案例教程（C 語言版）
9.3.1 冒泡排序 ......................................................................................................... 261
9.3.2 快速排序 ......................................................................................................... 263
9.4 選擇排序 .................................................................................................................... 266
9.4.1 簡單選擇排序 ................................................................................................. 266
9.4.2 堆排序 ............................................................................................................. 268
9.5 歸并排序 .................................................................................................................... 273
9.6 基數(shù)排序 .................................................................................................................... 275
9.6.1 多關鍵字排序 ................................................................................................. 275
9.6.2 鏈式基數(shù)排序 ................................................................................................. 275
9.7 本章小結 .................................................................................................................... 279
習題 ..................................................................................................................................... 280
編程實例 ............................................................................................................................. 282