●出版者的話
譯者序
前言
引言組織數據
序言設計類
P.1封裝
P.2說明方法
P.2.1注釋
P.2.2前置條件和後置條件
P.2.3斷言
P.3Java接口
P.3.1寫一個接口
P.3.2實現一個接口
P.3.3接口作為數據類型
P.3.4派生一個接口
P.3.5接口內命名常量
P.4選擇類
P.4.1標識類
P.4.2CRC卡
P.4.3統一建模語言
P.5重用類
第1章包
1.1什麼是包
1.2說明一個包
1.3使用ADT包
1.4像使用自動販賣機一樣使用ADT
1.5ADT集合
1.6Java類庫：接口set
Java插曲1泛型
第2章使用數組實現包
2.1使用固定大小的數組實現ADT包
2.1.1類比
2.1.2一組核心方法
2.1.3實現核心方法
2.1.4讓實現安全
2.1.5測試核心方法
2.1.6實現更多的方法
2.1.7刪除項的方法
2.2使用可變大小的數組實現ADT包
2.2.1可變大小數組
2.2.2包的新實現
2.3使用數組實現ADT包的優缺點
Java插曲2異常
第3章使用鏈式數據實現包
3.1鏈式數據
3.2ADT包的鏈式實現
3.2.1私有類Node
3.2.2類LinkedBag的框架
3.2.3定義一些核心方法
3.2.4測試核心方法
3.2.5方法getFrequencyOf
3.2.6方法contalns
3.3從鏈中刪除一項
3.4有設置和獲取方法的類Node
3.5使用鏈實現ADT包的優缺點
第4章算法的效率
4.1動機
4.2測量算法的效率
4.2.1計數基本操作
4.2.2很優、最差和平均情形
4.3大O表示
4.4描述效率
4.5實現ADT包的效率
4.5.1基於數組的實現
4.5.2鏈式實現
4.5.3兩種實現的比較
第5章棧
5.1ADT棧的規格說明
5.2使用棧來處理代數表達式
5.2.1問題求解：檢查中綴代數表達式中平衡的分隔符
5.2.2問題求解：將中綴代數表達式轉換為後綴表達式
5.2.3問題求解：計算後綴表達式的值
5.2.4問題求解：計算中綴表達式的值
5.3程序棧
5.4Java類庫：類stack
第6章棧的實現
6.1鏈式實現
6.2基於數組的實現
6.3基於向量的實現
6.3.1Java類庫：類Vector
6.3.2使用向量實現ADT棧
第7章遞歸
7.1什麼是遞歸
7.2跟蹤遞歸方法
7.3返回一個值的遞歸方法
7.4遞歸處理數組
7.5遞歸處理鏈
7.6遞歸方法的時間效率
7.6.1countDown的時間效率
7.6.2計算xn的時間效率
7.7困難問題的簡單求解方案
7.8簡單問題的低劣求解方案
7.9尾遞歸
7.10間接遞歸
7.11使用棧來替代遞歸
Java插曲3再談泛型
第8章排序簡介
8.1對數組進行排序的Java方法的組織
8.2選擇排序
8.2.1迭代選擇排序
8.2.2遞歸選擇排序
8.2.3選擇排序的效率
8.3插入排序
8.3.1迭代插入排序
8.3.2遞歸插入排序
8.3.3插入排序的效率
8.3.4鏈式結點鏈的插入排序
8.4希爾排序
8.4.1算法
8.4.2希爾排序的效率
8.5算法比較
第9章更快的排序方法
9.1歸並排序
9.1.1歸並數組
9.1.2遞歸歸並排序
9.1.3歸並排序的效率
9.1.4迭代歸並排序
9.1.5Java類庫中的歸並排序
9.2快速排序
9.2.1快速排序的效率
9.2.2創建劃分
9.2.3實現快速排序
9.2.4Java類庫中的快速排序
9.3基數排序
9.3.1基數排序的偽代碼
9.3.2基數排序的效率
9.4算法比較
Java插曲4再談異常
第10章隊列、雙端隊列和優先隊列
10.1ADT隊列
10.1.1問題求解：模擬排隊
10.1.2問題求解：計算出售股票的資本收益
10.1.3Java類庫：接口Queue
10.2ADT雙端隊列
10.2.1問題求解：計算出售股票的資本收益
10.2.2Java類庫：接口Deque
10.2.3Java類庫：類ArrayDeque
10.3ADT優先隊列
10.3.1問題求解：跟蹤任務分配
10.3.2Java類庫：類PriorityQueue
第11章隊列、雙端隊列和優先隊列的實現
11.1隊列的鏈式實現
11.2基於數組實現隊列
11.2.1循環數組
11.2.2帶一個不用位置的循環數組
11.3隊列的循環鏈式實現
11.4Java類庫：類AbstractQueue
11.5雙端隊列的雙向鏈式實現
11.6優先隊列的町能實現方案
第12章線性表
12.1ADT線性表的規格說明
12.2使用ADT線性表
12.3Java類庫：接口List
12.4Java類庫：類ArrayList
第13章使用數組實現線性表
13.1使用數組實現ADT線性表
13.1.1類比
13.1.2Java實現
13.1.3使用數組實現ADT線性袁的效率
第14章使用鏈式數據實現線性表
14.1鏈式結點鏈上的操作
14.1.1在不同的位置添加結點
14.1.2從不同的位置刪除鮚點
14.1.3私有方法getNodeAt
14.2開始實現
14.2.1數據域和構造方法
14.2.2添加到線性表的表尾
14.2.3在線性表的給定位置添加力，
14.2.4方法isEmpty和toArray
14.2.5測試核心方法
14.3繼續實現
14.4細化實現
14.5使用鏈實現ADT線性表的效率
14.6Java類庫：類LinkedList
Java插曲5迭代器
第15章ADT線性表的迭代器
15.1實現迭代器的方法
15.2獨立類迭代器
15.3內層類迭代器
15.3.1鏈式實現
15.3.2基於教組的實現
15.4為什麼迭代器方法在它自己的類中
15.5基於數組實現接門ListIterator
Java插曲6可變及不可變對像
第16章有序表
16.1ADT有序表的規格說明
16.2鏈式實現
16.2.1方法add
16.2.2鏈式實現的效率
16.3使用ADT線性表實現
Java插曲7繼承和多態
第17章繼承和線性表
17.1使用繼承實現有序表
17.2設計一個基類
17.3有序表的高效實現
第18章查找
18.1問題
18.2在無序數組中查找
18.2.1無序數組上的迭代順序查找
18.2.2無序數組上的遞歸順序查找
18.2.3順序查找數組的效率
18.3有序數組上的查找
18.3.1有序數組上的順序查找
18.3.2有序數組上的二分查找
18.3.3Java類庫：方法binarySearch
18.3.4數組上的二分查找的效率425
184無序鏈上的查找
18.4.1無序鏈上的迭代順序查找
18.4.2無序鏈上的遞歸順序查找
18.4.3鏈上查找的效率
18.5有序鏈上的查找
18.5.1有序鏈上的順序查找
18.5.2有序鏈上的二分查找
18.6查找方法的選撢
Java插曲8再論泛型
第19章字典
19.1ADT字典的規格說明
19.1.1Java接口
19.1.2迭代器
19.2使用ADT字典
19.2.1問題求解：電話號碼簿
19.2.2問題求解：字的頻度
19.2.3問題求解：字的詞彙索引
19.3Java類庫：接口Hap
第20章字典的實現
20.1基於數組的實現
20.1.1基於數組的無序字典
20.1.2基於數組的有序字典
20.2鏈式實現
20.2.1無序鏈式字典
20.2.2有序鏈式字典
第21章散列簡介
21.1什麼是散列
21.2散列函數
21.2.1計算散列碼
21.2.2將散列碼壓縮為散列表的下標
21.3解決衝突
21.3.1開放地址的線性探查
21.3.2開放地址的二次探查
21.3.3開放地址的雙散列
21.3.4開放地址的潛在問題
21.3.5拉鏈法
第22章使用散列實現字典
22.1散列的效率
22.1.1裝填因子
22.1.2開放地址法的代價
22.1.3拉鏈法的代價
22.2冉散列
22.3衝突解決方案的比較
22.4字典的散列實現
22.4.1散列表中的項
22.4.2數據域和構造方法
22.4.3方法getValue、remove和add
22.4.4迭代器
22.5Java類庫：類HashMap
22.6Java類庫：類HashSet
第23章樹
23.1樹的概念
23.1.1層次結構
23.1.2樹的術語
23.2樹的遍歷
23.2.1二又樹的遍歷
23.2.2一般樹的遍歷
23.3樹的Java接口
23.3.1所有樹的接口
23.3.2二叉樹的接口
23.4二叉樹的示例
23.4.1表達式樹
23.4.2決策樹
23.4.3二叉查找樹
23.4.4堆
23.5一般樹的示例
23.5.1語法樹
23.5.2遊戲樹
……
第24章樹的實現
第25章二叉查找樹的實現
第26章堆的實現
第27章平衡查找樹
第28章圖
第29章圖的實現
附錄A文檔和程序設計風格
附錄BJava基礎（在線）
附錄CJava類（在線）
附錄D從其他類創建類
附錄E文件輸入和輸出（在線）
索引

