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