《數據結構與算法JavaScript描述》是2014年人民郵電出版社出版的圖書，作者是Michael McMillan。
基本介紹
- 書名：數據結構與算法JavaScript描述
- 作者：[美] Michael McMillan
- 譯者：王群鋒 / 杜 歡
- ISBN： 9787115363398
- 頁數：216
- 定價：49.00元
- 出版社：人民郵電出版社
- 出版時間：2014-8
- 裝幀：平裝
內容簡介,作者簡介,譯者簡介,目錄,作品試讀,
內容簡介
通過本書的學習，讀者將能自如地選擇最合適的數據結構與算法，並在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產品設計、可用性實施，熱愛標準化。
目錄
推薦序 XI
前言 XII
第1章 JavaScript的編程環境和模型 1
1.1 JavaScript環境 1
1.2 JavaScript編程實踐 2
1.2.1 聲明和初始化變數 3
1.2.2 JavaScript中的算術運算和數學庫函式 3
1.2.3 判斷結構 4
1.2.4 循環結構 6
1.2.5 函式 7
1.2.6 變數作用域 7
1.2.7 遞歸 9
1.3 對象和面向對象編程 10
1.4 小結 11
第2章 數組 13
2.1 JavaScript中對數組的定義 13
2.2 使用數組 13
2.2.1 創建數組 14
2.2.2 讀寫數組 15
2.2.3 由字元串生成數組 15
2.2.4 對數組的整體性操作 16
2.3 存取函式 17
2.3.1 查找元素 17
2.3.2 數組的字元串表示 18
2.3.3 由已有數組創建新數組 18
2.4 可變函式 19
2.4.1 為數組添加元素 19
2.4.2 從數組中刪除元素 20
2.4.3 從數組中間位置添加和刪除元素 21
2.4.4 為數組排序 21
2.5 疊代器方法 22
2.5.1 不生成新數組的疊代器方法 22
2.5.2 生成新數組的疊代器方法 25
2.6 二維和多維數組 27
2.6.1 創建二維數組 27
2.6.2 處理二維數組的元素 28
2.6.3 參差不齊的數組 29
2.7 對象數組 30
2.8 對象中的數組 31
2.9 練習 32
第3章 列表 33
3.1 列表的抽象數據類型定義 33
3.2 實現列表類 34
3.2.1 append：給列表添加元素 35
3.2.2 remove：從列表中刪除元素 35
3.2.3 find：在列表中查找某一元素 35
3.2.4 length：列表中有多少個元素 36
3.2.5 toString：顯示列表中的元素 36
3.2.6 insert：向列表中插入一個元素 37
3.2.7 clear：清空列表中所有的元素 37
3.2.8 contains：判斷給定值是否在列表中 37
3.2.9 遍歷列表 38
3.3 使用疊代器訪問列表 39
3.4 一個基於列表的套用 40
3.4.1 讀取文本檔案 40
3.4.2 使用列表管理影碟租賃 41
3.5 練習 44
第4章 棧 45
4.1 對棧的操作 45
4.2 棧的實現 46
4.3 使用Stack類 48
4.3.1 數制間的相互轉換 49
4.3.2 回文 50
4.3.3 遞歸演示 51
4.4 練習 52
第5章 佇列 53
5.1 對佇列的操作 53
5.2 一個用數組實現的佇列 54
5.3 使用佇列：方塊舞的舞伴分配問題 57
5.4 使用佇列對數據進行排序 61
5.5 優先佇列 63
5.6 練習 65
第6章 鍊表 67
6.1 數組的缺點 67
6.2 定義鍊表 67
6.3 設計一個基於對象的鍊表 69
6.3.1 Node類 69
6.3.2 LinkedList類 69
6.3.3 插入新節點 69
6.3.4 從鍊表中刪除一個節點 71
6.4 雙向鍊表 74
6.5 循環鍊表 78
6.6 鍊表的其他方法 79
6.7 練習 79
第7章 字典 81
7.1 Dictionary類 81
7.2 Dictionary類的輔助方法 83
7.3 為Dictionary類添加排序功能 85
7.4 練習 86
第8章 散列 87
8.1 散列概覽 87
8.2 HashTable類 88
8.2.1 選擇一個散列函式 88
8.2.2 一個更好的散列函式 91
8.2.3 散列化整型鍵 93
8.2.4 對散列表排序、從散列表中取值 95
8.3 碰撞處理 96
8.3.1 開鏈法 96
8.3.2 線性探測法 99
8.4 練習 100
第9章 集合 101
9.1 集合的定義、操作和屬性 101
9.1.1 集合的定義 101
9.1.2 對集合的操作 102
9.2 Set類的實現 102
9.3 更多集合操作 104
9.4 練習 107
第10章 二叉樹和二叉查找樹 109
10.1 樹的定義 109
10.2 二叉樹和二叉查找樹 111
10.2.1 實現二叉查找樹 111
10.2.2 遍歷二叉查找樹 113
10.3 在二叉查找樹上進行查找 116
10.3.1 查找最小值和最大值 116
10.3.2 查找給定值 117
10.4 從二叉查找樹上刪除節點 118
10.5 計數 120
10.6 練習 123
第11章 圖和圖算法 125
11.1 圖的定義 125
11.2 用圖對現實中的系統建模 127
11.3 圖類 127
11.3.1 表示頂點 127
11.3.2 表示邊 127
11.3.3 構建圖 128
11.4 搜尋圖 130
11.4.1 深度優先搜尋 130
11.4.2 廣度優先搜尋 133
11.5 查找最短路徑 135
11.5.1 廣度優先搜尋對應的最短路徑 135
11.5.2 確定路徑 135
11.6 拓撲排序 137
11.6.1 拓撲排序算法 137
11.6.2 實現拓撲排序算法 137
11.7 練習 141
第12章 排序算法 143
12.1 數組測試平台 143
12.2 基本排序算法 145
12.2.1 冒泡排序 145
12.2.2 選擇排序 148
12.2.3 插入排序 150
12.2.4 基本排序算法的計時比較 151
12.3 高級排序算法 153
12.3.1 希爾排序 153
12.3.2 歸併排序 158
12.3.3 快速排序 163
12.4 練習 167
第13章 檢索算法 169
13.1 順序查找 169
13.1.1 查找最小值和最大值 172
13.1.2 使用自組織數據 175
13.2 二分查找算法 177
13.3 查找文本數據 183
13.4 練習 185
第14章 高級算法 187
14.1 動態規劃 187
14.1.1 動態規劃實例：計算斐波那契數列 188
14.1.2 尋找最長公共子串 191
14.1.3 背包問題：遞歸解決方案 194
14.1.4 背包問題：動態規劃方案 195
14.2 貪心算法 196
14.2.1 第一個貪心算法案例：找零問題 196
14.2.2 背包問題的貪心算法解決方案 197
14.3 練習 199
封面介紹 200
前言 XII
第1章 JavaScript的編程環境和模型 1
1.1 JavaScript環境 1
1.2 JavaScript編程實踐 2
1.2.1 聲明和初始化變數 3
1.2.2 JavaScript中的算術運算和數學庫函式 3
1.2.3 判斷結構 4
1.2.4 循環結構 6
1.2.5 函式 7
1.2.6 變數作用域 7
1.2.7 遞歸 9
1.3 對象和面向對象編程 10
1.4 小結 11
第2章 數組 13
2.1 JavaScript中對數組的定義 13
2.2 使用數組 13
2.2.1 創建數組 14
2.2.2 讀寫數組 15
2.2.3 由字元串生成數組 15
2.2.4 對數組的整體性操作 16
2.3 存取函式 17
2.3.1 查找元素 17
2.3.2 數組的字元串表示 18
2.3.3 由已有數組創建新數組 18
2.4 可變函式 19
2.4.1 為數組添加元素 19
2.4.2 從數組中刪除元素 20
2.4.3 從數組中間位置添加和刪除元素 21
2.4.4 為數組排序 21
2.5 疊代器方法 22
2.5.1 不生成新數組的疊代器方法 22
2.5.2 生成新數組的疊代器方法 25
2.6 二維和多維數組 27
2.6.1 創建二維數組 27
2.6.2 處理二維數組的元素 28
2.6.3 參差不齊的數組 29
2.7 對象數組 30
2.8 對象中的數組 31
2.9 練習 32
第3章 列表 33
3.1 列表的抽象數據類型定義 33
3.2 實現列表類 34
3.2.1 append：給列表添加元素 35
3.2.2 remove：從列表中刪除元素 35
3.2.3 find：在列表中查找某一元素 35
3.2.4 length：列表中有多少個元素 36
3.2.5 toString：顯示列表中的元素 36
3.2.6 insert：向列表中插入一個元素 37
3.2.7 clear：清空列表中所有的元素 37
3.2.8 contains：判斷給定值是否在列表中 37
3.2.9 遍歷列表 38
3.3 使用疊代器訪問列表 39
3.4 一個基於列表的套用 40
3.4.1 讀取文本檔案 40
3.4.2 使用列表管理影碟租賃 41
3.5 練習 44
第4章 棧 45
4.1 對棧的操作 45
4.2 棧的實現 46
4.3 使用Stack類 48
4.3.1 數制間的相互轉換 49
4.3.2 回文 50
4.3.3 遞歸演示 51
4.4 練習 52
第5章 佇列 53
5.1 對佇列的操作 53
5.2 一個用數組實現的佇列 54
5.3 使用佇列：方塊舞的舞伴分配問題 57
5.4 使用佇列對數據進行排序 61
5.5 優先佇列 63
5.6 練習 65
第6章 鍊表 67
6.1 數組的缺點 67
6.2 定義鍊表 67
6.3 設計一個基於對象的鍊表 69
6.3.1 Node類 69
6.3.2 LinkedList類 69
6.3.3 插入新節點 69
6.3.4 從鍊表中刪除一個節點 71
6.4 雙向鍊表 74
6.5 循環鍊表 78
6.6 鍊表的其他方法 79
6.7 練習 79
第7章 字典 81
7.1 Dictionary類 81
7.2 Dictionary類的輔助方法 83
7.3 為Dictionary類添加排序功能 85
7.4 練習 86
第8章 散列 87
8.1 散列概覽 87
8.2 HashTable類 88
8.2.1 選擇一個散列函式 88
8.2.2 一個更好的散列函式 91
8.2.3 散列化整型鍵 93
8.2.4 對散列表排序、從散列表中取值 95
8.3 碰撞處理 96
8.3.1 開鏈法 96
8.3.2 線性探測法 99
8.4 練習 100
第9章 集合 101
9.1 集合的定義、操作和屬性 101
9.1.1 集合的定義 101
9.1.2 對集合的操作 102
9.2 Set類的實現 102
9.3 更多集合操作 104
9.4 練習 107
第10章 二叉樹和二叉查找樹 109
10.1 樹的定義 109
10.2 二叉樹和二叉查找樹 111
10.2.1 實現二叉查找樹 111
10.2.2 遍歷二叉查找樹 113
10.3 在二叉查找樹上進行查找 116
10.3.1 查找最小值和最大值 116
10.3.2 查找給定值 117
10.4 從二叉查找樹上刪除節點 118
10.5 計數 120
10.6 練習 123
第11章 圖和圖算法 125
11.1 圖的定義 125
11.2 用圖對現實中的系統建模 127
11.3 圖類 127
11.3.1 表示頂點 127
11.3.2 表示邊 127
11.3.3 構建圖 128
11.4 搜尋圖 130
11.4.1 深度優先搜尋 130
11.4.2 廣度優先搜尋 133
11.5 查找最短路徑 135
11.5.1 廣度優先搜尋對應的最短路徑 135
11.5.2 確定路徑 135
11.6 拓撲排序 137
11.6.1 拓撲排序算法 137
11.6.2 實現拓撲排序算法 137
11.7 練習 141
第12章 排序算法 143
12.1 數組測試平台 143
12.2 基本排序算法 145
12.2.1 冒泡排序 145
12.2.2 選擇排序 148
12.2.3 插入排序 150
12.2.4 基本排序算法的計時比較 151
12.3 高級排序算法 153
12.3.1 希爾排序 153
12.3.2 歸併排序 158
12.3.3 快速排序 163
12.4 練習 167
第13章 檢索算法 169
13.1 順序查找 169
13.1.1 查找最小值和最大值 172
13.1.2 使用自組織數據 175
13.2 二分查找算法 177
13.3 查找文本數據 183
13.4 練習 185
第14章 高級算法 187
14.1 動態規劃 187
14.1.1 動態規劃實例：計算斐波那契數列 188
14.1.2 尋找最長公共子串 191
14.1.3 背包問題：遞歸解決方案 194
14.1.4 背包問題：動態規劃方案 195
14.2 貪心算法 196
14.2.1 第一個貪心算法案例：找零問題 196
14.2.2 背包問題的貪心算法解決方案 197
14.3 練習 199
封面介紹 200
作品試讀
本章描述了JavaScript 的編程環境和基本的編程模組，本書的後續章節將使用這些知識定義各種數據結構和實現各種算法。1.1 JavaScript環境JavaScript 歷來是一種僅在瀏覽器里運行的程式語言。然而在過去的幾年中，這種情況發生了變化，JavaScript 發展為可以作為桌面程式執行，或者在伺服器上執行。本書就使用這樣一種類似的環境：JavaScript shell，這是由Mozilla 提供的綜合JavaScript 編程環境SpiderMonkey 中的一部分。打開SpiderMonkey 的每日構建頁面，滾動至頁面底部，根據你的計算機作業系統，下載相應的JavaScript shell。下載完成後，有兩種使用JavaScript shell 的方式。可以選擇在互動模式下使用shell，也可以將JavaScript 代碼保存在一個檔案中，使用shell 進行解釋執行。在命令提示符下輸入js，進入shell 的互動模式，命令行里將會出現js> 提示符，這時就可以輸入JavaScript 表達式和語句了。下面演示了和JavaScript shell 進行互動的典型場景： bash js> 1 1 js> 1+23 js> var num = 1; js> num*124 124 js> for (var i = 1; i < 6; ++i) { print(i); } 1 2 34 5 js>你可以輸入算術表達式，JavaScript shell 立即會對其進行求值。也可以輸入任意合法的JavaScript 語句，JavaScript shell 也會馬上求值。如果你想探索JavaScript 語句進而了解它們的工作原理，那么這種互動式shell 是很棒的選擇。完成後，輸入quit() 語句退出shell。另外一種使用JavaScript shell 的方式是用它解釋執行一段完整的JavaScript 程式，這也是我們在本書剩餘部分使用shell 的方式。使用JavaScript shell 解釋運行程式，首先需要創建一個包含完整JavaScript 程式的檔案。可以使用任何文本編輯器，但是要確保將檔案保存為普通文本檔案。唯一的要求是檔案名稱必須以.js 作為後綴。JavaScript shell 看到這種後綴才會知道檔案里是一段JavaScript 程式。檔案保存完成後，在命令行里輸入js 和檔案名稱，就可以解釋執行該JavaScript 程式了。比如，假設將前面提到的for 循環代碼片段保存成一個loop.js 檔案，在命令行里輸入： c:\js>js loop.js 則會產生如下輸出： 1 23 4 5 程式執行完成後，自動返回命令行控制台。
