前言本書(shū)背后的哲理數(shù)據(jù)結(jié)構(gòu)與算法是過(guò)去幾十年來(lái)最重要的創(chuàng)新之一，是軟件工程師需要掌握 的基礎(chǔ)工具。但在我看來(lái)，大部分有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的書(shū)籍都太過(guò)于理論化、 太厚而且太自底向上化了： 太過(guò)于理論化 算法的數(shù)學(xué)分析基于簡(jiǎn)化的假設(shè)，這些假設(shè)限制了它在實(shí)踐中的實(shí)用性。 很多關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法的講解都忽略了其簡(jiǎn)單化而關(guān)注其數(shù)學(xué)基礎(chǔ)。在 本書(shū)中，我對(duì)這部分提出了最實(shí)用的講解而省略或不再?gòu)?qiáng)調(diào)其他方面內(nèi)容。太厚許多有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的書(shū)籍至少有 500 頁(yè)，一些甚至超過(guò) 1000 頁(yè)。 我重點(diǎn)關(guān)注的是我認(rèn)為對(duì)軟件工程師最有用的話題，這樣使得本書(shū)厚度很 薄。 太自底向上化 許多講述數(shù)據(jù)結(jié)構(gòu)的書(shū)關(guān)注于它是怎樣工作的（實(shí)現(xiàn)），而很少涉及怎樣 使用它們（接口）。在本書(shū)中，我采取了自頂向下策略，從接口開(kāi)始講起。 你在學(xué)習(xí) Java 集合框架中結(jié)構(gòu)的工作原理細(xì)節(jié)之前，先學(xué)到怎么使用它們。最后，有些書(shū)在講解這一話題時(shí)脫離了上下文而且沒(méi)有吸引力：只是一個(gè)又 一個(gè)煩人的數(shù)據(jù)結(jié)構(gòu)！我嘗試結(jié)合一個(gè) Web 搜索應(yīng)用來(lái)組織這個(gè)話題，從而 使其變得生動(dòng)有趣。Web 搜索應(yīng)用廣泛使用了數(shù)據(jù)結(jié)構(gòu)，并且是一個(gè)有趣而 重要的話題。Web 搜索應(yīng)用還帶來(lái)了一些通常不在初學(xué)數(shù)據(jù)結(jié)構(gòu)類的部分涉及的主題，包 括 Redis 的持久性數(shù)據(jù)結(jié)構(gòu)。對(duì)于該放棄什么內(nèi)容，我已經(jīng)做出了艱難的決定，但我已經(jīng)做出了一些妥協(xié)。 在本書(shū)中包括幾個(gè)大多數(shù)人永遠(yuǎn)不會(huì)使用的主題，但他們可能在技術(shù)面試中 需要知道這些內(nèi)容。對(duì)于這些主題，我既提出了傳統(tǒng)的做法，同時(shí)也給出了 我懷疑的理由。本書(shū)還介紹了軟件工程實(shí)踐的基本知識(shí)，包括版本控制和單元測(cè)試。大多數(shù) 章節(jié)包括一個(gè)練習(xí)，你可實(shí)踐所學(xué)的知識(shí)。每個(gè)練習(xí)都提供了檢查解決方案 的自動(dòng)測(cè)試。對(duì)于大多數(shù)練習(xí)，我在下一章的開(kāi)頭都介紹了我的解決方法。必備知識(shí)本書(shū)適用的讀者包括計(jì)算機(jī)科學(xué)及相關(guān)領(lǐng)域的大學(xué)生、專業(yè)的軟件工程師、 軟件工程培訓(xùn)師以及正在準(zhǔn)備技術(shù)面試的相關(guān)人員。在讀本書(shū)之前，你需要有很好的 Java 基礎(chǔ)。具體說(shuō)，你應(yīng)當(dāng)知道怎么定義一 個(gè)從已有類擴(kuò)展的新類或怎么實(shí)現(xiàn)一個(gè)接口。如果你對(duì) Java 編程已經(jīng)不熟悉 了，這里有兩本書(shū)你需要先學(xué)習(xí)一下： Downey 和 Mayfield 編寫(xiě)的《Think Java》(OReilly Media，2016)，適用 于沒(méi)有一點(diǎn)編程基礎(chǔ)的人。 Sierra 和 Bates 編寫(xiě)的《Head First Java》 (OReilly Media，2005)，適用 于學(xué)過(guò)另一種編程語(yǔ)言的人。如果你不熟悉 Java 的接口，你可能需要學(xué)習(xí) http://thinkdast.com/interface 上 提供的教程What Is an Interface?。詞匯方面的注釋：Interface（接口）一詞比較容易使人混淆。在應(yīng)用程序接口（API）中，它指提供一定功能的一組類和方法。在 Java 語(yǔ)言中，Interface（接口）還指一種語(yǔ)言特征，它與類相似，定義了 一組方法。你也應(yīng)該熟悉類型參數(shù)與通用類型。比如，你應(yīng)知道怎樣創(chuàng)建一個(gè)有類型 參數(shù)的對(duì)象，如 ArrayList。如果你對(duì)類型參數(shù)不熟悉，請(qǐng)參閱 http://thinkdast.com/types。你應(yīng)該熟悉 Java 集合框架（JCF），可參閱 http://thinkdast.com/collections。 特別是，你應(yīng)熟悉 List 接口、ArrayList 類和 LinkedList 類。你最好也應(yīng)該熟悉 Apache 的 Ant，它是 Java 的自動(dòng)編譯工具，可參閱 http:// thinkdast.com/anttut。你也應(yīng)該熟悉 JUnit，它是 Java 的單元測(cè)試框架，可參閱 http://thinkdast.com/ junit。使用書(shū)中的代碼本書(shū)的代碼在一個(gè) Git 庫(kù)中，參見(jiàn) http://thinkdast.com/repo。Git 是一個(gè)版本控制系統(tǒng)，它允許你跟蹤組成項(xiàng)目的文件。Git 控制下的一個(gè) 文件集稱為一個(gè)倉(cāng)庫(kù)（repository）。GitHub 是一個(gè)主機(jī)服務(wù)，為 Git 倉(cāng)庫(kù)提供了存儲(chǔ)空間和便捷的 Web 接口。它 提供了以下幾種使用代碼的方式： ? 可以按下 Fork 按鈕創(chuàng)建一個(gè) Git Hub 倉(cāng)庫(kù)的備份。如果你還沒(méi)有一個(gè) GitHub 賬戶，需要注冊(cè)一個(gè)。備份后，你將在 GitHub 上擁有自己的倉(cāng)庫(kù)， 可以使用它跟蹤你編寫(xiě)的代碼。然后你可以克隆這個(gè)倉(cāng)庫(kù)，將文件的一個(gè) 備份下載到你的計(jì)算機(jī)上。 ? 另一個(gè)做法是，可以不使用 Fork 備份而直接克隆倉(cāng)庫(kù)。如果你選擇這么做， 就不需要 GitHub 賬戶，但不能在 GitHub 上保存你的修改。 ? 如果你一點(diǎn)也不想使用 Git，可以按下 GitHub 頁(yè)或鏈接 http://think dast. com/zip 上的 Download 按鈕下載代碼的 ZIP 壓縮包。當(dāng)你克隆倉(cāng)庫(kù)或?qū)?ZIP 文件解壓后，就會(huì)找到一個(gè) ThinkDataStructures 目錄， 其下有一個(gè)子目錄 code。本書(shū)中的例子使用 Java 開(kāi)發(fā)工具包 7（Java SE Development Kit 7）開(kāi)發(fā)和測(cè) 試。如果你使用的是舊開(kāi)發(fā)版本，有些例子將不能運(yùn)行。如果你在使用一個(gè) 更新的版本，這些代碼都應(yīng)當(dāng)能正常運(yùn)行。本書(shū)使用約定本書(shū)使用以下排版約定：斜體（Italic）表示強(qiáng)調(diào)、按鍵、菜單選項(xiàng)、URL 網(wǎng)址和 email 地址。 黑體（Bold） 表示首次定義的新術(shù)語(yǔ)。 等寬字體（Constant width） 表示程序代碼清單，以及段落內(nèi)的文件名、文件擴(kuò)展，程序中的元素如變 量、函數(shù)名、數(shù)據(jù)類型、語(yǔ)句和關(guān)鍵字。等寬黑體 (Constant width bold)表示由用戶輸入的命令或其他文本。Safari 圖書(shū)在線Safari 圖書(shū)在線（www.safaribooksonline.com）是一個(gè)應(yīng)需而變的數(shù)字圖書(shū)館， 它以書(shū)籍和視頻的形式提供了來(lái)自全球范圍內(nèi)技術(shù)和企業(yè)領(lǐng)域資深作者撰寫(xiě) 的專業(yè)內(nèi)容。專業(yè)技術(shù)人員、軟件開(kāi)發(fā)人員、網(wǎng)頁(yè)設(shè)計(jì)師、商業(yè)和創(chuàng)意專業(yè)人士使用 Safari圖書(shū)在線作為研究解決問(wèn)題、學(xué)習(xí)和認(rèn)證培訓(xùn)的首要資源。Safari 圖書(shū)在線為企業(yè)、政府機(jī)構(gòu)、教育機(jī)構(gòu)和個(gè)人提供了一系列計(jì)劃和定價(jià) 方案。訂閱者可在一個(gè)快捷搜索的數(shù)據(jù)庫(kù)中獲得成千上萬(wàn)的書(shū)籍、培訓(xùn)視頻和 出版前的手稿，如 OReilly Media，Prentice Hall Professional，Addison- Wesley Professional，Microsoft Press，Sams，Que，Peachpit Press，F(xiàn)ocal Press，Cisco Press，John Wiley & Sons，Syngress，Morgan Kaufmann，IBM Redbooks，Packt，Adobe Press，F(xiàn)T Press，Apress，Manning，New Riders， McGraw-Hill，Jones & Bartlett，Course Technology 以及其他數(shù)百家出版社。 有關(guān) Safari 圖書(shū)在線的更多信息，請(qǐng)?jiān)L問(wèn)我們的網(wǎng)站。聯(lián)系方式請(qǐng)將您發(fā)現(xiàn)的問(wèn)題以及建議及時(shí)報(bào)告給出版商：美國(guó)：OReilly Media，Inc.1005 Gravenstein Highway North Sebastopol，CA 95472中國(guó)：北京市西城區(qū)西直門(mén)南大街2號(hào)成銘大廈C座807室（100035） 奧萊利技術(shù)咨詢（北京）有限公司發(fā)表評(píng)論或咨詢有關(guān)本書(shū)的技術(shù)問(wèn)題，請(qǐng)發(fā)送電子郵件至 bookquestions@ oreilly.com。關(guān)于我們的書(shū)籍、課程、會(huì)議和新聞的更多信息，請(qǐng)參閱我們的網(wǎng)站：http://www.oreilly.comhttp://www.oreilly.com.cn我們的 Facebook：http://facebook.com/oreilly。 我們的 Twitter：http://twitter.com/oreillymedia。我們的 YouTube：http://www.youtube.com/oreillymedia。致謝這本書(shū)是我在紐約 Flatiron 學(xué)校編寫(xiě)的全部課程內(nèi)容的一個(gè)改編版，這所學(xué)校 提供了各種與編程和 Web 開(kāi)發(fā)相關(guān)的在線課堂。他們基于這個(gè)材料有一個(gè)課 堂，提供在線開(kāi)發(fā)環(huán)境、來(lái)自講師和其他學(xué)生的幫助，以及結(jié)業(yè)證書(shū)。你可 在網(wǎng)站 http://flatironschool.com 上找到更多信息。 在 Flatiron 學(xué)校，Joe Burgess、Ann John 和 Charles Pletcher 提供了指導(dǎo)、 建議以及對(duì)初始版本從實(shí)現(xiàn)到測(cè)試整個(gè)過(guò)程的修改。感謝你們！ 非常感謝技術(shù)評(píng)論員 Barry Whitman、Patrick White 以及 Chris Mayfield， 他們發(fā)現(xiàn)了許多錯(cuò)誤并提供了許多有幫助的建議。當(dāng)然，書(shū)中還有錯(cuò)誤的 話，那是我的過(guò)失，與他們無(wú)關(guān)！ ? 感謝 OlinCollege 學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程的指導(dǎo)教師與學(xué)生們，他們閱 讀了本書(shū)并給出了有益的反饋意見(jiàn)。Charles Roumeliotis 為 OReilly 公司編輯了本書(shū)并作出了許多改進(jìn)。 如果你對(duì)本書(shū)有看法或評(píng)論，請(qǐng)發(fā)郵件到 feedback@greenteapress.com。