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