本書第一版非常暢銷，第二版在第一版的基礎上增加了新內容。本書全面介紹了基本的數據結構，是高等院校“數據結構”課程的理想教材。本書作者Sartaj Sahni從簡單介紹開始，提供了直觀的討論和實際的應用，因此本書非常適合于學生閱讀。

實際應用是本書的特色。Sahni博士對所討論的每種數據結構和算法設計方法都提供了幾種應用，并采用了以下主題的例子：排序、壓縮和編碼以及圖像處理。通過將概念與應用相結合，可激發學生的學習熱情和興趣。Sahni博士是一名優秀的對稱理論和實踐信息工作者，這就體現在本書的學術概念以及培養學生的興趣上。

本書中的市場開發（market-developed）教學法補充了一些概念，并給學生提供了大量練習。書中約有1000道練習題，包括綜合和簡單的編程問題以及項目。此外，本書還有一個關聯Web站點，其中包含了書中的所有程序、動畫、示例數據、生成的輸出、某些練習的答案和帶答案的示例測試。

關于作者

Sartaj Sahni是美國佛羅里達大學的著名教授，也是計算機信息科學與工程系主任。他是歐洲科學院、IEEA、ACM、AAAS和美國明尼蘇達州超級計算機學院的成員。Sahni博士是1997年IEEE Computer Society Taylor L. Booth Education Award、2003年 IEEE Computer Society W. Wallace McDowell Award和2003年ACM Karl Karlstorm Outstanding Educator Award的獲得者。Sahni取得坎普爾印度理工學院的工科學士學位，以及美國康奈爾大學的計算機科學碩士和博士學位。Sahni已經發表了250多篇研究論文，并編著了15部書籍。他的研究出版物涉及高效算法的設計與分析、并行計算、互聯網絡、設計自動化和醫學算法。

本書由孔芳（蘇州大學）、高偉（清華同方）主譯，沈金河審校。參與翻譯工作的人員還有歐陽宇、楊中民、郭蓓、張波、謝君英、盛海燕、易磊、唐美艷、代菊容、李蕾、李秋霞、趙崗善。

譯 者

2007年1月

前言
致謝
關于本書

