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

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