數(shù)據(jù)結構

第1章 緒論 1
1.1 數(shù)據(jù)結構研究什么 1
1.2 數(shù)據(jù)結構的發(fā)展概況和在計算機科學中的地位 3
1.3 基本概念和術語 4
1.4 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 6
1.5 算法和算法分析 7
1.6 小結 11
習題 11
第2章 線性表 12
2.1 線性表的基本概念 12
2.2 順序存儲的線性表 13
2.3 鏈式存儲的線性表 17
2.3.1 單鏈表 17
2.3.2 循環(huán)鏈表 32
2.3.3 雙向鏈表 33
2.4 廣義表 35
2.5 小結 37
習題 38
第3章 棧和隊列 40
3.1 棧 40
3.1.1 棧的定義和操作 40
3.1.2 棧的表示和操作的實現(xiàn) 41
3.1.3 棧的應用舉例 43
3.2 隊列 61
3.2.1 隊列定義和操作 61
3.2.2 隊列的表示和操作的實現(xiàn) 62
3.2.3 隊列的應用舉例 65
3.3 兩個棧和隊列的C語言程序舉例 68
3.4 小結 76
習題 76
第4章 串和數(shù)組 78
4.1 字符串 78
4.1.1 串的定義和操作 78
4.1.2 串的存儲結構和相應的操作 80
4.1.3 正文模式匹配 86
4.1.4 文本編輯 87
4.2 數(shù)組 89
4.2.1 數(shù)組的定義和操作 89
4.2.2 數(shù)組的順序表示 89
4.2.3 矩陣的壓縮存儲 90
4.2.4 一個數(shù)組應用的C語言程序 98
4.3 小結 101
習題 101
第5章 樹與二叉樹 102
5.1 樹的定義及基本術語 102
5.1.1 樹的定義 102
5.1.2 基本術語 103
5.2 二叉樹 104
5.2.1 二叉樹的性質 104
5.2.2 二叉樹的存儲結構 106
5.2.3 二叉樹的建立 109
5.3 遍歷二叉樹 114
5.3.1 二叉樹的遍歷算法 114
5.3.2 二叉樹遍歷算法的應用 120
5.4 線索二叉樹 127
5.4.1 二叉樹的線索化算法 129
5.4.2 線索二叉樹的有關操作 131
5.5 二叉排序樹（二叉查找樹） 135
5.5.1 二叉排序樹的建立和插入 135
5.5.2 二叉排序樹的查找 137
5.5.3 二叉排序樹的刪除 139
5.5.4 平衡二叉樹的概念 142
5.6 樹和森林 143
5.6.1 樹的存儲結構 143
5.6.2 樹和森林與二叉樹的轉化 146
5.6.3 樹和森林的遍歷 148
5.7 哈夫曼樹及其應用 151
5.8 小結 157
習題 158
第6章 圖 160
6.1 基本概念和術語 160
6.2 圖的存儲結構 163
6.2.1 鄰接矩陣 163
6.2.2 鄰接表 165
6.3 圖的遍歷 168
6.3.1 深度優(yōu)先搜索遍歷 168
6.3.2 廣度優(yōu)先搜索遍歷 171
6.4 連通網(wǎng)的最小生成樹 172
6.4.1 普里姆（Prim）算法 173
6.4.2 克魯斯卡爾(Kruskal)算法 177
6.5 最短路徑 180
6.5.1 從某個源點到其余各頂點的最短路徑 181
6.5.2 每一對頂點間的最短路徑 186
6.6 拓撲排序 189
6.7 關鍵路徑 194
6.8 小結 200
習題 200
第7章 排序 203
7.1 內(nèi)排序 204
7.1.1 內(nèi)排序的分類 204
7.1.2 插入排序 205
7.1.3 交換排序 211
7.1.4 選擇排序 216
7.1.5 合并排序 222
7.1.6 計數(shù)排序 229
7.1.7 基數(shù)排序 231
7.1.8 各種內(nèi)排序方法的比較討論 235
7.2 外排序 237
7.2.1 K路平衡歸并 237
7.2.2 置換-選擇排序 242
7.2.3 哈夫曼歸并樹 243
7.2.4 一個利用敗者樹進行外排序的C語言程序示例 245
7.3 小結 249
習題 250
第8章 查找 251
8.1 查找的基本概念 251
8.2 靜態(tài)查找表 252
8.3 動態(tài)查找表 256
8.3.1 B樹 256
8.3.2 B+樹 261
8.3.3 一個B+樹的C語言實例 265
8.3.4 B樹與B+樹各種操作的比較 276
8.4 哈希表 277
8.4.1 概述 277
8.4.2 哈希函數(shù) 279
8.4.3 處理沖突的方法及相應的造表和有關操作 280
8.4.4 哈希表的查找分析 285
8.5 小結 286
習題 287
第9章 文件 288
9.1 文件的基本概念和文件的存儲結構 288
9.2 順序文件 290
9.2.1 存儲在順序存儲器上的順序文件 290
9.2.2 存儲在直接存取存儲器上的順序文件 291
9.2.3 堆文件 292
9.3 索引文件和索引順序文件 292
9.3.1 索引文件 293
9.3.2 索引順序文件 293
9.3.3 對于B樹、B+樹需要注意的問題 294
9.4 哈希文件 296
9.4.1 文件的組織方式 296
9.4.2 文件的操作 298
9.4.3 文件的擴充 298
9.5 多關鍵字文件 299
9.5.1 索引鏈接文件（多重表文件） 299
9.5.2 倒排文件 301
9.6 小結 302
習題 303
參考書目 304

【媒體評論】