前言

數據結構與算法不僅僅是抽象概念。精通它們可以讓你寫出高效的代碼，從而讓軟件運行得更快，占用的內存更少。這對于如今的軟件應用非常重要，因為它們存在于更加移動化的平臺，并且要處理更多的數據。

但這一主題的大部分資料有一個通病——晦澀難懂。大多數教材使用了很多數學術語。如果你不是數學家，那么就很難明白它們到底在說什么。即便那些聲稱讓算法學習更加“簡單”的書，好像也都假定讀者學過高深的數學知識。很多人因此避開了這些概念。他們覺得自己還不夠“聰明”，無法理解它們。

然而事實上，數據結構與算法都可以歸結于常識。數學符號只是一種特定語言，所有數學知識都能用常識去解釋。在本書中，我將用常識（以及很多圖表）來解釋這些概念。我保證這樣學習起來既簡單又輕松。

一旦理解了概念，你就能寫出高效、快速并且優雅的代碼。你可以比較不同代碼的優劣，還能合理判斷特定情況下的最優解。

在本書中，我特地用更實際的方式來解釋概念，還介紹了你立刻就可以利用的一些思想。你當然能從書中學到計算機科學知識，但本書旨在讓看似抽象的概念變得更切實際。讀完本書后，你將能編寫出更好的代碼和更快速的軟件。

目標讀者

本書適合以下讀者。

• 計算機科學專業的學生，想要一本用簡潔語言解釋數據結構與算法的教材。本書可以作為你目前使用的“經典”教材的補充。
• 有編程基礎的初級開發者，想要學習計算機科學基礎，拓展編程知識和技巧，以提高編碼水平。
• 自學編程的開發者，未受過正規計算機科學教育（或者學過但是忘光了），想要借助數據結構與算法的力量讓代碼更優雅、更具擴展性。

無論你的水平如何，我都力求讓你能理解并享受本書。

新增內容

在英文版上一版出版后的幾年里，我曾給不同的受眾講授書中的內容。在此過程中，我不斷地優化自己的闡述，也發現了一些有趣而重要的新內容。而且也有人提出需要習題來實踐這些概念。

因此本書新增了如下內容。

• 上一版內容修正。為了敘述更清晰，我對上一版內容做了很多修改。盡管上一版確實讓這些復雜主題易于理解，我發現仍有改進的空間。

  上一版章節中的許多小節在本書中已經完全重寫，并且添加了一些全新的內容。我覺得光是這些改動就值得出版新版了。

   

• 新章節和新主題。本書新增了6章內容，介紹了一些我特別感興趣的主題。

  本書一直注重理論與實踐的結合，但我又加入了更多你可以直接投入實踐的內容。第7章和第20章這兩章專注于日常代碼，教你如何使用數據結構與算法知識寫出更高效的軟件。

  我在“遞歸”這一主題上使出了渾身解數。盡管上一版有一章介紹的是遞歸，但我又增加了全新的一章（第11章）來介紹如何編寫遞歸代碼。編寫遞歸代碼可能會困擾初學者，第11章會教你如何去做。據我所知沒有人寫過這一主題，所以我覺得這一章既獨特又有價值。第12章也是新增的，“動態規劃”這一主題很受歡迎，也是提高遞歸代碼效率的關鍵。

  數據結構的種類很多，我很難抉擇應該介紹哪些。不過，學習堆和字典樹的需求與日俱增，我也覺得它們很神奇，因此增加了第16章和第17章。

   

• 習題和答案。本書每章末尾都有習題，你可以用它們來實踐書中的內容。書末的附錄中提供了詳細解答。這兩個重要改動讓本書的學習體驗更加完整。

本書內容

正如你所想的那樣，本書講解了很多數據結構和算法。具體來說，結構如下。

第1章和第2章，解釋什么是數據結構和算法，并探索時間復雜度這一判斷算法效率的概念。在此過程中，我還會提到數組、集合以及二分查找。

第3章，用便于理解的方式介紹大O記法。大O記法的使用貫穿全書，因此這一章非常重要。

