《數據結構（C++語言版）》是2012年清華大學出版社出版的圖書，作者是鄧俊輝。
基本介紹
- 書名：數據結構（C++語言版）
- 作者：鄧俊輝
- ISBN：9787302268833
- 定價：39
- 出版社：清華大學出版社
- 出版時間：2012-2-3
- 裝幀：平裝
內容簡介,圖書目錄,
內容簡介
本書按照面向對象程式設計的思想，根據作者多年的教學積累，系統介紹各類數據結構的功能、表示和實現，對比各類數據結構適用的套用環境；結合實際問題展示算法設計的一般性模式與方法、算法實現的主流技巧，以及算法效率的評判依據和分析方法；以高度概括的體例為線索貫穿全書，並通過對比和類比揭示數據結構與算法的內在聯繫，幫助讀者形成整體性認識。
書中穿插大量驗證型、拓展型和反思型習題，以激發讀者的求知慾，培養自學能力和獨立思考習慣；近300幅插圖結合簡練的敘述，200多段代碼配合詳盡而簡潔的注釋，使深奧抽象的概念和過程得以具體化並便於理解和記憶。
圖書目錄
第1章 緒論 1
§1.1計算機與算法 2
1.1.1古埃及人的繩索 2
1.1.2歐幾里德的尺規 3
1.1.3起泡排序 4
1.1.4算法 5
1.1.5算法效率 8
§1.2複雜度度量 8
1.2.1問題規模、運行時間及時間
複雜度 9
1.2.2漸進複雜度 9
1.2.3空間複雜度 11
§1.3複雜度分析 12
1.3.1常數複雜度O(1) 12
1.3.2對數複雜度O(logn) 13
1.3.3線性複雜度O(n) 14
1.3.4多項式複雜度O(polynomial(n)) 15
1.3.5指數複雜度O(2n) 15
1.3.6複雜度層次 16
1.3.7輸入規模 16
§1.4*遞歸 17
1.4.1線性遞歸 17
1.4.2遞歸分析 18
1.4.3遞歸模式 20
1.4.4遞歸消除 22
1.4.5二分遞歸 24
§1.5抽象數據類型 27
習題 28
第2章 向量 31
§2.1從數組到向量 32
2.1.1數組 32
2.1.2向量 32
§2.2接口 33
2.2.1ADT接口 33
2.2.2操作實例 34
2.2.3Vector模板類 34
§2.3構造與析構 36
2.3.1默認構造方法 36
2.3.2基於複製的構造方法 36
2.3.3析構方法 37
§2.4動態空間管理 37
2.4.1靜態空間管理 37
2.4.2可擴充向量 38
2.4.3擴容 38
2.4.4分攤分析 39
2.4.5縮容 40
§2.5向量 41
2.5.1直接引用元素 41
2.5.2置亂器 41
2.5.3判等器與比較器 42
2.5.4無序查找 43
2.5.5插入 44
2.5.6刪除 45
2.5.7唯一化 46
2.5.8遍歷 47
§2.6有序向量 49
2.6.1比較器 49
2.6.2有序性甄別 49
2.6.3唯一化 49
2.6.4查找 52
2.6.5二分查找（版本A） 53
2.6.6Fibonacci查找 56
2.6.7二分查找（版本B） 59
2.6.8二分查找（版本C） 60
§2.7*排序與下界 61
2.7.1有序性 61
2.7.2排序及其分類 62
2.7.3下界 62
2.7.4比較樹 63
2.7.5估計下界 64
§2.8排序器 64
2.8.1統一入口 64
2.8.2起泡排序 65
2.8.3歸併排序 66
習題 69
第3章 列表 73
§3.1從向量到列表 74
3.1.1從靜態存儲到動態存儲 74
3.1.2由秩到位置 75
3.1.3列表 75
§3.2接口 75
3.2.1列表節點 75
3.2.2列表 76
§3.3列表 79
3.3.1頭、尾節點 79
3.3.2默認構造方法 79
3.3.3由秩到位置的轉換 80
3.3.4查找 80
3.3.5插入 81
3.3.6基於複製的構造 83
3.3.7刪除 84
3.3.8析構 85
3.3.9唯一化 86
3.3.10遍歷 86
§3.4有序列表 87
3.4.1唯一化 87
3.4.2查找 88
§3.5排序器 88
3.5.1統一入口 88
3.5.2插入排序 89
3.5.3選擇排序 91
3.5.4歸併排序 92
習題 94
第4章 棧與佇列 97
§4.1棧 98
4.1.1概述 98
4.1.2ADT接口 99
4.1.3操作實例 99
4.1.4Stack模板類 99
§4.2棧與遞歸 100
4.2.1遞歸的實現 101
4.2.2避免遞歸 102
§4.3典型套用 103
4.3.1逆序輸出 103
4.3.2遞歸嵌套 105
4.3.3延遲緩衝 108
4.3.4逆波蘭表達式 113
§4.4*試探回溯法 116
4.4.1試探與回溯 116
4.4.2八皇后 117
4.4.3迷宮尋徑 119
§4.5佇列 122
4.5.1概述 122
4.5.2ADT接口 122
4.5.3操作實例 123
4.5.4Queue模板類 124
§4.6佇列套用 124
4.6.1循環分配器 124
4.6.2銀行服務模擬 125
習題 126
第5章 二叉樹 129
§5.1二叉樹及其表示 130
5.1.1樹 130
5.1.2二叉樹 131
5.1.3多叉樹 132
§5.2編碼樹 134
5.2.1二進制編碼 134
5.2.2二叉編碼樹 136
§5.3二叉樹的實現 137
5.3.1二叉樹節點 137
5.3.2二叉樹節點操作接口 140
5.3.3二叉樹 141
§5.4Huffman編碼 146
5.4.1PFC編碼 146
5.4.2最優編碼樹 149
5.4.3Huffman編碼樹 152
5.4.4Huffman編碼算法 154
§5.5遍歷 160
5.5.1遞歸式遍歷 161
5.5.2疊代版先序遍歷 163
5.5.3疊代版中序遍歷 165
5.5.4疊代版後序遍歷 169
5.5.5層次遍歷 171
習題 172
第6章 圖 175
§6.1概述 176
§6.2抽象數據類型 179
6.2.1操作接口 179
6.2.2Graph模板類 180
§6.3鄰接矩陣 181
6.3.1原理 181
6.3.2實現 182
6.3.3時間性能 184
6.3.4空間性能 184
§6.4鄰接表 184
6.4.1原理 184
6.4.2複雜度 184
§6.5圖遍歷算法概述 185
§6.6廣度優先搜尋 186
6.6.1策略 186
6.6.2實現 186
6.6.3實例 187
6.6.4複雜度 187
6.6.5套用 188
§6.7深度優先搜尋 188
6.7.1策略 188
6.7.2實現 189
6.7.3實例 190
6.7.4複雜度 191
6.7.5套用 192
§6.8拓撲排序 192
6.8.1套用 192
6.8.2有向無環圖 193
6.8.3算法 193
6.8.4實現 193
6.8.5實例 194
6.8.6複雜度 194
§6.9*雙連通域分解 195
6.9.1關節點與雙連通域 195
6.9.2蠻力算法 195
6.9.3算法 196
6.9.4實現 196
6.9.5實例 198
6.9.6複雜度 199
§6.10優先權搜尋 199
6.10.1優先權與優先權數 199
6.10.2基本框架 200
6.10.3複雜度 201
§6.11最小支撐樹 201
6.11.1支撐樹 201
6.11.2最小支撐樹 201
6.11.3歧義性 201
6.11.4蠻力算法 202
6.11.5Prim算法 202
§6.12最短路徑 204
6.12.1最短路徑樹 204
6.12.2歧義性 205
6.12.3Dijkstra算法 205
習題 208
第7章 搜尋樹 211
§7.1搜尋 212
7.1.1循關鍵碼訪問 212
7.1.2詞條 213
7.1.3序與比較器 213
§7.2二叉搜尋樹 213
7.2.1順序性 213
7.2.2中序遍歷序列 214
7.2.3BST模板類 214
7.2.4查找算法及其實現 215
7.2.5插入算法及其實現 217
7.2.6刪除算法及其實現 218
§7.3平衡二叉搜尋樹 220
7.3.1樹高與性能 220
7.3.2理想平衡與適度平衡 221
7.3.3等價二叉搜尋樹 222
7.3.4等價變換與局部調整 222
§7.4AVL樹 223
7.4.1AVL樹 223
7.4.2節點插入 225
7.4.3節點刪除 228
7.4.4統一重平衡算法 230
習題 232
第8章 高級搜尋樹 235
§8.1伸展樹 236
8.1.1局部性 236
8.1.2逐層伸展 237
8.1.3雙層伸展 238
8.1.4分攤分析 240
8.1.5伸展樹的實現 243
§8.2B-樹 247
8.2.1多路平衡搜尋 247
8.2.2ADT接口及其實現 249
8.2.3關鍵碼查找 251
8.2.4性能分析 252
8.2.5關鍵碼插入 253
8.2.6上溢與分裂 254
8.2.7關鍵碼刪除 257
8.2.8下溢與合併 258
§8.3*紅黑樹 263
8.3.1概述 263
8.3.2紅黑樹接口定義 265
8.3.3節點插入算法 266
8.3.4節點刪除算法 269
§8.4*kd-樹 275
8.4.1範圍查詢 275
8.4.2kd-樹 278
8.4.3基於2d-樹的範圍查詢算法 279
習題 280
第9章 詞典 283
§9.1詞典 284
9.1.1操作接口 284
9.1.2操作實例 285
9.1.3接口定義 286
9.1.4判等器 286
9.1.5實現方法 287
§9.2*跳轉表 287
9.2.1Skiplist模板類 287
9.2.2總體邏輯結構 288
9.2.3四聯表 288
9.2.4查找 290
9.2.5空間複雜度 292
9.2.6時間複雜度 292
9.2.7插入 293
9.2.8刪除 296
§9.3散列表 298
9.3.1完美散列 298
9.3.2裝填因子與空間利用率 299
9.3.3散列函式 300
9.3.4散列表 303
9.3.5衝突及其排解 305
9.3.6開放定址策略 307
9.3.7查找與刪除 309
9.3.8插入 310
9.3.9更多開放定址策略 312
9.3.10散列碼轉換 314
§9.4*散列套用 316
9.4.1桶排序 316
9.4.2最大間隙 317
9.4.3基數排序 318
習題 319
第10章 優先權佇列 323
§10.1優先權佇列 324
10.1.1優先權與優先權佇列 324
10.1.2關鍵碼、比較器與偏序關係 325
10.1.3操作接口 325
10.1.4操作實例：選擇排序 325
10.1.5接口定義 326
10.1.6套用實例：Huffman編碼樹 326
§10.2堆 328
10.2.1完全二叉堆 329
10.2.2元素插入 331
10.2.3元素刪除 333
10.2.4建堆 335
10.2.5就地堆排序 338
§10.3*左式堆 341
10.3.1堆合併 341
10.3.2單側傾斜 341
10.3.3PQ_LeftHeap模板類 342
10.3.4空節點路徑長度 342
10.3.5左傾性與左式堆 343
10.3.6右側鏈 343
10.3.7合併算法 344
10.3.8合併操作merge()的實現 344
10.3.9實例 345
10.3.10複雜度 345
10.3.11基於合併的插入和刪除操作 346
習題 347
第11章 串 349
§11.1串及串匹配 350
11.1.1串 350
11.1.2串匹配 351
11.1.3測評標準與策略 352
§11.2蠻力算法 353
11.2.1算法描述 353
11.2.2算法實現 353
11.2.3時間複雜度 354
§11.3KMP算法 355
11.3.1構思 355
11.3.2next表 356
11.3.3KMP算法 357
11.3.4next[0]=-1 357
11.3.5構造next表 358
11.3.6性能分析 358
11.3.7繼續改進 359
§11.4*BM算法 361
11.4.1思路與框架 361
11.4.2壞字元策略 362
11.4.3好後綴策略 364
11.4.4綜合性能 368
§11.5*Karp-Rabin算法 369
11.5.1構思 369
11.5.2算法與實現 370
習題 373
第12章 排序 375
§12.1快速排序 376
12.1.1分治策略 376
12.1.2軸點 376
12.1.3快速排序算法 377
12.1.4快速劃分算法 377
12.1.5複雜度 379
12.1.6應對退化 381
§12.2*選取與中位數 382
12.2.1概述 382
12.2.2主流數 383
12.2.3歸併向量的中位數 385
12.2.4基於優先權佇列的選取 388
12.2.5基於快速劃分的選取 389
12.2.6k-選取算法 390
§12.3*希爾排序 392
12.3.1遞減增量策略 392
12.3.2增量序列 394
習題 397
附錄 399
插圖索引 400
表格索引 406
算法索引 407
代碼索引 408
關鍵字索引 414
