JAVA面向對象數據結構完全學習教程

內容簡介

本書主要介紹傳統的和現代的數據結構方面的知識，重點介紹問題的解決和軟體的設計。從基礎知識開始並貫穿全書，介紹並擴展了許旋熱多Java功能的套用，如類、對象、泛型、多態、包、接口、庫中的類、繼承、異常和執行緒等。我們還在整個講解過程中使用統一建模語言（UML）類圖來幫助建模並可視化對象、類、接口、應用程式及其相互關係。

圖書目錄

Chapter 1 知識整理

1.1 類、對象和應用程式

類

統一方法

對象

應用程式

1.2 組織類

繼承

包

1.3 異常

處理異常狀況

異常與類：埋習笑實例

1.4 數據結構

非獨立實現的結構

獨立實現結構

數據結構的含義

1.5 基本結構化機制

記憶體

引用

數組

1.6 算法比較：增長階分析

測算法的時間效率

情況複雜度

輸入值的大小

算法比較 66

增長順序 68

選擇排序算法 69

常見的增長階 72

小結 73

習題 74

Chapter 2 抽象數據類型—棧

2.1 抽象愉禁章

信息隱藏

數據抽象

數據層次

前置條件和後置條件

Java接口

基於接口的多態性

2.2 棧

棧的操作

棧的用法

2.3 集合元素

常用集合

2.4 棧接口

異常情況

接口

套用實例

2.5 基於數組的棧實現

ArrayBoundedstack類

棧操作的定義

ArrayListStack類

2.6 應用程式：平衡表達式

平衡類

應用程式

軟體架構

2.7 鍊表

數組與鍊表

LLNode類

鍊表操作

2.8 基於連結的棧

LinkedStack類

壓棧操作

彈棧操作

其他棧操作

比較棧的實現方式

2.9 應用程式：後綴表達式評估器

討論

後綴表達式求值

後綴表達式求值算法

錯誤處理

PostFixEvaluator類

PFixCLI類

2.10 棧變體

重新審視棧抽象數據類型

Java棧類和集合框架

小結

習題

Chapter 3 遞歸

3.1 遞歸定義、算法和程式

遞歸定義

遞歸計算

遞歸程式

階乘的疊代解決方案

3.2 三個問題

驗證遞歸算法

確定輸入限制

編寫遞歸方法

調試遞歸方法

3.3 數組的遞歸處理

二分查找

3.4 鍊表的遞歸處理

鍊表的遞歸性質

鍊表遍歷

鍊表轉換

3.5 塔

算法

方法

程式

3.6 分形

丁字方形的分形

變體

3.7 移除遞歸

遞歸的工作原理

尾調用消除

直接使用棧

3.8 何時使用遞歸解決方案

遞歸開銷

低效算法

清晰度

小結

習題

Chapter 4 抽象數據類型—挨台朽歸佇列

4.1 佇列

佇列操作

使用佇列

4.2 佇列接口

套用實例

4.3 基於數組的隊甩埋蒸循列實現

ArrayBoundedQueue類

ArrayUnboundedQueue類連碑屑

4.4 互動式測試驅動程式

一般方法

ArrayBoundedQueue類的測試驅動

使用測試驅動程式

4.5 基於連結的佇列實現

入隊操作

出隊操作

循環鍊表佇列設計

比較佇列實現

4.6 應用程式：回文

回文類

應用程式

4.7 佇列變體

特殊情況

玻璃佇列

雙端佇列

雙向鍊表

Java庫集合框架佇列/雙端佇列

4.8 應用程式：平均等待時間

問題討論和示例

Customer類

模擬

測試

4.9 並發、干擾和同步

Counter類

Java執行緒

干擾

同步

同步佇列

並發與Java庫集合類

小結

習題

Chapter 5 抽象數據類型—集合

5.1 集合接口

集合的前提

接口

5.2 實現基於數組的集合

5.3 應用程式：辭彙密度

5.4 重新探討比較對象

函式equals

Comparable接口

5.5 基於排序數組的集合的實現

參比元素

實現

以“拷貝”或“引用”蜜屑紋的方式實現抽象數據類型

示例程式

5.6 基於連結的集合的實現

內部表示形式

運算

比較集合實現

5.7 集合變體

Java集合框架

Bag ADT

Set ADT

小結

習題

Chapter 6 抽象數據類型—列表

6.1 列表接口

疊代

列表假設

接口

6.2 列表實現

基於數組的實現

基於鍊表的實現

6.3 應用程式：紙牌和遊戲

Card類

CardDeck類

應用程式：排列Card Hand

