數據結構與抽象：Java 語言描述 (原書第5版)
內容描述
本書是數據結構的經典教材，內容涵蓋線性結構、層次結構、圖等數據結構，排序、查找等重要方法，以及算法的評估和迭代/遞歸實現方式等，並採用Java語言基於數組和鏈表實現了各種ADT。本書的組織方式獨特，語言簡潔，示例豐富，程序規範，習題多樣。
本書新特色
新增加了一章討論遞歸，介紹語法、語言及回溯。
增加了新的設計決策、註、安全說明及編程技巧。
在大部分章節中，增加了側重游戲、電子商務及財務的練習和程序設計項目。
調整了某些主題的次序，相關的主題集中介紹，內容連貫。
修改了插圖，使之更容易閱讀和理解。
將“自測題”改名為“學習問題”，並將答案移至網站中，鼓勵小組一起討論答案。
書中包含了關於Java類的附錄，而不是將其放在網站中。
目錄大綱
出版者的話
譯者序
前言
導論組織數據1
序言設計類3
封裝3
規範說明方法5
註釋5
前置條件和後置條件5
斷言6
Java接口7
寫一個接口8
實現一個接口9
接口作為數據類型11
派生一個接口12
接口內的命名常量13
選擇類14
標識類15
CRC卡15
統一建模語言16
重用類18
練習19
項目19
第1章包22
什麼是包22
包的行為23
規範說明一個包23
一個接口28
使用ADT包30
像使用自動販賣機一樣使用ADT 33
ADT集合34
Java類庫：接口Set 35
本章小結35
練習36
項目37
Java插曲1泛型40
泛型數據類型40
接口中的泛型40
泛型類41
第2章使用數組實現包44
使用定長數組實現ADT包44
模擬44
一組核心方法45
實現核心方法46
讓實現安全52
測試核心方法54
實現更多的方法57
刪除項的方法59
使用變長數組實現ADT包67
變長數組67
包的新實現69
使用數組實現ADT包的優缺點71
本章小結72
程序設計技巧72
練習73
項目74
Java插曲2異常75
基礎75
處理異常77
延緩處理：throws子句77
現在處理：try-catch塊78
多個catch塊79
拋出異常80
第3章使用鍊式數據實現包83
鍊式數據83
添加到開頭形成一個鍊錶84
ADT包的鍊式實現85
私有類Node 85
類LinkedBag的框架87
定義一些核心方法88
測試核心方法91
方法getFrequencyOf 92
方法contains 93
從鍊錶中刪除一項94
方法remove和clear 95
有設置和獲取方法的類Node 98
使用鍊錶實現ADT包的優缺點101
本章小結101
程序設計技巧101
練習102
項目102
第4章算法的效率104
動機104
算法效率的衡量105
統計基本操作107
最優、最差和平均情況109
大O表示109
程序結構的複雜度112
圖示化效率113
實現ADT包的效率115
基於數組的實現115
鍊式實現117
兩種實現的比較118
本章小結118
練習118
項目121
第5章棧123
ADT棧的規範說明123
使用棧來處理代數表達式127
問題求解：檢查中綴代數表達式中平衡的分隔符128
問題求解：將中綴表達式轉換為後綴表達式132
問題求解：計算後綴表達式的值136
問題求解：計算中綴表達式的值137
程序棧139
Java類庫：類Stack 140
本章小結141
程序設計技巧141
練習141
項目143
第6章棧的實現146
鏈式實現146
基於數組的實現149
基於向量的實現152
Java類庫：類Vector 153
使用Vector實現ADT棧154
本章小結155
練習156
項目156
Java插曲3再論異常158
程序員定義的異常類158
繼承和異常162
finally塊163
第7章隊列、雙端隊列和優先隊列166
ADT隊列166
問題求解：模擬排隊169
問題求解：計算股票售出的資本收益174
Java類庫：接口Queue 177
ADT雙端隊列177
問題求解：計算股票售出的資本收益180
Java類庫：接口Deque 181
Java類庫：類ArrayDeque 182
ADT優先隊列183
問題求解：跟踪指派184
Java類庫：類PriorityQueue 185
本章小結186
程序設計技巧187
練習187
項目188
第8章隊列、雙端隊列和優先隊列的實現192
隊列的鍊式實現192
基於數組實現隊列196
循環數組196
帶一個未用元素的循環數組198
隊列的循環鍊式實現203
兩部分組成的循環鍊錶204
Java類庫：類AbstractQueue 209
隊列的雙向鍊式實現209
優先隊列的可能實現方案213
本章小結213
程序設計技巧214
練習214
項目215
第9章遞歸217
什麼是遞歸217
跟踪遞歸方法221
返回一個值的遞歸方法224
遞歸處理數組226
遞歸處理鍊錶228
遞歸方法的時間效率230
countDown的時間效率230
計算xn的時間效率231
尾遞歸232
使用棧來替代遞歸233
本章小結234
程序設計技巧234
練習235
項目237
第10章線性表240
ADT線性表的規範說明240
使用ADT線性表246
問題求解：使用大整數250
Java類庫：接口List 252
Java類庫：類ArrayList 252
本章小結253
練習253
項目254
第11章使用數組實現線性表257
使用數組實現ADT線性表257
模擬257
Java實現259
使用數組實現ADT線性表的效率266
本章小結268
練習268
項目269
第12章使用鍊式數據實現線性表271
結點鍊錶上的操作271
在不同的位置添加結點271
從不同的位置刪除結點275
私有方法getNodeAt 276
實現之初277
數據域和構造方法278
添加到線性表表尾279
在線性表的給定位置添加280
方法isEmpty和toArray 281
測試核心方法283
繼續實現284
完善實現286
尾引用287
使用鍊錶實現ADT線性表的效率290
Java類庫：類LinkedList 292
本章小結292
練習293
項目294
Java插曲4迭代器296
什麼是迭代器296
接口Iterator 297
接口Iterable 298
使用接口Iterator 299
Iterable和for-each循環302
接口ListIterator 303
再論接口List 306
使用接口ListIterator 306
第13章ADT線性表的迭代器309
實現迭代器的方法309
獨立類迭代器309
內部類迭代器312
鍊式實現313
基於數組的實現316
為什麼迭代器方法在它自己的類中319
基於數組實現接口ListIterator 320
內部類322
本章小結327
程序設計技巧327
練習327
項目329
第14章使用遞歸求解問題331
困難問題的簡單求解方案331
簡單問題的低劣求解方案336
語言和語法338
Java標識符語言338
前綴表達式語言339
前綴表達式的計算342
間接遞歸343
回溯343
穿越迷宮344
n皇后問題345
本章小結347
練習348
項目349
Java插曲5再論泛型352
接口Comparable 352
泛型方法354
限定的類型參數354
通配符357
限定的通配符357
第15章排序簡介360
對數組進行排序的Java方法的組織360
選擇排序361
迭代的選擇排序362
遞歸的選擇排序364
選擇排序的效率364
插入排序365
迭代的插入排序366
遞歸的插入排序367
插入排序的效率369
結點鍊錶上的插入排序369
希爾排序372
算法373
希爾排序的效率374
算法比較374
本章小結375
程序設計技巧375
練習375
項目377
第16章更快的排序方法379
歸併排序379
歸併數組379
遞歸的歸併排序380
歸併排序的效率382
迭代的歸併排序384
Java類庫中的歸併排序384
快速排序385
快速排序的效率385
創建劃分386
實現快速排序388
Java類庫中的快速排序390
基數排序390
基數排序的偽代碼392
基數排序的效率392
算法比較393
本章小結393
練習394
項目395
Java插曲6可變及不可變對象397
可變對象397
不可變對象398
創建只讀類399
伴生類400
第17章有序表403
ADT有序表的規範說明403
使用ADT有序表406
鍊式實現407
方法add 408
鍊式實現的效率414
使用ADT線性表的實現414
效率問題417
本章小結418
練習419
項目419
Java插曲7繼承和多態421
繼承的其他方面421
何時使用繼承421
保護訪問422
抽像類和方法422
接口與抽像類424
多態425
第18章繼承和線性表430
使用繼承實現有序表430
設計一個基類432
創建抽象基類436
有序表的高效實現439
方法add 439
本章小結440
程序設計技巧440
練習440
項目441
第19章查找443
問題443
在無序數組中查找443
無序數組中的迭代順序查找444
無序數組中的遞歸順序查找445
順序查找數組的效率446
在有序數組中查找446
有序數組中的順序查找447
有序數組中的二分查找447
Java類庫：binarySearch方法451
數組中二分查找的效率451
在無序鍊錶中查找453
無序鍊錶中的迭代順序查找453
無序鍊錶中的遞歸順序查找453
鍊錶中順序查找的效率454
在有序鍊錶中查找454
有序鍊錶中的順序查找454
有序鍊錶中的二分查找455
查找方法的選擇455
本章小結456
程序設計技巧456
練習456
項目458
Java插曲8三論泛型460
多個泛型460
第20章字典462
ADT字典的規範說明462
Java接口465
迭代器466
使用ADT字典468
問題求解：電話號碼簿468
問題求解：單詞的頻率472
問題求解：單詞的索引475
Java類庫：接口Map 478
本章小結478
程序設計技巧478
練習479
項目479
第21章字典的實現482
基於數組的實現482
基於無序數組的字典482
基於有序數組的字典487
鍊式實現491
無序鍊式字典491
有序鍊式字典492
本章小結494
程序設計技巧494
練習494
項目495
第22章散列簡介496
什麼是散列496
散列函數498
計算散列碼498
將散列碼壓縮為散列表的下標501
解決衝突502
開放地址的線性探查502
開放地址的二次探查507
開放地址的雙散列508
開放地址的潛在問題510
拉鍊法510
本章小結513
練習513
項目514
第23章使用散列實現字典516
散列的效率516
裝填因子516
開放地址法的代價517
拉鍊法的代價518
再散列519
衝突解決機制的比較520
使用散列實現字典521
散列表中的項521
數據域和構造方法522
方法getValue、remove和add 523
迭代器525
Java類庫：類HashMap 526
Java類庫：類HashSet 527
本章小結527
練習528
項目528
第24章樹531
樹的概念531
層次結構531
樹的術語532
樹的遍歷537
二叉樹的遍歷537
一般樹的遍歷538
用於樹的Java接口539
用於所有樹的接口539
用於二叉樹的接口540
二叉樹示例541
表達式樹541
決策樹543
二叉查找樹545
堆547
一般樹示例548
解析樹549
遊戲樹550
本章小結550
練習551
項目553
第25章樹的實現555
二叉樹中的結點555
二叉結點類556
ADT二叉樹的實現557
創建基本二叉樹557
方法initializeTree 559
訪問方法和賦值方法561
計算高度和結點個數562
遍歷563
表達式樹的實現567
一般樹568
用於一般樹的結點568
使用二叉樹表示一般樹569
本章小結570
程序設計技巧570
練習570
項目572
Java插曲9克隆574
可克隆的對象574
克隆一個數組579
克隆一個鍊錶581
有序表的克隆585
克隆一個二叉結點587
第26章二叉查找樹的實現589
入門知識589
用於二叉查找樹的接口590
重複項591
開始定義類592
查找和獲取593
遍歷595
添加一項595
遞歸實現596
迭代實現598
刪除一項600
刪除葉結點中的項600
刪除僅有一個孩子的結點中的項600
刪除有兩個孩子的結點中的項601
刪除根中的項604
遞歸實現604
迭代實現607
操作效率610
平衡的重要性611
結點按什麼次序添加611
ADT字典的實現612
本章小結614
練習615
項目617
第27章堆的實現620
再論：ADT堆620
使用數組表示堆620
添加項623
刪除根626
創建堆628
堆排序630
本章小結633
練習633
項目634
第28章平衡查找樹636
AVL樹636
單旋轉636
雙旋轉639
實現細節642
2-3樹646
在2-3樹中進行查找646
向2-3樹中添加項647
添加過程中結點的分裂649
2-4樹650
向2-4樹中添加項650
AVL樹、2-3樹和2-4樹的比較652
紅黑樹653
紅黑樹的特性654
向紅黑樹中添加項654
Java類庫：類TreeMap 659
B樹659
本章小結660
練習660
項目661
第29章圖663
一些示例及術語663
公路地圖663
航空公司的航線665
迷宮666
先修課程666
樹667
遍歷667
廣度優先遍歷668
深度優先遍歷669
拓撲序670
路徑672
尋找路徑673
無權圖中的最短路徑673
帶權圖中的最短路徑675
用於ADT圖的Java接口678
本章小結681
練習682
項目684
第30章圖的實現686
兩個實現概述686
鄰接矩陣686
鄰接表687
頂點和邊688
規範說明類Vertex 688
內部類Edge 690
類Vertex的實現691
ADT圖的實現694
基本操作694
圖算法697
本章小結699
練習699
項目701
附錄A文檔和程序設計風格702
附錄B Java類706
附錄C從其他類創建類727
補充材料1 Java基礎（在線）
補充材料2文件輸入輸出（在線）
補充材料3詞彙表（在線）
補充材料4學習問題答案（在線）
作者介紹
弗蘭克·M.卡拉諾（Frank M. Carrano）是美國羅得島大學計算機科學系榮譽退休教授，1969年獲得美國錫拉丘茲大學計算機科學專業博士學位。他的研究興趣包括數據結構、計算機科學教育、社會問題的計算處理和數值計算。Carrano教授撰寫了多本著名的計算機科學高年級本科生教科書。
蒂莫西·M. 亨利（Timothy M. Henry） 是美國新英格蘭理工學院計算機科學系副教授，1986年獲得美國歐道明大學計算機科學專業碩士學位，2001年獲得美國羅得島大學應用數學專業博士學位，自2000年以來一直保有美國PMI的項目管理專家（Project Management Professional，PMP）認證資格。他教授的課程有數據結構與抽象、編程語言基礎、操作系統與網絡、計算機系統基礎、計算機科學項目、文件系統取證等，研究領域涉及計算機和數學取證、交互式3D圖形關係、傳感器網絡。
