《數據結構、算法與套用：C++語言描述 》是2000年機械工業出版社出版的圖書，作者是Sartaj Sahni。該圖書在簡要回顧了基本的C++ 程式設計概念的基礎上，全面系統地介紹了佇列、堆疊、樹、圖等基本數據結構，以及貪婪算法、分而治之算法、分枝定界算法等多種算法設計方法。
基本介紹
- 書名：數據結構、算法與套用：C++語言描述
- 又名：Data Structures, Algorithms ,and Applications in C++
- ISBN：7111076451
- 頁數：535頁
- 出版社：機械工業出版社
- 出版時間：2000年1月1日
- 裝幀：平裝
- 開本：16開
- 正文語種：簡體中文
- 叢書名：計算機科學叢書
作者簡介,內容簡介,媒體評論,目錄,
作者簡介
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項。
內容簡介
《數據結構、算法與套用:C++語言描述》為數據結構與算法的繼續學習和研究奠定了一個堅實的基礎。更為可貴的是，《數據結構、算法與套用:C++語言描述》不僅僅介紹了理論知識，還提供了50多個套用實例及600多道練習題。
媒體評論
——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 操作符new9
1.3.2 一維數組9
1.3.3 異常處理10
1.3.4 操作符delete10
1.3.5 二維數組10
1.4 類13
1.4.1 類Currency13
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 異常類NoMem79
3.3.3 操作79
3.3.4 評價83
3.4 鍊表描述86
3.4.1 類ChainNode 和Chain86
3.4.2 操作88
3.4.3 擴充類Chain91
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 類Array1D131
4.1.5 類Array2D133
4.2 矩陣137
4.2.1 定義和操作137
4.2.2 類Matrix138
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 自定義Stack164
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 類SkipNode224
7.3.5 類SkipList225
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 抽象數據類型BinaryTree259
8.8 類BinaryTree260
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 類MaxHeap281
9.4 左高樹285
9.4.1 高度與寬度優先的最大及最小左高樹285
9.4.2 最大HBLT的插入287
9.4.3 最大HBLT的刪除287
9.4.4 合併兩棵最大HBLT287
9.4.5 初始化最大HBLT289
9.4.6 類MaxHBLT289
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 抽象數據類型WinnerTree306
10.3 類WinnerTree307
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和IndexedBSTree321
11.1.3 類BSTree322
11.1.4 搜尋322
11.1.5 插入323
11.1.6 刪除324
11.1.7 類DBSTree326
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和Digraph370
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 類LinkedBase381
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 類Network395
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
