數(shù)據(jù)結(jié)構(gòu)：從概念到C實(shí)現(xiàn)（第2版）

第1章緒論1
1.1問(wèn)題求解與程序設(shè)計(jì)2
1.1.1程序設(shè)計(jì)的一般過(guò)程2
1.1.2數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用4
1.1.3算法在程序設(shè)計(jì)中的作用5
1.1.4本書討論的主要內(nèi)容6
1.2數(shù)據(jù)結(jié)構(gòu)的基本概念8
1.2.1數(shù)據(jù)結(jié)構(gòu)8
1.2.2抽象數(shù)據(jù)類型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法13
1.4算法分析15
1.4.1算法的時(shí)間復(fù)雜度15
1.4.2算法的空間復(fù)雜度17
1.4.3算法分析舉例17
1.5擴(kuò)展與提高20
1.5.1從數(shù)據(jù)到大數(shù)據(jù)20
1.5.2算法分析的其他漸近符號(hào)22
1.6考研加油站23第2章線性表25
2.1引言26
2.2線性表的邏輯結(jié)構(gòu)27
2.2.1線性表的定義27
2.2.2線性表的抽象數(shù)據(jù)類型定義27數(shù)據(jù)結(jié)構(gòu)——從概念到C實(shí)現(xiàn)（第2版）目錄2.3線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)29
2.3.1順序表的存儲(chǔ)結(jié)構(gòu)定義29
2.3.2順序表的實(shí)現(xiàn)30
2.3.3順序表的使用34
2.4線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)35
2.4.1單鏈表的存儲(chǔ)結(jié)構(gòu)定義35
2.4.2單鏈表的實(shí)現(xiàn)37
2.4.3單鏈表的使用45
2.4.4雙鏈表46
2.4.5循環(huán)鏈表47
2.5擴(kuò)展與提高48
2.5.1線性表的靜態(tài)鏈表存儲(chǔ)48
2.5.2順序表的動(dòng)態(tài)分配方式50
2.5.3順序表和鏈表的比較52
2.6應(yīng)用實(shí)例53
2.6.1約瑟夫環(huán)問(wèn)題53
2.6.2一元多項(xiàng)式求和55
2.7考研加油站60第3章棧、隊(duì)列和數(shù)組63
3.1引言64
3.2棧65
3.2.1棧的邏輯結(jié)構(gòu)65
3.2.2棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)66
3.2.3棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)69
3.2.4順序棧和鏈棧的比較72
3.3隊(duì)列72
3.3.1隊(duì)列的邏輯結(jié)構(gòu)72
3.3.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)73
3.3.3隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)77
3.3.4循環(huán)隊(duì)列和鏈隊(duì)列的比較81
3.4多維數(shù)組81
3.4.1數(shù)組的邏輯結(jié)構(gòu)81
3.4.2數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址82
3.5矩陣的壓縮存儲(chǔ)83
3.5.1特殊矩陣的壓縮存儲(chǔ)83
3.5.2稀疏矩陣的壓縮存儲(chǔ)86
3.6擴(kuò)展與提高88
3.6.1兩棧共享空間88
3.6.2雙端隊(duì)列89
3.6.3廣義表91
3.7應(yīng)用實(shí)例94
3.7.1括號(hào)匹配問(wèn)題94
3.7.2表達(dá)式求值95
3.7.3八皇后問(wèn)題99
3.8考研加油站102第4章樹(shù)和二叉樹(shù)105
4.1引言106
4.2樹(shù)的邏輯結(jié)構(gòu)107
4.2.1樹(shù)的定義和基本術(shù)語(yǔ)107
4.2.2樹(shù)的抽象數(shù)據(jù)類型定義109
4.2.3樹(shù)的遍歷操作109
4.3樹(shù)的存儲(chǔ)結(jié)構(gòu)110
4.3.1雙親表示法110
4.3.2孩子表示法111
4.3.3孩子兄弟表示法112
4.4二叉樹(shù)的邏輯結(jié)構(gòu)113
4.4.1二叉樹(shù)的定義113
4.4.2二叉樹(shù)的基本性質(zhì)115
4.4.3二叉樹(shù)的抽象數(shù)據(jù)類型定義116
4.4.4二叉樹(shù)的遍歷操作117
4.5二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)119
4.5.1順序存儲(chǔ)結(jié)構(gòu)119
4.5.2二叉鏈表120
4.5.3三叉鏈表124
4.6森林124
4.6.1森林的邏輯結(jié)構(gòu)124
4.6.2樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換125
4.7最優(yōu)二叉樹(shù)127
4.7.1哈夫曼算法127
4.7.2哈夫曼編碼129
4.8擴(kuò)展與提高131
4.8.1二叉樹(shù)遍歷的非遞歸算法131
4.8.2線索二叉樹(shù)134
4.9應(yīng)用實(shí)例138
4.9.1堆與優(yōu)先隊(duì)列138
4.9.2并查集140
4.10考研加油站141第5章圖145
5.1引言146
5.2圖的邏輯結(jié)構(gòu)147
5.2.1圖的定義和基本術(shù)語(yǔ)147
5.2.2圖的抽象數(shù)據(jù)類型定義149
5.2.3圖的遍歷操作150
5.3圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)153
5.3.1鄰接矩陣153
5.3.2鄰接表156
5.3.3鄰接矩陣和鄰接表的比較161
5.4最小生成樹(shù)161
5.4.1Prim算法162
5.4.2Kruskal算法165
5.5最短路徑169
5.5.1Dijkstra算法169
5.5.2Floyd算法172
5.6有向無(wú)環(huán)圖及其應(yīng)用174
5.6.1AOV網(wǎng)與拓?fù)渑判?74
5.6.2AOE網(wǎng)與關(guān)鍵路徑177
5.7擴(kuò)展與提高179
5.7.1圖的其他存儲(chǔ)方法179
5.7.2圖的連通性181
5.8應(yīng)用實(shí)例183
5.8.1七巧板涂色問(wèn)題183
5.8.2醫(yī)院選址問(wèn)題184
5.9考研加油站187第6章查找技術(shù)189
6.1概述190
6.1.1查找的基本概念190
6.1.2查找算法的性能191
6.2線性表的查找技術(shù)191
6.2.1順序查找191
6.2.2折半查找192
6.3樹(shù)表的查找技術(shù)195
6.3.1二叉查找樹(shù)195
6.3.2平衡二叉樹(shù)201
6.3.3B樹(shù)204
6.4散列表的查找技術(shù)208
6.4.1散列查找的基本思想208
6.4.2散列函數(shù)的設(shè)計(jì)210
6.4.3處理沖突的方法211
6.4.4散列查找的性能分析215
6.5字符串模式匹配216
6.5.1BF算法216
6.5.2KMP算法218
6.6擴(kuò)展與提高220
6.6.1順序查找的改進(jìn)——分塊查找220
6.6.2折半查找的改進(jìn)——插值查找220
6.6.3平衡二叉樹(shù)的改進(jìn)——紅黑樹(shù)221
6.6.4B樹(shù)的改進(jìn)——B 樹(shù)227
6.6.5各種查找方法的比較228
6.7考研加油站228第7章排序技術(shù)231
7.1概述232
7.1.1排序的基本概念232
7.1.2排序算法的性能233
7.2插入排序233
7.2.1直接插入排序233
7.2.2希爾排序235
7.3交換排序237
7.3.1起泡排序237
7.3.2快速排序239
7.4選擇排序242
7.4.1簡(jiǎn)單選擇排序242
7.4.2堆排序244
7.5歸并排序248
7.5.1二路歸并排序的遞歸實(shí)現(xiàn)248
7.5.2二路歸并排序的非遞歸實(shí)現(xiàn)249
7.6外部排序251
7.6.1外部排序的基本思想251
7.6.2置換—選擇排序252
7.6.3敗者樹(shù)254
7.7擴(kuò)展與提高255
7.7.1排序問(wèn)題的時(shí)間下界255
7.7.2基數(shù)排序256
7.7.3各種排序方法的比較258
7.8考研加油站260參考文獻(xiàn)263第1章緒論1
1.1問(wèn)題求解與程序設(shè)計(jì)2
1.1.1程序設(shè)計(jì)的一般過(guò)程2
1.1.2數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用4
1.1.3算法在程序設(shè)計(jì)中的作用5
1.1.4本書討論的主要內(nèi)容6
1.2數(shù)據(jù)結(jié)構(gòu)的基本概念8
1.2.1數(shù)據(jù)結(jié)構(gòu)8
1.2.2抽象數(shù)據(jù)類型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法13
1.4算法分析15
1.4.1算法的時(shí)間復(fù)雜度15
1.4.2算法的空間復(fù)雜度17
1.4.3算法分析舉例17
1.5擴(kuò)展與提高20
1.5.1從數(shù)據(jù)到大數(shù)據(jù)20
1.5.2算法分析的其他漸進(jìn)符號(hào)22
1.6考研加油站23第2章線性表24
2.1引言25
2.2線性表的邏輯結(jié)構(gòu)26
2.2.1線性表的定義26
2.2.2線性表的抽象數(shù)據(jù)類型定義26數(shù)據(jù)結(jié)構(gòu)——從概念到C實(shí)現(xiàn)（第2版）目錄2.3線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)28
2.3.1順序表的存儲(chǔ)結(jié)構(gòu)定義28
2.3.2順序表的實(shí)現(xiàn)29
2.3.3順序表的使用33
2.4線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)34
2.4.1單鏈表的存儲(chǔ)結(jié)構(gòu)定義34
2.4.2單鏈表的實(shí)現(xiàn)36
2.4.3單鏈表的使用44
2.4.4雙鏈表45
2.4.5循環(huán)鏈表46
2.5擴(kuò)展與提高47
2.5.1線性表的靜態(tài)鏈表存儲(chǔ)47
2.5.2順序表的動(dòng)態(tài)分配方式49
2.5.3順序表和鏈表的比較51
2.6應(yīng)用實(shí)例52
2.6.1約瑟夫環(huán)問(wèn)題52
2.6.2一元多項(xiàng)式求和54
2.7考研加油站59第3章棧、隊(duì)列和數(shù)組61
3.1引言62
3.2棧63
3.2.1棧的邏輯結(jié)構(gòu)63
3.2.2棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)64
3.2.3棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)67
3.2.4順序棧和鏈棧的比較70
3.3隊(duì)列70
3.3.1隊(duì)列的邏輯結(jié)構(gòu)70
3.3.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)71
3.3.3隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)75
3.3.4循環(huán)隊(duì)列和鏈隊(duì)列的比較79
3.4多維數(shù)組79
3.4.1數(shù)組的邏輯結(jié)構(gòu)79
3.4.2數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址80
3.5矩陣的壓縮存儲(chǔ)81
3.5.1特殊矩陣的壓縮存儲(chǔ)81
3.5.2稀疏矩陣的壓縮存儲(chǔ)84
3.6擴(kuò)展與提高86
3.6.1兩棧共享空間86
3.6.2雙端隊(duì)列87
3.6.3廣義表89
3.7應(yīng)用舉例92
3.7.1括號(hào)匹配問(wèn)題92
3.7.2表達(dá)式求值93
3.7.3八皇后問(wèn)題97
3.8考研加油站100第4章樹(shù)和二叉樹(shù)102
4.1引言103
4.2樹(shù)的邏輯結(jié)構(gòu)104
4.2.1樹(shù)的定義和基本術(shù)語(yǔ)104
4.2.2樹(shù)的抽象數(shù)據(jù)類型定義106
4.2.3樹(shù)的遍歷操作106
4.3樹(shù)的存儲(chǔ)結(jié)構(gòu)107
4.3.1雙親表示法107
4.3.2孩子表示法108
4.3.3孩子兄弟表示法109
4.4二叉樹(shù)的邏輯結(jié)構(gòu)110
4.4.1二叉樹(shù)的定義110
4.4.2二叉樹(shù)的基本性質(zhì)112
4.4.3二叉樹(shù)的抽象數(shù)據(jù)類型定義113
4.4.4二叉樹(shù)的遍歷操作114
4.5二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)116
4.5.1順序存儲(chǔ)結(jié)構(gòu)116
4.5.2二叉鏈表117
4.5.3三叉鏈表121
4.6森林121
4.6.1森林的邏輯結(jié)構(gòu)121
4.6.2樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換122
4.7最優(yōu)二叉樹(shù)124
4.7.1哈夫曼算法124
4.7.2哈夫曼編碼126
4.8擴(kuò)展與提高128
4.8.1二叉樹(shù)遍歷的非遞歸算法128
4.8.2線索二叉樹(shù)131
4.9應(yīng)用實(shí)例135
4.9.1堆與優(yōu)先隊(duì)列135
4.9.2并查集137
4.10考研加油站138第5章圖141
5.1引言142
5.2圖的邏輯結(jié)構(gòu)143
5.2.1圖的定義和基本術(shù)語(yǔ)143
5.2.2圖的抽象數(shù)據(jù)類型定義145
5.2.3圖的遍歷操作146
5.3圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)149
5.3.1鄰接矩陣149
5.3.2鄰接表152
5.3.3鄰接矩陣和鄰接表的比較157
5.4最小生成樹(shù)157
5.4.1Prim算法158
5.4.3Kruskal算法161
5.5最短路徑165
5.5.1Dijkstra算法165
5.5.2Floyd算法168
5.6有向無(wú)環(huán)圖及其應(yīng)用170
5.6.1AOV網(wǎng)與拓?fù)渑判?70
5.6.2AOE網(wǎng)與關(guān)鍵路徑173
5.7擴(kuò)展與提高175
5.7.1圖的其他存儲(chǔ)方法175
5.7.2圖的連通性177
5.8應(yīng)用實(shí)例179
5.8.1七巧板涂色問(wèn)題179
5.8.2醫(yī)院選址問(wèn)題180
5.9考研加油站183第6章查找技術(shù)185
6.1概述186
6.1.1查找的基本概念186
6.1.2查找算法的性能187
6.2線性表的查找技術(shù)187
6.2.1順序查找187
6.2.2折半查找188
6.3樹(shù)表的查找技術(shù)191
6.3.1二叉查找樹(shù)191
6.3.2平衡二叉樹(shù)197
6.3.3B樹(shù)200
6.4散列表的查找技術(shù)204
6.4.1散列查找的基本思想204
6.4.2散列函數(shù)的設(shè)計(jì)206
6.4.3處理沖突的方法207
6.4.4散列查找的性能分析211
6.5字符串模式匹配212
6.5.1BF算法212
6.5.2KMP算法214
6.6擴(kuò)展與提高216
6.6.1順序查找的改進(jìn)——分塊查找216
6.6.2折半查找的改進(jìn)——插值查找216
6.6.3平衡二叉樹(shù)的改進(jìn)——紅黑樹(shù)217
6.6.4B樹(shù)的改進(jìn)——B 樹(shù)223
6.6.5各種查找方法的比較224
6.7考研加油站224第7章排序技術(shù)227
7.1概述228
7.1.1排序的基本概念228
7.1.2排序算法的性能229
7.2插入排序229
7.2.1直接插入排序229
7.2.2希爾排序231
7.3交換排序233
7.3.1起泡排序233
7.3.2快速排序235
7.4選擇排序238
7.4.1簡(jiǎn)單選擇排序238
7.4.2堆排序240
7.5歸并排序244
7.5.1二路歸并排序的遞歸實(shí)現(xiàn)244
7.5.2二路歸并排序的非遞歸實(shí)現(xiàn)245
7.6外部排序247
7.6.1外部排序的基本思想247
7.6.2置換選擇排序248
7.6.3敗者樹(shù)250
7.7擴(kuò)展與提高251
7.7.1排序問(wèn)題的時(shí)間下界251
7.7.2基數(shù)排序252
7.7.3各種排序方法的比較254
7.8考研加油站256參考文獻(xiàn)258