內容簡介
本書是作者對長期從事數據結構與數值方法課程的教學經驗進行總結和提煉而寫成的，涉及計算機軟體基礎與套用中的主要知識、技術和方法，既包含了數據結構的基本知識，又包含了數值方法的內容。具體內容有集合、數據結構與算法的基本概念，線性數據結構的存儲與運算，非線性數據結構的存儲與運算，查找與排序技術，矩陣與線性方程組，插值與逼近，各種數值問題的近似解法，數值問題的連分式解法。每章都配有一定數量的習題。
本書內容豐富、通俗易懂、實用性強，可作為高等學校相應課程的教材，也可作為廣大從事計算機套用工作的科技人員的參考書。
目錄
第1章數據、數學模型和算法................................................................................1
1.1數據時代...................................................................................................1
1.1.1什麼是數據.....................................................................................1
1.1.2大數據時代.....................................................................................2
1.1.3數據的重要性..................................................................................4
1.2數據的表示................................................................................................5
1.2.1二元關係及其性質...........................................................................5
1.2.2數據的邏輯結構..............................................................................9
1.2.3數據的存儲結構.............................................................................12
1.2.4抽象數據類型.................................................................................12
1.3數學模型..................................................................................................13
1.3.1什麼是數學模型.............................................................................13
1.3.2數學模型的種類.............................................................................14
1.3.3數學模型與計算機..........................................................................15
1.3.4數據結構.......................................................................................16
1.4算法及複雜度分析.....................................................................................16
1.4.1什麼是算法....................................................................................16
1.4.2問題與解.......................................................................................17
1.4.3算法的分析與評價..........................................................................18
1.5本章小結..................................................................................................22
第2章線性結構...................................................................................................24
2.1線性表.....................................................................................................24
2.1.1線性表的概念及其抽象數據類型......................................................24
2.1.2線性表的順序存儲——順序表.........................................................27
2.1.3線性表的鏈式存儲——鍊表.............................................................30
2.1.4線性表小結....................................................................................35
2.2棧............................................................................................................35
2.2.1棧的概念與實現.............................................................................35
2.2.2棧的套用.......................................................................................38
2.2.3遞歸..............................................................................................41
2.3佇列.........................................................................................................48
2.3.1佇列的概念與實現..........................................................................48
2.3.2優先權佇列....................................................................................51
2.4字元串.....................................................................................................55
2.4.1字元串的概念和ADT......................................................................55
2.4.2字元串的存儲表示..........................................................................56
2.4.3字元串的模式匹配和簡單匹配算法...................................................57
2.4.4KMP算法.....................................................................................58
2.5本章小結..................................................................................................61
第3章樹與二叉樹...............................................................................................62
3.1樹的基本概念...........................................................................................62
3.1.1普遍存在的樹結構..........................................................................62
3.1.2樹的定義和性質.............................................................................65
3.2二叉樹.....................................................................................................67
3.2.1二叉樹的定義和性質.......................................................................68
3.2.2二叉樹的表示和實現.......................................................................70
3.2.3二叉樹的遍歷.................................................................................76
3.2.4二叉樹運算....................................................................................81
3.2.5二叉樹的建立.................................................................................83
3.3二叉樹的套用...........................................................................................84
3.3.1表達式求值....................................................................................84
3.3.2二叉搜尋樹....................................................................................85
3.3.3Hu.man樹與編碼..........................................................................89
3.3.4堆.................................................................................................95
3.4並查集...................................................................................................102
3.5本章小結................................................................................................103
第4章圖...........................................................................................................105
4.1圖的基本概念.........................................................................................105
4.1.1圖的定義和概念...........................................................................105
4.1.2圖的抽象數據類型........................................................................110
4.1.3歐拉路徑.....................................................................................110
4.2圖的存儲結構.........................................................................................112
4.2.1圖的鄰接矩陣表示........................................................................112
4.2.2圖的鄰接表表示...........................................................................115
4.2.3圖的其他表示方法........................................................................119
4.3圖的遍歷................................................................................................122
4.3.1圖的深度優先遍歷........................................................................123
目錄IX
4.3.2圖的廣度優先遍歷........................................................................124
4.3.3圖遍歷的套用...............................................................................125
4.3.4圖的連通性..................................................................................128
4.4有向圖與有向無環圖...............................................................................129
4.4.1有向圖的連通性和傳遞閉包...........................................................129
4.4.2有向無環圖和拓撲排序.................................................................132
4.4.3關鍵路徑.....................................................................................135
4.5最小生成樹.............................................................................................137
4.5.1圖的生成樹與最小生成樹..............................................................137
4.5.2普里姆(Prim)算法......................................................................139
4.5.3克魯斯卡爾(Kruskal)算法............................................................142
4.6最短路徑問題.........................................................................................144
4.6.1單源最短路徑...............................................................................145
4.6.2全源最短路徑...............................................................................147
4.7最大流...................................................................................................149
4.7.1網路流的基本概念........................................................................150
4.7.2Ford-Fulkerson方法.....................................................................151
4.8匹配.......................................................................................................154
4.8.1二分圖和匹配的基本概念..............................................................154
4.8.2匈牙利算法..................................................................................155
4.8.3最大匹配與最大流........................................................................157
4.9本章小結................................................................................................157
第5章查找和排序.............................................................................................159
5.1線性查找表.............................................................................................159
5.1.1順序查找.....................................................................................160
5.1.2折半查找.....................................................................................161
5.1.3斐波那契查找...............................................................................162
5.1.4線性查找表的性能比較.................................................................163
5.2靜態索引結構.........................................................................................164
5.2.1索引查找.....................................................................................164
5.2.2索引存儲方式...............................................................................164
5.2.3索引檔案結構...............................................................................167
5.3二叉搜尋樹查找性能...............................................................................169
5.4散列方法................................................................................................172
5.4.1散列技術的基本思想.....................................................................172
5.4.2散列函式.....................................................................................173
5.4.3衝突處理.....................................................................................175
5.4.4散列的刪除..................................................................................178
5.4.5散列的性能..................................................................................178
5.5排序的概念及算法性能分析.....................................................................179
5.6基本排序方法.........................................................................................180
5.6.1冒泡排序.....................................................................................181
5.6.2插入排序.....................................................................................182
5.6.3直接選擇排序...............................................................................187
5.6.4基本排序方法的比較.....................................................................188
5.7快速排序................................................................................................189
5.7.1快速排序的過程...........................................................................189
5.7.2快速排序的性能分析.....................................................................191
5.8歸併排序................................................................................................192
5.8.1二路歸併.....................................................................................192
5.8.2自底向上的歸併排序.....................................................................192
5.8.3自頂向下的歸併排序.....................................................................194
5.9堆和堆排序.............................................................................................195
5.9.1堆排序的思想...............................................................................195
5.9.2堆排序的實現...............................................................................197
5.10內排序方法分析....................................................................................198
5.10.1排序方法的下界........................................................................198
5.10.2內排序方法的比較.....................................................................199
5.11本章小結..............................................................................................200
第6章數值計算問題..........................................................................................202
6.1引言.......................................................................................................202
6.2近似與誤差.............................................................................................204
6.2.1誤差的定義..................................................................................204
6.2.2誤差的分類..................................................................................209
6.2.3條件數與敏感性...........................................................................212
6.3實數的表示與運算...................................................................................214
6.3.1浮點數系統..................................................................................214
6.3.2浮點運算.....................................................................................217
6.4一元方程求解.........................................................................................219
6.4.1一元方程.....................................................................................219
6.4.2二分法.........................................................................................220
6.4.3不動點法.....................................................................................222
6.4.4牛頓法.........................................................................................225
6.4.5疊代誤差分析...............................................................................229
6.5線性方程組求解......................................................................................232
6.5.1線性方程組..................................................................................232
目錄XI
6.5.2向量與矩陣範數...........................................................................234
6.5.3線性方程組敏感性........................................................................239
6.5.4線性方程組直接解法.....................................................................242
6.5.5線性方程組疊代解法.....................................................................252
6.6擬合與插值.............................................................................................256
6.6.1線性最小二乘...............................................................................256
6.6.2多項式插值..................................................................................264
6.7本章小結................................................................................................267
第7章最最佳化初步.............................................................................................268
7.1最佳化問題及其性質...................................................................................268
7.2無約束最佳化問題......................................................................................271
7.2.1最佳化條件.....................................................................................271
7.2.2一維最佳化.....................................................................................272
7.2.3多維最佳化.....................................................................................275
7.3約束最佳化問題.........................................................................................279
7.3.1最佳化條件.....................................................................................279
7.3.2序列二次規劃法...........................................................................282
7.3.3障礙法.........................................................................................284
7.4凸最佳化...................................................................................................286
7.4.1凸集合.........................................................................................286
7.4.2凸函式.........................................................................................289
7.4.3凸最佳化問題..................................................................................292
7.5組合最佳化的數值求解...............................................................................294
7.5.1組合最佳化問題...............................................................................294
7.5.2線性規劃初步...............................................................................296
7.5.3頂點覆蓋的線性規劃求解..............................................................297
7.6本章小結................................................................................................298
第8章隨機算法.................................................................................................299
8.1隨機性與隨機數......................................................................................299
8.2舍伍德與拉斯維加斯算法.........................................................................301
8.3蒙特卡洛算法.........................................................................................304
8.4模擬退火與遺傳算法...............................................................................307
8.5本章小結................................................................................................310
第9章算法設計思想..........................................................................................311
9.1蠻力法...................................................................................................311
9.2分治法...................................................................................................313
9.2.1分治法的運行時間........................................................................314
9.2.2分治法套用舉例...........................................................................316
9.2.3減治法.........................................................................................319
9.2.4變治法.........................................................................................321
9.3貪心法...................................................................................................323
9.4動態規劃................................................................................................326
9.4.1動態規劃的基本原理.....................................................................326
9.4.2算法設計舉例...............................................................................328
9.5搜尋算法：回溯法與分支定界法...............................................................334
9.5.1組合最佳化問題的解空間.................................................................334
9.5.2回溯法.........................................................................................338
9.5.3分支定界法..................................................................................342
