目錄
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu) 1
1.1.1 數(shù)據(jù)結(jié)構(gòu)的一般概念 1
1.1.2 不同類型的問題對應(yīng)的數(shù)據(jù)結(jié)構(gòu)描述模型 2
1.1.3 數(shù)據(jù)結(jié)構(gòu)研究的發(fā)展歷史、內(nèi)容與趨勢 5
1.2 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念與術(shù)語 6
1.2.1 基本概念和術(shù)語 6
1.2.2 數(shù)據(jù)結(jié)構(gòu)模型描述實例分析 8
1.2.3 其他概念和術(shù)語 9
1.2.4 ADT的結(jié)構(gòu)及定義方法 13
1.2.5 多形數(shù)據(jù)類型 15
1.3 ADT的表示與實現(xiàn) 15
1.4 算法及其分析與評價 19
1.4.1 算法及其特征 19
1.4.2 算法設(shè)計的基本要求 19
1.4.3 算法的時間效率度量方法 20
1.4.4 常見的時間復(fù)雜度函數(shù)增長率分析 22
1.4.5 算法的空間復(fù)雜度 23
1.4.6 算法方案選擇的時空辯證關(guān)系 23
課外習(xí)題 23
第2章 集合與線性表 26
2.1 集合及其邏輯結(jié)構(gòu)特點 26
2.2 集合的ADT描述 26
2.3 集合的表示和實現(xiàn) 27
2.4 線性表及其邏輯結(jié)構(gòu)特點 29
2.5 線性表的ADT描述 30
2.6 線性表的順序表示和實現(xiàn) 33
2.7 線性表的鏈式表示和實現(xiàn) 35
2.7.1 線性鏈表的概念 35
2.7.2 (動態(tài))單鏈表的表示和實現(xiàn) 37
2.7.3 (靜態(tài))單鏈表的表示和實現(xiàn) 40
2.7.4 循環(huán)鏈表 44
2.7.5 雙向鏈表 44
2.8 線性表的應(yīng)用實例 47
課外習(xí)題 51
第3章 堆棧和隊列 54
3.1 堆棧 54
3.1.1 現(xiàn)實生活中的例子 54
3.1.2 堆棧的邏輯結(jié)構(gòu)特點 55
3.1.3 堆棧結(jié)構(gòu)的抽象數(shù)據(jù)類型定義 56
3.1.4 堆棧結(jié)構(gòu)的表示與實現(xiàn)方法 56
3.2 堆棧的應(yīng)用 61
3.3 *堆棧與遞歸 68
3.3.1 遞歸與遞歸函數(shù) 68
3.3.2 n階Hanoi塔問題 69
3.4 隊列 72
3.4.1 隊列的邏輯結(jié)構(gòu)特點 72
3.4.2 隊列的抽象數(shù)據(jù)類型定義 73
3.4.3 隊列的表示與實現(xiàn)方法 73
3.4.4 循環(huán)隊列 76
3.4.5 關(guān)于隊列問題的進一步討論 79
課外習(xí)題 80
第4章 字符串 83
4.1 字符串的類型定義 83
4.1.1 字符串的基本概念 83
4.1.2 字符串的邏輯結(jié)構(gòu)特點與類型定義 84
4.2 字符串的表示和實現(xiàn) 85
4.2.1 定長順序存儲表示 85
4.2.2 動態(tài)順序存儲表示 86
4.2.3 塊鏈存儲表示 89
4.3 *字符串的模式匹配算法 91
4.3.1 問題的提出 91
4.3.2 KMP算法 92
4.4 字符串操作應(yīng)用實例 95
4.4.1 文本編輯系統(tǒng) 95
4.4.2 *詞索引表的建立 96
課外習(xí)題 97
第5章 數(shù)組和廣義表 98
5.1 數(shù)組類型的一般定義 98
5.2 數(shù)組類型的一般表示與實現(xiàn) 99
5.3 矩陣的壓縮存儲與運算 101
5.3.1 有特殊規(guī)律的矩陣 101
5.3.2 取值稀疏的矩陣 103
5.4 廣義表 112
5.4.1 廣義表概述 112
5.4.2 廣義表的ADT定義 113
5.4.3 廣義表的存儲結(jié)構(gòu) 114
5.4.4 *廣義表的遞歸算法實現(xiàn) 116
5.5 *廣義表的應(yīng)用——m元多項式的表示 120
課外習(xí)題 122
第6章 樹和二叉樹 125
6.1 樹的概念及基本術(shù)語 125
6.1.1 樹的概念 125
6.1.2 樹的表示方法 126
6.1.3 樹結(jié)構(gòu)問題描述的基本術(shù)語 128
6.1.4 樹的ADT定義 129
6.2 二叉樹 130
6.2.1 二叉樹概述 130
6.2.2 二叉樹的性質(zhì) 133
6.2.3 二叉樹的存儲結(jié)構(gòu) 133
6.2.4 線性鏈表的存儲結(jié)構(gòu)實現(xiàn)和基本操作的函數(shù)聲明 135
6.3 二叉樹的遍歷和線索二叉樹 135
6.3.1 二叉樹的遍歷 135
6.3.2 二叉樹遍歷算法的應(yīng)用 137
6.3.3 線索二叉樹 139
6.4 樹和森林 143
6.4.1 樹的存儲結(jié)構(gòu) 143
6.4.2 森林與二叉樹的轉(zhuǎn)換 147
6.4.3 樹和森林的遍歷 148
6.5 哈夫曼樹及其應(yīng)用 148
6.5.1 哈夫曼樹 148
6.5.2 哈夫曼編碼 151
課外習(xí)題 156
第7章 圖 158
7.1 圖的定義及基本術(shù)語 158
7.1.1 基本術(shù)語 158
7.1.2 圖的ADT描述 161
7.2 圖的存儲結(jié)構(gòu) 162
7.2.1 引入 162
7.2.2 數(shù)組表示法 162
7.2.3 鄰接表表示法 165
7.2.4 十字鏈表表示法 167
7.2.5 鄰接多重表表示法 169
7.3 圖的遍歷 170
7.3.1 深度優(yōu)先搜索算法 171
7.3.2 廣度優(yōu)先搜索算法 172
7.4 圖的連通性問題 173
7.4.1 無向圖的連通分量和生成樹 173
7.4.2 *有向圖的強連通分量 174
7.4.3 最小生成樹 174
7.4.4 *關(guān)節(jié)點和重連通分量 178
7.5 有向無環(huán)圖及其應(yīng)用 181
7.5.1 TOP排序 183
7.5.2 關(guān)鍵路徑 186
7.6 最短路徑 190
7.6.1 單源點最短路徑求解 190
7.6.2 全部頂點對的最短路徑求解 193
課外習(xí)題 195
第8章 內(nèi)部排序 199
8.1 基本概念 199
8.2 插入排序 200
8.2.1 直接插入排序 200
8.2.2 直接插入排序的改進算法 201
8.2.3 Shell排序 206
8.3 快速排序 207
8.4 選擇排序 210
8.4.1 簡單選擇排序 210
8.4.2 樹形選擇排序 212
8.4.3 堆排序 213
8.5 歸并排序 216
8.6 基數(shù)排序 217
8.6.1 多關(guān)鍵字排序 217
8.6.2 鏈式基數(shù)排序 219
8.7 各種內(nèi)部排序方法的比較與優(yōu)化 222
課外習(xí)題 226
第9章 查找 229
9.1 基本概念 229
9.2 靜態(tài)查找表 230
9.2.1 靜態(tài)查找表的ADT定義 230
9.2.2 順序表的順序查找 230
9.2.3 有序順序表的查找 232
9.2.4 *靜態(tài)最優(yōu)查找樹的查找 235
9.2.5 索引順序表的查找 236
9.3 動態(tài)查找表 237
9.3.1 動態(tài)查找表的ADT定義 237
9.3.2 基于二叉樹的排序樹和平衡二叉樹 238
9.3.3 *B-樹和B+樹 248
9.3.4 *鍵樹 253
9.4 Hash表 257
9.4.1 Hash表概述 257
9.4.2 Hash函數(shù)的構(gòu)造方法 258
9.4.3 Hash沖突處理方法 262
9.4.4 Hash表的查找效率分析 265
課外習(xí)題 266
參考文獻 268
附錄 269