基本信息

書名:數據結構與算法分析-C++語言描述-

定價

作者:(美)Mark Allen Weiss(M. A. 韋斯)著,馮舜璽譯

出版社：電子工業出版社

出版日期：2016-08-01

ISBN：9787121290572

字數：833000

頁碼：508

版次：4

裝幀：平裝

開本：16開

商品重量：

編輯推薦

本版特色如下：
書中的闡述和算法均用C 新標準C 11的代碼實現。
unordered_map兩個類模板的簡要討論。
增加了基數排序和與選擇相關問題下界的證明。增加了對AVL樹刪除算法的實現。使用新的union/find分析同時改進此前各版的較弱的O(MlogN)界。

內容提要

本書是數據結構和算法分析的經典教材，書中使用主流的程序設計語言C 作為具體的實現語言。書中內容包括表、棧、隊列、樹、散列表、優先隊列、排序、不相交集算法、圖論算法、算法分析、算法設計、攤還分析、查找樹算法、k-d樹和配對堆等。本書把算法分析與C 程序的開發有機地結合起來，深入分析每種算法，內容全面、縝密嚴格，並細致講解精心構造程序的方法。

目錄

章 程序設計：綜述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::move25
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 表ADT64
3.2.1 表的簡單數組實現65
3.2.2 簡單鏈表65
3.3 STL中的vector和list67
3.3.1 迭代器68
3.3.2 例子：對表使用erase69
3.3.3 const_iterators70
3.4 vector的實現72
3.5 list的實現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.1 contains110
4.3.2 findMin和findMax111
4.3.3 insert112
4.3.4 remove113
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 logN)界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
0章 算法設計技巧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 回溯算法3

作者介紹

馮舜璽，天津師範大學數學科學學院退休教授，曾任天津市計算數學學會常務理事，主要教學及研究方向為數值代數，組合數學，數據結構與算法分析。

序言