本書是一本數據結構的優秀教材，Java語言與數據結構兩條知識主線貫穿始終，這兩條主線既相互獨立又相互支撐。本書介紹了計算機編程中使用的數據結構和算法，包括29章，每章涉及一個ADT或其不同實現的規格說明和用法；書中貫穿9個Java插曲，涉及Java的高級特性。本書主要講述了組織數據、設計類、包、棧、遞歸、排序、隊列、雙端隊列、優先隊列、線性表、有序表、查找、字典、散列、樹、二叉查找樹、堆、平衡查找樹、圖等內容，並對算法的效率進行了分析。本書非常適合作為大學本科生數據結構課程的教材，也可作為計算機研究與開發人員的參考書。

(美)弗蘭克 M.卡拉諾(Frank M.Carrano),(美)蒂莫西 M.亨利(Timothy M.Henry) 著;辛運幃,饒一梅 譯 著作

前    言Data Structures and Abstractions with Java, Fourth Edition歡迎使用本書，本書可作為數據結構課程的教材，例如CS-2課程。 作者集30餘年講授本科生計算機科學課程的教學經驗，時刻謹記師生的需求來寫作本書。作者想讓本書適合讀者閱讀，這樣學生學得更容易，老師教得更有效果。模仿現實世界情形的一些例子作為新素材的背景，幫助學生理解抽像概念。使用很多簡單的圖來解釋及闡述復雜的思想。 這次修訂保留了之前版本中的章節題目及次序。讀者會發現，我們特別強調不同數據結構的需求及實現的設計決策，同時新增加了對安全可靠程序設計慣例的介紹。 我們希望你樂於閱讀本書。與之前的眾多讀者一樣，你能學會（或講授）數據結構，有效果且能堅持下去。 歡迎使用本書的師生聯繫我們。非常感謝您的意見、建議等