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

目錄
前言
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的研究現(xiàn)狀與發(fā)展 1
1.1.1 國外的研究現(xiàn)狀與發(fā)展 1
1.1.2 國內(nèi)的研究現(xiàn)狀與發(fā)展 1
1.1.3 數(shù)據(jù)結(jié)構(gòu)在計算機專業(yè)中的地位 2
1.2 什么是數(shù)據(jù)結(jié)構(gòu) 3
1.3 相關(guān)概念 6
1.4 數(shù)據(jù)類型與抽象數(shù)據(jù)類型 10
1.5 算法和算法分析 13
1.5.1 算法簡述 13
1.5.2 算法的特征 13
1.5.3 算法對應的程序設(shè)計模式 14
1.5.4 時間復雜度 19
1.5.5 空間復雜度 22
1.6 數(shù)據(jù)結(jié)構(gòu)的選擇與評價 24
習題 24
第2章 線性表 26
2.1 線性表的概念、存儲結(jié)構(gòu)與應用 26
2.1.1 線性表的定義 26
2.1.2 線性表的抽象數(shù)據(jù)類型定義 26
2.1.3 線性表的存儲結(jié)構(gòu) 28
2.1.4 線性表的應用 29
2.2 線性表的順序存儲結(jié)構(gòu) 31
2.2.1 線性表的順序存儲結(jié)構(gòu)定義 31
2.2.2 線性表的順序存儲結(jié)構(gòu)的基本操作 32
2.3 線性表的鏈式存儲結(jié)構(gòu) 37
2.3.1 線性表的鏈式存儲結(jié)構(gòu)定義 37
2.3.2 線性表的鏈式存儲結(jié)構(gòu)的基本操作 38
2.3.3 循環(huán)鏈表、雙向鏈表的存儲結(jié)構(gòu)與操作 44
2.4 順序表與鏈表的比較 49
2.5 線性表的應用舉例 50
2.5.1 一元多項式的線性表的順序存儲結(jié)構(gòu)及特點 50
2.5.2 一元多項式的線性表的鏈式存儲結(jié)構(gòu) 50
習題 56
第3章 棧和隊列 60
3.1 棧 60
3.1.1 棧的定義 60
3.1.2 棧的抽象數(shù)據(jù)類型定義 60
3.1.3 棧的表示和實現(xiàn) 61
3.2 棧的應用 66
3.2.1 數(shù)制轉(zhuǎn)換 66
3.2.2 括號匹配 67
3.2.3 運用棧實現(xiàn)行編輯程序 69
3.2.4 迷宮求解 71
3.2.5 表達式求值 77
3.3 棧與遞歸 83
3.3.1 遞歸的定義 83
3.3.2 遞歸過程的內(nèi)部實現(xiàn) 85
3.3.3 遞歸消除 86
3.3.4 運用棧閱讀遞歸程序 89
3.4 隊列 100
3.4.1 隊列的定義 100
3.4.2 隊列的抽象數(shù)據(jù)類型定義 100
3.4.3 隊列的表示和實現(xiàn) 101
3.5 隊列的應用——離散事件模擬的例子 107
習題 113
第4章 串、數(shù)組和廣義表 116
4.1 串的基本概念、存儲結(jié)構(gòu)與基本操作 116
4.1.1 串的基本概念 116
4.1.2 串的存儲結(jié)構(gòu)及算法 120
4.1.3 串的模式匹配算法 128
4.1.4 文本編輯的應用 140
4.2 數(shù)組及其應用 144
4.2.1 數(shù)組 144
4.2.2 數(shù)組的應用——矩陣的壓縮存儲 149
4.3 廣義表的基本概念、抽象數(shù)據(jù)類型定義與基本操作 165
4.3.1 廣義表的基本概念 165
4.3.2 廣義表的抽象數(shù)據(jù)類型定義 166
4.3.3 廣義表的表示和實現(xiàn) 167
習題 171
第5章 樹和二叉樹 175
5.1 樹 175
5.1.1 樹的定義 175
5.1.2 樹的抽象數(shù)據(jù)類型定義 176
5.2 二叉樹 178
5.2.1 二叉樹的定義 178
5.2.2 二叉樹的抽象數(shù)據(jù)類型定義 178
5.2.3 二叉樹的性質(zhì) 180
5.2.4 二叉樹的存儲結(jié)構(gòu) 183
5.3 遍歷二叉樹 186
5.3.1 問題的提出 186
5.3.2 二叉樹遍歷算法 187
5.3.3 二叉樹遍歷遞歸算法的應用 193
5.4 線索二叉樹 198
5.4.1 問題的提出 198
5.4.2 線索二叉樹的存儲結(jié)構(gòu) 199
5.4.3 二叉樹的中序線索化 201
5.5 樹和森林 212
5.5.1 樹、森林與二叉樹的相互轉(zhuǎn)換 212
5.5.2 樹和森林的存儲 214
5.5.3 樹和森林的遍歷 217
5.6 哈夫曼樹及其應用 219
5.6.1 哈夫曼樹 219
5.6.2 哈夫曼編碼 222
5.6.3 哈夫曼樹的應用 228
習題 229
第6章 圖 235
6.1 圖的定義、抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu) 235
6.1.1 圖的定義和基本術(shù)語 235
6.1.2 圖的抽象數(shù)據(jù)類型定義 240
6.1.3 圖的存儲結(jié)構(gòu) 241
6.2 圖的遍歷 246
6.2.1 深度優(yōu)先搜索遞歸算法及其閱讀 247
6.2.2 廣度優(yōu)先搜索算法及其閱讀 259
6.3 生成樹與*小生成樹 265
6.3.1 Prim算法 266
6.3.2 Kruskal算法 268
6.3.3 破圈法 270
6.3.4 生成樹與圖的遍歷 272
6.4 兩點之間的*短路徑 273
6.4.1 從某個源點到其余各頂點的*短路徑 273
6.4.2 每一對頂點之間的*短路徑 278
6.5 有向無環(huán)圖及其應用 279
6.5.1 拓撲排序 280
6.5.2 關(guān)鍵路徑 288
習題 295
第7章 查找 301
7.1 查找的基本概念 301
7.2 靜態(tài)查找表 302
7.2.1 無序順序表查找——順序查找 302
7.2.2 有序順序表查找——折半查找 304
7.2.3 索引順序表查找——分塊查找 307
7.3 動態(tài)查找表 308
7.3.1 二叉排序樹 309
7.3.2 平衡二叉樹 314
7.4 哈希表 320
7.4.1 什么是哈希表 320
7.4.2 哈希函數(shù)的構(gòu)造方法 321
7.4.3 處理沖突的方法 323
7.4.4 哈希表的查找 330
7.4.5 哈希表實現(xiàn)的比較 331
習題 332
第8章 內(nèi)部排序 336
8.1 排序的基本概念 336
8.2 插入排序 337
8.2.1 直接插入排序 337
8.2.2 折半插入排序 339
8.2.3 表插入排序 340
8.2.4 希爾排序 342
8.3 交換排序 344
8.3.1 起泡排序 344
8.3.2 快速排序 345
8.4 選擇排序 348
8.4.1 簡單選擇排序 348
8.4.2 堆排序 349
8.5 歸并排序 352
8.6 分配排序 355
8.6.1 多關(guān)鍵字排序 355
8.6.2 基數(shù)排序 356
8.7 各種內(nèi)部排序方法的比較 359
習題 360
參考文獻 364