數據結構、算法與應用：C++語言描述

《數據結構、算法與應用：C++語言描述》在簡要回顧了基本的C++ 程序設計概念的基礎上，全面系統地介紹了隊列、堆棧、樹、圖等基本數據結構，以及貪婪算法、分而治之算法、分枝定界算法等多種算法設計方法，為數據結構與算法的繼續學習和研究奠定了一個堅實的基礎。更為可貴的是，《數據結構、算法與應用：C++語言描述》不僅僅介紹了理論知識，還提供了50多個應用實例及600多道練習題。

　　Sartaj Sahni，多年來一直從事數據結構和算法方面的研究和教育工作，具有豐富的教學經驗，曾獲得IEEE計算機協會1997年Taylor L. Booth教育獎。他撰寫了多部有關數據結構和算法方面的著作。本書是他在該領域為廣大讀者奉獻的又一力作 。
　　譯者簡介：
　　汪詩林，1968年3月生，國防科技大學計算機學院在職博士。近年來主要從事計算機軟件、數據庫、多媒體及虛擬現實等領域的教學和研究工作，獨立完成多項軟件研製任務，共發表教學和科研論文近30篇，獲部委級科技進步成果二等獎2項，三等獎4項，獲校級優秀教學成果三等獎1項。編寫及編譯教材各1部（《數字邏輯》、《最新人工智能語言——CommonLisp及CLOS的系統開發方法》）。1997年參加全國第一屆863高級技術人才培訓班。
　　王廣芳，1938年2月生，國防科技大學計算機學院教授。多年來從事計算機軟件的教學工作和科研工作，特別是數據結構、操作系統的教學與研究工作。編著出版《數據結構》、《操作系統原理與方法》、（（操作系統原理》等教材。曾獲國家級優秀教學成果一等獎1項，部委級優秀教學成果二等獎1項。參加多項有關計算機軟件的研製工作，特別是有關操作系統的研製工作，曾獲部委級科技進步一等獎2項、二等獎3項、3等獎2項。

　　「縱覽全書可以看出作者具有豐富的教材編寫經驗。它是一本新的、有關數據結構和算法的教材，適合於當前計算機本科教學的需要。」
　　——Sang W.Lee，密歇根大學
　　「注重應用不僅可以使課堂教學更生動，而且可以激勵學生投身於相關的應用。」
　　——Yu Lo C.Chang，新漢普郡大學

譯者序
前言
第一部分 預備知識
第1章 C++程序設計 1
1.1 引言 1
1.2 函數與參數 2
1.2.1 傳值參數 2
1.2.2 模板函數 3
1.2.3 引用參數 3
1.2.4 常量引用參數 4
1.2.5 返回值 4
1.2.6 遞歸函數 5

1.3 動態存儲分配 9
1.3.1 操作符new 9
1.3.2 一維數組 9
1.3.3 異常處理 10
1.3.4 操作符delete 10
1.3.5 二維數組 10

1.4 類 13
1.4.1 類Currency 13
1.4.2 使用不同的描述方法 18
1.4.3 操作符重載 20
1.4.4 引發異常 22
1.4.5 友元和保護類成員 23
1.4.6 增加#ifndef, #define和#endif語句 24

1.5 測試與調試 24
1.5.1 什麼是測試 24
1.5.2 設計測試數據 26
1.5.3 調試 28
1.6 參考及推薦讀物 29

第2章 程序性能 30
2.1 引言 30
2.2 空間複雜性 31
2.2.1 空間複雜性的組成 31
2.2.2 舉例 35

2.3 時間複雜性 37
2.3.1 時間複雜性的組成 37
2.3.2 操作計數 37
2.3.3 執行步數 44

2.4 漸進符號（O、 健?、 o） 55
2.4.1 大寫O符號 56
2.4.2 椒?58
2.4.3 符號 59
2.4.4 小寫o符號 60
2.4.5 特性 60
2.4.6 複雜性分析舉例 61
2.5 實際複雜性 66

2.6 性能測量 68
2.6.1 選擇實例的大小 69
2.6.2 設計測試數據 69
2.6.3 進行實驗 69
2.7 參考及推薦讀物 74

第二部分 數據結構
第3章 數據描述 75
3.1 引言 75
3.2 線性表 76
3.3 公式化描述 77
3.3.1 基本概念 77
3.3.2 異常類NoMem 79
3.3.3 操作 79
3.3.4 評價 83

3.4 鏈表描述 86
3.4.1 類ChainNode 和Chain 86
3.4.2 操作 88
3.4.3 擴充類Chain 91
3.4.4 鏈表遍歷器類 92
3.4.5 循環鏈表 93
3.4.6 與公式化描述方法的比較 94
3.4.7 雙向鏈表 95
3.4.8 小結 96

