本書主要介紹傳統(tǒng)的和現代的數據結構方面的知識,重點介紹問題的解決和軟件的設計。從基礎知識開始并貫穿全書,介紹并擴展了許多Java功能的應用,如類、對象、泛型、多態(tài)、包、接口、庫中的類、繼承、異常和線程等。還在整個講解過程中使用統(tǒng)一建模語言(UML)類圖來幫助建模并可視化對象、類、接口、應用程序及其相互關系。
JAVA面向對象數據結構編程經典教程,受到萬千讀者口碑檢驗!專業(yè)的人寫專業(yè)的書給專業(yè)的讀者!重印多次全新再造,去蕪存菁,重寫了大部分資料,另外新增大量數據結構相關鍵資料,幫助你深度掌握JAVA面向對象數據結構!
[ 美]內爾·黛爾 Nell Dale
得克薩斯大學奧斯汀分校計算機科學博士。她自 1975 年以來,一直在得克薩斯大學奧斯汀分校任教,同時專注于計算機科學教育、寫作。出版或參與出版過的專著有《Computer Science
Illuminated》《Programming and Problem Solving withC : Brief Edition》《C Plus Data Structures》等。
[ 美]奇普·威姆斯 Chip Weems
美國馬薩諸塞大學阿默斯特分校計算機科學專業(yè)副教授。在過去的 20 多年中,他教授了入門編程、軟件工程、計算機體系結構和并行處理等課程。自 1986 年以來,他與其他人合作編寫了 13 本教科書,幫助 100 多萬學生學習計算機編程。他的書已被譯成法語、西班牙語和俄語,F在,他從事計算機體系結構、編譯器、并行處理和編譯器體系結構協(xié)同優(yōu)化方面的研
究。出版或參與出版的專著有《Turbo Pascal》《Programmingand Problem Solving with C 》《Programming inC 》《C Plus Data Structures》等。
Chapter 1 知識整理
1.1 類、對象和應用程序
類
統(tǒng)一方法
對象
應用程序
1.2 組織類
繼承
包
1.3 異常
處理異常狀況
異常與類:實例
1.4 數據結構
非獨立實現的結構
獨立實現結構
數據結構的含義?
1.5 基本結構化機制
內存
引用
數組
1.6 算法比較:增長階分析
測算法的時間效率
情況復雜度
輸入值的大小
算法比較 66
增長順序 68
選擇排序算法 69
常見的增長階 72
小結 73
習題 74
Chapter 2 抽象數據類型—棧
2.1 抽象
信息隱藏
數據抽象
數據層次
前置條件和后置條件
Java接口
基于接口的多態(tài)性
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 鏈表的遞歸處理
鏈表的遞歸性質
鏈表遍歷
鏈表轉換
……
11.5 查找
順序查找
高概率排序
有序集合
哈希法
小結
習題
附錄A
附錄B
附錄C
附錄D
術語表
索引
抽象數據類型—隊列
知識目標
你可以
在抽象層次描述隊列和其實現
定義隊列接口
描述用數組實現隊列操作的算法
比較基于數組實現隊列的固定隊頭和浮動隊頭方法
說明如何用數組實現無界隊列
描述用鏈表實現隊列操作的算法
用增長階分析描述及比較隊列算法的效率
定義隊列中元素的間隔時間、服務時間、周轉時間和等待時間
說明并發(fā)線程如何互相干擾、引發(fā)出錯,以及如何預防該干擾
技能目標
你可以
用數組實現有界隊列抽象數據類型(ADT)
用數組實現無界隊列ADT
用鏈表實現無界隊列ADT
繪制圖表表示特定隊列實現的隊列操作效果
使用隊列ADT作為應用程序的一部分
給定到達時間和服務要求,計算隊列元素的周轉時間和等待時間
用隊列模擬系統(tǒng)調研真實世界中的隊列屬性
實現一個程序,它能正確使用線程以利用問題解決方案內置的平行性
本章我們將討論隊列。在邏輯上隊列與棧相對應,棧屬于“后進先出”結構,而
隊列屬于“先進先出”結構。在隊列中時間最長的元素就是最先移除的元素。與棧
一樣,隊列有多種與系統(tǒng)編程有關的重要用法,而且該結構也適用于其他多種應用
程序。
我們把隊列當成一種抽象數據類型,從抽象層次、應用層次和實現層次來對待。
在抽象層次,隊列用Java接口定義。我們將討論數種隊列應用程序,特別是探討如何
用隊列確定某個字符串是否屬于回文,并調研真實世界中的隊列屬性。我們將用兩種
基本方法實現隊列:數組和鏈表。除了用數組實現有界隊列之外,我們也會學習如何
用數組實現無界隊列。與我們處理視圖的正常順序有所不同,本章的最后一節(jié)討論了
如何使用隊列來保存旨在執(zhí)行并行的任務,而如果這種并行性能夠用于提高性能,我
們該如何使用Java來妥善利用并列。
4.1 隊列
在Chapter 2中學習的棧結構,通常是在同一端進行元素添加和移除。但如果我們
需要介紹一種有不同操作方式的集合,又該怎么辦呢?假設我們模擬洗車場洗車,車
輛從車場的一頭進去,從另一頭出來。元素從一端進入,再從相反的另一端出來的數
據結構稱為隊列。隊列數據結構,就跟洗車場一樣,其特點就是最先進去的元素(車
輛)是最先出來的元素(車輛)。
這種隊列的基本形式存在數種變體,為了進行區(qū)別,我們一般引用先進先出的隊
列。其他隊列版本將在第4.7節(jié)“隊列變體”和Chapter 9“抽象數據類型-優(yōu)先級隊
列”中進行介紹,F在我們把注意力集中在隊列的常見版本,即一般所說的“隊列”
是指先進先出的隊列。與棧的情況一樣,我們從三個層次把隊列視為一種抽象數據類
型:抽象、實現和應用層次。
隊列操作
書店的例子暗示了可以應用于隊列的兩種操作。首先,我們可以在隊尾添加新元
素,這個操作叫入隊(enqueue);其次,我們可以從隊頭移除元素,這個操作叫出隊
(dequeue)。圖4.2用方塊模擬隊列元素,向我們展示了上述操作對隊列產生的影響。
與棧操作的壓棧和退棧不一樣,隊列的添加和移除操作沒有標準的名稱。 enqueue
操作有時也會叫enq、 enque、 add(添加)或者insert(插入), dequeue的別稱也有
deq、 deque、 remove(移除)、或serve。
使用隊列
Chapter 2中討論了操作系統(tǒng)和編譯程序如何使用棧。同樣地,隊列也經常用于系
統(tǒng)編程。例如,某個操作系統(tǒng)通常備有隨時可執(zhí)行的處理隊列,或者等待特定事件發(fā)
生便可執(zhí)行的處理隊列。
另一個例子是,計算機系統(tǒng)通常必須提供“存儲區(qū)”,以存放在兩個處理進程、兩
個程序甚至兩個系統(tǒng)之間傳送的信息。這個存儲區(qū)通常稱為“緩存”,通常作為隊列實
現。例如,如果一個郵件伺服器在同一時間收到大量郵件信息,這些信息會先存放在
緩存區(qū),直到該郵件伺服器做好準備處理這些信息。如果伺服器是按照信息到達的先
后順序—先進先出的順序進行處理的話,那么該緩存就屬于隊列。
很多其他應用程序在處理之前都要先存儲請求。試想一下為顧客提供服務的應用
程序,比如出售飛機票或者電影票。這些應用程序通常會用隊列來處理請求。
如書店的例子所示,軟件所用的隊列在現實世界中有相對應的例子。類似的還有
我們要排隊買比薩、排隊進影院、排隊過收費站、排隊坐過山車等。隊列數據結構的
另一種重要應用是幫助我們模擬和分析現實世界的這些隊列,有關這點我們將在第4.8
節(jié)“應用程序:平均等待時間”中的范例應用中介紹。
4.2 隊列接口
本節(jié)將正式指定隊列ADT。除了enqueue和dequeue操作與push、 pop和top不同之
外,隊列所使用的基本方法與棧ADT一樣:
隊列都是泛型的—特定隊列持有的對象類型在該隊列實例化時由客戶端指示。
定義支持隊列的類在ch04.queues package中成組呈現。
提供觀察函數操作size(大。,以便應用程序確定隊列的大小。隊列的大小對于
應用程序而言很重要,因為它意味著元素可以待在隊列多久。
提供觀察函數操作isEmpty(為空)和isFull(為滿),以便客戶端在合適的情況下
能夠預防自己嘗試從空隊列中移除元素,或者在滿隊列中添加元素。
創(chuàng)建QueueUnderflowException(隊列下溢異常)和QueueOverflowException(隊列
溢出異常)兩個類。
創(chuàng)建一個QueueInterface(隊列接口),定義隊列方法的特征。實現隊列應該要實
現這個接口。
兩個異常類的代碼基本上與Chapter 2中棧所用的兩個異常類的代碼一樣,所以這
里不予展示。與棧的情況一樣,應用程序員能夠在訪問隊列之前,決定使用isFull和
isEmpty兩個觀察函數來預防出現問題,或者應用程序能夠嘗試訪問操作,“捕獲并處
理”引發(fā)的異常。
以下為QueueInterface。該接口定義隊列五個方法的特征—enqueue、 dequeue、
isEmpty、 isFull和size。