Java 語言程序設計 (進階篇), 12/e (Introduction to Java Programming and Data Structures, Comprehensive Version, 12/e)

戴開宇

復旦大學軟件學院教師，工程碩士導師。
中國計算機學會會員。
博士畢業於上海交通大學計算機應用專業，2011～2012年在美國佛羅里達大學作訪問學者。
承擔多門本科專業課程、通識教育課程以及工程碩士課程，
這些課程被評為校精品課程，上海市重點建設課程，IBM-教育部精品課程等。

中文版序
譯者序
前言
第19章 泛型 1
19.1 引言 1
19.2 動機和優點 1
19.3 定義泛型類和接口 4
19.4 泛型方法 5
19.5 示例學習：對一個對像數組進行排序 7
19.6 原生類型和向後兼容 8
19.7 通配泛型 10
19.8 泛型的擦除和限制 12
19.9 示例學習：泛型矩陣類 15
關鍵術語 19
本章小結 19
測試題 20
編程練習題 20

第20章 線性表、棧、隊列和優先隊列 22
20.1 引言 22
20.2 集合 23
20.3 迭代器 26
20.4 使用forEach方法 27
20.5 線性表 28
20.5.1 List接口中的通用方法 28
20.5.2 ArrayList和LinkedList類 30
20.6 Comparator接口 32
20.7 用於線性表和集合的靜態方法 36
20.8 示例學習：彈球 40
20.9 向量類和棧類 43
20.10 隊列和優先隊列 44
20.10.1 Queue接口 44
20.10.2 雙端隊列Deque和鍊錶LinkedList 45
20.11 示例學習：表達式求值 47
關鍵術語 51
本章小結 51
測試題 52
編程練習題 52

第21章 規則集和映射 57
21.1 引言 57
21.2 規則集 57
21.2.1 HashSet 58
21.2.2 LinkedHashSet 61
21.2.3 TreeSet 62
21.3 比較規則集和線性表的性能 65
21.4 示例學習：關鍵字計數 67
21.5 映射 69
21.6 示例學習：單詞的出現次數 73
21.7 單例與不可變的集合和映射 75
關鍵術語 76
本章小結 76
測試題 77
編程練習題 77

第22章 開發高效算法 79
22.1 引言 79
22.2 使用大O表示法來衡量算法效率 79
22.3 示例：確定大O 81
22.4 分析算法的時間複雜度 85
22.4.1 分析二分查找算法 85
22.4.2 分析選擇排序算法 85
22.4.3 分析漢諾塔問題 85
22.4.4 常用的遞推關係 86
22.4.5 比較常用的增長函數 86
22.5 使用動態編程求斐波那契數 87
22.6 使用歐幾里得算法求公約數 89
22.7 求素數的高效算法 93
22.8 使用分治法尋找最近點對 98
22.9 使用回溯法解決八皇后問題 101
22.10 計算幾何：尋找凸包 103
22.10.1 卷包裹算法 104
22.10.2 格雷厄姆算法 105
22.11 字符串匹配 106
22.11.1 暴力算法 106
22.11.2 Boyer-Moore算法 107
22.11.3 Knuth-Morris-Pratt算法 109
關鍵術語112
本章小結 112
測試題 113
編
程練習題 113
第23章 排序 120
23.1 引言 120
23.2 插入排序 121
23.3 冒泡排序123
23.4 歸併排序 125
23.5 快速排序 128
23.6 堆排序 132
23.6.1 堆的存儲 133
23.6.2 添加一個新結點 133
23.6.3 刪除根結點 134
23.6.4 Heap類 135
23.6.5 使用Heap類進行排序 137
23.6.6 堆排序的時間複雜度 138
23.7 桶排序和基數排序 139
23.8 外部排序 141
23.8.1 實現階段Ⅰ 143
23.8.2 實現階段Ⅱ 143
23.8.3 結合兩個階段 145
23.8.4 外部排序複雜度 148
關鍵術語 148
本章小結 148
測試題 149
編程練習題 149

第24章 實現線性表、棧、隊列和優先隊列 153
24.1 引言 153
24.2 線性表的通用操作 153
24.3 數組線性表 156
24.4 鍊錶 163
24.4.1 結點 163
24.4.2 MyLinkedList類 165
24.4.3 實現MyLinkedList 166
24.4.4 MyArrayList和MyLinkedList 174
24.4.5 鍊錶的變體 174
24.5 棧和隊列 176
24.6 優先隊列 179
本章小結 180
測試題 181
編程練習題 181

