《數據結構與抽象（Java版）（第三版）》是2016年10月電子工業出版社出版的圖書，作者是張引。
基本介紹
- 書名：數據結構與抽象（Java版）（第三版）
- 作者：張引
- ISBN：9787121276163
- 頁數：632頁
- 定價：89元
- 出版社：電子工業出版社
- 出版時間：2016年10月
- 開本：16開
內容簡介,圖書目錄,
內容簡介
本書是為數據結構入門課程而編寫的教材。作者Frank Carrano在編寫過程自始至終特別考慮到了Java與對象，為教師和學生提供了一種精心設計並經過教學實驗的方式藉助Java講授ADT和對象。本書獨特的設計將內容組織為相對較短的章。這種方式使學習更容易，並留出了教學的機動性。本書教給學生如何使用線性表、詞典、棧、佇列等等來組織數據。利用這些數據組織方式，學生們將學到算法設計的相關技術。
圖書目錄
目 錄
第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 文檔與程式設計風格
