《數據結構與問題求解（Java語言版）（第4版）》是2011年出版的圖書，作者是Mark Allen Weiss
基本介紹
- 中文名：數據結構與問題求解（Java語言版）（第4版）
- 作者：Mark Allen Weiss
- ISBN：9787302252962
- 裝幀：平裝
- ISBN：9787302252962
- 譯者：葛秀慧等
圖書簡介：,目錄,
圖書簡介：
數據結構與算法是程式設計的重要理論基礎，也是計算機科學課程中的核心課程。本書是專為計算機科學專業的兩個學期課程而設計，先介紹數據結構，然後對高級數據結構和算法進行分析。本書採用了獨特的方法，清晰地將每種數據結構的接口與其實現分離開來，即將如何使用數據結構與如何對數據結構編程相分離，並充分利用了已有的數據結構庫：Java集合類API。這就使學生更容易理解面向對象的編程思想，使學生先從用戶的角度進行需求分析，然後再以設計者的角度進行編程設計。
本書從抽象思維和解決問題的觀點出發，採用流行的Java程式語言，根據實踐需要，對數據結構進行介紹。數據結構課程的重點最終會從實現轉向使用，學生可以儘早地使用已有的軟體組件來設計大型項目。
數據結構課程的內容隨著時間的推移已經發生了演變，但所涵蓋的相關主題達成了普遍的共識，那就是軟體開發的原則，其中最突出的是封裝和信息隱藏的概念。在算法上，所有的數據結構課程往往都趨向於包括對運行時間分析、遞歸、基本排序算法和基本數據結構的介紹。本書共分五個部分：第一部分描述了整本書所使用的Java基礎知識；第二部分集中介紹基本的算法和構件塊；第三部分提供了一些實例研究；第四部分介紹數據結構的實現；第五部分是高級數據結構。另外，作為一部經典教材，本書內容嚴謹、全面、結構組織合理，講授這門課的教師可以根據本校學生的需求來摘取不同內容構成自己的講義。
另外值得強調的是這本書的適用性，它為專業人員提供了大量的、翔實的、來自真實世界的代碼，也為初學者提供了從淺入深、循序漸進學習數據結構與算法的豐富實例。本書既可以用於普通數據結構的學習，也可以作為高級數據結構的教材。同時，這本書每章末都有印證所學內容的大量、有趣的練習，以及要求學生自己動手來建立自己的應用程式。
目錄
第1部分 Java教程
第1章 Java基礎知識 3
1.1 通用環境 3
1.2 第一個程式 4
1.2.1 注釋 4
1.2.2 main 5
1.2.3 終端輸出 5
1.3 基本類型 5
1.3.1 概述 5
1.3.2 常量 6
1.3.3 基本類型的聲明與
初始化 6
1.3.4 終端輸入與輸出 7
1.4 基本運算符 7
1.4.1 賦值運算符 7
1.4.2 二元算術運算符 8
1.4.3 一元運算符 8
1.4.4 類型轉換 9
1.5 條件語句 9
1.5.1 關係和相等運算符 10
1.5.2 邏輯運算符 10
1.5.3 if語句 11
1.5.4 while語句 12
1.5.5 for語句 13
1.5.6 do語句 13
1.5.7 break和continue 14
1.5.8 switch語句 15
1.5.9 條件運算符 15
1.6 方法 16
1.6.1 方法名重載 17
1.6.2 存儲類 18
本章小結 18
重要概念 18
常見錯誤 20
網上資源 20
練習 20
簡答題 20
理論題 21
實踐題 21
程式設計題 22
參考文獻 22
第2章 引用類型 23
2.1 什麼是引用 23
2.2 對象和引用基礎 24
2.2.1 點（.）運算符 25
2.2.2 對象的聲明 25
2.2.3 垃圾回收 26
2.2.4 =的含義 26
2.2.5 參數傳遞 27
2.2.6 = =的含義 28
2.2.7 對象的無運算符重載 29
2.3 字元串 29
2.3.1 字元串處理基礎 29
2.3.2 字元串連線 30
2.3.3 字元串比較 30
2.3.4 其他String方法 30
2.3.5 將其他類型轉換成
字元串 31
2.4 數組 31
2.4.1 聲明、賦值與方法 32
2.4.2 動態數組擴展 34
2.4.3 ArrayList 36
2.4.4 多維數組 37
2.4.5 命令行參數 38
2.4.6 增強的for循環 39
2.5 異常處理 40
2.5.1 概述 40
2.5.2 finally子句 41
2.5.3 常見的異常 41
2.5.4 throw和throws
子句 42
2.6 輸入與輸出 43
2.6.1 基本流操作 43
2.6.2 Scanner類型 44
2.6.3 順序檔案 46
本章小結 49
重要概念 49
常見錯誤 50
網上資源 51
練習 51
簡答題 51
理論題 51
實踐題 52
程式設計題 54
參考文獻 56
第3章 對象與類 57
3.1 什麼是面向對象編程 57
3.2 簡單示例 58
3.3 javadoc 60
3.4 基本方法 62
3.4.1 構造函式 62
3.4.2 存取器和訪問器 62
3.4.3 輸出與toString 63
3.4.4 equals 64
3.4.5 main 64
3.5 示例：使用java.math.
BigInteger 64
3.6 其他構造 66
3.6.1 this引用 66
3.6.2 用於構造函式的this
縮寫 67
3.6.3 instanceof運算符 67
3.6.4 實例成員與靜態成員 68
3.6.5 靜態欄位與方法 68
3.6.6 靜態初始化塊 70
3.7 示例：實現BigRational類 71
3.8 包 74
3.8.1 import指令 75
3.8.2 package語句 76
3.8.3 CLASSPATH環境
變數 77
3.8.4 包可見性規則 77
3.9 設計模式：組合（對） 78
本章小結 79
重要概念 80
常見錯誤 81
網上資源 82
練習 82
簡答題 82
理論題 83
實踐題 83
程式設計題 85
參考文獻 87
第4章 繼承 88
4.1 什麼是繼承 88
4.1.1 創建新類 89
4.1.2 類型兼容性 92
4.1.3 動態分配和多態性 93
4.1.4 繼承層次結構 94
4.1.5 可見性規則 95
4.1.6 構造函式與super 95
4.1.7 final方法和類 96
4.1.8 重寫方法 97
4.1.9 類型兼容性修正 99
4.1.10 數組類型的
兼容性 100
4.1.11 協變返回類型 100
4.2 設計層次結構 101
4.2.1 抽象方法與抽象類 103
4.2.2 未來的設計 105
4.3 多重繼承 106
4.4 接口 108
4.4.1 指定接口 108
4.4.2 實現接口 108
4.4.3 多接口 109
4.4.4 接口是抽象類 109
4.5 Java的基本繼承 110
4.5.1 Object類 110
4.5.2 異常的層次結構 110
4.5.3 I/O：裝飾模式 110
4.6 使用繼承實現泛型組件 114
4.6.1 使用Object的泛型 114
4.6.2 基本類型的包裝 115
4.6.3 自動裝包/拆包 117
4.6.4 適配器：改變接口 117
4.6.5 泛型所使用的接口
類型 118
4.7 使用Java 5泛型實現
泛型組件 120
4.7.1 簡單的泛型類和
接口 121
4.7.2 通配符的綁定 121
4.7.3 泛型的靜態方法 123
4.7.4 類型綁定 123
4.7.5 類型擦除 124
4.7.6 泛型的限制 125
4.8 函子（函式對象） 127
4.8.1 嵌套類 130
4.8.2 局部類 130
4.8.3 匿名類 132
4.8.4 嵌套類和泛型 132
4.9 動態分配細節 133
本章小結 135
重要概念 136
常見錯誤 138
網上資源 138
習題 139
簡答題 139
理論題 140
實踐題 142
程式設計題 144
參考文獻 146
第2部分 算法與構件塊
第5章 算法分析 149
5.1 什麼是算法分析 149
5.2 算法運行時間的示例 152
5.3 最大連續子序列和的
問題 153
5.3.1 簡單O(N3)算法 154
5.3.2 改進的O(N2)算法 156
5.3.3 線性算法 157
5.4 一般的大O規則 159
5.5 對數 162
5.6 靜態查找問題 164
5.6.1 順序查找 164
5.6.2 二分查找 164
5.6.3 插值查找 167
5.7 檢查算法分析 168
5.8 大O分析的局限性 169
本章小結 169
重要概念 170
常見錯誤 170
網上資源 171
練習 171
簡答題 171
理論題 172
實踐題 176
程式設計題 178
參考文獻 179
第6章 集合類API 181
6.1 概述 181
6.2 疊代器模式 182
6.2.1 基本的疊代器
設計 183
6.2.2 基於繼承的疊代器和
工廠方法 185
6.3 集合類API：容器和
疊代器 186
6.3.1 Collection接口 187
6.3.2 Iterator接口 189
6.4 泛型算法 191
6.4.1 Comparator函式
對象 192
6.4.2 Collections類 192
6.4.3 二分查找 194
6.4.4 排序 194
6.5 List接口 196
6.5.1 ListIterator接口 196
6.5.2 LinkedList類 197
6.5.3 Lists的運行時間 200
6.5.4 從List中間刪除和
插入 202
6.6 棧與佇列 204
6.6.1 棧 204
6.6.2 棧與計算語言 205
6.6.3 佇列 206
6.6.4 在集合類API中的
棧與佇列 207
6.7 集合 207
6.7.1 TreeSet類 208
6.7.2 HashSet類 209
6.8 映射 213
6.9 優先權佇列 217
6.10 集合類API中的視圖 219
6.10.1 List的subList
方法 219
6.10.2 SortedSet的headSet、
subSet和tailSet
方法 220
本章小結 220
重要概念 221
常見錯誤 222
網上資源 222
練習 223
簡答題 223
理論題 223
實踐題 224
程式設計題 229
參考文獻 231
第7章 遞歸 232
7.1 什麼是遞歸 232
7.2 背景知識：數學歸
納法證明 233
7.3 基本遞歸 235
7.3.1 以任意基數列印數 236
7.3.2 運行的原因 238
7.3.3 如何運行 239
7.3.4 太多的遞歸是
危險的 240
7.3.5 樹的預備知識 241
7.3.6 其他的例子 242
7.4 數值套用 245
7.4.1 模運算 246
7.4.2 模的冪運算 246
7.4.3 最大公約數和乘法
逆元素 247
7.4.4 RSA密碼系統 250
7.5 分治算法 252
7.5.1 最大連續子序列和的
問題 252
7.5.2 基本分治循環的
分析 254
7.5.3 分治運行時間的
一般上界 257
7.6 動態規劃 259
7.7 回溯 262
本章小結 265
重要概念 265
常見錯誤 266
網上資源 266
練習 267
簡答題 267
理論題 267
實踐題 269
程式設計題 270
參考文獻 273
第8章 排序算法 274
8.1 排序為什麼重要 274
8.2 預備知識 275
8.3 插入排序和其他簡單排序的
分析 275
8.4 希爾排序 278
8.4.1 希爾排序的性能 279
8.5 歸併排序 281
8.5.1 以線性時間歸併
有序數組 281
8.5.2 歸併排序算法 283
8.6 快速排序 284
8.6.1 概述 285
8.6.2 快速排序分析 287
8.6.3 選擇支點 290
8.6.4 分割策略 291
8.6.5 鍵等於支點 292
8.6.6 三個元素的中值
分割 293
8.6.7 小數組 294
8.6.8 Java的快速
排序例程 294
8.7 快速選擇 296
8.8 排序的下限 297
本章小結 298
重要概念 299
常見錯誤 299
網上資源 299
練習 300
簡答題 300
理論題 300
實踐題 301
程式設計題 302
參考文獻 304
第9章 隨機化 305
9.1 為什麼需要隨機數 305
9.2 隨機數發生器 306
9.3 非均勻隨機數 312
9.4 生成隨機排列 313
9.5 隨機算法 314
9.6 隨機素性測試 316
本章小結 319
重要概念 319
常見錯誤 320
網上資源 320
練習 321
簡答題 321
理論題 321
實踐題 321
程式設計題 321
參考文獻 322
第3部分 應 用
第10章 娛樂與遊戲 327
10.1 縱橫找單詞 327
10.1.1 理論 327
10.1.2 Java實現 329
10.2 井字遊戲 334
10.2.1 ??? 剪枝 334
10.2.2 置換表 336
10.2.3 計算機下棋 339
本章小結 340
重要概念 340
常見錯誤 341
網上資源 341
練習 341
簡答題 341
理論題 342
實踐題 342
程式設計題 342
參考文獻 343
第11章 棧與編譯器 344
11.1 平衡符號檢查器 344
11.1.1 基本算法 344
11.1.2 實現 345
11.2 簡單的計算器 353
11.2.1 後綴機 354
11.2.2 中綴到後綴的
轉換 354
10.2.3 實現 357
10.2.4 表達式樹 363
本章小結 364
重要概念 364
常見錯誤 365
網上資源 365
練習 365
簡答題 365
理論題 366
實踐題 366
程式設計題 366
參考文獻 367
第12章 實用程式 368
12.1 檔案壓縮 368
12.1.1 前綴碼 369
12.1.2 霍夫曼算法 370
12.1.3 實現 372
12.2 交叉引用生成器 384
12.2.1 基本思想 384
12.2.2 Java實現 384
本章小結 387
重要概念 388
常見錯誤 388
網上資源 388
練習 388
簡答題 388
理論題 389
實踐題 389
程式設計題 390
參考文獻 392
第13章 模擬 393
13.1 約瑟夫問題 393
13.1.1 簡單的解決方案 394
13.1.2 更高效的算法 395
13.2 事件驅動模擬 397
13.2.1 基本思想 397
13.2.2 示例：電話銀行
模擬 398
本章小結 404
重要概念 405
常見錯誤 405
網上資源 405
練習 405
簡答題 405
理論題 405
實踐題 406
程式設計題 406
第14章 圖與路徑 407
14.1 圖的定義 407
14.1.1 圖的表示 409
14.2 無權最短路徑問題 417
14.2.1 理論 418
14.2.2 Java實現 420
14.3 非負權值的最短路徑
問題 421
14.3.1 理論：dijkstra
算法 421
14.3.2 Java實現 424
14.4 負權值的最短路徑問題 425
14.4.1 理論 426
14.4.2 Java實現 426
14.5 在無環圖中的路徑
問題 427
14.5.1 拓撲排序 428
14.5.2 無環圖最短路徑
算法的理論 429
14.5.3 Java實現 430
14.5.4 套用：關鍵路徑
分析 432
本章小結 434
重要概念 434
常見錯誤 435
網上資源 435
練習 435
簡答題 435
理論題 436
實踐題 437
程式設計題 437
參考文獻 438
第4部分 實 現
第15章 內部類和ArrayList的
實現 443
15.1 疊代器和嵌套類 443
15.2 疊代器和內部類 445
15.3 AbstractCollection類 447
15.4 StringBuilder 450
15.5 使用疊代器的ArrayList的
實現 451
本章小結 456
重要概念 456
常見錯誤 456
網上資源 456
練習 456
簡答題 456
理論題 457
實踐題 457
程式設計題 457
第16章 棧與佇列 459
16.1 動態數組實現 459
16.1.1 棧 459
16.1.2 佇列 462
16.2 鍊表實現 467
16.2.1 棧 467
16.2.2 佇列 469
16.3 兩種方法的比較 473
16.4 java.util.Stack類 473
16.5 雙端佇列 474
本章小結 475
重要概念 475
常見錯誤 475
網上資源 475
練習 475
簡答題 475
實踐題 476
程式設計題 476
第17章 鍊表 477
17.1 基本思想 477
17.1.1 頭結點 478
17.1.2 疊代器類 479
17.2 Java實現 480
17.3 雙鍊表和循環鍊表 485
17.4 有序鍊表 487
17.5 集合類AIP LinkedList類的
實現 488
本章小結 498
重要概念 498
常見錯誤 498
網上資源 498
練習 499
簡答題 499
理論題 499
實踐題 499
程式設計題 500
第18章 樹 502
18.1 一般樹 502
18.1.1 定義 502
18.1.2 實現 503
18.1.3 套用：檔案系統 504
18.2 二叉樹 507
18.3 遞歸與樹 512
18.4 樹的遍歷：疊代器類 514
18.4.1 後序遍歷 516
18.4.2 中序遍歷 520
18.4.3 前序遍歷 521
18.4.4 層序遍歷 523
本章小結 524
重要概念 524
常見錯誤 525
網上資源 525
練習 526
簡答題 526
理論題 527
實踐題 527
程式設計題 527
第19章 二叉查找樹 529
19.1 基本思想 529
19.1.1 操作 530
19.1.2 Java實現 531
19.2 順序統計量 537
19.2.1 Java實現 538
19.3 二叉查找樹操作的分析 541
19.4 AVL樹 543
19.4.1 性質 544
19.4.2 單旋轉 546
19.4.3 雙旋轉 548
19.4.4 AVL插入總結 550
19.5 紅黑樹 550
19.5.1 自底而上的插入 551
19.5.2 自頂而下的
紅黑樹 553
19.5.3 Java實現 554
19.5.4 自頂而下的刪除 560
19.6 AA樹 561
19.6.1 插入 562
19.6.2 刪除 564
19.6.3 Java實現 565
19.7 集合類API中TreeSet類
和TreeMap類的實現 569
19.8 B樹 582
本章小結 587
重要概念 588
常見錯誤 588
網上資源 589
練習 589
簡答題 589
理論題 589
實踐題 590
程式設計題 590
參考文獻 593
第20章 散列表 595
20.1 基本思想 595
20.2 散列函式 596
20.2.1 在java.lang.String
中的hashCode 598
20.3 線性探測法 599
20.3.1 線性探測法的
簡單分析 600
20.3.2 真的發生了什麼：
初始聚類 601
20.3.3 find操作的分析 602
20.4 二次探測法 603
20.4.1 Java實現 606
20.4.2 二次探測法的
分析 613
20.5 分離連結散列 614
20.6 散列表與二叉查找樹的
比較 616
20.7 散列的套用 616
本章小結 616
重要概念 617
常見錯誤 617
網上資源 618
練習 618
簡答題 618
理論題 618
實踐題 619
程式設計題 619
參考文獻 620
第21章 優先權佇列：二叉堆 622
21.1 基本思想 622
21.1.1 結構性質 623
21.1.2 堆序性質 624
21.1.3 允許的操作 624
21.2 基本操作的實現 627
21.2.1 插入 627
21.2.2 deleteMin操作 628
21.3 buildHeap操作：線性時間的
堆構造 630
21.4 高級操作：decreaseKey和
merge 633
21.5 內部排序：堆排序 634
21.6 外部排序 636
21.6.1 為什麼需要新
算法 636
21.6.2 外部排序的模型 636
21.6.3 簡單算法 636
21.6.4 多路歸併 638
21.6.5 多相歸併 639
21.6.6 置換選擇 640
本章小結 641
重要概念 642
常見錯誤 642
網上資源 642
練習 643
簡答題 643
理論題 643
實踐題 645
程式設計題 645
參考文獻 646
第5部分 高級數據結構
第22章 伸展樹 649
22.1 自調整和平攤分析 649
22.1.1 平攤時間限定 650
22.1.2 簡單的自調整策略
（不能運行） 650
22.2 基本自底向上的伸展樹 652
22.3 基本伸展樹的操作 653
22.4 自底向上伸展樹的分析 654
22.4.1 伸展限定的證明 656
22.5 自頂向下的伸展樹 658
22.6 自頂向下伸展樹的實現 661
22.7 伸展樹與其他查找樹的
比較 665
本章小結 665
重要概念 665
常見錯誤 666
網上資源 666
練習 666
簡答題 666
理論題 666
實踐題 667
程式設計題 667
參考文獻 667
第23章 歸併優先權佇列 668
23.1 斜堆 668
23.1.1 歸併是一種
基本操作 668
23.1.2 具有堆有序性樹的
簡化歸併 669
23.1.3 斜堆：一個簡單的
修改 669
23.1.4 斜堆的分析 670
23.2 偶堆 672
23.2.1 偶堆操作 672
23.2.2 偶堆的實現 674
23.2.3 套用：dijkstra的
最短加樹路徑算法 679
本章小結 681
重要概念 681
常見錯誤 681
網上資源 681
練習 682
簡答題 682
理論題 682
實踐題 682
程式設計題 682
參考文獻 683
第24章 不相交集類 684
24.1 等價關係 684
24.2 動態等價與套用 685
24.2.1 套用：生成迷宮 686
24.2.2 套用：最小生成樹 687
24.2.3 套用：最近共同
祖先問題 689
24.3 快速查找算法 692
24.4 快速並算法 693
24.4.1 智慧型並算法 694
24.4.2 路徑壓縮 696
24.5 Java實現 697
24.6 按秩並和路徑壓縮的
最壞情況 699
24.6.1 並/查找算法的
分析 699
本章小結 704
重要概念 704
常見錯誤 705
網上資源 705
練習 705
簡答題 705
理論題 706
實踐題 706
程式設計題 706
參考文獻 707
附錄A 運算符 709
附錄B 圖形化用戶界面 710
B.1 抽象視窗工具包和Swing 710
B.2 在Swing中的基本對象 711
B.2.1 組件 712
B.2.2 容器 713
B.2.3 頂級容器 713
B.2.4 JPanel 714
B.2.5 重要的I/O組件 715
B.3 基本原理 719
B.3.1 布局管理器 719
B.3.2 圖 722
B.3.3 事件 724
B.3.4 事件處理：適配器和
匿名內部類 726
B.3.5 總結：將所有片段
組合起來 728
B.3.6 是否需要明白Swing
的所有內容 728
小結 728
重要概念 729
常見錯誤 730
網上資源 731
練習 731
簡答題 731
實踐題 731
程式設計題 731
參考文獻 732
附錄C 位運算符 733
