目錄
第1章 緒論 1
1.1 數(shù)據(jù)結構 1
1.1.1 數(shù)據(jù)結構的一般概念 1
1.1.2 不同類型的問題對應的數(shù)據(jù)結構描述模型 2
1.1.3 數(shù)據(jù)結構研究的發(fā)展歷史、內(nèi)容與趨勢 5
1.2 數(shù)據(jù)結構的相關概念與術語 6
1.2.1 基本概念和術語 6
1.2.2 數(shù)據(jù)結構模型描述實例分析 8
1.2.3 其他概念和術語 9
1.2.4 ADT的結構及定義方法 13
1.2.5 多形數(shù)據(jù)類型 15
1.3 ADT的表示與實現(xiàn) 15
1.4 算法及其分析與評價 19
1.4.1 算法及其特征 19
1.4.2 算法設計的基本要求 19
1.4.3 算法的時間效率度量方法 20
1.4.4 常見的時間復雜度函數(shù)增長率分析 22
1.4.5 算法的空間復雜度 23
1.4.6 算法方案選擇的時空辯證關系 23
課外習題 23
第2章 集合與線性表 26
2.1 集合及其邏輯結構特點 26
2.2 集合的ADT描述 26
2.3 集合的表示和實現(xiàn) 27
2.4 線性表及其邏輯結構特點 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 線性表的應用實例 47
課外習題 51
第3章 堆棧和隊列 54
3.1 堆棧 54
3.1.1 現(xiàn)實生活中的例子 54
3.1.2 堆棧的邏輯結構特點 55
3.1.3 堆棧結構的抽象數(shù)據(jù)類型定義 56
3.1.4 堆棧結構的表示與實現(xiàn)方法 56
3.2 堆棧的應用 61
3.3 *堆棧與遞歸 68
3.3.1 遞歸與遞歸函數(shù) 68
3.3.2 n階Hanoi塔問題 69
3.4 隊列 72
3.4.1 隊列的邏輯結構特點 72
3.4.2 隊列的抽象數(shù)據(jù)類型定義 73
3.4.3 隊列的表示與實現(xiàn)方法 73
3.4.4 循環(huán)隊列 76
3.4.5 關于隊列問題的進一步討論 79
課外習題 80
第4章 字符串 83
4.1 字符串的類型定義 83
4.1.1 字符串的基本概念 83
4.1.2 字符串的邏輯結構特點與類型定義 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 字符串操作應用實例 95
4.4.1 文本編輯系統(tǒng) 95
4.4.2 *詞索引表的建立 96
課外習題 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 廣義表的存儲結構 114
5.4.4 *廣義表的遞歸算法實現(xiàn) 116
5.5 *廣義表的應用——m元多項式的表示 120
課外習題 122
第6章 樹和二叉樹 125
6.1 樹的概念及基本術語 125
6.1.1 樹的概念 125
6.1.2 樹的表示方法 126
6.1.3 樹結構問題描述的基本術語 128
6.1.4 樹的ADT定義 129
6.2 二叉樹 130
6.2.1 二叉樹概述 130
6.2.2 二叉樹的性質(zhì) 133
6.2.3 二叉樹的存儲結構 133
6.2.4 線性鏈表的存儲結構實現(xiàn)和基本操作的函數(shù)聲明 135
6.3 二叉樹的遍歷和線索二叉樹 135
6.3.1 二叉樹的遍歷 135
6.3.2 二叉樹遍歷算法的應用 137
6.3.3 線索二叉樹 139
6.4 樹和森林 143
6.4.1 樹的存儲結構 143
6.4.2 森林與二叉樹的轉換 147
6.4.3 樹和森林的遍歷 148
6.5 哈夫曼樹及其應用 148
6.5.1 哈夫曼樹 148
6.5.2 哈夫曼編碼 151
課外習題 156
第7章 圖 158
7.1 圖的定義及基本術語 158
7.1.1 基本術語 158
7.1.2 圖的ADT描述 161
7.2 圖的存儲結構 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 *關節(jié)點和重連通分量 178
7.5 有向無環(huán)圖及其應用 181
7.5.1 TOP排序 183
7.5.2 關鍵路徑 186
7.6 最短路徑 190
7.6.1 單源點最短路徑求解 190
7.6.2 全部頂點對的最短路徑求解 193
課外習題 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 多關鍵字排序 217
8.6.2 鏈式基數(shù)排序 219
8.7 各種內(nèi)部排序方法的比較與優(yōu)化 222
課外習題 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ù)的構造方法 258
9.4.3 Hash沖突處理方法 262
9.4.4 Hash表的查找效率分析 265
課外習題 266
參考文獻 268
附錄 269