第1章 Java綜述 1
1.1 簡介 2
1.2 Java程序結構 2
1.2.1 獨立運行的程序和Applet 2
1.2.2 包 3
1.2.3 引入類和包 4
1.2.4 超類和子類 4
1.3 Java編譯器和虛擬機 5
1.4 文檔注釋 6
1.5 數據類型 7
1.6 方法 8
1.6.1 參數 8
1.6.2 重載方法 9
1.7 異常 10
1.7.1 拋出一個異常 10
1.7.2 處理異常 11
1.8 自定義數據類型 12
1.8.1 Currency類 12
1.8.2 Currency的數據成員 13
1.8.3 Currency的方法成員 14
1.8.4 Currency的構造函數 14
1.8.5 創建Currency的實例 15
1.8.6 Currency的存取器（獲取）方法 15
1.8.7 Currency的存取器（設置）方法 16
1.8.8 調用方法和訪問數據成員 17
1.8.9 Currency的輸出和算術方法 18
1.8.10 main方法 19
1.9 訪問修飾符 21
1.10 繼承和方法重寫 21
1.11 重訪Currency 23
1.12 定義一個異常類 25
1.13 泛型方法 26
1.13.1 Computable接口 26
1.13.2 泛型方法abc 27
1.13.3 java.lang.Comparable接口 28
1.13.4 Operable接口 28
1.13.5 Zero和CloneableObject接口 28
1.13.6 MyInteger封裝類 29
1.13.7 使用數據類型和方法作為參數 29
1.14 垃圾收集 33
1.15 遞歸 33
1.15.1 遞歸函數 33
1.15.2 歸納 34
1.15.3 遞歸方法 35
1.16 測試和調試 39
1.16.1 什么是測試 39
1.16.2 設計測試數據 41
1.16.3 調試 43
1.17 參考資料和選擇性讀物 44
第2章 性能分析 45
2.1 什么是性能 45
2.2 空間復雜度 46
2.2.1 空間復雜度的組成 46
2.2.2 范例 49
2.3 時間復雜度 51
2.3.1 時間復雜度的組成 51
2.3.2 運算計數 52
2.3.3 最佳、最差和平均運算計數 56
2.3.4 步驟計數 61
第3章 漸近表示法 73
3.1 簡介 73
3.2 漸近表示法 75
3.2.1 表示法 75
3.2.2 和Θ表示法 77
3.3 漸近數學（可選） 79
3.3.1 O表示法 79
3.3.2 表示法 81
3.3.3 Θ表示法 82
3.3.4 表示法 84
3.3.5 屬性 84
3.4 復雜度分析范例 86
3.5 實用的復雜度 89
3.6 參考資料和選擇性讀物 91
第4章 性能測量 92
4.1 簡介 92
4.2 選擇實例規模 92
4.3 開發測試數據 93
4.4 建立試驗 93
4.5 緩存管理 98
4.5.1 一個簡單的計算機模型 98
4.5.2 遺漏緩存對運行時間的影響 99
4.5.3 矩陣乘法 99
4.6 參考資料和選擇性讀物 102
第5章 線性列表——數組表示形式 103
5.1 數據對象和結構 104
5.2 線性列表數據結構 105
5.2.1 抽象數據類型LinearList 105
5.2.2 LinearList接口 105
5.2.3 LinearListAsAbstractClass抽象類 106
5.3 數組表示形式 108
5.3.1 表示形式 108
5.3.2 改變一維數組的長度 109
5.3.3 類ArrayLinearList 110
5.3.4 ArrayLinearList的Iterator 114
5.4 矢量表示形式 121
5.5 在單個數組中的多個列表 124
5.6 性能測量 126
5.7 java.util.ArrayList類 128
5.8 參考資料和選擇性讀物 129
第6章 線性列表——鏈表表示 130
6.1 單向鏈表和鏈 131
6.1.1 表示形式 131
6.1.2 ChainNode類 132
6.1.3 Chain類 133
6.1.4 對ADT LinearList的擴展 137
6.1.5 ExtendedChain類 138
6.1.6 性能測量 139
6.2 循環列表和頭節點 144
6.3 雙向鏈表 146
6.4 鏈表術語表 147
6.5 應用 148
6.5.1 箱排序 148
6.5.2 基數排序 151
6.5.3 凸包 153
第7章 線性列表——模擬指針 158
7.1 需要模擬指針 158
7.2 模擬指針 159
7.3 內存管理 160
7.3.1 SimulatedSpace1類 161
7.3.2 SimulatedSpace2類 162
7.3.3 評價模擬內存管理 162
7.4 與垃圾收集比較 163
7.5 模擬鏈 164
7.5.1 SimulatedChain類 164
7.5.2 性能測量 165
7.6 內存管理鏈 167
7.7 應用程序——并查問題 168
7.7.1 等價類 168
7.7.2 應用程序 169
7.7.3 第一個并查解決方案 171
7.7.4 第二個并查解決方案 171
第8章 數組和矩陣 175
8.1 數組 175
8.1.1 抽象數據類型 175
8.1.2 對一個Java數組進行索引 176
8.1.3 行優先和列優先的映射 176
8.1.4 數組的數組表示形式 178
8.1.5 行優先和列優先的表示形式 178
8.1.6 不規則的二維數組 179
8.2 矩陣 180
8.2.1 定義和操作 180
8.2.2 Matrix類 182
8.3 特殊矩陣 186
8.3.1 定義和應用程序 186
8.3.2 對角線矩陣 188
8.3.3 三對角線矩陣 190
8.3.4 三角形矩陣 190
8.3.5 對稱矩陣 191
8.4 稀疏矩陣 194
8.4.1 目的 194
8.4.2 使用單線性表的表示 195
8.4.3 使用多線性表的表示 202
8.4.4 性能測量 204
第9章 堆棧 208
9.1 定義和應用 208
9.2 抽象數據類型 210
9.3 數組表示 211
9.3.1 實現為子類 211
9.3.2 類arrayStack 213
9.3.3 性能測量 214
9.4 鏈式表示 217
9.4.1 類DerivedLinkedStack 217
9.4.2 類LinkedStack 217
9.4.3 性能測量 218
9.5 應用 219
9.5.1 括號匹配 219
9.5.2 漢諾塔 220
9.5.3 重排有軌電車 222
9.5.4 開關箱路由 227
9.5.5 離線等價類問題 229
9.5.6 迷宮中的老鼠 232
9.6 參考資料和選擇性讀物 241
第10章 隊列 242
10.1 定義和應用 242
10.2 抽象數據類型 243
10.3 數組表示 244
10.3.1 表示方法 244
10.3.2 ArrayQueue類 246
10.4 鏈式表示 249
10.5 應用 252
10.5.1 有軌電車的重新安排 252
10.5.2 線路路由 254
10.5.3 圖像組件編號 257
10.5.4 機械工廠模擬 260
10.6 參考資料和選擇性讀物 272
第11章 跳表和散列表 273
11.1 字典 273
11.2 抽象數據類型 275
11.3 線性表表示 276
11.4 跳表表示（可選） 278
11.4.1 理想情形 278
11.4.2 插入和刪除 279
11.4.3 分配層級 280
11.4.4 類SkipNode 280
11.4.5 類SkipList 281
11.4.6 SkipList方法的復雜度 285
11.5 散列表表示 285
11.5.1 理想散列 285
11.5.2 散列函數和散列表 287
11.5.3 線性探查法 290
11.5.4 使用鏈表的散列 295
11.6 一個應用——文本壓縮 300
11.6.1 LZW壓縮 301
11.6.2 LZW壓縮的實現 302
11.6.3 LZW解壓縮 306
11.6.4 LZW解壓縮的實現 306
11.6.5 性能評估 309
11.7 參考資料和選擇性讀物 311
第12章 二叉樹和其他樹 312
12.1 樹 312
12.2 二叉樹 315
12.3 二叉樹的屬性 316
習題 318
12.4 二叉樹的表示 318
12.4.1 基于數組的表示 318
12.4.2 鏈接表示 319
12.5 常見的二叉樹操作 320
12.6 二叉樹遍歷 320
12.7 ADT BinaryTree 325
12.8 類LinkedBinaryTree 326
12.9 應用 329
12.9.1 信號放大器的布置 329
12.9.2 并查（Union-Find）問題 334
12.10 參考資料和選擇性讀物 343
第13章 優先級隊列 344
13.1 定義和應用 344
13.2 抽象數據類型 345
13.3 線性表 346
13.4 堆 347
13.4.1 定義 347
13.4.2 插入元素到最大堆 348
13.4.3 從最大堆中刪除元素 348
13.4.4 最大堆的初始化 349
13.4.5 MaxHeap類 350
13.5 左傾樹 354
13.5.1 基于高度和基于寬度的最小
和最大左傾樹 354
13.5.2 插入到最大HBLT 356
13.5.3 從最大HBLT中刪除 356
13.5.4 合并兩棵最大HBLT 356
13.5.5 初始化 358
13.5.6 MaxHBLT類 358
13.6 應用 362
13.6.1 堆排序 362
13.6.2 機器調度 363
13.6.3 哈夫曼編碼 366
13.7 參考資料和選擇性讀物 371
第14章 比賽樹 373
14.1 優勝樹及其應用 373
14.2 抽象數據類型WinnerTree 377
14.3 優勝樹的實現 377
14.3.1 表示 377
14.3.2 初始化一棵優勝樹 378
14.3.3 重新進行比賽 378
14.3.4 類CompleteWinnerTree 378
14.4 失敗樹 379
14.5 應用 381
14.5.1 使用首次適應法的容器裝包 381
14.5.2 使用下一適應法的容器裝包 385
14.6 參考資料和選擇性讀物 388
第15章 二叉搜索樹 389
15.1 定義 390
15.1.1 二叉搜索樹 390
15.1.2 可索引二叉搜索樹 391
15.2 抽象數據類型 392
15.3 二叉搜索樹的操作及其實現 393
15.3.1 BinarySearchTree類 393
15.3.2 搜索 393
15.3.3 插入一個元素 394
15.3.4 刪除一個元素 395
15.3.5 二叉搜索樹的高度 397
15.4 有重復記錄的二叉搜索樹 399
15.5 索引的二叉搜索樹 400
15.6 應用 401
15.6.1 柱狀圖 401
15.6.2 最優容器裝包 404
15.6.3 交叉分配 406
第16章 平衡搜索樹 413
16.1 AVL樹 414
16.1.1 定義 414
16.1.2 AVL樹的高度 415
16.1.3 AVL樹的表示 415
16.1.4 AVL搜索樹的搜索 415
16.1.5 AVL搜索樹的插入 415
16.1.6 從AVL搜索樹中刪除 418
16.2 紅黑樹 421
16.2.1 定義 421
16.2.2 紅黑樹的表示 423
16.2.3 紅黑樹的搜索 423
16.2.4 紅黑樹的插入 423
16.2.5 從紅黑樹中刪除 427
16.2.6 實現的考慮和復雜度 430
16.3 伸展樹 432
16.3.1 引言 432
16.3.2 伸展操作 432
16.3.3 分攤復雜度 434
16.4 B-樹 436
16.4.1 索引順序存取法（ISAM） 436
16.4.2 m-叉搜索樹 436
16.4.3 m叉排序B-樹 438
16.4.4 B-樹的高度 439
16.4.5 搜索B-樹 439
16.4.6 插入元素到B-樹 440
16.4.7 從B-樹中刪除 442
16.4.8 節點結構 445
16.5 參考資料和選擇性讀物 446
第17章 圖 447
17.1 定義 447
17.2 應用和更多的定義 449
習題 451
17.3 屬性 452
17.4 ADT Graph 453
17.5 不帶權值的圖的表示 454
17.5.1 鄰接矩陣 455
17.5.2 鏈式鄰接表 456
17.5.3 數組鄰接表 457
17.6 帶權圖的表示形式 458
17.7 類的實現 459
17.7.1 不同的類 459
17.7.2 鄰接矩陣類 460
17.7.3 到類Chain的擴展 463
17.7.4 鏈表類 464
17.8 圖的搜索方法 466
17.8.1 廣度優先搜索 466
17.8.2 廣度優先搜索的實現 468
17.8.3 Graph.bfs的復雜度分析 468
17.8.4 深度優先搜索 470
17.8.5 深度優先搜索的實現 471
17.8.6 Graph.dfs的復雜度分析 471
17.9 重訪的應用 472
17.9.1 查找路徑 472
17.9.2 連通圖和連通分量 474
17.9.3 生成樹 476
第18章 貪婪方法 479
18.1 最優化問題 479
18.2 貪婪方法 480
18.3 應用 483
18.3.1 集裝箱裝載 483
18.3.2 0/1背包問題 485
18.3.3 拓撲排序 487
18.3.4 二分覆蓋 490
18.3.5 單源最短路徑 493
18.3.6 最小生成樹 497
18.4 參考資料和選擇性讀物 507
第19章 分而治之 508
19.1 方法 508
19.2 應用 515
19.2.1 缺陷棋盤 515
19.2.2 歸并排序 517
19.2.3 快速排序 522
19.2.4 選擇 528
19.2.5 最近頂點對 530
19.3 求解遞歸等式 538
19.4 復雜度下界 540
19.4.1 最小最大問題的下界 541
19.4.2 排序的下界 542
第20章 動態規劃 544
20.1 方法 544
20.2 應用 546
20.2.1 0/1背包問題 546
20.2.2 矩陣乘法鏈 550
20.2.3 所有對最短路徑 555
20.2.4 帶負值的單源最短路徑 558
20.2.5 不相交網子集 562
20.3 參考資料和選擇性讀物 568
第21章 回溯法 569
21.1 方法 569
21.2 應用 574
21.2.1 集裝箱裝載 574
21.2.2 0/1背包問題 581
21.2.3 最大集團 584
21.2.4 旅行售貨員 587
21.2.5 電路板排列 589
第22章 分支限界法 595
22.1 方法 595
22.2 應用 598
22.2.1 集裝箱裝載 598
22.2.2 0/1背包問題 605
22.2.3 最大集團 607
22.2.4 旅行售貨員 609
22.2.5 電路板排列 612本書涵蓋了“數據結構和算法”的核心知識，使用Java語言描述，并對每種數據結構和算法的設計提供了多個實際應用。
本書共由三部分組成。第1部分包括第1~4章，回顧了Java編程概念及分析和測量程序性能的方法。第2部分包括第5~17章，深入研究了主要的數據結構。其中，第5~7章是本書研究的主干，探討了表示數據的各種方法─?數組、鏈表和模擬指針，其余章節論及了數據結構的其他表示方法。第3部分包括第18~22章，探討了常見的算法設計方法。
本書條理清晰，內容翔實。書中的算法都有完整的Java程序，且程序結構清晰、構思精巧。本書是高等院校“數據結構”課程的理想教材，也是讀者自學數據結構的極好讀物。

