數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用（Java語言描述）

本書第一版非常暢銷，第二版在第一版的基礎(chǔ)上增加了新內(nèi)容。本書全面介紹了基本的數(shù)據(jù)結(jié)構(gòu)，是高等院校“數(shù)據(jù)結(jié)構(gòu)”課程的理想教材。本書作者Sartaj Sahni從簡單介紹開始，提供了直觀的討論和實(shí)際的應(yīng)用，因此本書非常適合于學(xué)生閱讀。

實(shí)際應(yīng)用是本書的特色。Sahni博士對所討論的每種數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)方法都提供了幾種應(yīng)用，并采用了以下主題的例子：排序、壓縮和編碼以及圖像處理。通過將概念與應(yīng)用相結(jié)合，可激發(fā)學(xué)生的學(xué)習(xí)熱情和興趣。Sahni博士是一名優(yōu)秀的對稱理論和實(shí)踐信息工作者，這就體現(xiàn)在本書的學(xué)術(shù)概念以及培養(yǎng)學(xué)生的興趣上。

本書中的市場開發(fā)（market-developed）教學(xué)法補(bǔ)充了一些概念，并給學(xué)生提供了大量練習(xí)。書中約有1000道練習(xí)題，包括綜合和簡單的編程問題以及項(xiàng)目。此外，本書還有一個(gè)關(guān)聯(lián)Web站點(diǎn)，其中包含了書中的所有程序、動畫、示例數(shù)據(jù)、生成的輸出、某些練習(xí)的答案和帶答案的示例測試。

關(guān)于作者

Sartaj Sahni是美國佛羅里達(dá)大學(xué)的著名教授，也是計(jì)算機(jī)信息科學(xué)與工程系主任。他是歐洲科學(xué)院、IEEA、ACM、AAAS和美國明尼蘇達(dá)州超級計(jì)算機(jī)學(xué)院的成員。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取得坎普爾印度理工學(xué)院的工科學(xué)士學(xué)位，以及美國康奈爾大學(xué)的計(jì)算機(jī)科學(xué)碩士和博士學(xué)位。Sahni已經(jīng)發(fā)表了250多篇研究論文，并編著了15部書籍。他的研究出版物涉及高效算法的設(shè)計(jì)與分析、并行計(jì)算、互聯(lián)網(wǎng)絡(luò)、設(shè)計(jì)自動化和醫(yī)學(xué)算法。

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

譯 者

2007年1月

前言
致謝
關(guān)于本書

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

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