第4章、第5章和第6章，進一步學習大O記法，用它來給日常代碼提速。在此過程中，我會介紹不同的排序算法，比如冒泡排序、選擇排序和插入排序。

第7章，應用所學知識來分析真實代碼的效率。

第8章和第9章，討論另外幾個數據結構，比如哈希表、棧和隊列。我將展示它們對代碼速度和優雅程度的影響，以及如何使用它們解決實際問題。

第10章，介紹遞歸這一計算機科學的核心概念。我們會在這一章中分析遞歸，學習它在特定情況下的重要價值。第11章會講述如何編寫遞歸代碼，讓你免于困惑。

第12章，展示優化遞歸代碼、防止其失控的方法。第13章會展示如何用遞歸實現快速排序或是快速選擇這樣飛快的算法，提升你的算法開發能力。

接下來的幾章，即第14章、第15章、第16章、第17章和第18章，介紹鏈表、二叉查找樹、堆、字典樹、圖等基于節點的數據結構，以及它們各自的適用場景。

第19章，介紹空間復雜度。當設備磁盤空間相對較小，或是要處理大數據時，這一概念尤為重要。

最后一章，即第20章，介紹優化代碼效率的各種實用技巧，并為改進日常代碼提供新思路。

如何閱讀本書

你需要按順序閱讀本書。有些書的某些章節可以單獨翻閱或是跳過，但本書不行。本書中每一章的內容都需要前面的章節作為前置，而且本書的結構也經過巧妙設計，使得你可以一邊閱讀，一邊加深理解。

話雖這么說，后半部分的某些章并不互相依賴。下一頁的圖描述了各章間的依賴關系。

如果你想的話，那么確實可以跳過第10~13章。（哦！下一頁的這幅圖就是基于樹這一數據結構。第15章會對該圖進行介紹。）

還有一點很重要：為了讓本書易于理解，在首次介紹某個概念時，我不會一下子全部解釋清楚。有時，分析一個復雜概念的最佳方法就是循序漸進，理解了一部分之后再介紹下一部分。如果我定義了一個術語，那么在你學習完這個主題前，請先不要把它當作正式定義。

這樣做有利也有弊。為了讓本書更好懂，我會先過度簡化某些概念，然后再慢慢解釋，而不是確保每句話在學術意義上都完全正確。但也不用太擔心，因為最后你肯定能得到全面且準確的解釋。

代碼示例

本書中的概念并不局限于特定編程語言。因此我選擇用多種語言來展示書中的例子。這些語言包括Ruby、Python和JavaScript。如果你對這些語言有基本的認識就再好不過了。

盡管如此，我還是試著在編寫示例時遵循一條原則：即便你不熟悉這個例子所用的語言，應該也能看懂。為了達到這一目的，我沒有嚴格遵循每種語言最受歡迎的編程范式，因為某些范式可能會讓新接觸那種語言的人感到困惑。

我明白一本不停切換語言的書會帶來一定程度的思維轉換成本。不過，我覺得保持一本書在語言上的不可知性是很重要的。而且無論是什么語言，我都會試著讓代碼方便閱讀和理解。

在“代碼實現”小標題下有一些長一點兒的代碼片段。我當然希望你學習這些示例，但要閱讀下一部分并不需要理解每一行代碼。如果這些較長的代碼對你造成障礙，那么就暫時跳過（或者略讀）。

最后還有一點很重要：不是每個代碼片段都“適用于生產環境”。重點在于解釋清楚當前的概念。盡管我確實嘗試讓代碼盡量完整，還是可能漏掉一些邊界情況。肯定有一些地方能讓你做進一步優化，因此你可以盡情去做。

在線資源

本書網址是https://pragprog.com/titles/jwdsal2，你可以在上面找到本書的更多信息。還可以提交勘誤，比如內容上的建議或者拼寫錯誤，來幫助改進本書。1

1也可以通過圖靈社區本書主頁下載示例代碼或提交中文版勘誤。——編者注

更多信息

掃描下方二維碼，即可獲取電子書相關信息及讀者群通道入口。

致謝