1. 數據結構（Python語言描述） [曹岳輝　劉衛國　康松林　編著]
2. 數據結構——C語言（微課版） [主編 梁海英]
3. 數據結構（C語言版）習題解答及實訓指導 [李根強 謝月娥]
4. 數據結構（C語言版） [主編 李根強 劉浩 謝月娥]
5. 數據結構（Java版） [主編 李云平]
6. 數據結構 [主編 韓利凱 朱浩悅]
7. 數據結構（C語言版）（第三版） [主編 庫波 曹靜]
8. 數據結構（Java版） [孫琳 張宇]
9. 數據結構 [許繪香 段明義]
10. 數據結構（C語言描述） [李素若 陳萬華 游明坤 編著]
11. 數據結構習題解答及上機指導 [李素若 琚輝 嚴永松 編著]
12. 數據結構（C++描述）習題解答及實習指導 [李根強 謝月娥 主編]
13. 數據結構（C語言版）學習指導與習題解答 [趙堅 姜梅 主編]
14. 數據結構 [陸勤 主編 ]
15. 數據結構（C++描述） [李根強 主 編]
16. 數據結構（C++版）--習題解答及實習指導 [李根強 主編]
17. 數據結構算法--Visual C++ 6.0程序集 [侯識忠 等編著]
18. 數據結構算法--C++ Builder 6.0程序集 [侯識忠 等編著]
19. 數據結構（C語言版）學習指導與習題解答 [趙堅 姜梅 主編]
20. 數據結構（C語言版） [趙堅 姜梅 主編]
21. 數據結構（C語言描述） [斯慶巴拉 主編]
22. 數據結構（C++版）（第二版） [李根強]
23. 數據結構（C++版）（第二版）習題解答及實訓指導 [李根強]
24. 數據結構——用C語言描述 [蔡明志 編著]
25. 數據結構（C++版） [李根強 主編]
26. 數據結構--用C語言描述（第二版） [寧正元 易金聰 編著]
27. 數據結構（C語言描述） [馬秋菊 主編]
28. 數據結構（C/C++描述） [阮宏一 主編]
29. 數據結構--C語言描述（第二版） [王路群 主編]
30. 數據結構實驗程序 [智東杰 主 編]