本書是為數據結構入門課程而編寫的教材。作者Frank Carrano在編寫過程自始至終特別考慮到了Java與對象，為教師和學生提供了一種精心設計并經過教學實驗的方式借助Java講授ADT和對象。本書獨特的設計將內容組織為相對較短的章。這種方式使學習更容易，并留出了教學的機動性。本書教給學生如何使用線性表、詞典、棧、隊列等等來組織數據。利用這些數據組織方式，學生們將學到算法設計的相關技術。
本書在編寫過程中特別考慮到了面向對象程序設計(OOP)的思想與Java語言的特性。它不是從基于另一種程序設計語言的數據結構教材簡單地"改編"而來的，因此在數據結構的實現上更加"地道"地運用了Java語言，并且自始至終強調以面向對象的方式來思考、分析和解決問題。
張引，浙江大學計算機科學與技術學院副教授，1999年于浙江大學計算機系取得計算機應用博士學位并留校工作至今。主要研究領域為圖形圖像、模式識別、數據分析與挖掘、知識表達與發現。
Frank M.Carrano是美國羅得島大學計算機科學系的榮譽退休教授，于1969年獲得美國錫拉丘茲大學計算機科學專業博士學位。他的興趣包括數據結構、計算機科學教育、社會問題的計算處理和數值計算。Carrano教授對計算機科學高年級本科課程的設計和交付特別感興趣，曾撰寫了多本著名的計算機科學專業的本科教材。
目 錄
第1章 袋子
袋子
袋子的行為
袋子的規格說明
接口
ADT袋子的使用
像使用自動售貨機一樣使用ADT
Java類庫： 接口Set
第2章 使用數組實現袋子
使用固定大小的數組實現ADT袋子
一個類比
一組核心方法
核心方法的實現
核心方法的測試
更多方法的實現
刪除物品的方法
使用可變大小的數組實現ADT袋子
調整數組的大小
袋子的一種新的實現
使用數組實現ADT袋子的優缺點
第3章 使用鏈表實現袋子
鏈表
通過添加節點到表頭來創建鏈表
ADT袋子的鏈表實現
私有的類Node
類LinkedBag的概要
一些核心方法的定義
核心方法的測試
方法getFrequencyOf
方法contains
從鏈表中刪除物品
方法remove和clear
具有方法set和get的類Node
使用鏈表實現ADT袋子的優缺點
第4章 算法的效率
動機
算法效率的度量
基本操作次數的統計
最好、 最壞和平均情況
大O表示法
程序結構的復雜度
效率的圖形化表示
ADT袋子不同實現的效率
基于數組的實現
基于鏈表的實現
兩種實現方法的比較
第5章 棧
ADT棧的規格說明
利用棧處理代數表達式
應用問題： 中綴代數表達式中括號平衡的
檢查
應用問題： 中綴表達式向后綴表達式的
轉換
應用問題： 后綴表達式的求值
應用問題： 中綴表達式的求值
程序棧
Java類庫： 類Stack
第6章 棧的實現
基于鏈表的實現
基于數組的實現
基于向量的實現
Java類庫： Vector類
使用向量實現ADT棧
第7章 遞歸
什么是遞歸
跟蹤一個遞歸方法
有返回值的遞歸方法
遞歸地處理一個數組
遞歸地處理一個鏈表
遞歸方法的時間效率
countDown的時間效率
計算xn的時間效率
一個復雜問題的簡單解決方案
一個簡單問題的拙劣解決方案
尾遞歸
間接遞歸
使用棧代替遞歸
第8章 排序引論
組織Java對數組排序的方法
選擇排序
迭代選擇排序
遞歸選擇排序
選擇排序的效率
插入排序
迭代插入排序
遞歸插入排序
插入排序的效率
鏈表的插入排序
希爾排序
Java代碼
希爾排序的效率
算法比較
第9章 快速排序方法
歸并排序
數組的歸并
遞歸的歸并排序
歸并排序的效率
迭代的歸并排序
Java類庫中的歸并排序
快速排序
快速排序的效率
創建劃分
快速排序的Java代碼
Java類庫中的快速排序
基數排序
基數排序的偽代碼
基數排序的效率
算法比較
第10章 隊列、 雙端隊列和優先隊列
ADT隊列
解決問題： 模擬排隊
解決問題： 計算出售股票時的資本
增益（一）
Java類庫： 接口Queue
ADT雙端隊列
解決問題： 計算出售股票時的資本
增益（二）
Java類庫： 接口Deque
Java類庫： ArrayDeque類
ADT優先隊列
解決問題： 跟蹤你的作業
Java類庫： 類PriorityQueue
第11章 隊列、 雙端隊列和優先隊列的
實現
基于鏈表隊列的實現
基于數組隊列的實現
循環數組
有一個未使用存儲單元的循環數組
基于向量隊列的實現
基于循環鏈表隊列的實現
由兩部分構成的循環鏈表
Java類庫： 類AbstractQueue
基于雙向鏈表雙端隊列的實現
實現優先隊列的可用方法
第12章 線性表
ADT線性表的規格說明
使用ADT線性表
Java類庫： List接口
Jave類庫： ArraryList類
第13章 用數組實現線性表
用數組實現ADT線性表
一個類比
Java實現
用數組實現ADT線性表的效率
用Vector實現ADT線性表
第14章 用鏈表實現線性表
操作鏈表節點
在多種位置加入節點
在多種位置刪除節點
私有方法getNodeAt
開始實現
數據域和構造函數
在列表結尾加入
在列表給定位置加入
方法isEmpty和toArray
測試核心方法
繼續實現
一個更好的實現
尾引用
用鏈表實現ADT列表的效率
Java類庫： 類LinkedList
第15章 迭代器
迭代器是什么
Iterator接口
使用Iterator接口
獨立類迭代器
內部類迭代器
基于鏈表實現
基于數組實現
為什么迭代器方法在它們自己的
類中
ListIterator接口
使用ListIterator接口
ListIterator接口基于數組的實現
內部類
Java類庫： Iterable接口
Iterable和for-each循環
修改版接口List
第16章 有序表
ADT有序表的規格說明
使用ADT有序表
鏈表實現
方法add
鏈表實現的效率
使用ADT線性表的實現
效率問題
第17章 繼承及線性表
使用繼承實現有序表
設計一個基類
創建一個抽象基類
有序表的一種高效實現
方法add
第18章 查找
問題引入
查找無序數組
無序數組的迭代式順序查找
無序數組的遞歸式順序查找
順序查找數組的效率
查找有序數組
有序數組的順序查找
有序數組的二分查找
Java類庫： 方法binarySearch
二分查找數組的效率
查找無序鏈表
無序鏈表的迭代式順序查找
無序鏈表的遞歸式順序查找
順序查找鏈表的效率
查找有序鏈表
有序鏈表的順序查找
二分查找有序鏈表
查找方法的選擇
第19章 詞典
ADT詞典規格說明
Java接口
迭代器
使用ADT詞典
問題解決： 電話號碼本
問題解決： 詞頻
問題解決： 詞的索引
Java類庫： Map接口
第20章 詞典的實現
基于數組的實現
一個無序數組詞典
一個有序數組詞典
基于向量的實例
鏈式實例
一個無序鏈式詞典
一個有序鏈式詞典
第21章 散列概述
散列是什么
散列函數
計算散列碼
將散列碼壓縮成散列表的索引
處理沖突
用線性探測實現開放定址
用二次探測實現開放定址
用雙重散列實現開放定址
開放定址的潛在問題
鏈地址
第22章 用散列實現詞典
散列的效率
容載分析
開放定址消耗分析
鏈地址消耗分析
再散列
不同沖突解決方案的對比
用散列實現詞典的實例
散列表中的條目
數據域和構造函數
getValue， remove和add方法
迭代器
Java類庫： HashMap類
Java類庫： HashSet類
第23章 樹
樹的概念
層次化的數據組織
樹的術語
樹的遍歷
遍歷二叉樹
一般樹的遍歷
樹的Java接口
樹的通用接口
二叉樹的接口
二叉樹的例子
表達式樹
決策樹
二叉查找樹
堆
一般樹的例子
語法分析樹
游戲樹
第24章 樹的實現
二叉樹的節點
節點的接口
二叉樹節點的實現
ADT二叉樹的實現
創建基本二叉樹
privateSetTree方法
訪問器與更改器方法
計算高度和節點數
遍歷
表達式樹的實現
一般樹
一般樹的節點
用二叉樹表示一般樹
第25章 二叉查找樹的實現
開始
二叉查找樹接口
重復的條目
開始類定義
查找和檢索
遍歷
添加條目
遞歸實現
迭代實現
刪除條目
刪除一個葉子節點的條目
刪除節點有一個孩子的條目
刪除節點有兩個孩子的條目
刪除為根的條目
遞歸實現
迭代實現
操作的效率
平衡的重要性
節點添加的順序
ADT詞典實現
第26章 堆的實現
再論ADT堆
用數組表示堆
插入條目
刪除根
創建堆
堆排序
第27章 平衡查找樹
AVL樹
單旋轉
雙旋轉
實現細節
2-3樹
查找2-3樹
添加條目至2-3樹
添加時分裂節點
2-4樹
添加條目至2-4樹
比較AVL， 2-3和2-4樹
紅黑樹
紅黑樹的性質
添加條目到紅黑樹
Java類庫： TreeMap類
B樹
第28章 圖
一些示例和術語
公路線路圖
航空線路圖
迷宮
樹
遍歷
廣度優先遍歷
深度優先遍歷
拓撲排序
路徑
尋找路徑
無權圖的最短路徑算法
加權圖中的最短路徑
ADT圖的Java接口
第29章 圖的實現
兩種實現的概述
鄰接矩陣
鄰接表
頂點和邊
類Vertex的規格說明
內部類Edge
實現Vertex類
ADT圖的實現
基本操作
圖算法在 線 部 分
第30章 可變的、 不可變的和可復制的對象（英文版本）
附錄A Java基礎
附錄B Java類
附錄C 從已有類創建新類
附錄D 類的設計
附錄E 異常處理
附錄F 文件輸入與輸出
附錄G 文檔與程序設計風格
新書資訊