應用程式：Higher or Lower

應用程式：一對牌有多罕見

6.4 基於數組的有序列表的實現

插入排序

不支持的操作

Comparator接口

構造函式

套用實例

6.5 列表變體

Java庫列表

鍊表變體

鍊表作為節點數組

6.6 應用程式：大整數

大整數

內部表示

LargeIntList類

LargeInt類

加法和減法

LargeIntCLI程式

小結

習題

Chapter 7 抽象數據類型—二叉搜尋樹

7.1 樹

樹的遍歷

7.2 二叉搜尋樹

二叉樹

二叉搜尋樹

二叉樹遍歷

7.3 二叉搜尋樹接口

接口 449

7.4 實現層級：基礎級

7.5 疊代法VS遞歸法的實現

size函式的遞歸法

size函式的疊代法

遞歸還是疊代

7.6 實現層級：剩餘的觀察函式

contains和get函式

遍歷

7.7 實現層級：轉換函式

add操作

remove操作

7.8 二叉搜尋樹的功能

重新討論文本分析實驗

插入順序和樹形

平衡二叉搜尋樹

7.9 應用程式：詞頻計數器

類WordFreq

應用程式

7.10 樹的變體

特定套用的變體 4

平衡搜尋樹

小結

習題

Chapter 8 抽象數據類型—Map

8.1 Map接口

8.2 Map的實現

無序數組

有序數組

無序鍊表

有序鍊表

二叉搜尋樹

以基於ArrayList的方式實現

8.3 應用程式：從字元串到字元串的Map

8.4 哈希法

衝突

8.5 哈希函式

數組大小

哈希函式

Java對哈希的支持

複雜度

8.6 基於哈希的Map

實現

使用HMap類

8.7 Map的變體

混合結構

Java對Map的支持

小結

習題

Chapter 9 抽象數據類型—優先權佇列

9.1 優先權佇列接口

使用優先權佇列

接口

9.2 優先權佇列的實現

無序數組

有序數組

有序鍊表

二叉搜尋樹

9.3 堆

9.4 堆的實現

二叉樹的非連結表示

實現堆

Enqueue（入隊）方法

Dequeue（出隊）方法

套用實例

堆VS優先權佇列的其他表示

小結

習題

Chapter 10 抽象數據類型—圖

10.1 圖的介紹

10.2 圖的接口

10.3 圖的實現

基於數組的實現

連結實現

10.4 應用程式：圖的遍歷

深度優先搜尋

廣度優先搜尋

10.5 應用程式：單源最短路徑問題

小結

習題

Chapter 11 排序和查找算法

11.1 排序

測試工具

11.2 簡單排序

選擇排序

冒泡排序

插入排序

11.3 O(Nlog2N )排序

合併排序

快速排序

堆排序

11.4 更多的排序思考

測試

效率

對象和引用

比較對象

穩定性

11.5 查找

順序查找

高機率排序

有序集合

哈希法

小結

習題

附錄A

附錄B

附錄C

附錄D

術語表

索引

編輯推薦

本書是面向對象數據結構編程經典教程，主要講解JAVA面向對象數據結構。

作者簡介

（美）內爾·黛爾 Nell Dale

德克薩斯大學奧斯汀分校計算機科學博士。她自 1975 年以來，一直在德克薩斯大學奧斯汀分校任教，同時專注於計算機科學教育、寫作。出版或參與出版過的專著有《Computer Science Illuminated》《Programming and Problem Solving withC++: Brief Edition》《C++ Plus Data Structures》等。

（美）奇普·威姆斯 Chip Weems

美國麻薩諸塞大學阿默斯特分校計算機科學專業副教授。在過去的 20 多年中，他教授了入門編程、軟體工程、計算機體系結構和並行處理等課程。自 1986 年以來，他與其他人合作編寫了 13 本教科書，幫助 100 多萬學生學習計算機編程。他的書已被譯成法語、西班牙語和俄語。他從事計算機體系結構、編譯器、並行處理和編譯器體系結構協同最佳化方面的研

究。出版或參與出版的專著有《Turbo Pascal》《Programmingand Problem Solving with C++》《Programming inC++》《C++ Plus Data Structures》等。

（美）丹尼爾·T·喬伊斯 Daniel T. Joyce

美國維拉諾瓦大學計算機科學系的副教授。喬伊斯的研究興趣是軟體工程，重點是軟體需求識別。此外，他還活躍於計算機科學教育界。

JAVA面向對象數據結構完全學習教程

基本介紹

內容簡介

圖書目錄

編輯推薦

作者簡介

編輯推薦

作者簡介

熱門詞條