《數據結構、算法與套用——C++語言描述（原書第2版）》是2019年9月機械工業出版社出版的圖書，作者是（美）Sartaj、Sahni。
基本介紹
- 書名：數據結構、算法與套用——C++語言描述（原書第2版）
- 作者：（美）Sartaj、Sahni
- ISBN：9787111496007
- 定價：79.0元
- 出版社：機械工業出版社
- 出版時間：2019年9月
- 裝幀：平裝
- 開本：16開
內容簡介,圖書目錄,
內容簡介
本書共分三個部分。第一部分從第1章到第4章，旨在複習C++程式設計的概念以及程式性能的分析和測量方法。第二部分從第5章到第16章，研究數據結構，包括線性表、數組和矩陣、棧、佇列、字典、二叉樹、優先權佇列、競賽樹、搜尋樹和圖等。第三部分從第17章到第21章，研究常用算法，包括貪婪算法、分而治之算法、動態規劃、回溯算法和分枝定界算法。本書有800多道練習題和50多個套用實例。內容廣博，組織合理，論述清晰，循序漸進，而且對程式性能的分析和測量系統入微。本書不僅是數據結構和算法的經典教材，而且是計算機科學與工程領域的理想參考書。
圖書目錄
Data Structures, Algorithms, and Applications in C++, Second Edition
出版者的話
譯者序
前言
第一部分 預備知識
第1章 C++回顧 2
1.1 引言 2
1.2 函式與參數 3
1.2.1 傳值參數 3
1.2.2 模板函式 4
1.2.3 引用參數 4
1.2.4 常量引用參數 5
1.2.5 返回值 5
1.2.6 重載函式 6
1.3 異常 7
1.3.1 拋出異常 7
1.3.2 處理異常 7
1.4 動態存儲空間分配 9
1.4.1 操作符new 9
1.4.2 一維數組 9
1.4.3 異常處理 9
1.4.4 操作符delete 10
1.4.5 二維數組 10
1.5 自有數據類型 12
1.5.1 類currency 12
1.5.2 一種不同的描述方法 18
1.5.3 操作符重載 20
1.5.4 友元和保護性類成員 22
1.5.5 增加#ifndef、#define和#endif語句 23
1.6 異常類illegalParameterValue 24
1.7 遞歸函式 25
1.7.1 遞歸的數學函式 25
1.7.2 歸納 25
1.7.3 C++遞歸函式 26
1.8 標準模板庫 30
1.9 測試與調試 32
1.9.1 什麼是測試 32
1.9.2 測試數據的設計 34
1.9.3 調試 36
1.10 參考及推薦讀物 37
第2章 程式性能分析 38
2.1 什麼是程式性能 38
2.2 空間複雜度 39
2.2.1 空間複雜度的組成 39
2.2.2 舉例 42
2.3 時間複雜度 44
2.3.1 時間複雜度的組成 44
2.3.2 操作計數 45
2.3.3 最好、最壞和平均操作計數 48
2.3.4 步數 53
第3章 漸近記法 64
3.1 引言 64
3.2 漸近記法 65
3.2.1 大Ο記法 65
3.2.2 漸近記法Ω和Θ 67
3.3 漸近數學（可選） 69
3.3.1 大O記法 69
3.3.2 Ω記法 71
3.3.3 Θ記法 72
3.3.4 小ο記法 73
3.3.5 特性 73
3.4 複雜度分析舉例 75
3.5 實際複雜度 78
3.6 參考及推薦讀物 80
第4章 性能測量 81
4.1 引言 81
4.2 選擇實例的大小 82
4.3 設計測試數據 82
4.4 實驗設計 82
4.5 高速快取 87
4.5.1 簡單計算機模型 87
4.5.2 快取未命中對運行時間的影響 87
4.5.3 矩陣乘法 88
4.6 參考及推薦讀物 90
第二部分 數據結構
第5章 線性表——數組描述 92
5.1 數據對象和數據結構 92
5.2 線性表數據結構 93
5.2.1 抽象數據類型linearList 94
5.2.2 抽象類linearList 94
5.3 數組描述 95
5.3.1 描述 95
5.3.2 變長一維數組 96
5.3.3 類arrayList 97
5.3.4 C++疊代器 102
5.3.5 arrayList的一個疊代器 103
5.4 vector的描述 107
5.5 在一個數組中實現的多重表 109
5.6 性能測量 111
5.7 參考及推薦讀物 112
第6章 線性表——鏈式描述 113
6.1 單向鍊表 113
6.1.1 描述 113
6.1.2 結構chainNode 114
6.1.3 類chain 115
6.1.4 抽象數據類型linearList的擴充 121
6.1.5 類extendedChain 121
6.1.6 性能測量 122
6.2 循環鍊表和頭節點 126
6.3 雙向鍊表 128
6.4 鍊表用到的辭彙表 129
6.5 套用 130
6.5.1 箱子排序 130
6.5.2 基數排序 134
6.5.3 凸包 135
6.5.4 並查集 137
第7章 數組和矩陣 146
7.1 數組 146
7.1.1 抽象數據類型 146
7.1.2 C++數組的索引 147
7.1.3 行主映射和列主映射 147
7.1.4 用數組的數組來描述 148
7.1.5 行主描述和列主描述 149
7.1.6 不規則二維數組 149
7.2 矩陣 151
7.2.1 定義和操作 151
7.2.2 類matrix 152
7.3 特殊矩陣 157
7.3.1 定義和套用 157
7.3.2 對角矩陣 158
7.3.3 三對角矩陣 159
7.3.4 三角矩陣 160
7.3.5 對稱矩陣 161
7.4 稀疏矩陣 164
7.4.1 基本概念 164
7.4.2 用單個線性表描述 165
7.4.3 用多個線性表描述 170
7.4.4 性能測量 172
第8章 棧 175
8.1 定義和套用 175
8.2 抽象數據類型 177
8.3 數組描述 178
8.3.1 作為一個派生類實現 178
8.3.2 類arrayStack 179
8.3.3 性能測量 181
8.4 鍊表描述 182
8.4.1 類derivedLinkedStack 182
8.4.2 類linkedStack 183
8.4.3 性能測量 184
8.5 套用 184
8.5.1 括弧匹配 184
8.5.2 漢諾塔 185
8.5.3 列車車廂重排 187
8.5.4 開關盒布線 191
8.5.5 離線等價類問題 193
8.5.6 迷宮老鼠 196
8.6 參考及推薦讀物 204
第9章 佇列 205
9.1 定義和套用 205
9.2 抽象數據類型 206
9.3 數組描述 207
9.3.1 描述 207
9.3.2 類arrayQueue 209
9.4 鍊表描述 212
9.5 套用 214
9.5.1 列車車廂重排 214
9.5.2 電路布線 217
9.5.3 圖元識別 219
9.5.4 工廠仿真 222
9.6 參考及推薦讀物 234
第10章 跳表和散列 235
10.1 字典 235
10.2 抽象數據類型 236
10.3 線性表描述 237
10.4 跳表表示（可選） 239
10.4.1 理想情況 239
10.4.2 插入和刪除 241
10.4.3 級的分配 241
10.4.4 結構skipNode 242
10.4.5 類skipList 242
10.4.6 skipList方法的複雜度 246
10.5 散列表描述 246
10.5.1 理想散列 246
10.5.2 散列函式和散列表 248
10.5.3 線性探查 250
10.5.4 鏈式散列 255
10.6 一個套用——文本壓縮 260
10.6.1 LZW壓縮 260
10.6.2 LZW壓縮的實現 261
10.6.3 LZW解壓縮 264
10.6.4 LZW解壓縮的實現 265
10.6.5 性能評價 268
10.7 參考及推薦讀物 269
第11章 二叉樹和其他樹 270
11.1 樹 270
11.2 二叉樹 273
11.3 二叉樹的特性 274
11.4 二叉樹的描述 275
11.4.1 數組描述 275
11.4.2 鍊表描述 276
11.5 二叉樹常用操作 277
11.6 二叉樹遍歷 277
11.7 抽象數據類型BinaryTree 281
11.8 類linkedBinaryTree 282
11.9 套用 285
11.9.1 設定信號放大器 285
11.9.2 並查集 288
11.10 參考及推薦讀物 296
第12章 優先權佇列 297
12.1 定義和套用 297
12.2 抽象數據類型 298
12.3 線性表 299
12.4 堆 299
12.4.1 定義 299
12.4.2 大根堆的插入 300
12.4.3 大根堆的刪除 301
12.4.4 大根堆的初始化 301
12.4.5 類maxHeap 302
12.4.6 堆和STL 305
12.5 左高樹 306
12.5.1 高度優先與寬度優先的最大及最小左高樹 306
12.5.2 最大HBLT的插入 308
12.5.3 最大HBLT的刪除 308
12.5.4 兩棵最大HBLT的合併 308
12.5.5 初始化 309
12.5.6 類maxHblt 310
12.6 套用 313
12.6.1 堆排序 313
12.6.2 機器調度 314
12.6.3 霍夫曼編碼 317
12.7 參考及推薦讀物 322
第13章 競賽樹 323
13.1 贏者樹和套用 323
13.2 抽象數據類型WinnerTree 326
13.3 贏者樹的實現 327
13.3.1 表示 327
13.3.2 贏者樹的初始化 328
13.3.3 重新組織比賽 328
13.3.4 類completeWinnerTree 328
13.4 輸者樹 329
13.5 套用 331
13.5.1 用最先適配法求解箱子裝載問題 331
13.5.2 用相鄰適配法求解箱子裝載問題 335
13.6 參考及推薦讀物 337
第14章 搜尋樹 338
14.1 定義 338
14.1.1 二叉搜尋樹 338
14.1.2 索引二叉搜尋樹 340
14.2 抽象數據類型 340
14.3 二叉搜尋樹的操作和實現 341
14.3.1 類binarySearchTree 341
14.3.2 搜尋 342
14.3.3 插入 342
14.3.4 刪除 343
14.3.5 二叉搜尋樹的高度 346
14.4 帶有相同關鍵字元素的二叉搜尋樹 347
14.5 索引二叉搜尋樹 348
14.6 套用 349
14.6.1 直方圖 349
14.6.2 箱子裝載問題的最優匹配法 351
14.6.3 交叉分布 353
第15章 平衡搜尋樹 359
15.1 AVL樹 360
15.1.1 定義 360
15.1.2 AVL樹的高度 361
15.1.3 AVL樹的描述 361
15.1.4 AVL搜尋樹的搜尋 361
15.1.5 AVL搜尋樹的插入 361
15.1.6 AVL搜尋樹的刪除 364
15.2 紅-黑樹 367
15.2.1 基本概念 367
15.2.2 紅-黑樹的描述 368
15.2.3 紅-黑樹的搜尋 368
15.2.4 紅-黑樹的插入 368
15.2.5 紅-黑樹的刪除 371
15.2.6 實現細節的考慮及複雜性分析 374
15.3 分裂樹 376
15.3.1 介紹 376
15.3.2 分裂樹的操作 376
15.3.3 折算複雜性 378
15.4 B-樹 379
15.4.1 索引順序訪問方法 379
15.4.2 m叉搜尋樹 380
15.4.3 m階B-樹 381
15.4.4 B-樹的高度 382
15.4.5 B-樹的搜尋 382
15.4.6 B-樹的插入 382
15.4.7 B-樹的刪除 384
15.4.8 節點結構 387
15.5 參考及推薦讀物 389
第16章 圖 390
16.1 基本概念 390
16.2 套用和更多的概念 391
16.3 特性 394
16.4 抽象數據類型graph 395
16.5 無權圖的描述 396
16.5.1 鄰接矩陣 396
16.5.2 鄰接鍊表 397
16.5.3 鄰接數組 398
16.6 加權圖的描述 400
16.7 類實現 400
16.7.1 不同的類 400
16.7.2 鄰接矩陣類 401
16.7.3 擴充chain類 405
16.7.4 鍊表類 405
16.8 圖的遍歷 407
16.8.1 廣度優先搜尋 407
16.8.2 廣度優先搜尋的實現 408
16.8.3 方法graph::bfs的複雜性分析 409
16.8.4 深度優先搜尋 410
16.8.5 深度優先搜尋的實現 411
16.8.6 方法graph::dfs的複雜性分析 412
16.9 套用 412
16.9.1 尋找一條路徑 412
16.9.2 連通圖及其構成 414
16.9.3 生成樹 415
第三部分 算法設計方法
第17章 貪婪算法 420
17.1 最最佳化問題 420
17.2 貪婪算法思想 421
17.3 套用 424
17.3.1 貨箱裝載 424
17.3.2 0/1背包問題 425
17.3.3 拓撲排序 427
17.3.4 二分覆蓋 430
17.3.5 單源最短路徑 433
17.3.6 最小成本生成樹 436
17.4 參考及推薦讀物 445
第18章 分而治之 446
18.1 算法思想 446
18.2 套用 453
18.2.1 殘缺棋盤 453
18.2.2 歸併排序 455
18.2.3 快速排序 459
18.2.4 選擇 464
18.2.5 相距最近的點對 466
18.3 解遞歸方程 474
18.4 複雜度的下限 475
18.4.1 最小最大問題的下限 476
18.4.2 排序算法的下限 477
第19章 動態規劃 479
19.1 算法思想 479
19.2 套用 481
19.2.1 0/1背包問題 481
19.2.2 矩陣乘法鏈 484
19.2.3 所有頂點對之間的最短路徑 489
19.2.4 帶有負值的單源最短路徑 492
19.2.5 網組的無交叉子集 496
19.3 參考及推薦讀物 501
第20章 回溯法 502
20.1 算法思想 502
20.2 套用 506
20.2.1 貨箱裝載 506
20.2.2 0/1背包問題 512
20.2.3 最大完備子圖 515
20.2.4 旅行商問題 517
20.2.5 電路板排列 519
第21章 分支定界 525
21.1 算法思想 525
21.2 套用 528
21.2.1 貨箱裝載 528
21.2.2 0/1背包問題 535
21.2.3 最大完備子圖 536
21.2.4 旅行商問題 538
21.2.5 電路板排列 541
