目錄
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu) 1
1.1.1 數(shù)據(jù)結(jié)構(gòu)的一般概念 1
1.1.2 不同類型的問(wèn)題對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)描述模型 2
1.1.3 數(shù)據(jù)結(jié)構(gòu)研究的發(fā)展歷史、內(nèi)容與趨勢(shì) 5
1.2 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念與術(shù)語(yǔ) 6
1.2.1 基本概念和術(shù)語(yǔ) 6
1.2.2 數(shù)據(jù)結(jié)構(gòu)模型描述實(shí)例分析 8
1.2.3 其他概念和術(shù)語(yǔ) 9
1.2.4 ADT的結(jié)構(gòu)及定義方法 13
1.2.5 多形數(shù)據(jù)類型 15
1.3 ADT的表示與實(shí)現(xiàn) 15
1.4 算法及其分析與評(píng)價(jià) 19
1.4.1 算法及其特征 19
1.4.2 算法設(shè)計(jì)的基本要求 19
1.4.3 算法的時(shí)間效率度量方法 20
1.4.4 常見的時(shí)間復(fù)雜度函數(shù)增長(zhǎng)率分析 22
1.4.5 算法的空間復(fù)雜度 23
1.4.6 算法方案選擇的時(shí)空辯證關(guān)系 23
課外習(xí)題 23
第2章 集合與線性表 26
2.1 集合及其邏輯結(jié)構(gòu)特點(diǎn) 26
2.2 集合的ADT描述 26
2.3 集合的表示和實(shí)現(xiàn) 27
2.4 線性表及其邏輯結(jié)構(gòu)特點(diǎn) 29
2.5 線性表的ADT描述 30
2.6 線性表的順序表示和實(shí)現(xiàn) 33
2.7 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 35
2.7.1 線性鏈表的概念 35
2.7.2 (動(dòng)態(tài))單鏈表的表示和實(shí)現(xiàn) 37
2.7.3 (靜態(tài))單鏈表的表示和實(shí)現(xiàn) 40
2.7.4 循環(huán)鏈表 44
2.7.5 雙向鏈表 44
2.8 線性表的應(yīng)用實(shí)例 47
課外習(xí)題 51
第3章 堆棧和隊(duì)列 54
3.1 堆棧 54
3.1.1 現(xiàn)實(shí)生活中的例子 54
3.1.2 堆棧的邏輯結(jié)構(gòu)特點(diǎn) 55
3.1.3 堆棧結(jié)構(gòu)的抽象數(shù)據(jù)類型定義 56
3.1.4 堆棧結(jié)構(gòu)的表示與實(shí)現(xiàn)方法 56
3.2 堆棧的應(yīng)用 61
3.3 *堆棧與遞歸 68
3.3.1 遞歸與遞歸函數(shù) 68
3.3.2 n階Hanoi塔問(wèn)題 69
3.4 隊(duì)列 72
3.4.1 隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn) 72
3.4.2 隊(duì)列的抽象數(shù)據(jù)類型定義 73
3.4.3 隊(duì)列的表示與實(shí)現(xiàn)方法 73
3.4.4 循環(huán)隊(duì)列 76
3.4.5 關(guān)于隊(duì)列問(wèn)題的進(jìn)一步討論 79
課外習(xí)題 80
第4章 字符串 83
4.1 字符串的類型定義 83
4.1.1 字符串的基本概念 83
4.1.2 字符串的邏輯結(jié)構(gòu)特點(diǎn)與類型定義 84
4.2 字符串的表示和實(shí)現(xiàn) 85
4.2.1 定長(zhǎng)順序存儲(chǔ)表示 85
4.2.2 動(dòng)態(tài)順序存儲(chǔ)表示 86
4.2.3 塊鏈存儲(chǔ)表示 89
4.3 *字符串的模式匹配算法 91
4.3.1 問(wèn)題的提出 91
4.3.2 KMP算法 92
4.4 字符串操作應(yīng)用實(shí)例 95
4.4.1 文本編輯系統(tǒng) 95
4.4.2 *詞索引表的建立 96
課外習(xí)題 97
第5章 數(shù)組和廣義表 98
5.1 數(shù)組類型的一般定義 98
5.2 數(shù)組類型的一般表示與實(shí)現(xiàn) 99
5.3 矩陣的壓縮存儲(chǔ)與運(yùn)算 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 廣義表的存儲(chǔ)結(jié)構(gòu) 114
5.4.4 *廣義表的遞歸算法實(shí)現(xiàn) 116
5.5 *廣義表的應(yīng)用——m元多項(xiàng)式的表示 120
課外習(xí)題 122
第6章 樹和二叉樹 125
6.1 樹的概念及基本術(shù)語(yǔ) 125
6.1.1 樹的概念 125
6.1.2 樹的表示方法 126
6.1.3 樹結(jié)構(gòu)問(wèn)題描述的基本術(shù)語(yǔ) 128
6.1.4 樹的ADT定義 129
6.2 二叉樹 130
6.2.1 二叉樹概述 130
6.2.2 二叉樹的性質(zhì) 133
6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 133
6.2.4 線性鏈表的存儲(chǔ)結(jié)構(gòu)實(shí)現(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 樹的存儲(chǔ)結(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ù)語(yǔ) 158
7.1.1 基本術(shù)語(yǔ) 158
7.1.2 圖的ADT描述 161
7.2 圖的存儲(chǔ)結(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 圖的連通性問(wèn)題 173
7.4.1 無(wú)向圖的連通分量和生成樹 173
7.4.2 *有向圖的強(qiáng)連通分量 174
7.4.3 最小生成樹 174
7.4.4 *關(guān)節(jié)點(diǎn)和重連通分量 178
7.5 有向無(wú)環(huán)圖及其應(yīng)用 181
7.5.1 TOP排序 183
7.5.2 關(guān)鍵路徑 186
7.6 最短路徑 190
7.6.1 單源點(diǎn)最短路徑求解 190
7.6.2 全部頂點(diǎn)對(duì)的最短路徑求解 193
課外習(xí)題 195
第8章 內(nèi)部排序 199
8.1 基本概念 199
8.2 插入排序 200
8.2.1 直接插入排序 200
8.2.2 直接插入排序的改進(jìn)算法 201
8.2.3 Shell排序 206
8.3 快速排序 207
8.4 選擇排序 210
8.4.1 簡(jiǎn)單選擇排序 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 鏈?zhǔn)交鶖?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 動(dòng)態(tài)查找表 237
9.3.1 動(dòng)態(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
參考文獻(xiàn) 268
附錄 269