前言

在過去的幾年中，得益于Node.js和SpiderMonkey等平臺，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表、棧、隊列、圖等），也包括傳統的排序和查找算法。本書討論在使用JavaScript進行服務器端編程時，如何實現這些數據結構和算法。

JavaScript程序員會發現本書很有用，因為本書討論了在JavaScript語言的限制下，如何實現數據結構和算法。這些限制包括：數組即對象、無處不在的全局變量、基于原型的對象模型等。JavaScript作為一種編程語言，名聲有點“不大好”，但是本書展示了如何使用JavaScript語言中“好的一面”去實現高效的數據結構和算法，進而為JavaScript正名。

為什么要學習數據結構和算法

我假設本書的讀者中，有很多人沒接受過正規的計算機科學教育。如果你接受過，那么你已經知道了學習數據結構和算法為何如此重要。如果你沒有計算機科學學位或者沒有正規學習過計算機科學，那么請耐心讀完本節。

計算機科學家尼克勞斯 ·沃思（Nicklaus Wirth）寫過一本計算機程序設計教材，書名是《算法+數據結構=程序》（Algorithms+Data Structures=Programs, Prentice-Hall）。這個書名就概括了計算機編程的精要。除了“Hello world! ”等無關緊要的程序，任何一個有些規模的程序都需要某種類型的數據結構來保存程序中用到的數據，還需要一個或多個算法將數據從輸入轉換為輸出。

對于那些沒有在學校學習過計算機科學的程序員來說，唯一熟悉的數據結構就是數組。在處理一些問題時，數組無疑是很好的選擇，但對于很多復雜的問題，數組就顯得太過簡陋了。大多數有經驗的程序員都愿意承認這樣一個事實：對于很多編程問題，當他們想出一個合適的數據結構，設計和實現解決這些問題的算法就變得手到擒來。

二叉查找樹（BST）就是一個這樣的例子。設計二叉查找樹的目的是為了方便查找一組數據中的最小值和最大值，由這個數據結構自然引申出一個查找算法，該算法比目前最好的查找算法效率還要高。不熟悉二叉查找樹的程序員可能會使用一個更簡單的數據結構，但效率上就打了個折扣。

學習算法非常重要，因為解決同樣的問題，往往可以使用多種算法。對于高效程序員來說，知道哪種算法效率最高非常重要。比如，現在至少有六七種排序算法，如果知道快速排序比選擇排序效率更高，那么就會讓排序過程變得高效。又比如，實現一個線性查找的算法很簡單，但是如果知道有時二分查找可能比線性查找快兩倍以上，那你勢必會寫出一個更好的程序。

深入學習數據結構和算法，不僅可以知道哪種數據結構和算法更高效，還會知道如何找出最適合解決手頭問題的數據結構和算法。寫程序，尤其是用JavaScript寫程序時，經常需要權衡，知道了本書涵蓋的數據結構和算法的優缺點，在解決具體的編程問題時就容易做出正確的選擇。

閱讀本書需要的工具

本書使用的編程環境是基于SpiderMonkey JavaScript引擎的JavaScript shell。第1章提供了該shell的下載說明。也可以使用其他一些JavaScript Shell，比如Node.js提供的JavaScript shell，你只需自己對書中的程序做一些轉換，就能在Node.js上運行。除了JavaScript shell，再有一個用于編寫JavaScript程序的文本編輯器就夠了。

本書組織結構

· 第1章 簡單概述JavaScript語言，至少介紹了本書用到的JavaScript特性。這一章還展示了貫穿全書的編程風格。

· 第2章 討論計算機編程中最常見的數據結構：數組。數組是JavaScript原生的數據類型。

· 第3章 介紹我們實現的第一個數據結構：列表。

· 第4章 介紹棧。棧是一種貫穿計算機科學的數據結構，編譯器和操作系統的實現都用到了棧。

· 第5章 討論隊列。隊列是對你在銀行或雜貨店里所排隊伍的一種抽象。隊列廣泛應用于處理數據之前，必須先把數據按順序排成一隊的模擬軟件中。

· 第6章 介紹鏈表。鏈表是對列表的修改，鏈表里的每個元素都是一個單獨的對象，該對象和它兩邊的元素相連。當程序中需要插入和刪除多個元素時，使用鏈表非常高效。

· 第7章 展示如何實現和使用字典，字典是將數據存儲為鍵值對的數據結構。

· 實現字典的一種方法是通過散列表，第8章討論了如何實現散列表和在表中存儲數據的散列算法。

· 第9章 介紹集合。和數據結構相關的書通常不會介紹集合，但是當某個數據集不允許有重復元素出現時，使用集合是一個很好的選擇。

· 第10章 的重點是二叉樹和二叉查找樹。前面提到過，二叉查找樹是一種存儲有序元素的極佳選擇。

· 第11章 介紹圖和圖的算法。圖用來表示計算機網絡節點或者地圖上的城市等數據。

