世界著名計算機教材精選：Java軟件結構與數據結構（第3版）

《Java軟件結構與數據結構（第3版）》是著名作者John Lewis與Joseph Chase作為其一流的CSI教材「Java Software Solutions：Foundations of Program Design」的姊妹篇。儘管《Java軟件結構與數據結構（第3版）》的英文名為「Java Software Structures：Designing and Using Data Structures」，但正如作者在前言中所說的那樣，《Java軟件結構與數據結構（第3版）》其實是一本可作為「數據結構與算法」課程的教材。根據使用了前兩版的教師和學生的反饋，作者在第3版中進行了重大修改，以適應教學的需要。最重要的修改包括這樣幾個方面：
　　（1）對《Java軟件結構與數據結構（第3版）》的基本結構進行了重新設計，以使得這些內容之間的脈絡更加清晰；
　　（2）第3版把對面向對象概念的複習作為一個附錄以供參考；
　　（3）上一版給出了幾個完整的Java程序設計案例和源代碼，在第3版中進行了刪除，並把這幾個程序案例源代碼放在了網上供讀者下載。譯者認為，這不僅壓縮了不少篇幅，而且使得《Java軟件結構與數據結構（第3版）》更像是一本數據結構與算法的教材，而不是Java程序設計的教材；
　　（4）第3版擴展了對圖的討論，把「圖」與「散列」兩章的順序進行了調換，使得脈絡更清晰。本版還添加了一章來專門討論Set與Map集合。
　　總之，這些修改都是建立在使用以前版本教學的基礎上，為教師提供更多的機會和更好的靈活性來使用《Java軟件結構與數據結構（第3版）》。

第1章 概述 1
1.1 軟件質量 1
1.1.1 正確性 2
1.1.2 可靠性 2
1.1.3 健壯性 3
1.1.4 可用性 3
1.1.5 可維護性 3
1.1.6 可重用性 4
1.1.7 可移植性 4
1.1.8 運行效率 4
1.1.9 質量問題 5
1.2 數據結構 5
1.2.1 一個物理示例 5
1.2.2 以集裝箱作為對象 7
關鍵概念小結 7
自測題 8
練習題 8
自測題答案 8

第2章 算法分析 9
2.1 算法效率分析 9
2.2 增長函數與大O記法 10
2.3 增長函數的比較 12
2.4 時間複雜度分析 13
2.4.1 循環運行的複雜度分析 13
2.4.2 嵌套循環的複雜度分析 14
2.4.3 方法調用的複雜度分析 15
關鍵概念小結 16
自測題 16
練習題 17
自測題答案 17
參考文獻 18

第3章 集合 19
3.1 概述 19
3.1.1 抽象數據類型 20
3.1.2 Java集合API 21
3.2 棧集合 22
3.3 主要的面向對象概念 23
3.3.1 繼承 24
3.3.2 類層次 25
3.3.3 Object類 26
3.3.4 多態性 27
3.3.5 引用與類層次 28
3.3.6 泛型 29
3.4 棧ADT 30
接口 30
3.5 使用棧計算後綴表達式 32
3.6 異常 38
3.6.1 異常消息 39
3.6.2 try語句 39
3.6.3 異常傳播 40
3.7 用數組實現棧 41
管理容量 41
3.8 ArrayStack類 42
3.8.1 構造函數 43
3.8.2 push操作 44
3.8.3 pop操作 45
3.8.4 peek操作 46
3.8.5 其他操作 46
關鍵概念小結 46
自測題 47
練習題 48
程序設計項目 48
自測題答案 49

第4章 鏈式結構 51
4.1 鏈接作為引用 51
4.2 管理鏈表 53
4.2.1 訪問元素 53
4.2.2 插入結點 54
4.2.3 刪除結點 55
4.2.4 啞結點 55
4.3 無鏈接的元素 56
雙向鏈表 56

4.4 用鏈表實現棧 57
4.4.1 LinkedStack類 57
4.4.2 push操作 60
4.4.3 pop操作 61
4.4.4 其他操作 62
4.5 使用棧來穿越迷宮 62
4.6 java.util.Stack類實現棧 67
4.6.1 獨有的操作 68
4.6.2 繼承與實現 68
關鍵概念小結 69
自測題 69
練習題 69
程序設計項目 70
自測題答案 70

第5章 隊列 72
5.1 概述 72
5.2 使用隊列：代碼密鑰 75
5.3 使用隊列：售票口模擬 77
5.4 用鏈表實現隊列 81
5.4.1 enqueue操作 83
5.4.2 dequeue操作 84
5.4.3 其他操作 85
5.5 用數組實現隊列 85
5.5.1 enqueue操作 88
5.5.2 dequeue操作 90
5.5.3 其他操作 90
關鍵概念小結 90
自測題 91
練習題 91
程序設計項目 92
自測題答案 92

