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

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

【媒體評(píng)論】