3.5 間接尋址 99
3.5.1 基本概念 99
3.5.2 操作 100

3.6 模擬指針 102
3.6.1 SimSpace的操作 103
3.6.2 採用模擬指針的鏈表 106
3.7 描述方法的比較 110

3.8 應用 111
3.8.1 箱子排序 111
3.8.2 基數排序 116
3.8.3 等價類 117
3.8.4 凸包 122
3.9 參考及推薦讀物 127

第4章 數組和矩陣 128
4.1 數組 128
4.1.1 抽象數據類型 128
4.1.2 C++數組 129
4.1.3 行主映射和列主映射 129
4.1.4 類Array1D 131
4.1.5 類Array2D 133

4.2 矩陣 137
4.2.1 定義和操作 137
4.2.2 類Matrix 138

4.3 特殊矩陣 141
4.3.1 定義和應用 141
4.3.2 對角矩陣 143
4.3.3 三對角矩陣 144
4.3.4 三角矩陣 145
4.3.5 對稱矩陣 146

4.4 稀疏矩陣 149
4.4.1 基本概念 149
4.4.2 數組描述 149
4.4.3 鏈表描述 154

第5章 堆棧 161
5.1 抽象數據類型 161
5.2 派生類和繼承 162
5.3 公式化描述 163
5.3.1 Stack的效率 164
5.3.2 自定義Stack 164
5.4 鏈表描述 166

5.5 應用 169
5.5.1 括號匹配 169
5.5.2 漢諾塔 170
5.5.3 火車車廂重排 172
5.5.4 開關盒布線 176
5.5.5 離線等價類問題 178
5.5.6 迷宮老鼠 180
5.6 參考及推薦讀物 188

第6章 隊列 189
6.1 抽象數據類型 189
6.2 公式化描述 190
6.3 鏈表描述 194
6.4 應用 197
6.4.1 火車車廂重排 197
6.4.2 電路布線 201
6.4.3 識別圖元 204
6.4.4 工廠仿真 206
6.5 參考及推薦讀物 217

第7章 跳錶和散列 218
7.1 字典 218
7.2 線性表描述 219
7.3 跳錶描述 222
7.3.1 理想情況 222
7.3.2 插入和刪除 223
7.3.3 級的分配 224
7.3.4 類SkipNode 224
7.3.5 類SkipList 225
7.3.6 複雜性 229

7.4 散列表描述 229
7.4.1 理想散列 229
7.4.2 線性開型尋址散列 230
7.4.3 鏈表散列 234

7.5 應用——文本壓縮 238
7.5.1 LZW壓縮 239
7.5.2 LZW壓縮的實現 239
7.5.3 LZW解壓縮 243
7.5.4 LZW解壓縮的實現 243
7.6 參考及推薦讀物 247

第8章 二叉樹和其他樹 248
8.1 樹 248
8.2 二叉樹 251
8.3 二叉樹的特性 252
8.4 二叉樹描述 253
8.4.1 公式化描述 253
8.4.2 鏈表描述 254
8.5 二叉樹常用操作 256
8.6 二叉樹遍歷 256
8.7 抽象數據類型BinaryTree 259
8.8 類BinaryTree 260

8.9 抽象數據類型及類的擴充 263
8.9.1 輸出 263
8.9.2 刪除 264
8.9.3 計算高度 264
8.9.4 統計節點數 265

8.10 應用 265
8.10.1 設置信號放大器 265
8.10.2 在線等價類 268
8.11 參考及推薦讀物 275

第9章 優先隊列 276
9.1 引言 276
9.2 線性表 277
9.3 堆 278
9.3.1 定義 278
9.3.2 最大堆的插入 279
9.3.3 最大堆的刪除 279
9.3.4 最大堆的初始化 280
9.3.5 類MaxHeap 281

9.4 左高樹 285
9.4.1 高度與寬度優先的最大及最小左高樹 285
9.4.2 最大HBLT的插入 287
9.4.3 最大HBLT的刪除 287
9.4.4 合併兩棵最大HBLT 287
9.4.5 初始化最大HBLT 289
9.4.6 類MaxHBLT 289

9.5 應用 293
9.5.1 堆排序 293
9.5.2 機器調度 294
9.5.3 霍夫曼編碼 297
9.6 參考及推薦讀物 302

第10章 競賽樹 303
10.1 引言 303
10.2 抽象數據類型WinnerTree 306
10.3 類WinnerTree 307
10.3.1 定義 307
10.3.2 類定義 307
10.3.3 構造函數、析構函數及Winner函數 308
10.3.4 初始化贏者樹 308
10.3.5 重新組織比賽 310
10.4 輸者樹 311

10.5 應用 312
10.5.1 用最先匹配法求解箱子裝載問題 312
10.5.2 用相鄰匹配法求解箱子裝載問題 316

