目錄
前言
第1章　緒論　1
1.1　數(shù)據(jù)結(jié)構(gòu)的基本概念　1
1.2　基本術(shù)語(yǔ)　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ù)的存儲(chǔ)結(jié)構(gòu)　8
1.3.3　數(shù)據(jù)的運(yùn)算與操作　9
1.4　算法與算法分析　10
1.4.1　算法的基本概念　10
1.4.2　算法的重要特性　10
1.4.3　算法設(shè)計(jì)的基本方法　11
1.4.4　算法評(píng)價(jià)要素　12
1.4.5　算法的時(shí)間復(fù)雜度　13
1.4.6　算法的空間復(fù)雜度　17
習(xí)題　18
第2章　線性表　19
2.1　線性表的基本概念　19
2.1.1　線性表的定義和特點(diǎn)　19
2.1.2　線性表的基本操作　20
2.2　順序存儲(chǔ)的線性表　21
2.2.1　順序存儲(chǔ)方法　21
2.2.2　順序表的結(jié)構(gòu)定義及初始化　22
2.2.3　順序表的基本操作　23
2.2.4　順序表的特點(diǎn)和適用性　27
2.3　鏈?zhǔn)酱鎯?chǔ)的線性表　27
2.3.1　鏈?zhǔn)酱鎯?chǔ)方法　27
2.3.2　單向鏈表及其結(jié)構(gòu)定義　27
2.3.3　不帶頭結(jié)點(diǎn)單向鏈表　28
2.3.4　帶頭結(jié)點(diǎn)單向鏈表　32
2.3.5　循環(huán)鏈表　41
2.3.6　雙向鏈表　44
2.3.7　靜態(tài)鏈表　48
2.4　順序表與鏈表對(duì)比分析　50
2.5　鏈表的應(yīng)用　51
2.5.1　一元多項(xiàng)式加法運(yùn)算　51
2.5.2　Shapefile圖形文件的讀取　54
習(xí)題　59
第3章　棧和隊(duì)列　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á)式計(jì)算　67
3.2.1　表達(dá)式轉(zhuǎn)換為后綴表達(dá)式原理　67
3.2.2　表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法　68
3.2.3　后綴表達(dá)式的計(jì)算　70
3.2.4　表達(dá)式計(jì)算測(cè)試　71
3.3　隊(duì)列　71
3.3.1　隊(duì)列的概念　71
3.3.2　隊(duì)列的基本操作　72
3.3.3　順序隊(duì)列　73
3.3.4　循環(huán)隊(duì)列　74
3.3.5　鏈?zhǔn)疥?duì)列　76
3.4　隊(duì)列應(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　動(dòng)態(tài)多維數(shù)組的創(chuàng)建　88
4.1.4　多維數(shù)組的一維數(shù)組存儲(chǔ)　90
4.2　特殊矩陣的壓縮存儲(chǔ)　91
4.2.1　對(duì)稱矩陣的壓縮存儲(chǔ)　92
4.2.2　下三角矩陣的壓縮存儲(chǔ)　92
4.2.3　上三角矩陣的壓縮存儲(chǔ)　93
4.2.4　對(duì)角矩陣的壓縮存儲(chǔ)　93
4.2.5　特殊矩陣類型定義與基本運(yùn)算　94
4.3　稀疏矩陣　96
4.3.1　三元組存儲(chǔ)結(jié)構(gòu)　96
4.3.2　十字鏈表存儲(chǔ)結(jié)構(gòu)　103
4.3.3　稀疏矩陣存儲(chǔ)性能分析　106
4.4　廣義表　107
4.4.1　廣義表的概念　107
4.4.2　廣義表的性質(zhì)　107
4.4.3　廣義表的鏈?zhǔn)酱鎯?chǔ)　108
習(xí)題　109
第5章　樹　111
5.1　樹的基本概念　111
5.1.1　樹的定義　111
5.1.2　樹的基本術(shù)語(yǔ)　111
5.2　二叉樹　112
5.2.1　二叉樹的概念　112
5.2.2　二叉樹的性質(zhì)　113
5.2.3　二叉樹的基本操作　114
5.2.4　二叉樹的順序存儲(chǔ)實(shí)現(xiàn)　116
5.2.5　二叉樹的鏈?zhǔn)酱鎯?chǔ)實(shí)現(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　中序線索二叉樹的運(yùn)算　129
5.4　哈夫曼樹及其應(yīng)用　132
5.4.1　哈夫曼樹的定義　132
5.4.2　哈夫曼樹的構(gòu)建方法　132
5.4.3　哈夫曼樹的存儲(chǔ)　133
5.4.4　哈夫曼編碼　134
5.4.5　哈夫曼樹構(gòu)建及編碼和譯碼算法　135
5.4.6　哈夫曼樹構(gòu)建及編碼和譯碼示例　139
5.5　優(yōu)先隊(duì)列　140
5.5.1　優(yōu)先隊(duì)列的概念　140
5.5.2　二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列　141
5.5.3　二叉堆的基本算法　143
5.5.4　四叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列　144
5.5.5　四叉堆的基本算法　146
5.6　四叉樹及其在空間數(shù)據(jù)存儲(chǔ)中的應(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)勢(shì)四叉樹結(jié)構(gòu)　164
習(xí)題　166
第6章　圖　169
6.1　圖的基本概念　169
6.1.1　圖的定義　169
6.1.2　圖的術(shù)語(yǔ)　169
6.1.3　圖的基本操作　172
6.2　圖的存儲(chǔ)結(jié)構(gòu)　173
6.2.1　圖的鄰接矩陣存儲(chǔ)　174
6.2.2　鄰接矩陣圖的基本操作算法　176
6.2.3　圖的鄰接表存儲(chǔ)　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　查找方法及性能評(píng)價(jià)　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é)點(diǎn)插入　229
7.3.2　二叉排序樹的查找與結(jié)點(diǎn)刪除　230
7.3.3　二叉排序樹的查找性能分析　233
7.4　平衡二叉樹　234
7.4.1　平衡二叉樹的定義　234
7.4.2　平衡二叉樹的插入與創(chuàng)建　235
7.4.3　平衡二叉樹的結(jié)點(diǎn)刪除　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　排序算法性能測(cè)試實(shí)驗(yàn)　291
8.9　流域離散單元上游集水面積計(jì)算中的排序應(yīng)用　293
8.9.1　集水面積的概念和計(jì)算方法　293
8.9.2　計(jì)算單元集水面積算法　294
習(xí)題　299
主要參考文獻(xiàn)　301