數(shù)據(jù)結(jié)構(gòu)及其空間數(shù)據(jù)應(yīng)用
本書為地理信息科學(xué)相關(guān)專業(yè)的數(shù)據(jù)結(jié)構(gòu)教學(xué)和學(xué)習(xí)編寫。全書共分8章，第1章介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念、內(nèi)涵和算法分析方法；第2～4章討論了線性表、棧和隊列及其應(yīng)用，分析了多維數(shù)組、特殊矩陣和稀疏矩陣的壓縮存儲方法等，還對廣義表做了扼要介紹；第5、6章討論了二叉樹、優(yōu)先隊列、哈夫曼樹及其應(yīng)用、四叉樹空間數(shù)據(jù)結(jié)構(gòu)與算法，介紹了圖及其存儲結(jié)構(gòu)、最小生成樹、最短路徑分析及相關(guān)算法；第7、8章討論了各種查找方法、二叉查找樹、B樹、R樹空間索引，探討了各種排序方法并給出多種改進(jìn)的新算法。書中給出的應(yīng)用實例多數(shù)與地理信息科學(xué)有關(guān)。本書結(jié)構(gòu)合理、內(nèi)容翔實、視角獨特、算法豐富，便于教學(xué)和自學(xué)。
更多科學(xué)出版社服務(wù)，請掃碼獲取。
目錄
前言
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念 1
1.2 基本術(shù)語 5
1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵 7
1.3.1 數(shù)據(jù)的邏輯結(jié)構(gòu) 7
1.3.2 數(shù)據(jù)的存儲結(jié)構(gòu) 8
1.3.3 數(shù)據(jù)的運算與操作 9
1.4 算法與算法分析 10
1.4.1 算法的基本概念 10
1.4.2 算法的重要特性 10
1.4.3 算法設(shè)計的基本方法 11
1.4.4 算法評價要素 12
1.4.5 算法的時間復(fù)雜度 13
1.4.6 算法的空間復(fù)雜度 17
習(xí)題 18
第2章 線性表 19
2.1 線性表的基本概念 19
2.1.1 線性表的定義和特點 19
2.1.2 線性表的基本操作 20
2.2 順序存儲的線性表 21
2.2.1 順序存儲方法 21
2.2.2 順序表的結(jié)構(gòu)定義及初始化 22
2.2.3 順序表的基本操作 23
2.2.4 順序表的特點和適用性 27
2.3 鏈?zhǔn)酱鎯Φ木�性表 27
2.3.1 鏈?zhǔn)酱鎯Ψ椒ā?7
2.3.2 單向鏈表及其結(jié)構(gòu)定義 27
2.3.3 不帶頭結(jié)點單向鏈表 28
2.3.4 帶頭結(jié)點單向鏈表 32
2.3.5 循環(huán)鏈表 41
2.3.6 雙向鏈表 44
2.3.7 靜態(tài)鏈表 48
2.4 順序表與鏈表對比分析 50
2.5 鏈表的應(yīng)用 51
2.5.1 一元多項式加法運算 51
2.5.2 Shapefile圖形文件的讀取 54
習(xí)題 59
第3章 棧和隊列 61
3.1 �！�61
3.1.1 棧的概念 61
3.1.2 棧的基本操作 62
3.1.3 順序�！�62
3.1.4 鏈棧 65
3.2 棧的應(yīng)用一表達(dá)式計算 67
3.2.1 表達(dá)式轉(zhuǎn)換為后綴表達(dá)式原理 67
3.2.2 表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法 68
3.2.3 后綴表達(dá)式的計算 70
3.2.4 表達(dá)式計算測試 71
3.3 隊列 71
3.3.1 隊列的概念 71
3.3.2 隊列的基本操作 72
3.3.3 順序隊列 73
3.3.4 循環(huán)隊列 74
3.3.5 鏈?zhǔn)疥犃小?6
3.4 隊列應(yīng)用 78
3.4.1 數(shù)字圖像四元組壓縮轉(zhuǎn)換原理 78
3.4.2數(shù)字圖像四元組壓縮轉(zhuǎn)換算法 79
習(xí)題 82
第4章 數(shù)組、矩陣和廣義表 84
4.1 數(shù)組 84
4.1.1 一維數(shù)組 84
4.1.2 多維數(shù)組 85
4.1.3 動態(tài)多維數(shù)組的創(chuàng)建 88
4.1.4 多維數(shù)組的一維數(shù)組存儲 90
4.2 特殊矩陣的壓縮存儲 91
4.2.1 對稱矩陣的壓縮存儲 92
4.2.2 下三角矩陣的壓縮存儲 92
4.2.3 上三角矩陣的壓縮存儲 93
4.2.4 對角矩陣的壓縮存儲 93
4.2.5 特殊矩陣類型定義與基本運算 94
4.3 稀疏矩陣 96
4.3.1 三元組存儲結(jié)構(gòu) 96
4.3.2 十字鏈表存儲結(jié)構(gòu) 103
4.3.3 稀疏矩陣存儲性能分析 106
4.4 廣義表 107
4.4.1 廣義表的概念 107
4.4.2 廣義表的性質(zhì) 107
4.4.3 廣義表的鏈?zhǔn)酱鎯Α?08
習(xí)題 109
第5章 樹 111
5.1 樹的基本概念 111
5.1.1 樹的定義 111
5.1.2 樹的基本術(shù)語 111
5.2 二叉樹 112
5.2.1 二叉樹的概念 112
5.2.2 二叉樹的性質(zhì) 113
5.2.3 二叉樹的基本操作 114
5.2.4 二叉樹的順序存儲實現(xiàn) 116
5.2.5 二叉樹的鏈?zhǔn)酱鎯崿F(xiàn) 117
5.2.6 二叉樹的遍歷及算法118
5.2.7 鏈?zhǔn)蕉鏄涞膭?chuàng)建 122
5.2.8 鏈?zhǔn)蕉鏄涞幕静僮魉惴ā?23
5.3 線索二叉樹 127
5.3.1 線索二叉樹的概念 127
5.3.2 線索二叉樹的定義 127
5.3.3 二叉樹的中序線索化算法 128
5.3.4 中序線索二叉樹的運算 129
5.4 哈夫曼樹及其應(yīng)用 132
5.4.1 哈夫曼樹的定義 132
5.4.2 哈夫曼樹的構(gòu)建方法 132
5.4.3 哈夫曼樹的存儲 133
5.4.4 哈夫曼編碼 134
5.4.5 哈夫曼樹構(gòu)建及編碼和譯碼算法 135
5.4.6 哈夫曼樹構(gòu)建及編碼和譯碼示例 139
5.5 優(yōu)先隊列 140
5.5.1 優(yōu)先隊列的概念 140
5.5.2 二叉堆實現(xiàn)的優(yōu)先隊列 141
5.5.3 二叉堆的基本算法 143
5.5.4 四叉堆實現(xiàn)的優(yōu)先隊列 144
5.5.5 四叉堆的基本算法 146
5.6 四叉樹及其在空間數(shù)據(jù)存儲中的應(yīng)用 147
5.6.1 四叉樹的概念及性質(zhì). 147
5.6.2 常規(guī)四叉樹編碼 148
5.6.3 常規(guī)四叉樹的構(gòu)建算法 150
5.6.4 線性四叉樹編碼 153
5.6.5 線性四叉樹的構(gòu)建算法 156
5.6.6 優(yōu)勢四叉樹結(jié)構(gòu) 164
習(xí)題 166
第6章 圖 169
6.1 圖的基本概念 169
6.1.1 圖的定義 169
6.1.2 圖的術(shù)語 169
6.1.3 圖的基本操作 172
6.2 圖的存儲結(jié)構(gòu) 173
6.2.1 圖的鄰接矩陣存儲 174
6.2.2 鄰接矩陣圖的基本操作算法 176
6.2.3 圖的鄰接表存儲 180
6.2.4 鄰接表圖的基本操作算法 183
6.3 圖的遍歷 189
6.3.1 深度優(yōu)先搜索概念 190
6.3.2 深度優(yōu)先搜索算法 191
6.3.3 廣度優(yōu)先搜索概念 193
6.3.4 廣度優(yōu)先搜索算法 194
6.3.5 圖的連通性 196
6.4 最小生成樹 197
6.4.1 最小生成樹的概念 197
6.4.2 Prim算法 198
6.4.3 Kruskal算法 202
6.5 最短路徑 205
6.5.1 單源最短路徑問題 206
6.5.2 單源最短路徑算法 207
6.5.3 多源最短路徑問題 210
6.5.4 多源最短路徑算法 212
習(xí)題 214
第7章 查找 217
7.1 查找的概念 217
7.1.1 查找概述 217
7.1.2 查找方法及性能評價 218
7.2 基本查找方法 218
7.2.1 順序查找 218
7.2.2 折半查找 220
7.2.3 靜態(tài)樹表查找 223
7.2.4 斐波那契查找225
7.2.5 插值查找 227
7.2.6 分塊順序查找 227
7.3 二叉排序樹查找 228
7.3.1 二叉排序樹的創(chuàng)建與結(jié)點插入 229
7.3.2 二叉排序樹的查找與結(jié)點刪除 230
7.3.3 二叉排序樹的查找性能分析 233
7.4 平衡二叉樹 234
7.4.1 平衡二叉樹的定義 234
7.4.2 平衡二叉樹的插入與創(chuàng)建 235
7.4.3 平衡二叉樹的結(jié)點刪除 239
7.5 B樹與R樹空間索引 243
7.5.1 B樹及其定義 244
7.5.2 B 樹查找 245
7.5.3 B樹的插入與刪除 246
7.5.4 B+樹 247
7.5.5 R樹空間索引 248
7.6 散列表及其查找 250
7.6.1 散列和散列表 250
7.6.2 散列函數(shù)構(gòu)造 251
7.6.3 沖突及其解決方法 253
7.6.4 散列表查找與散列法分析 258
習(xí)題 260
第8章 排序262
8.1 排序的概念 262
8.2 插入排序 263
8.2.1 直接插入排序 263
8.2.2 折半插入排序 264
8.2.3 鏈表的直接插入排序 265
8.2.4 算法性能分析 266
8.3 Shell排序 267
8.3.1 Shell排序原理 267
8.3.2 改進(jìn)的Shell排序方法 268
8.4 堆排序 270
8.4.1 二叉堆排序 270
8.4.2 四叉堆排序 272
8.5 歸并排序 274
8.5.1 常規(guī)歸并排序 274
8.5.2 顯式歸并排序 276
8.5.3 鏈?zhǔn)綒w并排序 278
8.6 快速排序 280
8.6.1 中間記錄關(guān)鍵字為基準(zhǔn)的快速排序 281
8.6.2 首記錄關(guān)鍵字為基準(zhǔn)的快速排序 282
8.6.3 鏈?zhǔn)剿姆直砜焖倥判蛩惴ā?84
8.7 基數(shù)排序 286
8.7.1 基數(shù)排序的原理 286
8.7.2 基數(shù)排序算法 288
8.8 各種排序方法的性能比較 289
8.8.1 排序算法的性能特征 289
8.8.2 排序算法性能測試實驗 291
8.9 流域離散單元上游集水面積計算中的排序應(yīng)用 293
8.9.1 集水面積的概念和計算方法 293
8.9.2 計算單元集水面積算法 294
習(xí)題 299
主要參考文獻(xiàn) 301
書單推薦
