目錄
前言
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用 1
1.2 本書討論的主要內(nèi)容 1
1.3 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念 2
1.3.1 數(shù)據(jù)結(jié)構(gòu) 2
1.3.2 抽象數(shù)據(jù)類型相關(guān)概念 3
1.4 算法及算法分析 4
1.4.1 算法及其描述方法 4
1.4.2 算法分析 7
習題1 9
第2章 線性表 13
2.1 線性表的邏輯結(jié)構(gòu) 13
2.1.1 線性表的定義 13
2.1.2 線性表的抽象數(shù)據(jù)類型定義 13
2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn) 15
2.2.1 線性表的順序存儲結(jié)構(gòu)——順序表 15
2.2.2 順序表的實現(xiàn) 16
2.3 線性表的鏈式存儲結(jié)構(gòu)及實現(xiàn) 20
2.3.1 單鏈表 20
2.3.2 循環(huán)鏈表 28
2.3.3 雙鏈表 29
2.4 順序表和鏈表的比較 30
2.4.1 時間性能比較 31
2.4.2 空間性能比較 31
2.5 線性表的其他存儲方法 31
2.5.1 靜態(tài)鏈表 31
2.5.2 間接尋址 33
2.6 應用舉例 34
2.6.1 順序表的應用舉例——大整數(shù)求和 34
2.6.2 單鏈表的應用舉例——一元多項式求和 35
習題2 37
第3章 棧和隊列 42
3.1 棧 42
3.1.1 棧的邏輯結(jié)構(gòu) 42
3.1.2 棧的順序存儲結(jié)構(gòu)及實現(xiàn) 44
3.1.3 棧的鏈式存儲結(jié)構(gòu)及實現(xiàn) 48
3.1.4 順序棧與鏈棧的比較 50
3.1.5 棧的應用舉例 51
3.2 隊列 52
3.2.1 隊列的邏輯結(jié)構(gòu) 52
3.2.2 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 53
3.2.3 隊列的鏈式存儲結(jié)構(gòu)及實現(xiàn) 57
3.2.4 循環(huán)隊列與鏈隊列的比較 58
3.3 應用舉例 59
習題3 62
第4章 字符串和多維數(shù)組 65
4.1 字符串.65
4.1.1 字符串的定義 65
4.1.2 字符串的存儲結(jié)構(gòu) 66
4.1.3 字符串的模式匹配 68
4.2 數(shù)組 71
4.2.1 數(shù)組的定義 72
4.2.2 數(shù)組的存儲結(jié)構(gòu)與尋址 72
4.3 矩陣的壓縮存儲 73
4.3.1 特殊矩陣的壓縮存儲 73
4.3.2 稀疏矩陣的壓縮存儲 75
4.4 廣義表.77
4.5 應用舉例 80
4.5.1 字符串的應用舉例——凱撒密碼 80
4.5.2 數(shù)組的應用舉例——N階幻方 80
習題4 81
第5章 樹與二叉樹 85
5.1 樹的定義和基本術(shù)語 85
5.2 二叉樹.89
5.2.1 二叉樹的定義 89
5.2.2 二叉樹的性質(zhì) 91
5.2.3 二叉樹的存儲結(jié)構(gòu) 94
5.3 遍歷二叉樹和線索二叉樹 96
5.3.1 遍歷二叉樹 96
5.3.2 線索二叉樹 98
5.4 樹和森林 101
5.4.1 樹的存儲結(jié)構(gòu) 101
5.4.2 森林與二叉樹的轉(zhuǎn)換 104
5.4.3 樹與森林的遍歷 106
5.5 哈夫曼樹及編碼 108
5.5.1 最優(yōu)二叉樹（哈夫曼樹） 108
5.5.2 哈夫曼編碼 111
5.6 樹的計數(shù) 115
習題5 119
第6章 圖 123
6.1 圖的定義和術(shù)語 123
6.2 圖的存儲結(jié)構(gòu) 128
6.2.1 數(shù)組表示法 129
6.2.2 鄰接表 132
6.2.3 十字鏈表 133
6.2.4 鄰接多重表 135
6.3 圖的遍歷 136
6.3.1 深度優(yōu)先搜索 136
6.3.2 廣度優(yōu)先搜索 138
6.4 圖的連通性問題 139
6.4.1 無向圖的連通分量和生成樹 139
6.4.2 有向圖的強連通分量 141
6.4.3 最小生成樹 141
6.4.4 關(guān)節(jié)點和重連通分量 145
6.5 有向無環(huán)圖 148
6.5.1 拓撲排序 149
6.5.2 關(guān)鍵路徑 152
6.6 最短路徑 156
6.6.1 從某個源點到其余各頂點的最短路徑 157
6.6.2 每一對頂點之間的最短路徑 159
習題6 161
第7章 查找 164
7.1 靜態(tài)查找表 166
7.1.1 順序表的查找 166
7.1.2 有序表的查找 169
7.1.3 靜態(tài)樹表的查找 172
7.1.4 索引順序表的查找 176
7.2 動態(tài)查找表 177
7.2.1 二叉排序樹和平衡二叉樹 178
7.2.2 B樹和B+樹 190
7.2.3 鍵樹 196
7.3 哈希表 200
7.3.1 什么是哈希表 200
7.3.2 哈希函數(shù)的構(gòu)造方法 202
7.3.3 處理沖突的方法 206
7.3.4 哈希表的查找及其分析 208
習題7 212
第8章 內(nèi)部排序 217
8.1 內(nèi)部排序概述.217
8.2 插入排序 219
8.2.1 直接插入排序 219
8.2.2 其他插入排序 220
8.2.3 希爾排序 225
8.3 快速排序 228
8.4 選擇排序 232
8.4.1 簡單選擇排序 232
8.4.2 樹形選擇排序 234
8.4.3 堆排序 235
8.5 歸并排序 238
8.6 基數(shù)排序 240
8.6.1 多關(guān)鍵字排序 240
8.6.2 鏈式基數(shù)排序 241
8.7 各種內(nèi)部排序方法的比較討論 243
習題8 247
第9章 外部排序 252
9.1 外存信息的存取 252
9.2 外部排序的方法 255
9.3 多路平衡歸并的實現(xiàn) 256
9.4 置換-選擇排序 259
9.5 最佳歸并樹 264
習題9 266
參考文獻 269