數(shù)據(jù)結(jié)構(gòu)：抽象建模、實(shí)現(xiàn)與應(yīng)用

前言
第1章　概論 1
1.1　引言 1
1.2　數(shù)據(jù)結(jié)構(gòu)相關(guān)概念及術(shù)語(yǔ) 1
1.3　抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn) 3
1.4　算法與算法分析 6
1.4.1　算法 6
1.4.2　算法分析與度量 8
1.5　小結(jié) 10
1.6　練習(xí) 10
第2章　線性表 11
2.1　引言 11
2.2　線性表的抽象數(shù)據(jù)類(lèi)型 11
2.3　線性表的順序表示與實(shí)現(xiàn) 15
2.3.1　順序表的定義和特點(diǎn) 15
2.3.2　順序表的存儲(chǔ)結(jié)構(gòu) 15
2.3.3　順序表基本操作的實(shí)現(xiàn)與性能分析 16
2.4　線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 19
2.4.1　單鏈表 20
2.4.2　其他形式的鏈表 24
2.5　線性表的應(yīng)用舉例 27
2.6　小結(jié) 31
2.7　練習(xí) 31
第3章　棧和隊(duì)列 32
3.1　引言 32
3.2　棧的抽象數(shù)據(jù)類(lèi)型 32
3.3　棧的順序表示與實(shí)現(xiàn) 33
3.4　棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 36
3.5　棧的應(yīng)用舉例 37
3.5.1　逆序輸出問(wèn)題 37
3.5.2　最近匹配與比較問(wèn)題 38
3.5.3　遞歸與回溯問(wèn)題 43
3.6　隊(duì)列的抽象數(shù)據(jù)類(lèi)型 47
3.7　隊(duì)列的順序表示與實(shí)現(xiàn) 48
3.8　隊(duì)列的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 50
3.9　隊(duì)列的應(yīng)用舉例 52
3.10　小結(jié) 53
3.11　練習(xí) 53
第4章　數(shù)組、廣義表和字符串 54
4.1　引言 54
4.2　數(shù)組 54
4.2.1　一維數(shù)組 54
4.2.2　二維數(shù)組 55
4.3　特殊矩陣的壓縮存儲(chǔ) 56
4.3.1　對(duì)稱矩陣 56
4.3.2　對(duì)角矩陣 57
4.4　稀疏矩陣的壓縮存儲(chǔ) 57
4.4.1　稀疏矩陣的三元組表示 57
4.4.2　三元組的順序表表示 58
4.4.3　三元組的十字鏈表表示 61
4.5　廣義表 62
4.5.1　廣義表的概念 62
4.5.2　廣義表的抽象數(shù)據(jù)類(lèi)型 63
4.5.3　廣義表的存儲(chǔ)結(jié)構(gòu) 64
4.6　字符串 66
4.6.1　字符串的抽象數(shù)據(jù)類(lèi)型 66
4.6.2　字符串的存儲(chǔ)結(jié)構(gòu)與子串定位 67
4.7　小結(jié) 68
4.8　練習(xí) 68
第5章　樹(shù)和二叉樹(shù) 70
5.1　引言 70
5.2　樹(shù)的定義和基本術(shù)語(yǔ) 70
5.2.1　樹(shù)的定義 70
5.2.2　樹(shù)的邏輯表示 71
5.2.3　樹(shù)的基本術(shù)語(yǔ) 72
5.2.4　樹(shù)的抽象數(shù)據(jù)類(lèi)型 72
5.3　二叉樹(shù) 73
5.3.1　二叉樹(shù)的定義 73
5.3.2　二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型 74
5.3.3　二叉樹(shù)的性質(zhì) 76
5.3.4　二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 77
5.3.5　二叉樹(shù)的遍歷 79
5.3.6　二叉樹(shù)遍歷算法的
應(yīng)用舉例 81
5.4　樹(shù)和森林 85
5.4.1　樹(shù)與二叉樹(shù)的轉(zhuǎn)換 85
5.4.2　森林與二叉樹(shù)的轉(zhuǎn)換 86
5.4.3　樹(shù)和森林的遍歷 87
5.5　霍夫曼樹(shù) 88
5.5.1　霍夫曼樹(shù)的定義 88
5.5.2　霍夫曼樹(shù)的構(gòu)造 90
5.5.3　霍夫曼編碼 90
5.5.4　霍夫曼樹(shù)和霍夫曼編碼的算法實(shí)現(xiàn) 92
5.6　小結(jié) 94
5.7　練習(xí) 94
第6章　圖 95
6.1　引言 95
6.2　圖的定義、基本術(shù)語(yǔ)和抽象數(shù)據(jù)類(lèi)型 95
6.3　圖的存儲(chǔ)方式 97
6.3.1　鄰接矩陣 97
6.3.2　鄰接表 99
6.4　圖的遍歷 101
6.4.1　深度優(yōu)先遍歷 101
6.4.2　廣度優(yōu)先遍歷 102
6.4.3　圖的遍歷算法的應(yīng)用舉例 103
6.5　最小生成樹(shù) 107
6.5.1　最小生成樹(shù)的定義 107
6.5.2　普里姆算法 108
6.5.3　克魯斯卡爾算法 111
6.6　拓?fù)渑判蚺c關(guān)鍵路徑 112
6.6.1　拓?fù)渑判?112
6.6.2　AOE網(wǎng)與關(guān)鍵路徑 113
6.7　最短路徑問(wèn)題 116
6.7.1　單源最短路徑問(wèn)題 116
6.7.2　所有頂點(diǎn)對(duì)之間的最短路徑 119
6.8　小結(jié) 121
6.9　練習(xí) 122
第7章　查找 123
7.1　引言 123
7.2　查找表的定義與抽象數(shù)據(jù)類(lèi)型 123
7.3　順序表的靜態(tài)查找 124
7.3.1　順序查找 125
7.3.2　折半查找 126
7.3.3　索引查找 129
7.4　樹(shù)表的動(dòng)態(tài)查找 130
7.4.1　二叉排序樹(shù) 130
7.4.2　平衡二叉排序樹(shù) 138
7.4.3　B-樹(shù) 141
7.4.4　B+樹(shù) 146
7.5　哈希表的查找 147
7.5.1　哈希表的定義 147
7.5.2　哈希函數(shù)的構(gòu)造方法 148
7.5.3　處理沖突的方式 150
7.5.4　哈希表的查找 152
7.5.5　性能分析 153
7.6　小結(jié) 155
7.7　練習(xí) 156
第8章　排序 157
8.1　引言 157
8.2　排序的定義與分類(lèi) 157
8.2.1　排序的定義 157
8.2.2　排序的分類(lèi) 157
8.2.3　排序的數(shù)據(jù)類(lèi)型 158
8.3　插入排序 158
8.3.1　直接插入排序 158
8.3.2　希爾排序 160
8.4　交換排序 162
8.4.1　簡(jiǎn)單交換排序 162
8.4.2　快速排序 164
8.5　選擇排序 166
8.5.1　簡(jiǎn)單選擇排序 167
8.5.2　樹(shù)形選擇排序 168
8.5.3　堆排序 169
8.6　歸并排序 173
8.7　基數(shù)排序 175
8.7.1　多關(guān)鍵字的排序 175
8.7.2　基數(shù)排序的實(shí)現(xiàn) 176
8.8　各種內(nèi)部排序方法的比較 178
8.9　小結(jié) 179
8.10　練習(xí) 179