第25章 二叉搜索樹 183
25.1 引言 183
25.2 二叉搜索樹基礎 183
25.3 表示二叉搜索樹 184
25.4 查找一個元素 185
25.5 在BST中插入一個元素 185
25.6 樹的遍歷 187
25.7 BST類 188
25.8 刪除BST中的一個元素 197
25.9 樹的可視化和MVC 202
25.10 迭代器 205
25.11 示例學習：數據壓縮 207
關鍵術語 211
本章小結 211
測試題 212
編程練習題 212

第26章 AVL樹 216
26.1 引言 216
26.2 重新平衡樹 217
26.3 為AVL樹設計類 219
26.4 重寫insert方法 220
26.5 實現旋轉 221
26.6 實現delete方法 221
26.7 AVLTree類 222
26.8 測試 AVLTree類 227
26.9 AVL樹的時間複雜度分析 230
關鍵術語 231
本章小結 231
測試題 231
編程練習題 231

第27章 散列 233
27.1 引言 233
27.2 什麼是散列 233
27.3 散列函數和散列碼 234
27.3.1 基本數據類型的散列碼 234
27.3.2 字符串的散列碼 235
27.3.3 壓縮散列碼 235
27.4 使用開放地址法處理衝突 236
27.4.1 線性探測法 236
27.4.2 二次探測法 237
27.4.3 雙重散列法 238
27.5 使用分離***法處理衝突 240
27.6 裝填因子和再散列 241
27.7 使用散列實現映射 242
27.8 使用散列實現規則集 250
關鍵術語 256
本章小結 257
測試題 257
編程練習題 257

第28章 圖及其應用 259
28.1 引言 259
28.2 基本的圖術語 260
28.3 表示圖 262
28.3.1 表示頂點 262
28.3.2 表示邊：邊數組 263
28.3.3 表示邊：Edge對象 264
28.3.4 表示邊：鄰接矩陣 264
28.3.5 表示邊：鄰接線性表 265
28.4 圖的建模 267
28.5 圖的可視化 276
28.6 圖的遍歷 279
28.7 深度優先搜索 280
28.7.1 DFS算法 280
28.7.2 DFS的實現 281
28.7.3 DFS的應用 283
28.8 示例學習：連通圓問題 283
28.9 廣度優先搜索 285
28.9.1 BFS算法 286
28.9.2 BFS的實現 286
28.9.3 BFS的應用 288
28.10 示例學習：9枚硬幣反面問題 288
關鍵術語 294
本章小結 294
測試題 294
編程練習題 294

第29章 加權圖及其應用 299
29.1 引言 299
29.2 加權圖的表示 300
29.2.1 加權邊的表示：邊數組 300
29.2.2 加權鄰接矩陣 301
29.2.3 鄰接線性表 301
29.3 WeightedGraph類 302
29.4 最小生成樹 309
29.4.1 最小生成樹算法 310
29.4.2 完善Prim的MST算法 311
29.4.3 MST算法的實現 312
29.5 尋找最短路徑 315
29.6 示例學習：加權的9枚硬幣反面問題 323
關鍵術語 326
本章小結 326
測試題 326
編程練習題 327

第30章 集合流的聚合操作 333
30.1 引言 333
30.2 流管道 334
30.2.1 Stream.of、limit和forEach方法 336
30.2.2 sorted方法 336
30.2.3 filter方法 337
30.2.4 max和min方法 337
30.2.5 anyMatch、allMatch和noneMatch方法 337
30.2.6 map、distinct和count方法 337
30.2.7 findFirst、findAny和toArray方法 338
30.3 IntStream、LongStream和DoubleStream 339
30.4 並行流 341
30.5 使用reduce方法進行流的歸約 344
30.6 使用collect方法進行流的歸約 346
30.7 使用groupingBy收集器進行元素分組 349
30.8 示例學習 352
30.8.1 示例學習：數字分析 352
30.8.2 示例學習：計算字母的出現次數 352
30.8.3 示例學習：計算字符串中每個字母的出現次數 353
30.8.4 示例學習：處理二維數組中的所有元素 354
30.8.5 示例學習：得到目錄大小 355
30.8.6 示例學習：關鍵字計數 356
30.8.7 示例學習：單詞出現次數 357
本章小結 358
測試題 359
編程練習題 359
附錄A Java關鍵字和保留字 360
附錄B ASCII字符集 361
附錄C 操作符優先級表 362
附錄D Java修飾符 363
附錄E 特殊浮點值 364
附錄F 數係 365
附錄G 位操作符 369
附錄H 正則表達式 370
附錄I 枚舉類型 376
附錄J 大O、大Ω和大Θ表示法 380