《數據結構與算法分析——C++語言描述（第四版）》是2016年8月電子工業出版社出版的圖書，作者是馮舜璽。
基本介紹
- 書名：數據結構與算法分析——C++語言描述（第四版）
- 作者：馮舜璽
- ISBN：9787121290572
- 頁數：508頁
- 定價：89元
- 出版社：電子工業出版社
- 出版時間：2016年8月
- 開本：16開
內容簡介,圖書目錄,
內容簡介
本書是數據結構和算法分析的經典教材，書中使用主流的程式設計語言C++作為具體的實現語言。書中內容包括表、棧、佇列、樹、散列表、優先佇列、排序、不相交集算法、圖論算法、算法分析、算法設計、攤還分析、查找樹算法、k-d樹和配對堆等。本書把算法分析與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 模運算(modular arithmetic) 4
1.2.5 證明方法 5
1.3 遞歸簡論 7
1.4 C++類 10
1.4.1 基本的class語法 10
1.4.2 構造函式的附加語法和訪問
函式 11
1.4.3 接口與實現的分離 13
1.4.4 vector類和string類 16
1.5 C++細節 17
1.5.1 指針(pointer) 18
1.5.2 左值、右值和引用 19
1.5.3 參數傳遞 21
1.5.4 返回值傳遞 23
1.5.5 std::swap和std::move 25
1.5.6 五大函式：析構函式，拷貝構造
函式，移動構造函式，拷貝賦值
operator=，移動賦值operator= 26
1.5.7 C風格數組和字元串 30
1.6 模板 31
1.6.1 函式模板 31
1.6.2 類模板 32
1.6.3 Object、Comparable和一個
例子 33
1.6.4 函式對象 34
1.6.5 類模板的分離式編譯 37
1.7 使用矩陣 37
1.7.1 數據成員、構造函式和基本訪問
函式 38
1.7.2 operator[] 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 表ADT 64
3.2.1 表的簡單數組實現 65
3.2.2 簡單鍊表 65
3.3 STL中的vector和list 67
3.3.1 疊代器 68
3.3.2 例子：對表使用erase 69
3.3.3 const_iterators 70
3.4 vector的實現 72
3.5 list的實現 76
3.6 棧ADT 86
3.6.1 棧模型 86
3.6.2 棧的實現 86
3.6.3 套用 87
3.7 佇列ADT 93
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.1 contains 110
4.3.2 findMin和findMax 111
4.3.3 insert 112
4.3.4 remove 113
4.3.5 析構函式和拷貝構造函式 115
4.3.6 平均情況分析 115
4.4 AVL樹 118
4.4.1 單旋轉 119
4.4.2 雙旋轉 121
4.5 伸展樹 128
4.5.1 一個簡單的想法(不能直接
使用) 128
4.5.2 展開 130
4.6 樹的遍歷 134
4.7 B樹 135
4.8 標準庫中的集合與映射 140
4.8.1 集合(set) 140
4.8.2 映射(map) 141
4.8.3 set和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.5 d堆 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 對手下界(adversary lower
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(M log*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.2 Dijkstra算法 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.1 Prim算法 327
9.5.2 Kruskal算法 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.7 NP完全性介紹 340
9.7.1 難與易 341
9.7.2 NP類 341
9.7.3 NP完全問題 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.3 treap樹 453
12.4 後綴數組和後綴樹 456
12.4.1 後綴數組 456
12.4.2 後綴樹 458
12.4.3 後綴數組和後綴樹的線性
時間構建 461
12.5 k-d樹 471
12.6 配對堆 474
小結 479
練習 479
參考文獻 483
附錄A 類模板的分離式編譯 486
索引 489
