Java語言程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)（進(jìn)階篇 原書第11版）

出版者的話

中文版序

譯者序

前言

第19章　泛型 1

19.1　引言 1

19.2　動機和優(yōu)點 1

19.3　定義泛型類和接口 4

19.4　泛型方法 5

19.5　示例學(xué)習(xí)：對一個對象數(shù)組進(jìn)行排序 7

19.6　原生類型和向后兼容 8

19.7　通配泛型 10

19.8　泛型的擦除和限制 12

19.9　示例學(xué)習(xí)：泛型矩陣類 15

關(guān)鍵術(shù)語 19

本章小結(jié) 19

測試題 20

編程練習(xí)題 20

第20章　線性表、棧、隊列和優(yōu)先隊列 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　數(shù)組線性表類ArrayList和鏈表類LinkedList 29

20.6　Comparator接口 32

20.7　線性表和集合的靜態(tài)方法 36

20.8　示例學(xué)習(xí)：彈球 39

20.9　向量類和棧類 42

20.10　隊列和優(yōu)先隊列 44

20.10.1　Queue接口 44

20.10.2　雙端隊列Deque和鏈表LinkedList 45

20.11　示例學(xué)習(xí)：表達(dá)式求值 47

關(guān)鍵術(shù)語 51

本章小結(jié) 51

測試題 51

編程練習(xí)題 51

第21章　規(guī)則集和映射 57

21.1　引言 57

21.2　規(guī)則集 57

21.2.1　HashSet 58

21.2.2　LinkedHashSet 61

21.2.3　TreeSet 62

21.3　比較規(guī)則集和線性表的性能 65

21.4　示例學(xué)習(xí)：關(guān)鍵字計數(shù) 67

21.5　映射 69

21.6　示例學(xué)習(xí)：單詞的出現(xiàn)次數(shù) 73

21.7　單元素與不可變的集合和映射 75

關(guān)鍵術(shù)語 76

本章小結(jié) 76

測試題 77

編程練習(xí)題 77

第22章　開發(fā)高效算法 79

22.1　引言 79

22.2　使用大?O?標(biāo)記來衡量算法效率 79

22.3　示例：確定大O 81

22.4　分析算法的時間復(fù)雜度 85

22.4.1　分析二分查找算法 85

22.4.2　分析選擇排序算法 85

22.4.3　分析漢諾塔問題 85

22.4.4　常用的遞推關(guān)系 86

22.4.5　比較常用的增長函數(shù) 86

22.5　使用動態(tài)編程尋找斐波那契數(shù) 87

22.6　使用歐幾里得算法求最大公約數(shù) 89

22.7　尋找素數(shù)的高效算法 93

22.8　使用分而治之法尋找最近點對 99

22.9　使用回溯法解決八皇后問題 101

22.10　計算幾何：尋找凸包 103

22.10.1　卷包裹算法 104

22.10.2　格雷厄姆算法 105

關(guān)鍵術(shù)語 106

本章小結(jié) 106

測試題 107

編程練習(xí)題 107

第23章　排序 114

23.1　引言 114

23.2　插入排序 115

23.3　冒泡排序 117

23.4　歸并排序 119

23.5　快速排序 122

23.6　堆排序 126

23.6.1　堆的存儲 127

23.6.2　添加一個新的結(jié)點 127

23.6.3　刪除根結(jié)點 128

23.6.4　Heap類 129

23.6.5　使用Heap類進(jìn)行排序 131

23.6.6　堆排序的時間復(fù)雜度 132

23.7　桶排序和基數(shù)排序 133

23.8　外部排序 135

23.8.1　實現(xiàn)階段Ⅰ 136

23.8.2　實現(xiàn)階段Ⅱ 137

23.8.3　結(jié)合兩個階段 139

23.8.4　外部排序復(fù)雜度 141

關(guān)鍵術(shù)語 142

本章小結(jié) 142

測試題 142

編程練習(xí)題 142

第24章　實現(xiàn)線性表、棧、隊列和優(yōu)先隊列 146

24.1　引言 146

24.2　線性表的通用操作 146

24.3　數(shù)組線性表 149

24.4　鏈表 156

24.4.1　結(jié)點 156

24.4.2　MyLinkedList類 158

24.4.3　實現(xiàn)MyLinkedList 159

24.4.4　MyArrayList和MyLinkedList 167

24.4.5　鏈表的變體 167

24.5　棧和隊列 169

24.6　優(yōu)先隊列 172

本章小結(jié) 173

測試題 174

編程練習(xí)題 174

第25章　二叉搜索樹 176

25.1　引言 176

25.2　二叉搜索樹 176

25.2.1　表示二叉搜索樹 177

25.2.2　查找一個元素 178

25.2.3　在BST中插入一個元素 178

25.2.4　樹的遍歷 179

25.2.5　BST類 180

25.3　刪除BST中的一個元素 189

25.4　樹的可視化和MVC 194

25.5　迭代器 197

25.6　示例學(xué)習(xí)：數(shù)據(jù)壓縮 199

關(guān)鍵術(shù)語 204

本章小結(jié) 204

