數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計

出版者的話
前言
教學(xué)方案設(shè)計
第1章　引論1
　1.1　算法及其復(fù)雜性的概念1
　　1.1.1　算法與程序1
　　1.1.2　算法復(fù)雜性的概念2
　　1.1.3　算法復(fù)雜性的漸近性態(tài)3
　1.2　算法的表達(dá)與數(shù)據(jù)表示4
　　1.2.1　問題求解4
　　1.2.2　表達(dá)算法的抽象機(jī)制5
　1.3　抽象數(shù)據(jù)類型8
　　1.3.1　抽象數(shù)據(jù)類型的基本概念8
　　1.3.2　使用抽象數(shù)據(jù)類型的好處9
　1.4　數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型10
　1.5　用C語言描述數(shù)據(jù)結(jié)構(gòu)與算法11
　　1.5.1　變量和指針11
　　1.5.2　函數(shù)與參數(shù)傳遞12
　　1.5.3　結(jié)構(gòu)13
　　1.5.4　動態(tài)存儲分配14
　本章小結(jié)14
　習(xí)題15
　算法實(shí)驗(yàn)16
　　算法實(shí)驗(yàn)題1.1　哥德巴赫猜想問題16
　　算法實(shí)驗(yàn)題1.2　連續(xù)整數(shù)和問題16
第2章　表17
　2.1　表的基本概念17
　2.2　用數(shù)組實(shí)現(xiàn)表18
　2.3　用指針實(shí)現(xiàn)表22
　2.4　用間接尋址方法實(shí)現(xiàn)表25
　2.5　用游標(biāo)實(shí)現(xiàn)表27
　2.6　循環(huán)鏈表32
　2.7　雙鏈表34
　2.8　表的搜索游標(biāo)37
　　2.8.1　用數(shù)組實(shí)現(xiàn)表的搜索游標(biāo)38
　　2.8.2　單循環(huán)鏈表的搜索游標(biāo)38
　2.9　應(yīng)用40
　本章小結(jié)41
　習(xí)題41
　算法實(shí)驗(yàn)43
　　算法實(shí)驗(yàn)題2.1　向量分類問題43
　　算法實(shí)驗(yàn)題2.2　條形圖輪廓問題43
第3章　棧45
　3.1　棧的基本概念45
　3.2　用數(shù)組實(shí)現(xiàn)棧46
　3.3　用指針實(shí)現(xiàn)棧48
　3.4　應(yīng)用50
　本章小結(jié)52
　習(xí)題52
　算法實(shí)驗(yàn)54
　　算法實(shí)驗(yàn)題3.1　車皮編序問題54
　　算法實(shí)驗(yàn)題3.2　單柱Hanoi塔問題55
　　算法實(shí)驗(yàn)題3.3　多棧模擬問題55
　　算法實(shí)驗(yàn)題3.4　親兄弟問題56
第4章　隊(duì)列57
　4.1　隊(duì)列的基本概念57
　4.2　用指針實(shí)現(xiàn)隊(duì)列58
　4.3　用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列60
　4.4　應(yīng)用64
　本章小結(jié)66
　習(xí)題66
　算法實(shí)驗(yàn)67
　　算法實(shí)驗(yàn)題4.1　組隊(duì)列問題67
　　算法實(shí)驗(yàn)題4.2　雙棧隊(duì)列問題68
　　算法實(shí)驗(yàn)題4.3　猴子分桃問題69
　　算法實(shí)驗(yàn)題4.4　逆序表問題69
第5章　遞歸71
　5.1　遞歸的概念71
　5.2　遞歸程序設(shè)計76
　　5.2.1　分治與遞歸76
　　5.2.2　動態(tài)規(guī)劃77
　　5.2.3　回溯與遞歸83
　5.3　模擬遞歸85
　5.4　應(yīng)用87
　本章小結(jié)89
　習(xí)題89
　算法實(shí)驗(yàn)90
　　算法實(shí)驗(yàn)題5.1　刪數(shù)問題90
　　算法實(shí)驗(yàn)題5.2　最優(yōu)服務(wù)次序問題91
　　算法實(shí)驗(yàn)題5.3　最大k乘積問題91
　　算法實(shí)驗(yàn)題5.4　字符串比較問題92
第6章　排序與選擇93
　6.1　簡單排序算法93
　　6.1.1　冒泡排序94
　　6.1.2　插入排序94
　　6.1.3　選擇排序95
　　6.1.4　簡單排序算法的計算復(fù)雜性95
　6.2　快速排序算法96
　　6.2.1　算法基本思想及實(shí)現(xiàn)96
　　6.2.2　算法的性能97
　　6.2.3　隨機(jī)快速排序算法98
　　6.2.4　非遞歸快速排序算法98
　　6.2.5　三數(shù)取中劃分算法99
　　6.2.6　三劃分快速排序算法100
　6.3　合并排序算法101
　　6.3.1　算法基本思想及實(shí)現(xiàn)101
　　6.3.2　對基本算法的改進(jìn)102
　　6.3.3　自底向上的合并排序算法102
　　6.3.4　自然合并排序103
　　6.3.5　鏈表結(jié)構(gòu)的合并排序算法103
　6.4　線性時間排序算法104
　　6.4.1　計數(shù)排序104
　　6.4.2　桶排序105
　6.5　中位數(shù)與第k小元素106
　　6.5.1　平均情況下的線性時間選擇算法107
　　6.5.2　最壞情況下的線性時間選擇算法108
　6.6　應(yīng)用109
　本章小結(jié)110
　習(xí)題111
　算法實(shí)驗(yàn)112
　　算法實(shí)驗(yàn)題6.1　交換排序問題112
　　算法實(shí)驗(yàn)題6.2　DNA排序問題112
　　算法實(shí)驗(yàn)題6.3　輸油管道問題113
　　算法實(shí)驗(yàn)題6.4　最優(yōu)服務(wù)次序問題114
第7章　樹115
　7.1　樹的定義115
　7.2　樹的遍歷117
　7.3　樹的表示法119
　　7.3.1　父結(jié)點(diǎn)數(shù)組表示法119
　　7.3.2　兒子鏈表表示法119
　　7.3.3　左兒子右兄弟表示法120
　7.4　二叉樹120
　7.5　ADT二叉樹122
　7.6　二叉樹的實(shí)現(xiàn)123
　　7.6.1　二叉樹的順序存儲結(jié)構(gòu)123
　　7.6.2　二叉樹的結(jié)點(diǎn)度表示法124
　　7.6.3　用指針實(shí)現(xiàn)二叉樹124
　7.7　線索二叉樹128
　7.8　應(yīng)用129
　本章小結(jié)132
　習(xí)題133
　算法實(shí)驗(yàn)135
　　算法實(shí)驗(yàn)題7.1　層序列表問題135
　　算法實(shí)驗(yàn)題7.2　最近公共祖先問題135
　　算法實(shí)驗(yàn)題7.3　子樹問題136
　　算法實(shí)驗(yàn)題7.4　同構(gòu)二叉樹問題136
　　算法實(shí)驗(yàn)題7.5　后序中序遍歷問題137
第8章　集合138
　8.1　以集合為基礎(chǔ)的抽象數(shù)據(jù)類型138
　　8.1.1　集合的定義和記號138
　　8.1.2　定義在集合上的基本運(yùn)算139
　8.2　用位向量實(shí)現(xiàn)集合140
　8.3　用鏈表實(shí)現(xiàn)集合142
　8.4　應(yīng)用145
　本章小結(jié)146
　習(xí)題146
　算法實(shí)驗(yàn)147
　　算法實(shí)驗(yàn)題　半數(shù)集問題147
第9章　符號表148
　9.1　實(shí)現(xiàn)符號表的簡單方法148
　9.2　用散列表實(shí)現(xiàn)符號表149
　　9.2.1　開散列150
　　9.2.2　閉散列151
　　9.2.3　散列函數(shù)及其效率155
　　9.2.4　閉散列的重新散列技術(shù)156
　9.3　應(yīng)用156
　本章小結(jié)157
　習(xí)題158
　算法實(shí)驗(yàn)158
　　算法實(shí)驗(yàn)題9.1　偽隨機(jī)排列問題158
　　算法實(shí)驗(yàn)題9.2　字符串散列問題159
　　算法實(shí)驗(yàn)題9.3　英文文本分析問題159
　　算法實(shí)驗(yàn)題9.4　最長模式串問題160
第10章　字典161
　10.1　字典的定義161
　10.2　用數(shù)組實(shí)現(xiàn)字典162
　10.3　用二叉搜索樹實(shí)現(xiàn)字典162
　10.4　AVL樹169
　　10.4.1　AVL樹的定義和性質(zhì)169
　　10.4.2　旋轉(zhuǎn)變換170
　　10.4.3　AVL樹的插入運(yùn)算173
　　10.4.4　AVL樹的刪除運(yùn)算174
　10.5　應(yīng)用177
　本章小結(jié)179
　習(xí)題179
　算法實(shí)驗(yàn)180
　　算法實(shí)驗(yàn)題10.1　裝箱問題180
　　算法實(shí)驗(yàn)題10.2　電路板連線問題181
　　算法實(shí)驗(yàn)題10.3　辭典問題182
第11章　優(yōu)先隊(duì)列183
　11.1　優(yōu)先隊(duì)列的定義183
　11.2　用字典實(shí)現(xiàn)優(yōu)先隊(duì)列184
　11.3　優(yōu)先級樹和堆184
　11.4　用數(shù)組實(shí)現(xiàn)堆186
　11.5　可并優(yōu)先隊(duì)列188
　　11.5.1　左偏樹的定義188
　　11.5.2　用左偏樹實(shí)現(xiàn)可并優(yōu)先隊(duì)列189
　11.6　應(yīng)用192
　本章小結(jié)195
　習(xí)題195
　算法實(shí)驗(yàn)196
　　算法實(shí)驗(yàn)題11.1　多機(jī)調(diào)度問題196
　　算法實(shí)驗(yàn)題11.2　整數(shù)字典問題197
　　算法實(shí)驗(yàn)題11.3　最小權(quán)語言問題197
　　算法實(shí)驗(yàn)題11.4　二叉搜索堆問題198
第12章　并查集199
　12.1　并查集的定義及其簡單實(shí)現(xiàn)199
　12.2　用父結(jié)點(diǎn)數(shù)組實(shí)現(xiàn)并查集200
　12.3　應(yīng)用203
　本章小結(jié)204
　習(xí)題204
　算法實(shí)驗(yàn)205
　　算法實(shí)驗(yàn)題12.1　二進(jìn)制方程問題205
　　算法實(shí)驗(yàn)題12.2　網(wǎng)絡(luò)連通問題206
　　算法實(shí)驗(yàn)題12.3　朋友問題206
　　算法實(shí)驗(yàn)題12.4　無向圖的連通分支問題207
第13章　圖208
　13.1　圖的基本概念208
　13.2　抽象數(shù)據(jù)類型圖211
　13.3　圖的表示法211
　　13.3.1　鄰接矩陣表示法211
　　13.3.2　鄰接表表示法212
　　13.3.3　緊縮鄰接表213
　13.4　用鄰接矩陣實(shí)現(xiàn)圖213
　　13.4.1　用鄰接矩陣實(shí)現(xiàn)賦權(quán)有向圖213
　　13.4.2　用鄰接矩陣實(shí)現(xiàn)賦權(quán)無向圖215
　　13.4.3　用鄰接矩陣實(shí)現(xiàn)有向圖216
　　13.4.4　用鄰接矩陣實(shí)現(xiàn)無向圖216
　13.5　用鄰接表實(shí)現(xiàn)圖217
　　13.5.1　用鄰接表實(shí)現(xiàn)有向圖217
　　13.5.2　用鄰接表實(shí)現(xiàn)無向圖219
　　13.5.3　用鄰接表實(shí)現(xiàn)賦權(quán)有向圖220
　　13.5.4　用鄰接表實(shí)現(xiàn)賦權(quán)無向圖222
　13.6　圖的遍歷223
　　13.6.1　廣度優(yōu)先搜索223
　　13.6.2　深度優(yōu)先搜索225
　13.7　最短路徑226
　　13.7.1　單源最短路徑226
　　13.7.2　所有頂點(diǎn)對之間的最短路徑229
　13.8　最小支撐樹230
　　13.8.1　最小支撐樹性質(zhì)230
　　13.8.2　Prim算法231
　　13.8.3　Kruskal算法233
　13.9　圖匹配234
　本章小結(jié)236
　習(xí)題237
　算法實(shí)驗(yàn)238
　　算法實(shí)驗(yàn)題13.1　圖的2著色問題238
　　算法實(shí)驗(yàn)題13.2　賦權(quán)有向圖中心問題239
　　算法實(shí)驗(yàn)題13.3　最長簡單路徑問題239
　　算法實(shí)驗(yàn)題13.4　計算機(jī)網(wǎng)絡(luò)問題240
　　算法實(shí)驗(yàn)題13.5　差分約束問題240
　　算法實(shí)驗(yàn)題13.6　有截止時間的工作排序問題241
參考文獻(xiàn)243