目 錄
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的概念 1
1.1.1 數(shù)據(jù)結(jié)構(gòu)的研究方向 1
1.1.2 數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語 3
1.1.3 數(shù)據(jù)類型與抽象數(shù)據(jù)類型 5
1.2 算法與算法分析 5
1.2.1 算法的概念與描述 5
1.2.2 算法分析 8
1.3 本章小結(jié) 12
習(xí)題1 12
第2章 線性表 15
2.1 線性表的概念 15
2.1.1 線性表的定義與特點(diǎn) 15
2.1.2 線性表的基本運(yùn)算 16
2.1.3 線性表的抽象數(shù)據(jù)類型定義 16
2.2 線性表的順序存儲(chǔ) 17
2.2.1 線性表的順序存儲(chǔ)及其特點(diǎn) 17
2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn) 17
2.2.3 線性表的順序存儲(chǔ)優(yōu)缺點(diǎn) 20
2.3 線性表的鏈?zhǔn)酱鎯?chǔ) 21
2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)及其特點(diǎn) 21
2.3.2 單鏈表的建立 23
2.3.3 單鏈表插入和刪除運(yùn)算的實(shí)現(xiàn) 26
2.3.4 單向循環(huán)鏈表 29
2.3.5 雙向鏈表及其運(yùn)算 31
2.3.6 靜態(tài)鏈表 34
2.3.7 線性表鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn) 35
2.4 線性表的應(yīng)用 36
2.4.1 線性表存儲(chǔ)結(jié)構(gòu)的選擇 36
2.4.2 線性表的應(yīng)用舉例 36
2.5 本章小結(jié) 39
習(xí)題2 39
第3章 棧和隊(duì)列 42
3.1 棧的定義與基本運(yùn)算 42
3.2 棧的存儲(chǔ)與運(yùn)算實(shí)現(xiàn) 43
3.2.1 順序棧及其運(yùn)算實(shí)現(xiàn) 43
3.2.2 鏈棧及其運(yùn)算實(shí)現(xiàn) 45
3.2.3 棧的應(yīng)用—括號(hào)匹配 47
3.3 隊(duì)列的定義與基本運(yùn)算 49
3.4 隊(duì)列的存儲(chǔ)與運(yùn)算實(shí)現(xiàn) 49
3.4.1 順序隊(duì)列及其運(yùn)算實(shí)現(xiàn) 49
3.4.2 假溢出與循環(huán)隊(duì)列 51
3.4.3 鏈隊(duì)列及其運(yùn)算實(shí)現(xiàn) 52
3.5 棧和隊(duì)列的綜合應(yīng)用 54
3.5.1 棧的綜合應(yīng)用 54
3.5.2 隊(duì)列的綜合應(yīng)用 58
3.6 本章小結(jié) 59
習(xí)題3 60
第4章 數(shù)組、廣義表與串 63
4.1 數(shù)組的概念與存儲(chǔ) 63
4.1.1 數(shù)組的概念 63
4.1.2 數(shù)組的存儲(chǔ) 64
4.1.3 特殊矩陣的壓縮存儲(chǔ) 65
4.1.4 稀疏矩陣的壓縮存儲(chǔ) 66
4.2 廣義表 69
4.2.1 廣義表的概念與術(shù)語 69
4.2.2 廣義表的運(yùn)算 69
4.2.3 廣義表的存儲(chǔ) 70
4.3 串的定義與存儲(chǔ) 71
4.3.1 串的定義 71
4.3.2 串的存儲(chǔ) 71
4.3.3 串的常見運(yùn)算 73
4.4 串的模式匹配 74
4.4.1 串的模式匹配BF算法 74
4.4.2 串的模式匹配KMP算法 75
4.5 數(shù)組的應(yīng)用舉例 80
4.6 串的應(yīng)用舉例 82
4.7 本章小結(jié) 83
習(xí)題4 84
第5章 樹與二叉樹 86
5.1 樹的基本概念與性質(zhì) 86
5.1.1 樹的定義與術(shù)語 86
5.1.2 樹的表示與基本運(yùn)算 87
5.2 二叉樹的概念與存儲(chǔ) 88
5.2.1 二叉樹的定義及基本運(yùn)算 88
5.2.2 二叉樹的性質(zhì) 90
5.2.3 二叉樹的存儲(chǔ) 91
5.2.4 二叉樹的建立 93
5.3 二叉樹性質(zhì)應(yīng)用舉例 95
5.4 二叉樹的遍歷 96
5.4.1 二叉樹遍歷的概念與思想 96
5.4.2 二叉樹遍歷的遞歸算法 97
5.4.3 二叉樹的層次遍歷 98
5.4.4 二叉樹的非遞歸遍歷 99
5.5 線索二叉樹 102
5.5.1 二叉樹的線索化 103
5.5.2 遍歷線索二叉樹 105
5.6 樹與森林 108
5.6.1 樹的存儲(chǔ) 108
5.6.2 樹及森林與二叉樹的轉(zhuǎn)換 111
5.6.3 樹與森林的遍歷 113
5.7 哈夫曼樹與哈夫曼編碼 114
5.7.1 哈夫曼編碼概述 114
5.7.2 哈夫曼樹與哈夫曼編碼的實(shí)現(xiàn) 115
5.8 樹與二叉樹的應(yīng)用舉例 120
5.9 本章小結(jié) 122
習(xí)題5 123
第6章 圖 126
6.1 圖的概念與性質(zhì) 126
6.1.1 圖的定義 126
6.1.2 圖的有關(guān)術(shù)語 127
6.1.3 圖的基本運(yùn)算 130
6.2 圖的存儲(chǔ) 131
6.2.1 圖的鄰接矩陣存儲(chǔ) 131
6.2.2 圖的鄰接表存儲(chǔ) 134
6.2.3 圖的十字鏈表存儲(chǔ)與鄰接多重表存儲(chǔ) 136
6.3 圖的遍歷 137
6.3.1 圖的深度優(yōu)先遍歷 138
6.3.2 圖的廣度優(yōu)先遍歷 141
6.4 最小生成樹 146
6.4.1 Prim算法構(gòu)造最小生成樹 147
6.4.2 Kruskal算法構(gòu)造最小生成樹 149
6.5 最短路徑 152
6.5.1 單源最短路徑—Dijkstra算法 153
6.5.2 任意兩個(gè)頂點(diǎn)間最短路徑—Floyd算法 157
6.6 拓?fù)湫蛄?160
6.6.1 拓?fù)湫蛄械母拍?161
6.6.2 拓?fù)湫蛄械臉?gòu)造 162
6.6.3 拓?fù)湫蛄械膽?yīng)用舉例 164
6.7 關(guān)鍵路徑 164
6.7.1 關(guān)鍵路徑的概念 165
6.7.2 關(guān)鍵路徑的構(gòu)造 166
6.7.3 關(guān)鍵路徑的應(yīng)用舉例 167
6.8 圖的綜合應(yīng)用舉例 169
6.9 本章小結(jié) 171
習(xí)題6 172
第7章 查找 176
7.1 查找的基本概念 176
7.1.1 查找的定義與分類 176
7.1.2 查找算法的性能評(píng)價(jià) 177
7.2 基于線性表的查找 178
7.2.1 順序查找 178
7.2.2 折半查找 179
7.2.3 分塊查找 181
7.3 基于樹表的查找 182
7.3.1 二叉排序樹 183
7.3.2 平衡二叉排序樹 187
7.3.3 B-樹 191
7.3.4 B+樹 195
7.4 基于哈希表的查找 196
7.4.1 哈希查找的基本思想 196
7.4.2 哈希函數(shù)的構(gòu)造 197
7.4.3 常見沖突處理方法 198
7.4.4 哈希表的基本運(yùn)算 200
7.5 查找算法的應(yīng)用舉例 203
7.6 本章小結(jié) 204
習(xí)題7 205
第8章 排序 207
8.1 排序的基本概念 207
8.1.1 排序的定義及分類 207
8.1.2 排序算法的性能評(píng)價(jià)指標(biāo) 208
8.2 插入排序 209
8.2.1 直接插入排序 209
8.2.2 折半插入排序 211
8.2.3 希爾排序 212
8.3 交換排序 214
8.3.1 冒泡排序 214
8.3.2 快速排序 216
8.4 選擇排序 219
8.4.1 簡(jiǎn)單選擇排序 219
8.4.2 堆排序 220
8.5 歸并排序 224
8.6 多關(guān)鍵字排序 226
8.6.1 多關(guān)鍵字排序的基本概念 226
8.6.2 基數(shù)排序 227
8.7 排序算法的應(yīng)用舉例 230
8.8 本章小結(jié) 231
習(xí)題8 233
參考資料 236