第11章 搜索樹 319
11.1 二叉搜索樹 320
11.1.1 基本概念 320
11.1.2 抽象數據類型BSTree和IndexedBSTree 321
11.1.3 類BSTree 322
11.1.4 搜索 322
11.1.5 插入 323
11.1.6 刪除 324
11.1.7 類DBSTree 326
11.1.8 二叉搜索樹的高度 327

11.2 AVL樹 328
11.2.1 基本概念 328
11.2.2 AVL樹的高度 328
11.2.3 AVL樹的描述 329
11.2.4 AVL搜索樹的搜索 329
11.2.5 AVL搜索樹的插入 329
11.2.6 AVL搜索樹的刪除 332

11.3 紅－黑樹 334
11.3.1 基本概念 334
11.3.2 紅－黑樹的描述 336
11.3.3 紅－黑樹的搜索 336
11.3.4 紅－黑樹的插入 336
11.3.5 紅－黑樹的刪除 339
11.3.6 實現細節的考慮及複雜性分析 343

11.4 B－樹 344
11.4.1 索引順序訪問方法 344
11.4.2 m 叉搜索樹 345
11.4.3 m 序B－樹 346
11.4.4 B－樹的高度 347
11.4.5 B－樹的搜索 348
11.4.6 B－樹的插入 348
11.4.7 B－樹的刪除 350
11.4.8 節點結構 353

11.5 應用 354
11.5.1 直方圖 354
11.5.2 用最優匹配法求解箱子裝載問題 357
11.5.3 交叉分佈 359
11.6 參考及推薦讀物 363

第12章 圖 365
12.1 基本概念 365
12.2 應用 366
12.3 特性 368
12.4 抽象數據類型Graph和Digraph 370
12.5 無向圖和有向圖的描述 371
12.5.1 鄰接矩陣 371
12.5.2 鄰接壓縮表 373
12.5.3 鄰接鏈表 374
12.6 網絡描述 375

12.7 類定義 376
12.7.1 不同的類 376
12.7.2 鄰接矩陣類 377
12.7.3 擴充Chain類 380
12.7.4 類LinkedBase 381
12.7.5 鏈接類 382

12.8 圖的遍歷 386
12.8.1 基本概念 386
12.8.2 鄰接矩陣的遍歷函數 387
12.8.3 鄰接鏈表的遍歷函數 388

12.9 語言特性 389
12.9.1 虛函數和多態性 389
12.9.2 純虛函數和抽象類 391
12.9.3 虛基類 391
12.9.4 抽象類和抽象數據類型 393

12.10 圖的搜索算法 394
12.10.1 寬度優先搜索 394
12.10.2 類Network 395
12.10.3 BFS的實現 395
12.10.4 BFS的複雜性分析 396
12.10.5 深度優先搜索 397

12.11 應用 399
12.11.1 尋找路徑 399
12.11.2 連通圖及其構件 400
12.11.3 生成樹 402

第三部分 算法設計方法
第13章 貪婪算法 405
13.1 最優化問題 405
13.2 算法思想 406
13.3 應用 409
13.3.1 貨箱裝船 409
13.3.2 0/1背包問題 410
13.3.3 拓撲排序 412
13.3.4 二分覆蓋 415
13.3.5 單源最短路徑 421
13.3.6 最小耗費生成樹 424
13.4 參考及推薦讀物 433

第14章 分而治之算法 434
14.1 算法思想 434
14.2 應用 440
14.2.1 殘缺棋盤 440
14.2.2 歸併排序 443
14.2.3 快速排序 447
14.2.4 選擇 452
14.2.5 距離最近的點對 454
14.3 解遞歸方程 462

14.4 複雜性的下限 463
14.4.1 最小最大問題的下限 464
14.4.2 排序算法的下限 465

第15章 動態規劃 467
15.1 算法思想 467
15.2 應用 469
15.2.1 0/1背包問題 469
15.2.2 圖像壓縮 471
15.2.3 矩陣乘法鏈 476
15.2.4 最短路徑 480
15.2.5 網絡的無交叉子集 483
15.2.6 元件摺疊 486
15.3 參考及推薦讀物 491

第16章 回溯 492
16.1 算法思想 492
16.2 應用 496
16.2.1 貨箱裝船 496
16.2.2 0/1背包問題 503
16.2.3 最大完備子圖 506
16.2.4 旅行商問題 508
16.2.5 電路板排列 510

第17章 分枝定界 516
17.1 算法思想 516
17.2 應用 519
17.2.1 貨箱裝船 519
17.2.2 0/1背包問題 526
17.2.3 最大完備子圖 528
17.2.4 旅行商問題 529
17.2.5 電路板排列 532