數(shù)據(jù)結(jié)構(gòu)

第1章 緒論1
1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容和作用1
1.2 數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本概念3
1.2.1 基本概念3
1.2.2 數(shù)據(jù)結(jié)構(gòu)3
1.3 算法及其描述和分析5
1.3.1 算法及其設(shè)計原則5
1.3.2 算法的描述5
1.3.3 算法效率的衡量方法6
1.3.4 算法的存儲空間需求7
習題18
第2章 線性表10
2.1 線性表的邏輯結(jié)構(gòu)10
2.1.1 線性表的定義10
2.1.2 線性表的基本操作11
2.2 線性表的順序表示及其實現(xiàn)12
2.2.1 順序表12
2.2.2 順序表上的基本操作實現(xiàn)13
2.2.3 順序表應(yīng)用舉例17
2.3 線性表的鏈式表示及其實現(xiàn)18
2.3.1 單鏈表18
2.3.2 單鏈表基本運算及其實現(xiàn)19
2.3.3 循環(huán)鏈表23
2.3.4 雙向鏈表24
2.3.5 靜態(tài)鏈表26
2.4 一元多項式的表示27
2.5 線性表的應(yīng)用舉例29
習題230
第3章 棧和隊列33
3.1 棧33
3.1.1 棧的定義及基本運算33
3.1.2 棧的存儲與操作實現(xiàn)34
3.1.3 棧的應(yīng)用舉例36
3.2 隊列43
3.2.1 隊列的定義及基本運算43
3.2.2 隊列的存儲表示和操作的實現(xiàn)44
3.2.3 隊列應(yīng)用舉例47
習題350
◆數(shù)據(jù)結(jié)構(gòu)目 錄第4章 串52
4.1 串的定義、表示和實現(xiàn)52
4.1.1 串的基本概念52
4.1.2 串的基本操作53
4.2 串的存儲和基本運算實現(xiàn)54
4.2.1 串的定長順序存儲與基本運算實現(xiàn)54
4.2.2 串的堆存儲與基本運算實現(xiàn)56
4.2.3 串的塊鏈存儲與基本運算實現(xiàn)57
4.3 串的模式匹配58
4.3.1 簡單模式匹配算法58
4.3.2 改進的模式匹配算法59
4.4 串的應(yīng)用舉例63
習題465
第5章 數(shù)組和廣義表66
5.1 數(shù)組66
5.1.1 數(shù)組的定義66
5.1.2 數(shù)組的順序存儲結(jié)構(gòu)66
5.2 特殊矩陣的壓縮存儲 68
5.2.1 對稱矩陣 68
5.2.2 下(上)三角矩陣 69
5.2.3 對角矩陣69
5.3 稀疏矩陣的壓縮存儲70
5.3.1 稀疏矩陣定義70
5.3.2 稀疏矩陣的壓縮存儲方法--三元組表70
5.3.3 稀疏矩陣的壓縮存儲方法--十字鏈存儲法74
5.4 廣義表75
5.4.1 廣義表的概念和基本操作75
5.4.2 廣義表的存儲結(jié)構(gòu)76
5.4.3 廣義表基本操作的實現(xiàn)79
習題582
第6章 樹和二叉樹84
6.1 樹的類型定義84
6.2 二叉樹85
6.2.1 二叉樹的類型定義85
6.2.2 二叉樹的幾個特性86
6.2.3 二叉樹的基本操作87
6.3 二叉樹的存儲87
6.3.1 順序存儲結(jié)構(gòu)87
6.3.2 鏈式存儲結(jié)構(gòu)88
6.4 二叉樹的操作90
6.4.1 二叉樹的遍歷90
6.4.2 二叉樹的其他操作算法舉例92
6.5 線索二叉樹94
6.5.1 二叉樹的線索鏈表94
6.5.2 以中序線索鏈表為存儲結(jié)構(gòu)的中序遍歷96
6.5.3 線索鏈表的生成96
6.6 樹和森林97
6.6.1 樹的存儲結(jié)構(gòu)97
6.6.2 樹、森林與二叉樹的相互轉(zhuǎn)換101
6.6.3 樹、森林的遍歷102
6.6.4 應(yīng)用舉例103
6.7 哈夫曼樹及其應(yīng)用104
6.7.1 最優(yōu)二叉樹的定義104
6.7.2 最優(yōu)二叉樹的構(gòu)造方法105
6.7.3 最優(yōu)前綴編碼106
6.7.4 哈夫曼編碼算法的實現(xiàn)108
習題6110
第7章 圖112
7.1 圖的基本概念112
7.1.1 圖的定義和術(shù)語112
7.1.2 圖的基本操作116
7.2 圖的存儲結(jié)構(gòu)116
7.2.1 鄰接矩陣117
7.2.2 鄰接表119
7.3 圖的遍歷121
7.3.1 深度優(yōu)先遍歷121
7.3.2 廣度優(yōu)先遍歷123
7.4 圖的連通性124
7.4.1 圖的連通性及其判定124
7.4.2 生成樹與最小生成樹125
7.5 有向無環(huán)圖及其應(yīng)用129
7.5.1 有向無環(huán)圖的概念129
7.5.2 AOV網(wǎng)與拓撲排序130
7.5.3 AOE網(wǎng)與關(guān)鍵路徑133
7.6 最短路徑139
7.6.1 求某一頂點到其余各頂點的最短路徑139
7.6.2 求任意一對頂點之間的最短路徑142
7.7 應(yīng)用舉例144
習題7148
第8章 查找151
8.1 靜態(tài)查找表151
8.1.1 順序查找152
8.1.2 有序表的折半查找153
8.1.3 分塊查找155
8.2 動態(tài)查找表156
8.2.1 二叉排序樹156
8.2.2 平衡二叉樹160
8.2.3 B-樹和B+樹165
8.3 哈希表171
8.3.1 哈希表與哈希方法171
8.3.2 常用的哈希函數(shù)172
8.3.3 處理沖突的方法174
8.3.4 哈希表的查找分析176
習題8177
第9章 排序179
9.1 內(nèi)排序算法179
9.1.1 插入排序179
9.1.2 交換排序186
9.1.3 選擇排序189
9.1.4 二路歸并排序193
9.1.5 基數(shù)排序195
9.2 外排序算法199
習題9200
參考文獻203