數(shù)據(jù)結構與算法設計

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