內容簡介
《Java程式設計與數據結構》本書在介紹如何開發面向對象程式的同時，還著重講解了標準數據結構的主題。作者首先介紹了Java中需要特別掌握的部分，然後討論了程式設計中類、繼承、多態性、遞歸和複雜度分析等概念。本書還講述了標準的抽象數據類型(ADT):棧、列表、樹、表和圖等，包括了對不同實現和複雜度以及ADT套用的討論。最後一章介紹了執行緒和同步技術，為學生轉向計算機科學的高級課程作了鋪墊。另外，作者還採用大量的案例分析貫穿全書始終，突出了軟體的生命周期。
圖書目錄
第1章 概述 1
1.1 集合 1
1.1.1 集合的分類 1
1.1.2 關於集合的操作 2
1.2 抽象數據類型 3
1.3 算法分析 4
1.3.1 簡單性和清晰度 4
1.3.2 空間效率 4
1.3.3 時間效率 4
1.4 算法類型 5
1.4.1 貪婪算法 6
1.4.2 分治算法 6
1.4.3 回溯算法 6
1.5 軟體開發過程 7
1.5.1 複雜性 7
1.5.2 脆弱性 7
1.5.3 可擴展性 8
1.5.4 互連性 8
1.6 面向對象程式設計簡介 8
1.6.1 過程式程式設計 8
1.6.2 函式式程式設計 8
1.6.3 面向對象程式設計(OOP) 9
1.6.4 面向對象程式設計的直觀概括 9
1.7 軟體開發生命周期 10
1.8 本書的軟體開發方法 11
1.8.1 需求 12
1.8.2 分析 12
1.8.3 設計 12
1.8.4 實現 12
1.9 分析和設計階段的測試 12
1.10 測試代碼 13
1.10.1 單元、集成和驗收測試 13
1.10.2 測試內容 13
1.10.3 如何設計測試數據 14
1.11 正確性的證明 15
1.12 軟體開發過程的其他方面 15
1.12.1 編碼約定 15
1.12.2 前置條件和後置條件 16
1.13 層次系統的開發 17
第2章 面向對象程式設計和基本的
輸入輸出功能 20
2.1 簡介 20
2.2 類和對象 21
2.2.1 示例：字元串對象 21
2.2.2 示例：終端輸出 22
2.2.3 對象、類和計算機記憶體 22
2.2.4 對象的3個特徵 23
2.2.5 客戶端和伺服器 23
2.3 Employee類 23
2.3.1 用戶需求 23
2.3.2 類模板的結構 26
2.3.3 Employee類的設計和實現 27
2.3.4 構造函式和異常 28
2.3.5 this的使用 30
2.3.6 取值方法、賦值方法和
toString方法 30
2.3.7 測試等同性 32
2.3.8 比較及接口Comparable 33
2.3.9 複製對象及接口Cloneable 34
2.3.10 對象序列化 35
2.3.11 finalize和dispose方法 36
2.3.12 使用對象時一些有用的提示 37
2.4 繼承和多態 37
2.5 實現一個簡單的圖形層次結構 38
2.5.1 實現Shape類 38
2.5.2 實現Circle類 39
2.5.3 構造函式和super保留字 40
2.5.4 其他方法和super保留字 41
2.5.5 實現Rectangle類 41
2.5.6 保護型(protected)變數和方法 42
2.5.7 實現、擴展、重寫和終結 43
2.6 圖形類的使用 43
2.6.1 查找合適的方法 44
2.6.2 圖形數組 45
2.7 將圖形作為參數和返回值 47
2.7.1 示例：輸入Retangle，
輸出Circle 47
2.7.2 示例：輸入任意圖形，
輸出Circle 48
2.7.3 示例：輸入任意圖形，
輸出任意圖形 48
2.8 面向對象系統的分解 49
2.8.1 確定類 50
2.8.2 分配職責 51
2.8.3 確定數據屬性 51
2.8.4 確定方法 52
2.8.5 類和對象模型之間的關係 52
2.9 基於字元的流輸入、輸出 53
2.9.1 介紹鍵盤讀取器 54
2.9.2 擴展鍵盤讀取器 56
2.9.3 檔案讀取器 57
2.9.4 格式化輸出 59
2.9.5 使用支持類 62
第3章 基於GUI的Java應用程式 64
3.1 模型-視圖-控制器模式 64
3.2 溫度轉換程式的代碼 65
3.2.1 模型 65
3.2.2 視圖 66
3.2.3 控制器 67
3.2.4 視圖和控制器的完整代碼 68
3.3 GridBagLayout類 70
3.4 EasyGridLayout類 72
3.5 IntegerField類和DoubleField類 74
3.6 彈出式訊息 75
3.7 其他視窗組件 77
3.7.1 選單和文本區 78
3.7.2 複選框和單選按鈕 80
3.7.3 列表框 83
3.8 模式對話框的使用 88
3.9 多視窗應用程式 93
3.10 偵聽器共享 96
3.11 方法一覽表 98
第4章 複雜度 107
4.1 衡量算法的效率 107
4.1.1 測量算法的執行時間 107
4.1.2 對指令計數 109
4.1.3 用代數方法推導增長率 111
4.1.4 測量算法使用的記憶體 112
4.2 比較增長率 112
4.2.1 使用代數方法比較增長率 112
4.2.2 大O表示法 114
4.2.3 最佳、最差和平均性能 115
4.3 查找算法 116
4.3.1 數組的線性查找法 116
4.3.2 數組的二分查找法 117
4.4 排序算法 119
4.4.1 選擇排序 119
4.4.2 冒泡排序 120
4.4.3 插入排序 121
4.5 案例分析：記錄運行時間
以及對指令計數 122
4.5.1 要求 122
4.5.2 分析 123
4.5.3 Algorithms類的設計 123
4.5.4 Algorithms類的實現 123
4.5.5 AlgorithmProfiler類的
設計和實現 125
第5章 數組和鍊表 130
5.1 數組的特性 130
5.1.1 隨機訪問和連續地址記憶體 130
5.1.2 靜態記憶體和動態記憶體 131
5.1.3 物理大小和邏輯大小 132
5.2 數組操作 133
5.2.1 增加數組的大小 133
5.2.2 減小數組大小 134
5.2.3 向數組中插入數據項 134
5.2.4 從數組中移除數據項 135
5.2.5 數組方法的測試程式 136
5.2.6 複雜度的權衡：查找和
修改數組 136
5.3 鍊表 137
5.3.1 單鍊表和雙向鍊表 137
5.3.2 不連續地址記憶體和節點 138
5.3.3 定義單鏈節點類 139
5.3.4 使用單鏈節點類 140
5.4 單鍊表的操作 142
5.4.1 遍歷 142
5.4.2 查找(對象或第i項) 143
5.4.3 替換(對象或第i項) 144
5.4.4 在首端插入 144
5.4.5 在尾端插入 145
5.4.6 在首端移除 146
5.4.7 在尾端移除 147
5.4.8 插入(對象或第i項) 148
5.4.9 移除(對象或第i項) 149
5.4.10 複雜度的權衡：時間、
空間和單鍊表 150
5.5 鍊表的各種變體 150
5.5.1 帶有虛頭節點的循環鍊表 150
5.5.2 雙向鍊表 151
第6章 集合概述 155
6.1 簡介 155
6.1.1 本書中集合的概述 156
6.1.2 Tiny集合 158
6.2 多種實現 158
6.3 集合和強制類型轉換 159
6.4 集合和串列化 161
6.5 疊代器 162
6.5.1 疊代器的使用 162
6.5.2 實現Tiny和iterator方法 163
6.6 集合和集合視圖 166
6.6.1 兩個例子 167
6.6.2 Collection接口中的方法 168
6.6.3 collectionView方法的
實現(可選內容) 169
6.6.4 AbstractCollection
實現(可選內容) 170
6.7 集合的原型和專門版本 172
6.7.1 Tiny專門版本的概述
(可選內容) 172
6.7.2 Tiny接口的擴展(可選內容) 173
6.7.3 將Tiny方法分配給類
(可選內容) 174
6.7.4 編寫代碼的細節(可選內容) 175
6.8 本章嚮導 179
第7章 棧 182
7.1 棧概述 182
7.2 棧原型 183
7.3 棧的使用 184
7.4 棧原型的實現 186
7.4.1 數組實現 186
7.4.2 鍊表實現 188
7.4.3 兩個實現的時間和空間分析 191
7.5 棧的3個套用 192
7.5.1 算術表達式求值 192
7.5.2 回溯算法 195
7.5.3 記憶體管理 196
7.6 專門版本的接口 200
7.7 專門版本的實現 201
7.8 案例分析：後綴表達式求值 204
7.8.1 要求 204
7.8.2 分析 205
7.8.3 設計 207
7.8.4 實現 210
第8章 佇列 216
8.1 佇列概述 216
8.2 佇列的原型 217
8.3 佇列原型的實現 219
8.3.1 鍊表實現 219
8.3.2 數組實現 220
8.3.3 兩種實現的時間和空間分析 222
8.4 佇列的兩個套用 223
8.4.1 模擬 223
8.4.2 CPU循環調度 224
8.5 專門版本的接口 225
8.6 專門版本的實現 226
8.7 案例分析1：模擬超市
結賬流程 228
8.7.1 要求 228
8.7.2 分析 228
8.7.3 總體設計 230
8.7.4 MarketModel類的設計 230
8.7.5 MarketModel類的實現 231
8.7.6 Cashier類的設計 232
8.7.7 Cashier類的實現 233
8.7.8 Customer類的設計 234
8.7.9 Customer類的實現 234
8.8 優先佇列 236
8.9 案例分析2：急診室調度 237
8.9.1 要求 237
8.9.2 分析 237
8.9.3 推薦界面 238
第9章 列表 240
9.1 列表概述 240
9.2 列表原型 241
9.3 列表的使用 244
9.4 列表原型的實現 247
9.4.1 靜態數組實現 247
9.4.2 雙向鍊表實現 250
9.4.3 兩種實現的時間和空間分析 256
9.5 列表的3個套用 258
9.5.1 堆存儲管理 258
9.5.2 對磁碟檔案的組織 259
9.5.3 其他ADT實現 260
9.6 專門版本的接口 261
9.7 專門版本的實現 263
9.8 案例分析：維護任務列表
(to-do列表) 267
9.8.1 要求 268
9.8.2 分析 268
9.8.3 設計 269
9.8.4 實現 270
第10章 遞歸、查找、排序和回溯 279
10.1 遞歸概述 279
10.1.1 實現遞歸 280
10.1.2 跟蹤遞歸調用 281
10.1.3 編寫遞歸方法的準則 282
10.1.4 遞歸方法的運行支持 283
10.1.5 兩種遞歸方法的分析 284
10.1.6 兩種遞歸方法的空間分析 286
10.2 遞歸和查找 287
10.2.1 數組的線性查找 287
10.2.2 數組的二分查找 288
10.3 遞歸和排序 290
10.3.1 快速排序 291
10.3.2 歸併排序 295
10.4 遞歸和回溯 299
10.5 採用遞歸的理由 301
10.5.1 消除遞歸 302
10.5.2 尾遞歸 303
10.6 案例分析1：迷宮解決方案 304
10.6.1 要求 304
10.6.2 分析 304
10.6.3 類 306
10.6.4 MazeView的實現 306
10.6.5 MazeModel的實現 308
10.7 遞歸下降及其程式語言 310
10.7.1 語法介紹 310
10.7.2 識別、解析和解釋語言
中的語句 312
10.7.3 辭彙分析和掃描器 312
10.7.4 解析策略 313
10.8 案例分析2：遞歸下降解析器 313
10.8.1 要求 313
10.8.2 分析 314
10.8.3 推薦的用戶界面 314
10.8.4 Parser的實現 315
第11章 樹 319
11.1 樹的概述 319
11.1.1 樹的討論 321
11.1.2 普通樹和二叉樹的
正式定義 322
11.2 樹的表示 322
11.2.1 鍊表表示 322
11.2.2 完全二叉樹的數組表示 324
11.3 二叉樹的操作 325
11.3.1 二叉樹的原型 326
11.3.2 BinaryTreePT的測試程式 328
11.3.3 BinaryTreePT類的實現 330
11.4 案例分析1：解析表達式樹 335
11.4.1 要求 335
11.4.2 用戶界面 336
11.4.3 ExpressionTree類的
分析和設計 336
11.4.4 Parser類的分析、
設計和實現 337
11.5 普通樹操作 339
11.5.1 樹的接口 339
11.5.2 TreeIterator接口 342
11.6 普通樹類的實現(可選內容) 345
11.6.1 實現中的類職責 345
11.6.2 AbstractTree類的
設計和實現 346
11.6.3 LinkedTree類的
設計和實現 349
11.6.4 樹疊代器的設計和實現 351
11.7 案例分析2：技能資料庫 353
11.7.1 要求 353
11.7.2 分析 354
11.7.3 模型類的設計和實現 355
11.7.4 視圖類的設計和實現 358
第12章 特殊樹 361
12.1 堆 361
12.1.1 二叉樹的形狀 361
12.1.2 可比對象 362
12.1.3 Heap接口 362
12.1.4 Heap實現 363
12.1.5 堆排序的實現 364
12.1.6 add方法和pop方法
的實現 365
12.1.7 分析堆排序 367
12.1.8 疊代器的實現 367
12.1.9 使用堆實現優先佇列 368
12.2 二叉搜尋樹 372
12.2.1 排序集合抽象數據
類型及其接口 372
12.2.2 排序集合抽象數據
類型的實現 373
12.2.3 二分查找 374
12.2.4 二叉搜尋樹的實現 375
12.2.5 分析二叉搜尋樹 378
12.3 “更好的”二叉搜尋樹
(可選內容) 379
12.3.1 2-3樹 379
12.3.2 AVL樹 380
第13章 無序集合：集、映射和包 385
13.1 集、映射和包概述 385
13.1.1 集 385
13.1.2 映射 386
13.1.3 包 387
13.1.4 無序集合的疊代器 387
13.1.5 一個簡短的例子 387
13.2 實現的考慮事項 389
13.2.1 散列 389
13.2.2 散列鍊表方法的分析 390
13.2.3 其他散列策略 390
13.3 映射原型類 391
13.3.1 HashMapPT類的接口 391
13.3.2 HashMapPT類的設計 392
13.4 集原型類 396
13.4.1 HashSetPT類的接口 396
13.4.2 設計和實現 397
13.5 包原型類 399
13.5.1 HashBagPT類的接口 399
13.5.2 設計和實現 400
13.6 Java集合框架中的Map類
和Set類 401
13.6.1 映射 401
13.6.2 Set接口 404
13.7 將Bag ADT添加到集合框架 405
13.7.1 Bag接口 405
13.7.2 Bag實現 406
13.8 案例分析1：檔案索引系統 409
13.8.1 要求 409
13.8.2 分析 409
13.8.3 設計和實現 410
13.9 案例分析2：信貸批准系統 417
13.9.1 要求 417
13.9.2 分析 417
13.9.3 類 417
13.9.4 設計和實現 418
第14章 圖 426
14.1 概述 426
14.2 術語 427
14.3 圖的表示 429
14.3.1 鄰接矩陣 429
14.3.2 鄰接表 430
14.3.3 兩種表示的分析 431
14.3.4 運行時間的進一步分析 431
14.4 圖的遍歷 432
14.4.1 連通圖的一般遍歷算法 432
14.4.2 深度優先遍歷和廣度
優先遍歷 432
14.4.3 圖的分量 434
14.5 圖中的樹 435
14.5.1 生成樹和生成森林 435
14.5.2 最小生成樹 435
14.5.3 最小生成樹算法 435
14.6 拓撲排序 437
14.7 最短路徑問題 438
14.7.1 Dijkstra算法 438
14.7.2 初始化 439
14.7.3 計算 439
14.7.4 分析 440
14.8 圖原型 440
14.8.1 使用圖原型的例子 440
14.8.2 LinkedGraphPT類 441
14.8.3 LinkedVertexPT類 448
14.8.4 LinkedEdgePT類 451
14.9 一個專門的圖實現(可選內容) 453
14.9.1 Graph接口 454
14.9.2 權值 456
14.9.3 實現 457
14.9.4 關於性能的提示 460
14.10 案例分析：測試圖的算法 461
14.10.1 要求 461
14.10.2 分析 461
14.10.3 GraphDemoView類 461
14.10.4 GraphDemoModel類 466
第15章 多執行緒、網路和客戶端
/伺服器編程 470
15.1 執行緒和進程 470
15.1.1 執行緒 471
15.1.2 休眠執行緒 472
15.1.3 生產者、消費者和同步 474
15.2 網路、伺服器和客戶端 479
15.2.1 IP位址 479
15.2.2 連線埠、伺服器和客戶端 481
15.2.3 套接字和一個日期/時間
客戶端程式 481
15.2.4 伺服器套接字和一個
日期/時間伺服器端程式 483
15.2.5 客戶端和伺服器端之間
的雙向會話 485
15.2.6 使伺服器處理多個客戶端 485
15.2.7 使用伺服器守護進程 486
15.2.8 使用客戶端處理器 489
15.2.9 模型-視圖-控制器模式 491
15.3 案例分析：校園電話目錄 491
15.3.1 要求 491
15.3.2 分析 492
15.3.3 設計 493
15.3.4 實現 493
附錄A Java語言特性回顧 499
A.1 保留字 499
A.2 數據類型 499
A.3 變數、作用域和生命周期 501
A.4 表達式 502
A.5 控制語句 503
A.5.1 複合語句 503
A.5.2 if和if-else語句 503
A.5.3 while和do-while語句 504
A.5.4 for語句 504
A.5.5 switch語句 504
A.6 混合模式運算和強制類型轉換 505
A.7 字元串 505
A.8 數組 507
A.9 方法和參數 508
A.10 引用類型 509
A.11 包裝器類 510
A.12 類 510
A.13 接口 510
A.14 適配器 511
A.15 異常 511
A.16 程式包 512
A.17 文本檔案 513
附錄B 層次結構、接口及類 516
B.1 層次結構 516
B.2 接口 516
B.3 類 516
附錄C 安裝指令 518
C.1 使用JDK 518
C.2 使用JGrasp 519
術語表 520
