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