編輯推薦
隨著JavaScript成功走齣客戶端,在服務器端編程中得到日益廣泛的應用,JavaScript程序員需要實現與C#或Java等傳統麵嚮對象編程語言相似的數據結構與算法。本書是用JavaScript描述數據結構與算法的開山之作,匯聚瞭作者多年的實戰經驗。這本實戰指南通過豐富的示例,嚮讀者透徹講解瞭在JavaScript環境下,如何通過一係列存儲機製(包括鏈錶、棧、隊列和圖)高效地達到編程目的。
內容簡介
在過去幾年中,JavaScript憑藉Node.js和SpiderMonkey等平颱,在服務器端編程中得到瞭廣泛應用。JavaScript程序員因而迫切需要使用傳統語言(比如C++和Java)提供的工具,包括傳統的數據結構以及傳統的排序和查找算法。《圖靈程序設計叢書:數據結構與算法JavaScript描述》討論在數組即對象、無處不在的全局變量、基於原型的對象模型等JavaScript語言的環境下,如何實現高效的數據結構和算法。
《圖靈程序設計叢書:數據結構與算法JavaScript描述》適閤JavaScript程序員以及對JavaScript語言感興趣的學習者,特彆是在學校中沒有係統學習過計算機科學相關課程的“跨界”程序員。
作者簡介
麥剋米倫(Michael McMillan),作為大學老師和程序員,曾編寫過多部受到好評的數據結構與算法圖書,包括Data Structures and Algorithms Using C#、Data Structures and Algorithms Using Visual Basic.NET,以及其他計算機教程,如Object-Oriented Programming with Visual Basic.NET、C++ Programming: An Introduction、Java Programming Tutorial、Perl from the Ground Up等。Michael現在阿肯色州北小石城普瓦斯基技術學院當講師,教授計算機信息係統。他還是北小石城阿肯色大學的兼職講師,教授信息科學。在做講師之前,他曾是阿肯色兒童醫院的一名程序設計師/分析師,負責統計計算和數據分析。
王群鋒,1981年生於陝西省富平縣橋西大隊三裏村,2004年畢業於西安電子科技大學。畢業後當瞭一名程序員,現居西安,在IBM西安研發中心從事下一代統計預測軟件的開發工作。
杜歡,淘寶網高級技術專傢,2012年加入淘寶,曾就職於雅虎颱灣及CISCO。對前端架構、前後端協作有自己的見解,專注於Web産品設計、可用性實施,熱愛標準化。
內頁插圖
精彩書評
★本書對前端工程師是非常好的數據結構與算法入門書籍,它的難度非常適閤前端工程師來補習基礎知識。
——程劭非,阿裏無綫事業部高級技術專傢
目錄
推薦序
前言
第1章 JavaScript的編程環境和模型
1.1 JavaScript環境
1.2 JavaScript編程實踐
1.2.1 聲明和初始化變量
1.2.2 JavaScript中的算術運算和數學庫函數
1.2.3 判斷結構
1.2.4 循環結構
1.2.5 函數
1.2.6 變量作用域
1.2.7 遞歸
1.3 對象和麵嚮對象編程
1.4 小結
第2章 數組
2.1 JavaScript中對數組的定義
2.2 使用數組
2.2.1 創建數組
2.2.2 讀寫數組
2.2.3 由字符串生成數組
2.2.4 對數組的整體性操作
2.3 存取函數
2.3.1 查找元素
2.3.2 數組的字符串錶示
2.3.3 由已有數組創建新數組
2.4 可變函數
2.4.1 為數組添加元素
2.4.2 從數組中刪除元素
2.4.3 從數組中間位置添加和刪除元素
2.4.4 為數組排序
2.5 迭代器方法
2.5.1 不生成新數組的迭代器方法
2.5.2 生成新數組的迭代器方法
2.6 二維和多維數組
2.6.1 創建二維數組
2.6.2 處理二維數組的元素
2.6.3 參差不齊的數組
2.7 對象數組
2.8 對象中的數組
2.9 練習
第3章 列錶
3.1 列錶的抽象數據類型定義
3.2 實現列錶類
3.2.1 append:給列錶添加元素
3.2.2 remove:從列錶中刪除元素
3.2.3 find:在列錶中查找某一元素
3.2.4 length:列錶中有多少個元素
3.2.5 toString:顯示列錶中的元素
3.2.6 insert:嚮列錶中插入一個元素
3.2.7 clear:清空列錶中所有的元素
3.2.8 contains:判斷給定值是否在列錶中
3.2.9 遍曆列錶
3.3 使用迭代器訪問列錶
3.4 一個基於列錶的應用
3.4.1 讀取文本文件
3.4.2 使用列錶管理影碟租賃
3.5 練習
第4章 棧
4.1 對棧的操作
4.2 棧的實現
4.3 使用Stack類
4.3.1 數製間的相互轉換
4.3.2 迴文
4.3.3 遞歸演示
4.4 練習
第5章 隊列
5.1 對隊列的操作
5.2 一個用數組實現的隊列
5.3 使用隊列:方塊舞的舞伴分配問題
5.4 使用隊列對數據進行排序
5.5 優先隊列
5.6 練習
第6章 鏈錶
6.1 數組的缺點
6.2 定義鏈錶
6.3 設計一個基於對象的鏈錶
6.3.1 Node類
6.3.2 LinkedList類
6.3.3 插入新節點
6.3.4 從鏈錶中刪除一個節點
6.4 雙嚮鏈錶
6.5 循環鏈錶
6.6 鏈錶的其他方法
6.7 練習
第7章 字典
7.1 Dictionary類
7.2 Dictionary類的輔助方法
7.3 為Dictionary類添加排序功能
7.4 練習
第8章 散列
8.1 散列概覽
8.2 HashTable類
8.2.1 選擇一個散列函數
8.2.2 一個更好的散列函數
8.2.3 散列化整型鍵
8.2.4 對散列錶排序、從散列錶中取值
8.3 碰撞處理
8.3.1 開鏈法
8.3.2 綫性探測法
8.4 練習
第9章 集閤
9.1 集閤的定義、操作和屬性
9.1.1 集閤的定義
9.1.2 對集閤的操作
9.2 Set類的實現
9.3 更多集閤操作
9.4 練習
第10章 二叉樹和二叉查找樹
10.1 樹的定義
10.2 二叉樹和二叉查找樹
10.2.1 實現二叉查找樹
10.2.2 遍曆二叉查找樹
10.3 在二叉查找樹上進行查找
10.3.1 查找最小值和最大值
10.3.2 查找給定值
10.4 從二叉查找樹上刪除節點
10.5 計數
10.6 練習
第11章 圖和圖算法
11.1 圖的定義
11.2 用圖對現實中的係統建模
11.3 圖類
11.3.1 錶示頂點
11.3.2 錶示邊
11.3.3 構建圖
11.4 搜索圖
11.4.1 深度優先搜索
11.4.2 廣度優先搜索
11.5 查找最短路徑
11.5.1 廣度優先搜索對應的最短路徑
11.5.2 確定路徑
11.6 拓撲排序
11.6.1 拓撲排序算法
11.6.2 實現拓撲排序算法
11.7 練習
第12章 排序算法
12.1 數組測試平颱
12.2 基本排序算法
12.2.1 冒泡排序
12.2.2 選擇排序
12.2.3 插入排序
12.2.4 基本排序算法的計時比較
12.3 高級排序算法
12.3.1 希爾排序
12.3.2 歸並排序
12.3.3 快速排序
12.4 練習
第13章 檢索算法
13.1 順序查找
13.1.1 查找最小值和最大值
13.1.2 使用自組織數據
13.2 二分查找算法
13.3 查找文本數據
13.4 練習
第14章 高級算法
14.1 動態規劃
14.1.1 動態規劃實例:計算斐波那契數列
14.1.2 尋找最長公共子串
14.1.3 背包問題:遞歸解決方案
14.1.4 背包問題:動態規劃方案
14.2 貪心算法
14.2.1 第一個貪心算法案例:找零問題
14.2.2 背包問題的貪心算法解決方案
14.3 練習
封麵介紹
前言/序言
在過去的幾年中,得益於Node.js和SpiderMonkey等平颱,JavaScript越來越廣泛地用於服務器端編程。鑒於JavaScript語言已經走齣瞭瀏覽器,程序員發現他們需要更多傳統語言(比如C++和Java)提供的工具。這些工具包括傳統的數據結構(如鏈錶、棧、隊列、圖等),也包括傳統的排序和查找算法。《圖靈程序設計叢書:數據結構與算法JavaScript描述》討論在使用JavaScript進行服務器端編程時,如何實現這些數據結構和算法。
JavaScript程序員會發現《圖靈程序設計叢書:數據結構與算法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章 實現字典的一種方法是通過散列錶,第8章討論瞭如何實現散列錶和在錶中存儲數據的散列算法。
第9章 介紹集閤。和數據結構相關的書通常不會介紹集閤,但是當某個數據集不允許有重復元素齣現時,使用集閤是一個很好的選擇。
第10章 重點是二叉樹和二叉查找樹。前麵提到過,二叉查找樹是一種存儲有序元素的極佳選擇。
第11章 介紹圖和圖的算法。圖用來錶示計算機網絡節點或者地圖上的城市等數據。
第12章 轉嚮算法,討論各種排序算法,包括簡單易實現但處理大數據集時效率不高的算法,以及適閤處理大數據集的復雜算法。
第13章 主題還是算法,不過這迴是查找算法,比如綫性查找和二分查找。
第14章 本書的最後一章,討論兩種更高級的算法——動態規劃和貪心算法。
這些算法能解決難題,通常的算法在麵對這些問題時要麼執行速度太慢,要麼難於實現。我們會分析幾個用動態規劃和貪心算法解決的典型問題。
《算法啓示錄:JavaScript驅動的計算思維解析》 在這本深入探討算法與數據結構的著作中,我們並非僅僅羅列枯燥的代碼與抽象的理論,而是旨在引領讀者踏上一段激發計算思維的奇妙旅程。本書以JavaScript為主要的編程語言載體,它以其易學易用的特性和廣泛的應用前景,成為瞭理解復雜算法概念的絕佳工具。我們將從最基礎的數據組織方式入手,逐步深入到高效的算法設計與分析,最終觸及現代軟件開發中至關重要的核心技術。 第一部分:數據的基石——理解與構建 萬丈高樓平地起,數據結構便是構建一切復雜軟件係統的基石。在本書的第一部分,我們將首先構建對數據最基本形態的深刻理解。 數組的奧秘與變奏: 從最熟悉的數組開始,我們將不僅僅停留在其作為綫性序列的定義。我們將深入探討動態數組的內存管理機製,瞭解其動態擴容的內在邏輯,以及在不同操作(如插入、刪除、查找)下的時間復雜度分析。在此基礎上,我們將引入鏈錶,作為數組的補充和延伸。鏈錶的動態性、節點間的連接方式,以及單嚮鏈錶、雙嚮鏈錶、循環鏈錶等不同變體,將為我們提供一種全新的數據組織視角。我們將詳細剖析它們在內存使用、插入刪除效率等方麵的優勢與劣勢,並通過JavaScript代碼實現,讓抽象的概念落地。 棧與隊列的先進後齣與先進先齣: 棧(LIFO)和隊列(FIFO)作為兩種基本而強大的綫性數據結構,在計算機科學中無處不在。我們將通過生動的比喻,例如“後進先齣的盤子堆”來解釋棧的工作原理,並演示其在函數調用棧、錶達式求值、括號匹配等經典場景中的應用。接著,我們將探討隊列,將其比作“排隊買票”,理解其在任務調度、消息隊列、廣度優先搜索等場景下的重要作用。本書將詳細闡述如何使用JavaScript數組或鏈錶來實現棧和隊列,並分析各自實現的效率。 遞歸的魅力與迴溯的智慧: 遞歸是解決許多問題的一種優雅而強大的方法,它允許函數調用自身來解決更小規模的相同問題。我們將從斐波那契數列、階乘等簡單例子入手,逐步引導讀者理解遞歸的定義、基本情況(base case)和遞歸步驟(recursive step)。更重要的是,我們將深入探討遞歸的效率問題,以及如何通過尾遞歸優化或迭代來避免棧溢齣。在遞歸的基礎上,我們將引入迴溯法,它是一種通過嘗試所有可能的解決方案,並在不符閤要求的路徑上“迴溯”來尋找最優解的算法策略。我們將通過解決經典的N皇後問題、數獨求解等實例,充分展現迴溯法的威力。 第二部分:算法的脈絡——設計與優化 理解瞭數據結構的組織方式,我們便可以開始探索如何高效地操作這些數據,這就是算法的範疇。本部分的重點在於算法的設計思想、實現方法以及性能分析。 排序的藝術: 排序是數據處理中最基本也是最常見的操作之一。我們將從簡單的冒泡排序、插入排序、選擇排序開始,理解它們的工作原理和時間復雜度。然後,我們將深入到更高效的排序算法,如快速排序和歸並排序。我們將詳細解析它們的分治思想,理解它們的平均時間復雜度與最壞時間復雜度,並對比分析它們的優劣。我們將提供JavaScript的實現,並探討原地排序與非原地排序的區彆。 查找的效率: 在海量數據中快速定位目標信息是至關重要的。本書將詳細介紹順序查找作為基礎,並重點講解二分查找。我們將強調二分查找的前提條件——有序數據,並深入剖析其對數級彆的時間復雜度是如何實現的。此外,我們還將探討哈希錶(散列錶)這一高效查找結構,理解哈希函數的設計原則、衝突解決方法(如鏈地址法、開放地址法),以及其在常數時間級彆進行插入、刪除和查找的奧秘。 樹的層級結構與遍曆: 樹是一種非綫性數據結構,它以層級的方式組織數據,在計算機科學中扮演著舉足輕重的角色。我們將從二叉樹的基本概念開始,理解節點、根節點、子節點、葉子節點等術語。隨後,我們將詳細講解二叉樹的各種遍曆方式:前序遍曆、中序遍曆和後序遍曆,並闡述它們在不同場景下的應用,例如中序遍曆可以實現有序輸齣。接著,我們將深入到更高級的樹結構,如二叉搜索樹(BST),理解其有序性帶來的查找效率優勢,並探討其在插入和刪除操作中可能齣現的性能退化問題。之後,我們將引齣平衡二叉搜索樹的概念,如AVL樹和紅黑樹,解釋它們如何通過自平衡機製來保證查找、插入和刪除操作的對數時間復雜度,雖然本書不深入講解其平衡機製的實現細節,但會闡述其重要性和基本原理。 圖的連接世界: 圖數據結構用於錶示對象之間的復雜關係。我們將介紹圖的基本概念,如頂點、邊、有嚮圖、無嚮圖、帶權圖等。我們將詳細講解兩種經典的圖遍曆算法:深度優先搜索(DFS)和廣度優先搜索(BFS)。DFS常用於查找路徑、連通性等問題,而BFS則常用於尋找最短路徑(在無權圖上)。我們將通過JavaScript代碼演示如何錶示圖(如鄰接矩陣和鄰接錶),以及如何實現DFS和BFS。在此基礎上,我們將觸及一些重要的圖算法,如Dijkstra算法(單源最短路徑)和Floyd-Warshall算法(所有頂點對最短路徑),理解它們解決實際問題的能力。 第三部分:算法的進階與應用 在掌握瞭基本的數據結構和算法後,我們將進一步探索更高級的算法設計範式,並探討它們在現代軟件開發中的實際應用。 動態規劃的優化之道: 動態規劃是一種通過將復雜問題分解為子問題,並存儲子問題的解來避免重復計算的算法設計技術。我們將從一個簡單的例子,如背包問題或爬樓梯問題開始,逐步引導讀者理解動態規劃的核心思想:最優子結構和重疊子問題。我們將演示如何通過構建狀態轉移方程來解決問題,並使用錶格(數組)來存儲中間結果。我們將通過更復雜的實例,如最長公共子序列、硬幣找零等,來鞏固動態規劃的應用。 貪心算法的局部最優解: 貪心算法是一種在每一步選擇當前狀態下最好或最可用的選項,從而希望達到全局最優解的算法設計方法。我們將通過活動選擇問題、霍夫曼編碼等經典例子,來理解貪心算法的工作原理。我們將探討貪心算法的適用條件,並強調並非所有問題都適閤使用貪心算法。 算法的分析與衡量: 理解算法的效率是至關重要的。本書將深入講解大O符號(Big O notation)的含義,它是衡量算法時間復雜度和空間復雜度的標準。我們將詳細解析常數時間O(1)、對數時間O(log n)、綫性時間O(n)、綫性對數時間O(n log n)、平方時間O(n^2)等不同復雜度級彆,並通過實例來展示不同算法在這些復雜度下的性能錶現。我們將強調為什麼理解時間復雜度的重要性,以及如何在實際開發中選擇更優的算法。 JavaScript在算法實踐中的優勢: JavaScript作為一門動態、弱類型的腳本語言,在算法的教學和實踐中展現齣其獨特的優勢。其簡潔的語法使得概念的錶達更加直觀,而其在前端和後端(Node.js)的廣泛應用,則讓學習到的算法知識能夠迅速落地。本書將充分利用JavaScript的特性,通過清晰、簡潔的代碼示例,讓讀者在動手實踐中加深對算法的理解。我們將討論在JavaScript中實現各種數據結構和算法時需要注意的性能細節,以及如何利用JavaScript的內置功能來優化代碼。 結語:計算思維的啓迪 《算法啓示錄:JavaScript驅動的計算思維解析》不僅僅是一本關於數據結構和算法的書籍,它更是一扇通往計算思維大門的鑰匙。我們希望通過對核心概念的深入淺齣地講解,配閤豐富的JavaScript代碼示例,能夠幫助讀者建立起嚴謹的邏輯思維能力,掌握解決復雜問題的係統方法,並培養齣能夠駕馭代碼、優化性能的工程素養。無論您是初學者,還是希望鞏固和提升自身技能的開發者,相信都能從本書中獲得寶貴的啓示,為您的編程之路注入更強的動力。