數(shù)據(jù)結(jié)構(gòu)考點精要與解題指導

第1章　緒論　1
1.1　考點精要　1
1.1.1　什么是數(shù)據(jù)結(jié)構(gòu)　1
1.1.2　算法和算法分析　2
1.2　例題解析　3
1.3　自測題及參考答案　6

第2章　線性表　10
2.1　考點精要　10
2.1.1　線性表的概念　10
2.1.2　線性表的順序存儲結(jié)構(gòu)　11
2.1.3　線性表的鏈式存儲結(jié)構(gòu)　13
2.2　例題解析　17
2.3　自測題及參考答案　25

第3章　棧和隊列　44
3.1　考點精要　44
3.1.1　?！?4
3.1.2　隊列　48
3.1.3　利用棧實現(xiàn)遞歸算法到非遞歸算法的轉(zhuǎn)換　52
3.2　例題解析　54
3.3　自測題及參考答案　63

第4章　串　74
4.1　考點精要　74
4.1.1　串的基本概念　74
4.1.2　順序串　74
4.1.3　鏈串　77
4.1.4　串的模式匹配　80
4.2　例題解析　81
4.3　自測題及參考答案　84

第5章　數(shù)組和廣義表　90
5.1　考點精要　90
5.1.1　數(shù)組　90
5.1.2　特殊矩陣的壓縮存儲　91
5.1.3　稀疏矩陣　92
5.1.4　廣義表　96
5.2　例題解析　100
5.3　自測題及參考答案　107

第6章　樹和二叉樹　116
6.1　考點精要　116
6.1.1　樹的基本概念　116
6.1.2　二叉樹的概念和性質(zhì)　118
6.1.3　二叉樹的存儲結(jié)構(gòu)　120
6.1.4　二叉樹的基本運算及其實現(xiàn)　121
6.1.5　二叉樹的遍歷　124
6.1.6　線索二叉樹　125
6.1.7　哈夫曼樹　126
6.2　例題解析　127
6.3　自測題及參考答案　134

第7章　圖　160
7.1　考點精要　160
7.1.1　圖的基本概念　160
7.1.2　圖的遍歷　162
7.1.3　生成樹和最小生成樹　164
7.1.4　最短路徑　165
7.1.5　拓撲排序　166
7.1.6　AOE網(wǎng)與關(guān)鍵路徑　166
7.2　例題解析　167
7.3　自測題及參考答案　174

第8章　查找　188
8.1　考點精要　188
8.1.1　線性表的查找　188
8.1.2　樹表的查找　190
8.1.3　哈希表查找　193
8.2　例題解析　195
8.3　自測題及參考答案　200

第9章　內(nèi)排序　214
9.1　考點精要　214
9.1.1　排序的概念　214
9.1.2　插入排序　214
9.1.3　交換排序　215
9.1.4　選擇排序　217
9.1.5　歸并排序　219
9.1.6　基數(shù)排序　220
9.2　例題解析　222
9.3　自測題及參考答案　228

第10章　外排序　239
10.1　考點精要　239
10.1.1　外排序概述　239
10.1.2　磁盤排序　239
10.1.3　磁帶排序方法　241
10.2　例題解析　241
10.3　自測題及參考答案　243

第11章　文件　246
11.1　考點精要　246
11.1.1　文件的基本概念　246
11.1.2　順序文件　246
11.1.3　索引文件　247
11.1.4　索引順序文件　247
11.1.5　散列文件　248
11.1.6　多關(guān)鍵字文件　248
11.2　例題解析　248
11.3　自測題及參考答案　252

附錄　本書程序使用的C++語法說明　254
參考文獻　255