第6章 列表 94
6.1 概述 94
6.1.1 迭代器 96
6.1.2 往列表添加元素 97
6.1.3 接口與多態性 98
6.2 有序列表使用示例：聯賽主辦者 104
6.3 索引列表使用示例：Josephus問題 109

6.4 使用數組實現列表 111
6.4.1 remove操作 112
6.4.2 contains操作 114
6.4.3 iterator操作 115
6.4.4 有序列表的add操作 117
6.4.5 無序列表的特有操作 118
6.4.6 無序列表的addAfter操作 118
6.5 使用鏈表實現列表 119
6.5.1 remove操作 119
6.5.2 雙向鏈表 121
6.5.3 iterator操作 124
6.6 Java集合API中的列表 126
6.6.1 Cloneable接口 126
6.6.2 Serializable接口 127
6.6.3 RandomAccess接口 127
6.6.4 java.util.Vector接口 127
6.6.5 java.util.ArrayList接口 129
6.6.6 java.util.LinkedList接口 130
關鍵概念小結 132
自測題 133
練習題 133
程序設計項目 134
自測題答案 134

第7章 遞歸 136
7.1 遞歸地思考 136
7.1.1 無窮遞歸 137
7.1.2 數學中的遞歸 138
7.2 遞歸地編程 138
7.2.1 遞歸與迭代 140
7.2.2 直接遞歸與間接遞歸 140
7.3 使用遞歸 141
7.3.1 穿越迷宮 141
7.3.2 漢諾塔 145
7.4 遞歸算法分析 149
關鍵概念小結 150
自測題 151
練習題 151
程序設計項目 152
自測題答案 153

第8章 排序與查找 154
8.1 查找 154
8.1.1 靜態方法 155
8.1.2 泛型方法 155
8.1.3 線性查找法 156
8.1.4 二分查找法 157
8.1.5 查找算法的比較 159
8.2 排序 160
8.2.1 選擇排序法 162
8.2.2 插入排序法 164
8.2.3 冒泡排序法 165
8.2.4 快速排序法 167
8.2.5 歸併排序法 170
8.3 基數排序法 171
關鍵概念小結 175
自測題 176
練習題 176
程序設計項目 177
自測題答案 177

第9章 樹 178
9.1 概述 178
樹的分類 179
9.2 實現樹的策略 180
9.2.1 樹的數組實現之計算策略 180
9.2.2 樹的數組實現之模擬鏈接策略 181
9.2.3 樹的分析 182
9.3 樹的遍歷 182
9.3.1 前序遍歷 183
9.3.2 中序遍歷 183
9.3.3 後序遍歷 184
9.3.4 層序遍歷 184
9.4 二叉樹 185
9.5 使用二叉樹：表達式樹 188
9.6 用鏈表實現二叉樹 197
9.6.1 find方法 199
9.6.2 iteratorInOrder方法 201
9.7 用數組實現二叉樹 202
9.7.1 find方法 203
9.7.2 iteratorInOrder方法 204
關鍵概念小結 205
自測題 205
練習題 206
程序設計項目 206
自測題答案 206

第10章 二叉查找樹 208
10.1 概述 208
10.2 用鏈表實現二叉查找樹 211
10.2.1 addElement操作 211
10.2.2 removeElement操作 213
10.2.3 removeAllOccurrences操作 216
10.2.4 removeMin操作 217
10.3 用數組實現二叉查找樹 218
10.3.1 addElement操作 219
10.3.2 removeElement操作 221
10.3.3 replace操作 223
10.3.4 removeAllOccurrences操作 227
10.3.5 removeMin操作 227
10.4 用有序列表實現二叉查找樹 228
BinarySearchTreeList實現的分析 231
10.5 平衡二叉查找樹 232
10.5.1 右旋 233
10.5.2 左旋 233
10.5.3 右左旋 234
10.5.4 左右旋 234
10.6 實現二叉查找樹：AVL樹 235
10.6.1 AVL樹的右旋 235
10.6.2 AVL樹的左旋 236
10.6.3 AVL樹的右左旋 236
10.6.4 AVL樹的左右旋 236
10.7 實現二叉查找樹：紅黑樹 237
10.7.1 紅黑樹中的元素插入 237
10.7.2 紅黑樹中的元素刪除 239
10.8 實現二叉查找樹：Java集合API 241
關鍵概念小結 243
自測題 244
練習題 245
程序設計項目 245
自測題答案 246
參考文獻 247

第11章 優先隊列與堆 248
11.1 堆 248
11.1.1 addElement操作 250
11.1.2 removeMin操作 251
11.1.3 findMin操作 252
11.2 使用堆：優先級隊列 252
11.3 用鏈表實現堆 256
11.3.1 addElement操作 257
11.3.2 removeMin操作 259
11.3.3 findMin操作 261
11.4 用數組實現堆 261
11.4.1 addElement操作 262
11.4.2 removeMin操作 263
11.4.3 findMin操作 265
11.5 使用堆：堆排序 265
關鍵概念小結 266
自測題 267
練習題 267
程序設計項目 268
自測題答案 268

