數(shù)據結構

第1章 概論 1
1.1 學習數(shù)據結構的重要性 1
1.2 什么是數(shù)據結構 2
1.3 數(shù)據的邏輯結構 3
1.3.1 基本概念 3
1.3.2 數(shù)據的邏輯結構 4
1.3.3 數(shù)據結構的分類 5
1.4 數(shù)據的存儲結構 6
1.5 數(shù)據運算和算法 9
1.5.1 數(shù)據運算 9
1.5.2 算法 10
1.5.3 算法評價 11
習題 12
第2章 線性表 13
2.1 線性表的定義和運算 13
2.1.1 線性表的定義 13
2.1.2 線性表的基本運算 14
2.2 線性表的順序存儲結構及其運算 15
2.2.1 線性表的順序存儲結構 15
2.2.2 順序表的運算 16
2.3 線性表的鏈接存儲結構及其運算 19
2.3.1 線性鏈表 19
2.3.2 單鏈表及其運算 21
2.3.3 雙向鏈表 25
2.3.4 循環(huán)鏈表 28
2.4 線性表的應用舉例 30
2.4.1 在"線切割編程控制軟件"中的鏈表 30
2.4.2 在"多傳感器偵察數(shù)據的融合處理"中的雙向鏈表 34
習題 35
第3章 堆棧與隊列 36
3.1 棧 37
3.1.1 棧的定義 37
3.1.2 棧的基本運算 38
3.2 棧的存儲結構與基本運算 38
3.2.1 棧的順序存儲結構 38
3.2.2 棧的運算 39
3.2.3 雙棧結構 41
3.2.4 棧的鏈接存儲結構及其運算 43
3.3 棧的應用舉例 45
3.3.1 棧的應用之一：表達式的計算 45
3.3.2 棧的應用之二：數(shù)制轉換 49
3.3.3 棧的應用之三：括號匹配的檢驗 50
3.3.4 棧的應用之四：微軟Word軟件中的"取消"與
"重復"命令的設計 52
3.4 遞歸 53
3.4.1 遞歸算法 53
3.4.2 遞歸的應用 54
3.4.3 遞歸算法分析 56
3.5 隊列 56
3.6 隊列的存儲結構 57
3.6.1 隊列的順序存儲結構 58
3.6.2 順序隊列的基本運算 59
3.6.3 循環(huán)隊列 61
3.6.4 鏈接存儲結構 63
3.7 隊列的實際應用 65
3.7.1 在"打印機軟件設計"中的隊列 65
3.7.2 在"考慮沖突的模具生產計劃調度系統(tǒng)"中的隊列 65
3.7.3 在"智能排隊系統(tǒng)"中的隊列 69
習題 71
第4章 串 73
4.1 串的定義 73
4.2 串的存儲結構 74
4.2.1 順序存儲 75
4.2.2 鏈接存儲 76
4.2.3 索引存儲 77
4.3 串的基本運算 78
4.3.1 串的基本運算 78
4.3.2 串基本運算的C語言算法 78
4.4 串的應用舉例 84
4.4.1 在"軟件漢化"中的字符串 84
4.4.2 在現(xiàn)代軟件開發(fā)工具中的串操作 84
習題 86
第5章 數(shù)組和廣義表 87
5.1 數(shù)組 88
5.1.1 數(shù)組的定義 88
5.1.2 數(shù)組的順序存儲結構 88
5.2 數(shù)組應用舉例 90
5.2.1 在"Visual Basic"中的數(shù)組 90
5.2.2 Java中的數(shù)組 91
5.2.3 在"陣列處理機（數(shù)組處理機）"中的數(shù)組 92
5.2.4 在"圖形化編程語言Lab VIEW"中的數(shù)組運算 92
5.3 矩陣的壓縮存儲 93
5.3.1 特殊矩陣的壓縮存儲 93
5.3.2 稀疏矩陣及存儲 95
5.3.3 三元組表 96
5.3.4 稀疏矩陣鏈接存儲：十字鏈表 99
5.4 廣義表 100
5.4.1 廣義表的定義 100
5.4.2 廣義表的存儲結構 101
5.5 特殊矩陣和廣義表的應用舉例 103
5.5.1 在"群落與生態(tài)系統(tǒng)"研究中的三角矩陣 103
5.5.2 在"基于FMS生產調度與控制的零件動態(tài)工藝模型"
中的稀疏矩陣 105
5.5.3 在"中文字字同現(xiàn)概率統(tǒng)計及應用"中的稀疏矩陣 107
習題 108
第6章 樹和二叉樹 110
6.1 樹的基本概念 110
6.1.1 樹的定義 110
6.1.2 樹的表示方法 112
6.1.3 樹的存儲結構 113
6.2 二叉樹 114
6.2.1 二叉樹的定義 114
6.2.2 二叉樹的基本性質 115
6.3 二叉樹的鏈接存儲 116
6.3.1 二叉鏈表 116
6.3.2 二叉鏈表的生成 117
6.4 二叉樹的遍歷 119
6.4.1 二叉樹遍歷算法 119
6.4.2 層次遍歷算法 122
6.4.3 遍歷算法 123
6.5 線索二叉樹 124
6.5.1 建立線索二叉樹 124
6.5.2 訪問線索二叉樹 127
6.6 樹、森林與二叉樹的關系 128
6.6.1 樹與二叉樹之間的轉換 128
6.6.2 森林與二叉樹 130
6.6.3 一般樹和森林的運算 131
6.7 哈夫曼樹 132
6.7.1 哈夫曼樹的基本概念 132
6.7.2 判定樹 134
6.7.3 哈夫曼編碼 135
6.8 樹和二叉樹的應用舉例 138
6.8.1 在"電力地理信息系統(tǒng)" 中的樹和二叉樹的應用 138
6.8.2 在"工程計算書自動生成技術" 中的樹的應用 139
6.8.3 在"PLC指令代碼的文法分析和翻譯"中的二叉樹結構 141
6.8.4 在"基于用戶的CAPP零件編碼系統(tǒng)的研究"中的二叉樹 142
習題 145
第7章 圖 147
7.1 圖的基本概念 147
7. 2 圖的存儲結構 151
7.2.1 鄰接矩陣表示法 151
7.2.2 鄰接表表示法 154
7.3 圖的運算 155
7.4 圖的遍歷 157
7.4.1 深度優(yōu)先搜索遍歷 157
7.4.2 廣度優(yōu)先搜索遍歷 160
7.4.3 無向圖的遍歷 162
7.5 圖的應用 163
7.5.1 最小生成樹 163
7.5.2 最短路徑 168
7.5.3 拓撲（Topology）排序 172
7.6 圖的應用實例 174
7.6.1 圖在地理信息系統(tǒng)（GIS）中的作用 174
7.6.2 在"變電站故障定位及恢復處理智能系統(tǒng)" 中的圖論應用 178
7.6.3 在Internet路由器中的圖論應用 180
習題 182
第8章 查找 184
8.1 基本概念 184
8.2 線性表中的查找 186
8.2.1 順序查找 186
8.2.2 二分法查找 187
8.2.3 分塊查找 189
8.3 散列表及其查找 192
8.3.1 散列表的概念 192
8.3.2 散列函數(shù)的構造方法 194
8.3.3 沖突處理 196
8.4 查找的應用實例 200
8.4.1 "口令"或"密碼"的查找 200
8.4.2 計算機病毒的檢測技術 201
8.4.3 在"電信通話記錄"中的查找 204
習題 205
第9章 排序 206
9.1 排序的基本概念 206
9.2 插入排序 209
9.2.1 插入排序概述 209
9.2.2 直接插入排序 210
9.2.3 二分插入排序 212
9.2.4 希爾排序 214
9.3 選擇排序 216
9.3.1 直接選擇排序 216
9.3.2 樹形選擇排序 218
9.3.3 堆排序 220
9.4 交換排序 226
9.4.1 冒泡排序 226
9.4.2 快速排序 229
9.5 歸并排序 232
9.5.1 二路歸并 232
9.5.2 一趟歸并算法 235
9.5.3 歸并排序 237
9.5.4 算法分析 237
9.6 基數(shù)排序 238
9.6.1 多關鍵字的排序 238
9.6.2 基數(shù)排序 239
9.7 幾種排序方法的比較 242
9.8 排序運算的實際應用事例 244
9.8.1 在"全國普通高校招生網上錄取系統(tǒng)"中的排序 244
9.8.2 在"風險評估"中的排序 246
習題 249
第10章 文件 251
10.1 文件的基本概念 251
10.2 順序文件 253
10.3 索引文件 254
10.3.1 索引順序與B+ 樹文件 256
10.3.2 VSAM文件 259
10.4 散列文件 260
10.5 多關鍵字文件 262
10.5.1 多關鍵字文件的概念 262
10.5.2 多重表文件 263
10.5.3 倒排文件 263
10.6 文件應用的實例 264
10.6.1 在Visual Basic中的文件 264
10.6.2 在"太湖流域水情自動監(jiān)測系統(tǒng)"中的順序文件 266
10.6.3 在"超市商品庫存"中的多關鍵字文件 268
習題 270
參考文獻 272