· 第12章 轉向算法，討論各種排序算法，包括簡單易實現但處理大數據集時效率不高的算法，以及適合處理大數據集的復雜算法。

· 第13章 的主題還是算法，不過這回是查找算法，比如線性查找和二分查找。

· 第14章 是本書的最后一章，討論兩種更高級的算法——動態規劃和貪心算法。這些算法能解決難題，通常的算法在面對這些問題時要么執行速度太慢，要么難于實現。我們會分析幾個用動態規劃和貪心算法解決的典型問題。

排版約定

本書使用的排版約定如下。

? 楷體

表示新的術語。

? 等寬字體

表示程序片段，也用于在正文中表示程序中使用的變量、函數名、命令行代碼、環境變量、語句和關鍵字等元素。

? 等寬粗體

表示應該由用戶逐字輸入的命令或者其他文本。

? 等寬斜體

表示應該由用戶輸入的值或根據上下文決定的值替換的文本。

使用代碼示例

可以在這里下載本書隨附的資料（代碼示例、練習題等）:https://github.com/oreillymedia/data_structures_and_algorithms_using_javascript。

讓本書助你一臂之力。也許你需要在自己的程序或文檔中用到本書中的代碼。除非大段大段地使用，否則不必與我們聯系取得授權。例如，無需請求許可，就可以用本書中的幾段代碼寫成一個程序。但是銷售或者發布O'Reilly圖書中代碼的光盤則必須事先獲得授權。引用書中的代碼來回答問題也無需授權。將大段的示例代碼整合到你自己的產品文檔中則必須經過許可。

使用我們的代碼時，希望你能標明它的出處，但不強求。出處一般包括書名、作者、出版商和ISBN，例如：Data Structure and Algorithms Using JavaScript , Michael McMillan著（O'Reilly,2014）。版權所有，978-1-449-36493-9。

如果還有關于使用代碼的未盡事宜，可以隨時與我們聯系：permissions@oreilly.com。

Safari? Books Online

Safari Books Online（http://www.safaribooksonline.com）是應需而變的數字圖書館。它同時以圖書和視頻的形式出版世界頂級技術和商務作家的專業作品。

Safari Books Online是技術專家、軟件開發人員、Web設計師、商務人士和創意人士開展調研、解決問題、學習和認證培訓的第一手資料。

對于組織團體、政府機構和個人，Safari Books Online提供各種產品組合和靈活的定價策略。用戶可通過一個功能完備的數據庫檢索系統訪問O'Reilly Media、Prentice Hall Profes-sional、Addison-Wesley Professional、Microsoft Press、Sams、Que、Peachpit Press、Focal Press、Cisco Press、John Wiley & Sons、Syngress、Morgan Kaufmann、IBM Redbooks、Packt、Adobe Press、FT Press、Apress、Manning、New Riders、McGraw-Hill、Jones &Bartlett、Course Technology以及其他幾十家出版社的上千種圖書、培訓視頻和正式出版之前的書稿。要了解Safari Books Online的更多信息，我們網上見。

聯系我們

請把對本書的評價和問題發給出版社。

美國：

O'Reilly Media, Inc.

1005 Gravenstein Highway North

Sebastopol, CA95472

中國：

北京市西城區西直門南大街2號成銘大廈C座807室（100035）

奧萊利技術咨詢（北京）有限公司

O'Reilly的每一本書都有專屬網頁，你可以在那兒找到本書的相關信息，包括勘誤表、示例代碼以及其他信息。本書的網站地址是：

http://oreil.ly/data_structures_algorithms_JS。

對于本書的評論和技術性問題，請發送電子郵件到：

bookquestions@oreilly.com

要了解更多O'Reilly圖書、培訓課程、會議和新聞的信息，請訪問以下網站：

http://www.oreilly.com

我們在Facebook的地址如下：http://facebook.com/oreilly

請關注我們的Twitter動態：http://twitter.com/oreillymedia

我們的YouTube視頻地址如下：http://www.youtube.com/oreillymedia

致謝

寫成本書，需要感謝很多人。首先要感謝我的組稿編輯Simon St. Laurent，他對本書充滿信心并鼓勵我開始寫作。Meghan Blanchette女士為了讓我按時完成寫作費盡心思，如果本書有過拖稿現象，那一定不是她的錯。Brian MacDonald做了很多工作讓本書變得通俗易懂，他編輯校訂了本書的一些章節，文字比我當初的更清晰。我還要感謝技術審稿人，他們閱讀了本書的全部文字和代碼，并且指出了行文和代碼表達不夠清楚的地方。我的同事Cynthia Fehrenbach將我簡陋的草圖繪制成現在精美、清晰的插圖，在本書將要出版的最后時刻，她還愿意重新繪制幾幅插圖，對此我要特別感謝她。最后，我要感謝在Mozilla工作的所有人，是他們設計了如此出色的JavaScript引擎和命令行工具，他們還為如何使用JavaScript語言和這個工具編寫了非常棒的文檔。