前　　言
Data Structures and Problem Solving Using Java, Fourth Edition
本書是為計算機科學專業(yè)兩學期系列課程而設計的，從典型的數據結構開始，然后介紹高級數據結構和算法分析。它適用于2001年計算機課程項目（CC2001，ACM和IEEE的聯合項目）的最終報告所概述的“B.1導論課程”中兩門或三門課程系列中的課程。
數據結構課程的內容已經發(fā)展了很多年。雖然涉及主題時有普遍的共識，但在細節(jié)上仍存在相當大的分歧。被一致接受的主題之一是軟件開發(fā)原則，最突出的是封裝和信息隱藏的概念。算法方面，所有數據結構課程都傾向于包括運行時間分析、遞歸、基本排序算法和基本數據結構的介紹。許多大學提供高級課程，涵蓋更高層次的數據結構、算法及運行時間分析主題。本書的內容旨在涵蓋兩個層次的課程，所以不需要購買第二本教材。
雖然數據結構中最激烈的爭論圍繞著編程語言的選擇，但也需要做出其他基本選擇：
先介紹面向對象設計還是基于對象的設計。
數學嚴謹程度。
數據結構的實現和其用途之間的適當平衡。
與所選語言相關的編程細節(jié)（例如，GUI應該盡早使用）。
我編寫這本書時的目的是，希望從抽象思維及問題求解的視角提供數據結構和算法的實用性介紹。我試圖覆蓋關于數據結構、數據結構的分析及其Java實現的所有重要細節(jié)，但同時避開在理論上有趣但沒有廣泛應用的數據結構。在一門課程中，不可能覆蓋所有不同的數據結構，包括它們的使用及分析。所以，我設計了本書，讓教師在選擇主題時具有靈活性。教師需要在實踐和理論方面進行適當的平衡，然后選擇最適合課程的主題。正如我將在后面所討論的，我組織內容時會盡量減少各章之間的依賴性。
第4版更新
提供了關于使用類（第2章）、編寫類（第3章）及接口（第4章）的額外討論。
第6章包含了附加資料，討論了線性表的運行時間、映射的使用及Java Collections API中視圖的使用。
描述了Scanner類，貫穿全書的代碼使用了Scanner類。
第9章描述并實現了48位線性同余生成器，這是Java和C++庫中的一部分。
第20章有一些關于獨立鏈散列表及String hashCode方法的新資料。
對文字做了大量修訂，改進了上一版的文字表達。
在第一、二和四部分提供了更多新練習。
獨特的方法
我的基本前提是，所有語言中的軟件開發(fā)工具都帶有大型庫，而且許多數據結構都是這些庫的一部分。我設想最終將數據結構課程的重點從實現轉移到使用。在本書中，我采用了獨特的方法，將數據結構劃分為規(guī)范說明和后續(xù)實現，并利用了已有的數據結構庫Java Collections API。
第二部分的第6章討論了適合大部分應用的Collections API的子集。第二部分還涉及基本分析技術、遞歸和排序。第三部分包含使用Collections API數據結構的眾多應用程序。使用過的數據結構的Collections API的實現將在第四部分展示。因為Collections API是Java的一部分，所以學生可以在早期使用已有的軟件組件設計大型項目。
盡管本書中主要使用了Collections API，但本書既不是關于Collections API的書，也不是關于實現Collections API的入門教材。本書仍是一本強調數據結構及基本的問題求解技術的書。當然，用來設計數據結構的一般技術也適用于Collections API的實現，所以第四部分的幾章中包括了Collections API的實現。不過，教師可以選擇第四部分中沒有討論Collections API協(xié)議的更簡單的實現。用于介紹Collections API的第6章對理解第三部分中的代碼很重要。我試圖僅使用Collections API的基本部分。
很多教師更愿意選擇傳統(tǒng)的方法，即定義、實現然后使用每個數據結構。因為第三部分和第四部分的內容之間沒有依賴性，所以使用本書也可以用來講授傳統(tǒng)課程。
先導課
使用本書的學生應該具備面向對象或面向過程程序設計語言的知識。假設學生已經了解了基本特性，包括基本數據類型、運算符、控制結構、函數（方法），以及輸入輸出（但不一定是數組和類）。
學習過C++或Java的學生可能發(fā)現前四章的某些地方閱讀起來很輕松。不過，如果之前學過的課程中沒有涉及Java細節(jié)的部分，閱讀起來依然會相當困難。
學習過另一種語言的學生，應該從第1章開始，循序漸進。如果學生想使用一些Java參考書，那么第1章中給出了一些推薦。
離散數學的知識對本書的學習是有幫助的，但離散數學不是絕對必要的先導課。本書給出了幾個數學證明，且在更復雜的證明之前都進行了簡單的數學回顧。第7章和第19～24章需要一定程度的數學知識。教師可以選擇簡單跳過證明的數學內容，只給出結果。本書中的所有證明都清楚地標注出來。
Java
本書使用Java編程語言給出相關代碼。Java語言常常與C++進行比較。Java更有優(yōu)勢，程序員常常認為Java比C++更安全、更便攜、更易于使用。
在編寫本書時，使用Java需要做一些決定。所做的決定如下：
需要的編譯器版本最低是Java 5。請確保你正使用的編譯器與Java 5兼容。
不強調GUI。雖然GUI是Java中一個很好的特性，但它們似乎是實現細節(jié)，而不是核心數據結構的主題。我們在書中沒有使用Swing，但因為許多教師可能愿意使用，所以在附錄B中對Swing進行了簡短介紹。
不強調Applet。Applet使用GUI。另外，本書的重點是數據結構，而不是語言特性。愿意討論Applet的教師需要使用Java參考資料來進行補充。
沒有使用內部類。內部類主要用在Collections API的實現中，如果愿意的話，教師可以避免使用。
在介紹引用變量時討論了指針的概念。Java沒有指針類型，但有引用類型。不過，傳統(tǒng)上指針是數據結構中需要介紹的重要主題。在討論引用變量時我用其他語言說明了指針的概念。
沒有討論線程。計算機科學社區(qū)的有些成員在爭論，在入門級編程系列課程中，多線程計算是否應該成為核心主題。雖然在未來這是有可能的，但很少有入門級編程課程討論這個困難的主題。
Java 5的有些特性沒有用到。包括：
靜態(tài)引入。沒有使用是因為在我看來，它實際上讓代碼變得難讀。
枚舉類型。沒有使用是因為很少有地方能聲明客戶可用的公有枚舉類型。在少數幾個可能的地方，它似乎對代碼的可讀性沒有幫助。
本書的組織
本書在第一部分介紹Java和面向對象編程（特別是抽象）。在設計類和繼承之前，討論了基本類型、引用類型和一些預定義的類及異常。
在第二部分，討論了大O及算法范式，包括遞歸和隨機。用完整的一章介紹排序，有一章描述了基本的數據結構。我使用Collections API來表示數據結構的接口和運行時間。在本書的這些章節(jié)中，教師可以采取幾種方法來介紹其余的內容，包括以下兩種：
當描述每種數據結構時，討論第四部分中相應的實現（Collections API版本或更簡單的版本）。教師可以按照練習中的建議，要求學生以不同的方式擴展類。
展示如何使用每個Collections API類，并在課程后期介紹其實現。第三部分的案例研究可用來支持這種方法。由于每個現代Java編譯器都有完整的實現，因此教師可以在編程項目中使用Collections API。稍后給出使用這種方法的細節(jié)。
第五部分描述高級數據結構，如伸展樹、配對堆和不相交集合數據結構，如果時間允許，可以介紹這些內容，或者在后續(xù)課程中介紹。
各章結構組織
第一部分由四章組成，描述了貫穿本書所用的Java的基本內容。第1章描述基本類型，說明如何用Java編寫基本的程序。第2章討論引用類型，說明指針的一般概念—雖然Java沒有指針—以便學生能了解這個重要的數據結構主題；還說明了幾種基本的引用類型（字符串、數組、文件和Scanner），討論了異常的使用。第3章繼續(xù)這個討論，描述如何實現一個類。第4章說明了在設計層次關系中繼承的使用（包括異常類和I/O）及泛型組件。包括包裝類、適配器和裝飾器模式在內的設計模式的資料都在第一部分討論。
第二部分重點介紹基本算法和構成要素。第5章全面討論時間復雜度和大O符號，還討論并分析了二分搜索。第6章很重要，因為它涉及Collections API，并直觀討論了每個數據結構應該支持的操作的運行時間。（這些數據結構的實現，包括Collections API風格及簡化版本，都在第四部分提供。）這一章還介紹了迭代器模式及嵌套類、局部類和匿名類。內部類推遲到第四部分，屆時作為一種實現技術來討論。第7章先介紹歸納法證明，從而描述遞歸，還討論了分治、動態(tài)規(guī)劃和回溯。其中一節(jié)描述了幾個用于實現RSA加密系統(tǒng)的遞歸數值算法。對于許多學生來說，第7章后半部分的內容更適合后續(xù)課程。第8章描述并編寫代碼，分析了幾個基本排序算法，包括插入排序、希爾排序、歸并排序和快速排序，以及排序附帶的內容，還證明了排序的經典下界，并討論了選擇的相關問題。最后，第9章是個簡單的章節(jié)，討論了隨機數，包括它們的生成以及在隨機算法中的使用。
第三部分提供了幾個案例研究，每一章圍繞一個一般性的主題進行組織。第10章通過研究游戲說明了一些重要的技術。第11章通過研究檢查平衡符號的算法和經典的運算符優(yōu)先級解析算法，討論了棧在計算機語言中的使用，同時提供了這兩個算法的完整代碼實現。第12章討論了文件壓縮和交叉引用生成的基本實用程序，提供了二者的完整實現。第13章先觀察了一個可以被視為模擬的問題，然后研究了更經典的事件驅動模擬，從而對模擬進行了廣泛研究。最后，第14章說明了如何使用數據結構高效實現圖的幾種最短路徑算法。
第四部分呈現了數據結構的實現。第15章討論了作為一種實現技術的內部類，并說明了它們在實現ArrayList中的作用。在第四部分的其余章節(jié)中，提供了使用簡單協(xié)議（insert、 find、remove及它們的變形）的實現。有些情況下，（除了由于需要大量的操作而變得復雜之外）還提出了傾向于使用更復雜Java語法的Collections API實現。這部分還運用了數學知識，特別是在第19～21章，可以由教師決定是否跳過。第16章提供了棧和隊列的實現。這些數據結構首先使用擴展數組實現，然后使用鏈表實現。Collections API版本在第16章最后討論。第17章描述了一般鏈表。單鏈表用一個簡單的協(xié)議來說明，本章最后給出了使用雙向鏈表的更復雜的Collections API版本。第18章描述了樹