數據結構與算法分析--C++語言描述（第四版）

第1章程序設計：綜述1
1.1本書討論的內容1
1.2數學知識復習2
1.2.1指數（exponent）2
1.2.2對數（logarithm）2
1.2.3級數（series）3
1.2.4模運算（modulararithmetic）4
1.2.5證明方法5
1.3遞歸簡論7
1.4C++類10
1.4.1基本的class語法10
1.4.2構造函數的附加語法和訪問
函數11
1.4.3接口與實現的分離13
1.4.4vector類和string類16
1.5C++細節17
1.5.1指針（pointer）18
1.5.2左值、右值和引用19
1.5.3參數傳遞21
1.5.4返回值傳遞23
1.5.5std：：swap和std：：move25
1.5.6五大函數：析構函數，拷貝構造
函數，移動構造函數，拷貝賦值
operator=，移動賦值operator=26
1.5.7C風格數組和字符串30
1.6模板31
1.6.1函數模板31
1.6.2類模板32
1.6.3Object、Comparable和一個
例子33
1.6.4函數對象34
1.6.5類模板的分離式編譯37
1.7使用矩陣37
1.7.1數據成員、構造函數和基本訪問
函數38
1.7.2operator（）38
1.7.3五大函數39
小結39
練習39
參考文獻41
第2章算法分析42
2.1數學基礎42
2.2模型44
2.3要分析的問題44
2.4運行時間計算47
2.4.1一個簡單的例子47
2.4.2一般法則47
2.4.3最大子序列和問題的求解49
2.4.4運行時間中的對數54
2.4.5最壞情形分析的局限性57
小結58
練習58
參考文獻63
第3章表、棧和隊列64
3.1抽象數據類型（ADT）64
3.2表ADT64
3.2.1表的簡單數組實現65
3.2.2簡單鏈表65
3.3STL中的vector和list67
3.3.1迭代器68
3.3.2例子：對表使用erase69
3.3.3const_iterators70
3.4vector的實現72
3.5list的實現76
3.6棧ADT86
3.6.1棧模型86
3.6.2棧的實現86
3.6.3應用87
3.7隊列ADT93
3.7.1隊列模型93
3.7.2隊列的數組實現93
3.7.3隊列的應用95
小結96
練習96
第4章樹100
4.1預備知識100
4.1.1樹的實現101
4.1.2樹的遍歷及應用102
4.2二叉樹105
4.2.1實現105
4.2.2一個例子——表達式樹105
4.3查找樹ADT——二叉查找樹108
4.3.1contains110
4.3.2findMin和findMax111
4.3.3insert112
4.3.4remove113
4.3.5析構函數和拷貝構造函數115
4.3.6平均情況分析115
4.4AVL樹118
4.4.1單旋轉119
4.4.2雙旋轉121
4.5伸展樹128
4.5.1一個簡單的想法（不能直接
使用）128
4.5.2展開130
4.6樹的遍歷134
4.7B樹135
4.8標准庫中的集合與映像140
4.8.1集合（set）140
4.8.2映射（map）141
4.8.3set和map的實現142
4.8.4使用多個映射（map）的例142
小結147
練習147
參考文獻153
第5章散列155
5.1一般想法155
5.2散列函數155
5.3分離鏈接法157
5.4不用鏈表的散列表161
5.4.1線性探測法161
5.4.2平方探測法163
5.4.3雙散列166
5.5再散列167
5.6標准庫中的散列表169
5.7以最壞情形O（1）訪問的散列表170
5.7.1完美散列170
5.7.2杜鵑散列172
5.7.3跳房子散列181
5.8通用散列184
5.9可擴散列186
小結188
練習189
參考文獻193
第6章優先隊列（堆）196
6.1模型196
6.2一些簡單的實現197
6.3二叉堆197
6.3.1結構性質197
6.3.2堆序性質198
6.3.3基本的堆操作199
6.3.4其他的堆操作203
6.4優先隊列的應用206
6.4.1選擇問題206
6.4.2事件模擬207
6.5d堆208
6.6左式堆209
6.6.1左式堆的性質209
6.6.2左式堆操作210
6.7斜堆215
6.8二項隊列216
6.8.1二項隊列構建216
6.8.2二項隊列操作217
6.8.3二項隊列的實現219
6.9標准庫中的優先隊列224
小結225
練習225
參考文獻229
第7章排序232
7.1預備知識232
7.2插入排序233
7.2.1算法233
7.2.2插入排序的STL實現233
7.2.3插入排序的分析235
7.3一些簡單排序算法的下界235
7.4希爾排序236
7.4.1希爾排序的最壞情形分析237
7.5堆排序239
7.5.1堆排序的分析241
7.6歸並排序242
7.6.1歸並排序的分析245
7.7快速排序247
7.7.1選取樞紐元249
7.7.2分割策略250
7.7.3小數組252
7.7.4實際的快速排序例程252
7.7.5快速排序的分析254
7.7.6選擇問題的線性期望時間
算法256
7.8排序算法的一般下界258
7.8.1決策樹258
7.9選擇問題的決策樹下界260
7.10對手下界（adversarylower
bounds）262
7.11線性時間排序：桶式排序和
基數排序265
7.12外部排序269
7.12.1為什麼需要一些新的算法269
7.12.2外部排序模型269
7.12.3簡單算法269
7.12.4多路合並270
7.12.5多相合並271
7.12.6替換選擇272
小結273
練習題273
參考文獻278
第8章不相交集類281
8.1等價關系281
8.2動態等價性問題281
8.3基本數據結構283
8.4靈巧求並算法286
8.5路徑壓縮288
8.6按秩求並和路徑壓縮的最壞
情形289
8.6.1緩慢增長的函數289
8.6.2通過遞歸分解進行的分析290
8.6.3一個O（Mlog*N）界295
8.6.4一個O（Mα（M，N））界296
8.7一個應用297
小結299
練習299
參考文獻301
第9章圖論算法303
9.1若干定義303
9.1.1圖的表示304
9.2拓撲排序305
9.3最短路徑算法308
9.3.1無權最短路徑309
9.3.2Dijkstra算法312
9.3.3具有負邊值的圖317
9.3.4無圈圖318
9.3.5所有頂點對間的最短路徑320
9.3.6最短路徑的例320
9.4網絡流問題322
9.4.1一個簡單的最大流算法323
9.5最小生成樹326
9.5.1Prim算法327
9.5.2Kruskal算法329
9.6深度優先搜索的應用330
9.6.1無向圖331
9.6.2雙連通性332
9.6.3歐拉回路335
9.6.4有向圖338
9.6.5查找強分支339
9.7NP完全性介紹340
9.7.1難與易341
9.7.2NP類341
9.7.3NP完全問題342
小結344
練習344
參考文獻350
第10章算法設計技巧353
10.1貪婪算法353
10.1.1一個簡單的調度問題354
10.1.2哈夫曼編碼355
10.1.3近似裝箱問題359
10.2分治算法366
10.2.1分治算法的運行時間367
10.2.2最近點問題369
10.2.3選擇問題371
10.2.4一些算術問題的理論改進374
10.3動態規划377
10.3.1用表代替遞歸377
10.3.2矩陣乘法的順序安排379
10.3.3最優二叉查找樹382
10.3.4所有點對最短路徑384
10.4隨機化算法386
10.4.1隨機數發生器387
10.4.2跳躍表392
10.4.3素性測試393
10.5回溯算法396
10.5.1收費公路重建問題396
10.5.2博弈400
小結405
練習406
參考文獻413
第11章攤還分析418
11.1一個無關的智力問題418
11.2二項隊列419
11.3斜堆423
11.4斐波那契堆425
11.4.1切除左式堆中的節點425
11.4.2二項隊列的懶惰合並427
11.4.3斐波那契堆操作429
11.4.4時間界的證明430
11.5伸展樹432
小結436
練習436
參考文獻437
第12章高級數據結構及其實現439
12.1自頂向下伸展樹439
12.2紅黑樹445
12.2.1自底向上的插入446
12.2.2自頂向下紅黑樹447
12.2.3自頂向下刪除452
12.3treap樹453
12.4后綴數組和后綴樹456
12.4.1后綴數組456
12.4.2后綴樹458
12.4.3后綴數組和后綴樹的線性
時間構建461
12.5k—d樹471
12.6配對堆474
小結479
練習479
參考文獻483
附錄A類模板的分離式編譯486
索引489