雖然寫書這件事看起來好像是一個人的工作，但是如果沒有一路支持我的這么多人，本書就不可能付梓。感謝你們所有人。

感謝我美麗的妻子Rena，感謝你一路相伴，給予我情感上的支持。當我像個隱士一樣躲在黑暗中寫作時，你處理好了所有事情。感謝我可愛的孩子們：Tuvi、Leah、Shaya和Rami。感謝你們在我寫這本“酸法”書時展現的耐心。沒錯，我終于寫完了。

感謝我的父母：Howard Wengrow 先生和Debbie Wengrow 夫人。感謝你們激發我對計算機編程的興趣，并幫助我一路前行。你們可能不知道，正是因為你們在我9歲生日時幫我請了一位計算機家教，我才能走上這條職業道路，并且寫出本書。

感謝我妻子的父母：Paul Pinkus先生和Kreindel Pinkus夫人。感謝你們對我和我的家人一如既往的支持。你們的智慧和熱情對我來說意義非凡。

當第一次把書稿提交給Pragmatic Bookshelf出版公司時，我自以為寫得很好。但出版公司優秀的工作人員提出的建議以及需求讓本書變得更加出色，遠超我自己所能。感謝我的編輯Brian MacDonald，你教會了我正確的寫書方式。你的見解讓每個章節都變得更深刻。書中到處都能看到你付出的心血。感謝原主編Susannah Pfalzer和執行編輯Dave Rankin，你們讓我看到了本書的潛力，幫我把基于理論的書稿打造成一本適合普通程序員的書。感謝發行人Andy Hunt和Dave Thomas，感謝你們讓Pragmatic Bookshelf成為最棒、作者最愿意合作的出版公司，也感謝你們相信本書。

感謝天賦異稟的軟件開發者和藝術家Colleen McGuckin，感謝你把我拙劣的草圖變成美麗的數字圖像。你憑借高超的畫技和對細節的追求創作出了非凡的圖畫。要是沒有它們，本書肯定一文不值。

有許多專家對本書進行了評審，我感到非常幸運。你們的反饋非常到位，讓本書的內容變得盡可能準確。我要感謝你們對本書做出的貢獻。

第1版的評審人如下：Alessandro Bahgat、Ivo Balbaert、Alberto Boschetti、Javier Collado、Mohamed Fouad、Derek Graham、Neil Hainer、Peter Hampton、Rod Hilton、Jeff Holland、Jessica Janiuk、Aaron Kalair、Stephan K?mper、Arun S. Kumar、Sean Lindsay、Nigel Lowry、Joy McCaffrey、Daivid Morgan、Jasdeep Narang、Stephen Orr、Kenneth Parekh、Jason Pike、Sam Rose、Frank Ruiz、Brian Schau、Tibor Simic、Matteo Vaccari、Stephen Wolff和Peter W. A. Wood。

第2版的評審人如下：Rinaldo Bonazzo、Mike Browne、Craig Castelaz、Jacob Chae、Zulfikar Dharmawan、Ashish Dixit、Dan Dybas、Emily Ekhdal、Derek Graham、Rod Hilton、Jeff Holland、Grant Kazan、Sean Lindsay、Nigel Lowry、Dary Merckens、Kevin Mitchell、Nouran Mhmoud、Daivid Morgan、Brent Morris、Emanuele Origgi、Jason Pike、Ayon Roy、Brian Schau、Mitchell Volk和Peter W. A. Wood。

除了正式的評審人，還要感謝那些在我創作過程中，對書稿提出建議的讀者。你們的建議、評價和問題都是無價之寶。

還要感謝Actualize所有的職員、學生和校友的支持。本書原本是Actualize的一個項目，你們都曾通過不同方式參與其中。最后，特別感謝Luke Evans為我提供了創作本書的靈感。

感謝以上所有人讓本書得以出版。

聯系方式

我喜歡和讀者聯系，并且誠摯邀請你們在LinkedIn上聯系我。我很樂意通過你們的好友請求——只要發信息說你是本書讀者就行。我期待聽到你們的感想。

杰伊·溫格羅
jay@actualize.co
2020年5月