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

出版者的話
前言
教學(xué)方案設(shè)計(jì)
第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　問(wèn)題求解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語(yǔ)言描述數(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　動(dòng)態(tài)存儲(chǔ)分配14
　本章小結(jié)14
　習(xí)題15
　算法實(shí)驗(yàn)16
　　算法實(shí)驗(yàn)題1.1　哥德巴赫猜想問(wèn)題16
　　算法實(shí)驗(yàn)題1.2　連續(xù)整數(shù)和問(wèn)題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　向量分類問(wèn)題43
　　算法實(shí)驗(yàn)題2.2　條形圖輪廓問(wèn)題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　車皮編序問(wèn)題54
　　算法實(shí)驗(yàn)題3.2　單柱Hanoi塔問(wèn)題55
　　算法實(shí)驗(yàn)題3.3　多棧模擬問(wèn)題55
　　算法實(shí)驗(yàn)題3.4　親兄弟問(wèn)題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ì)列問(wèn)題67
　　算法實(shí)驗(yàn)題4.2　雙棧隊(duì)列問(wèn)題68
　　算法實(shí)驗(yàn)題4.3　猴子分桃問(wèn)題69
　　算法實(shí)驗(yàn)題4.4　逆序表問(wèn)題69
第5章　遞歸71
　5.1　遞歸的概念71
　5.2　遞歸程序設(shè)計(jì)76
　　5.2.1　分治與遞歸76
　　5.2.2　動(dòng)態(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ù)問(wèn)題90
　　算法實(shí)驗(yàn)題5.2　最優(yōu)服務(wù)次序問(wèn)題91
　　算法實(shí)驗(yàn)題5.3　最大k乘積問(wèn)題91
　　算法實(shí)驗(yàn)題5.4　字符串比較問(wèn)題92
第6章　排序與選擇93
　6.1　簡(jiǎn)單排序算法93
　　6.1.1　冒泡排序94
　　6.1.2　插入排序94
　　6.1.3　選擇排序95
　　6.1.4　簡(jiǎn)單排序算法的計(jì)算復(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　對(duì)基本算法的改進(jìn)102
　　6.3.3　自底向上的合并排序算法102
　　6.3.4　自然合并排序103
　　6.3.5　鏈表結(jié)構(gòu)的合并排序算法103
　6.4　線性時(shí)間排序算法104
　　6.4.1　計(jì)數(shù)排序104
　　6.4.2　桶排序105
　6.5　中位數(shù)與第k小元素106
　　6.5.1　平均情況下的線性時(shí)間選擇算法107
　　6.5.2　最壞情況下的線性時(shí)間選擇算法108
　6.6　應(yīng)用109
　本章小結(jié)110
　習(xí)題111
　算法實(shí)驗(yàn)112
　　算法實(shí)驗(yàn)題6.1　交換排序問(wèn)題112
　　算法實(shí)驗(yàn)題6.2　DNA排序問(wèn)題112
　　算法實(shí)驗(yàn)題6.3　輸油管道問(wèn)題113
　　算法實(shí)驗(yàn)題6.4　最優(yōu)服務(wù)次序問(wèn)題114
第7章　樹(shù)115
　7.1　樹(shù)的定義115
　7.2　樹(shù)的遍歷117
　7.3　樹(shù)的表示法119
　　7.3.1　父結(jié)點(diǎn)數(shù)組表示法119
　　7.3.2　兒子鏈表表示法119
　　7.3.3　左兒子右兄弟表示法120
　7.4　二叉樹(shù)120
　7.5　ADT二叉樹(shù)122
　7.6　二叉樹(shù)的實(shí)現(xiàn)123
　　7.6.1　二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)123
　　7.6.2　二叉樹(shù)的結(jié)點(diǎn)度表示法124
　　7.6.3　用指針實(shí)現(xiàn)二叉樹(shù)124
　7.7　線索二叉樹(shù)128
　7.8　應(yīng)用129
　本章小結(jié)132
　習(xí)題133
　算法實(shí)驗(yàn)135
　　算法實(shí)驗(yàn)題7.1　層序列表問(wèn)題135
　　算法實(shí)驗(yàn)題7.2　最近公共祖先問(wèn)題135
　　算法實(shí)驗(yàn)題7.3　子樹(shù)問(wèn)題136
　　算法實(shí)驗(yàn)題7.4　同構(gòu)二叉樹(shù)問(wèn)題136
　　算法實(shí)驗(yàn)題7.5　后序中序遍歷問(wèn)題137
第8章　集合138
　8.1　以集合為基礎(chǔ)的抽象數(shù)據(jù)類型138
　　8.1.1　集合的定義和記號(hào)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ù)集問(wèn)題147
第9章　符號(hào)表148
　9.1　實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法148
　9.2　用散列表實(shí)現(xiàn)符號(hào)表149
　　9.2.1　開(kāi)散列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ī)排列問(wèn)題158
　　算法實(shí)驗(yàn)題9.2　字符串散列問(wèn)題159
　　算法實(shí)驗(yàn)題9.3　英文文本分析問(wèn)題159
　　算法實(shí)驗(yàn)題9.4　最長(zhǎng)模式串問(wèn)題160
第10章　字典161
　10.1　字典的定義161
　10.2　用數(shù)組實(shí)現(xiàn)字典162
　10.3　用二叉搜索樹(shù)實(shí)現(xiàn)字典162
　10.4　AVL樹(shù)169
　　10.4.1　AVL樹(shù)的定義和性質(zhì)169
　　10.4.2　旋轉(zhuǎn)變換170
　　10.4.3　AVL樹(shù)的插入運(yùn)算173
　　10.4.4　AVL樹(shù)的刪除運(yùn)算174
　10.5　應(yīng)用177
　本章小結(jié)179
　習(xí)題179
　算法實(shí)驗(yàn)180
　　算法實(shí)驗(yàn)題10.1　裝箱問(wèn)題180
　　算法實(shí)驗(yàn)題10.2　電路板連線問(wèn)題181
　　算法實(shí)驗(yàn)題10.3　辭典問(wèn)題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)先級(jí)樹(shù)和堆184
　11.4　用數(shù)組實(shí)現(xiàn)堆186
　11.5　可并優(yōu)先隊(duì)列188
　　11.5.1　左偏樹(shù)的定義188
　　11.5.2　用左偏樹(shù)實(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)度問(wèn)題196
　　算法實(shí)驗(yàn)題11.2　整數(shù)字典問(wèn)題197
　　算法實(shí)驗(yàn)題11.3　最小權(quán)語(yǔ)言問(wèn)題197
　　算法實(shí)驗(yàn)題11.4　二叉搜索堆問(wèn)題198
第12章　并查集199
　12.1　并查集的定義及其簡(jiǎn)單實(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)制方程問(wèn)題205
　　算法實(shí)驗(yàn)題12.2　網(wǎng)絡(luò)連通問(wèn)題206
　　算法實(shí)驗(yàn)題12.3　朋友問(wèn)題206
　　算法實(shí)驗(yàn)題12.4　無(wú)向圖的連通分支問(wèn)題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)無(wú)向圖215
　　13.4.3　用鄰接矩陣實(shí)現(xiàn)有向圖216
　　13.4.4　用鄰接矩陣實(shí)現(xiàn)無(wú)向圖216
　13.5　用鄰接表實(shí)現(xiàn)圖217
　　13.5.1　用鄰接表實(shí)現(xiàn)有向圖217
　　13.5.2　用鄰接表實(shí)現(xiàn)無(wú)向圖219
　　13.5.3　用鄰接表實(shí)現(xiàn)賦權(quán)有向圖220
　　13.5.4　用鄰接表實(shí)現(xiàn)賦權(quán)無(wú)向圖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)對(duì)之間的最短路徑229
　13.8　最小支撐樹(shù)230
　　13.8.1　最小支撐樹(shù)性質(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著色問(wèn)題238
　　算法實(shí)驗(yàn)題13.2　賦權(quán)有向圖中心問(wèn)題239
　　算法實(shí)驗(yàn)題13.3　最長(zhǎng)簡(jiǎn)單路徑問(wèn)題239
　　算法實(shí)驗(yàn)題13.4　計(jì)算機(jī)網(wǎng)絡(luò)問(wèn)題240
　　算法實(shí)驗(yàn)題13.5　差分約束問(wèn)題240
　　算法實(shí)驗(yàn)題13.6　有截止時(shí)間的工作排序問(wèn)題241
參考文獻(xiàn)243