第12章 多路查找樹 270
12.1 整合樹的概念 270
12.2 2-3樹 270
12.2.1 往2-3樹中插入元素 271
12.2.2 從2-3樹中刪除元素 273
12.3 2-4樹 275
12.4 B樹 276
12.4.1 B*樹 277
12.4.2 B+樹 277
12.4.3 B樹的分析 278
12.5 B樹的實現策略 278
關鍵概念小結 279
自測題 279
練習題 279
程序設計項目 280
自測題答案 280
參考文獻 281


第13章 圖 282
13.1 無向圖 282
13.2 有向圖 284
13.3 網絡 285
13.4 常用的圖算法 286
13.4.1 遍歷 286
13.4.2 測試連通性 289
13.4.3 最小生成樹 290
13.4.4 判定最短路徑 293
13.5 圖的實現策略 293
13.5.1 鄰接列表 293
13.5.2 鄰接矩陣 294
13.6 用鄰接矩陣實現無向圖 295
13.6.1 addEdge方法 298
13.6.2 addVertex方法 299
13.6.3 expandCapacity方法 300
13.6.4 其他方法 300
關鍵概念小結 300
自測題 301
練習題 301
程序設計項目 302
自測題答案 302
參考文獻 303

第14章 散列 304
14.1 概述 304
14.2 散列函數 305
14.2.1 餘數法 306
14.2.2 摺疊法 306
14.2.3 平方取中法 307
14.2.4 基數轉換法 307
14.2.5 數字分析法 307
14.2.6 長度相關法 307
14.2.7 Java語言中的散列函數 308
14.3 解決衝突 308
14.3.1 鏈地址法 308
14.3.2 開放地址法 310
14.4 從散列表刪除元素 312
14.4.1 從鏈地址實現中刪除 312
14.4.2 從開放地址實現中刪除 312
14.5 Java集合API中的散列表 313
14.5.1 Hashtable類 313
14.5.2 HashSet類 314
14.5.3 HashMap類 315
14.5.4 IdentityHashMap類 316
14.5.5 WeakHashMap類 317
14.5.6 LinkedHashSet與LinkedHashMap 318
關鍵概念小結 319
自測題 319
練習題 320
程序設計項目 320
自測題答案 321

第15章 Set與Map集合 323
15.1 Set集合 323
15.2 使用Set：bingo程序 326
15.3 用數組實現Set 329
15.3.1 add操作 330
15.3.2 addAll操作 332
15.3.3 removeRandom操作 332
15.3.4 remove操作 333
15.3.5 union操作 334
15.3.6 contains操作 335
15.3.7 equals操作 336
15.3.8 其他操作 337
15.3.9 UML描述 337
15.4 用鏈表實現Set 338
15.4.1 add操作 338
15.4.2 removeRandom操作 339
15.4.3 remove操作 340
15.4.4 其他操作 341
15.5 Map集合與Java集合API 341
關鍵概念小結 342
自測題 343
練習題 343
程序設計項目 343
自測題答案 344

附錄A UML 346
A.1 統一建模語言 346
A.2 UML類圖 346
A.3 UML關係 347
關鍵概念小結 349
自測題 350
練習題 350
自測題答案 350

附錄B 面向對象設計 351
B.1 概述 351
B.2 使用對象 351
B.2.1 抽象 352
B.2.2 創建對象 353
B.3 類庫與包 354
import聲明 355
B.4 狀態與行為 355
B.5 類 356
實例數據 359
B.6 封裝 359
B.6.1 可見性修飾符 360
B.6.2 局部數據 361
B.7 構造函數 361
B.8 方法重載 362
B.9 再談引用 363
B.9.1 空引用 363
B.9.2 this引用 364
B.9.3 別名 365
B.9.4 垃圾回收 367
B.9.5 將對象作為參數傳遞 367
B.10 static修飾符 368
B.10.1 靜態變量 368
B.10.2 靜態方法 369
B.11 包裝類 369
B.12 接口 370
B.12.1 Comparable接口 371
B.12.2 Iterator接口 372
B.13 繼承 372
B.13.1 派生類 373
B.13.2 protected修飾符 375
B.13.3 super引用 375
B.13.4 重載方法 376
B.14 類的層次結構 376
B.14.1 Object類 377
B.14.2 抽象類 378
B.14.3 接口的層次結構 379
B.15 多態性 379
B.15.1 引用和類的層次結構 380
B.15.2 基於繼承的多態性 381
B.15.3 基於接口的多態性 382
B.16 泛型 384
B.17 異常 385
B.17.1 異常消息 385
B.17.2 try語句 386
B.17.3 異常傳播 387
B.17.4 異常類的層次結構 387
關鍵概念小結 388
自測題 390
練習題 390
程序設計項目 391
自測題答案 392