測試題 204

編程練習(xí)題 204

第26章　AVL樹 208

26.1　引言 208

26.2　重新平衡樹 209

26.3　為AVL樹設(shè)計類 211

26.4　重寫insert方法 212

26.5　實現(xiàn)旋轉(zhuǎn) 213

26.6　實現(xiàn)delete方法 213

26.7　AVLTree類 214

26.8　測試 AVLTree類 219

26.9　AVL樹的時間復(fù)雜度分析 222

關(guān)鍵術(shù)語 222

本章小結(jié) 223

測試題 223

編程練習(xí)題 223

第27章　散列 225

27.1　引言 225

27.2　什么是散列 225

27.3　散列函數(shù)和散列碼 226

27.3.1　基本數(shù)據(jù)類型的散列碼 226

27.3.2　字符串的散列碼 227

27.3.3　壓縮散列碼 227

27.4　使用開放地址法處理沖突 228

27.4.1　線性探測法 228

27.4.2　二次探測法 230

27.4.3　雙重散列法 230

27.5　使用分離鏈接法處理沖突 232

27.6　裝填因子和再散列 232

27.7　使用散列實現(xiàn)映射 233

27.8　使用散列實現(xiàn)規(guī)則集 242

關(guān)鍵術(shù)語 248

本章小結(jié) 249

測試題 249

編程練習(xí)題 249

第28章　圖及其應(yīng)用 251

28.1　引言 251

28.2　基本的圖術(shù)語 252

28.3　表示圖 254

28.3.1　表示頂點 254

28.3.2　表示邊：邊數(shù)組 255

28.3.3　表示邊：Edge對象 256

28.3.4　表示邊：鄰接矩陣 256

28.3.5　表示邊：鄰接線性表 257

28.4　圖的建模 259

28.5　圖的可視化 268

28.6　圖的遍歷 271

28.7　深度優(yōu)先搜索 272

28.7.1　DFS的算法 272

28.7.2　DFS的實現(xiàn) 273

28.7.3　DFS的應(yīng)用 274

28.8　示例學(xué)習(xí)：連通圓問題 275

28.9　廣度優(yōu)先搜索 278

28.9.1　BFS的算法 278

28.9.2　BFS的實現(xiàn) 278

28.9.3　BFS的應(yīng)用 280

28.10　示例學(xué)習(xí)：9枚硬幣反面問題 281

關(guān)鍵術(shù)語 286

本章小結(jié) 286

測試題 286

編程練習(xí)題 286

第29章　加權(quán)圖及其應(yīng)用 291

29.1　引言 291

29.2　加權(quán)圖的表示 292

29.2.1　加權(quán)邊的表示：邊數(shù)組 292

29.2.2　加權(quán)鄰接矩陣 293

29.2.3　鄰接線性表 293

29.3　WeightedGraph類 294

29.4　最小生成樹 301

29.4.1　最小生成樹算法 302

29.4.2　完善Prim的MST算法 303

29.4.3　MST算法的實現(xiàn) 304

29.5　尋找最短路徑 307

29.6　示例學(xué)習(xí)：加權(quán)的9枚硬幣反面問題 315

關(guān)鍵術(shù)語 318

本章小結(jié) 318

測試題 319

編程練習(xí)題 319

第30章　集合流的聚合操作 325

30.1　引言 325

30.2　流管道 326

30.2.1　Stream.of、limit、forEach方法 328

30.2.2　sorted方法 329

30.2.3　filter方法 329

30.2.4　max和min方法 329

30.2.5　anyMatch、allMatch和noneMatch方法 329

30.2.6　map、distinct和count方法 329

30.2.7　findFirst、findAny和toArray方法 330

30.3　IntStream、LongStream和DoubleStream 331

30.4　并行流 333

30.5　使用reduce方法進(jìn)行流的歸約 336

30.6　使用collect方法進(jìn)行流的歸約 338

30.7　使用groupingBy收集器進(jìn)行元素分組 341

30.8　示例學(xué)習(xí) 344

30.8.1　示例學(xué)習(xí)：數(shù)字分析 344

30.8.2　示例學(xué)習(xí)：計算字母的出現(xiàn)次數(shù) 345

30.8.3　示例學(xué)習(xí)：計算字符串中每個字母的出現(xiàn)次數(shù) 346

30.8.4　示例學(xué)習(xí)：處理二維數(shù)組中的所有元素 347

30.8.5　示例學(xué)習(xí)：得到目錄大小 348

30.8.6　示例學(xué)習(xí)：關(guān)鍵字計數(shù) 349

30.8.7　示例學(xué)習(xí)：單詞出現(xiàn)次數(shù) 350

本章小結(jié) 351

測試題 351

編程練習(xí)題 351

附錄A　Java關(guān)鍵字 353

附錄B　ASCII字符集 354

附錄C 　操作符優(yōu)先級表 355

附錄D　Java修飾符 356

附錄E　特殊浮點值 357

附錄F　數(shù)系 358

附錄G　位操作符 362

附錄H　正則表達(dá)式 363

附錄I　枚舉類型 367