学习JavaScript数据结构与算法（第2版）

本书首先介绍了JavaScript 语言的基础知识以及ES6 和ES7 中引入的新功能，接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构，之后探讨了各种排序和搜索算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索，然后介绍了动态规划和贪心算法等常用的高-级算法以及函数式编程，zui后还介绍了如何计算算法的复杂度。　　本书适用于前端Web 开发人员，以及所有对JavaScript 数据结构与算法感兴趣的读者。

Loiane Groner 花旗银行软件开发经理，负责海外项目的开发和团队管理；原IBM公司系统分析师及团队负责人；巴西坎皮纳斯Java用户组（CampinasJUG）ling导者、圣埃斯皮里图Java用户组（ESJUG）协调人；巴西各大型技术会议特邀发言人；Sencha和Java技术布道者，通过博客（http://loianegroner.com）为软件开发社区撰稿，发表关于IT职业发展和常用开发技术的文章和视频。另著有《精通Ext JS》等书。

　　数据结构是计算机为了高效地利用资源而组织数据的一种方式。数据结构和算法是解决一切编程问题的基础。

　　本书首先介绍了JavaScript语言的基础知识，接着讨论了数组、栈、队列和链表等重要的数据结构，随后分析了集合、字典和散列表的工作原理，接下来阐述了什么是树以及如何使用二叉树和二叉搜索树，然后介绍了图、DFS和BFS算法，以及各种排序（冒泡排序、选择排序、插入排序、归并排序、快速排序等）和搜索（顺序搜索、二分搜索）算法，zui后介绍了动态规划和贪心算法等高ji算法。

　　相较上一版，这一版新增了ES6和ES7的新功能介绍，补充了ES6的当前实现。同时拓展了对树、图、排序算法、动态规划和贪心算法的讨论，增加了AVL树、Dijkstra算法、Floyd-Warshall算法、Prim算法、Kruskal算法、堆排序、分布式排序、背包问题、矩阵链相乘等内容。此外还概述了函数式编程、NP完全理论。

　　如果你是计算机科学专业的学生，或是刚刚开启职业生涯的技术人员，想探索JavaScript的zui佳能力，这本书一定适合你。

第1章JavaScript简介1

1．1JavaScript数据结构与算法1

1．2环境搭建2

1．2．1最简单的环境搭建2

1．2．2使用Web服务器（XAMPP）4

1．2．3使用Node．js搭建Web服务器5

1．3JavaScript基础6

1．3．1变量7

1．3．2操作符9

1．3．3真值和假值11

1．3．4相等操作符（==和===）12

1．4控制结构14

1．4．1条件语句14

1．4．2循环15

1．5函数16

1．6JavaScript面向对象编程17

1．7调试工具18

1．8ECMAScript概述19

1．9ECMAScript6的功能21

1．9．1用let替代var声明变量21

1．9．2常量23

1．9．3模板字面量23

1．9．4箭头函数24

1．9．5函数的参数默认值24

1．9．6声明展开和剩余参数25

1．9．7使用类进行面向对象编程27

1．10ECMAScript7的功能29

1．11小结30

第2章数组31

2．1为什么用数组31

2．2创建和初始化数组32

2．3添加元素33

2．3．1使用push方法33

2．3．2插入元素到数组首位34

2．4删除元素34

2．5在任意位置添加或删除元素36

2．6二维和多维数组36

2．6．1迭代二维数组的元素37

2．6．2多维数组38

2．7JavaScript的数组方法参考39

2．7．1数组合并39

2．7．2迭代器函数40

2．7．3ECMAScript6和数组的新功能42

2．7．4排序元素46

2．7．5搜索48

2．7．6输出数组为字符串49

2．8类型数组50

2．9小结51

第3章栈52

3．1栈数据结构52

3．1．1创建栈53

3．1．2向栈添加元素53

3．1．3从栈移除元素53

3．1．4查看栈顶元素54

3．1．5检查栈是否为空54

3．1．6清空和打印栈元素54

3．2ECMAScript6和Stack类56

3．3用栈解决问题59

3．4小结61

第4章队列62

4．1队列数据结构62

4．2创建队列63

4．2．1向队列添加元素63

4．2．2从队列移除元素63

4．2．3查看队列头元素64

4．2．4检查队列是否为空64

4．2．5打印队列元素64

4．3用ECMAScript6语法实现的Queue类66

4．4优先队列66

4．5循环队列——击鼓传花68

4．6JavaScript任务队列70

4．7小结70

第5章链表71

5．1链表数据结构71

5．2创建链表72

5．2．1向链表尾部追加元素73

5．2．2从链表中移除元素75

5．2．3在任意位置插入元素77

5．2．4实现其他方法79

5．3双向链表82

5．3．1在任意位置插入新元素82

5．3．2从任意位置移除元素85

5．4循环链表87

5．5小结88

第6章集合89

6．1构建数据集合89

6．2创建集合89

6．2．1has(value)方法90

6．2．2add方法91

6．2．3remove和clear方法91

6．2．4size方法92

6．2．5values方法93

6．2．6使用Set类93

6．3集合操作94

6．3．1并集94

6．3．2交集95

6．3．3差集97

6．3．4子集98

6．4ES6——Set类99

6．5小结101

第7章字典和散列表102

7．1字典102

7．1．1创建字典102

7．1．2使用Dictionary类105

7．2散列表106

7．2．1创建散列表106

7．2．2使用HashTable类108

7．2．3散列表和散列集合109

7．2．4处理散列表中的冲突109

7．2．5创建更好的散列函数117

7．3ES6——Map类118

7．4ES6——WeakMap类和WeakSet类118

7．5小结119

第8章树120

8．1树数据结构120

8．2树的相关术语121

8．3二叉树和二叉搜索树121

8．3．1创建BinarySearchTree类122

8．3．2向树中插入一个键123

8．4树的遍历126

8．4．1中序遍历126

8．4．2先序遍历127

8．4．3后序遍历128

8．5搜索树中的值129

8．5．1搜索最小值和最大值130

8．5．2搜索一个特定的值131

8．5．3移除一个节点133

8．6自平衡树137

8．6．1Adelson-Velskii-Landi树（AVL树）137

8．6．2更多关于二叉树的知识143

8．7小结143

第9章图144

9．1图的相关术语144

9．2图的表示146

9．2．1邻接矩阵146

9．2．2邻接表147

9．2．3关联矩阵148

9．3创建Graph类148

9．4图的遍历150

9．4．1广度优先搜索151

9．4．2深度优先搜索156

9．5最短路径算法162

9．5．1Dijkstra算法163

9．5．2Floyd-Warshall算法165

9．6最小生成树166

9．6．1Prim算法166

9．6．2Kruskal算法168

9．7小结169

第10章排序和搜索算法170

10．1排序算法170

10．1．1冒泡排序171

10．1．2选择排序174

10．1．3插入排序175

10．1．4归并排序176

10．1．5快速排序179

10．1．6堆排序183

10．1．7计数排序、桶排序和基数排序（分布式排序）186

10．2搜索算法187

10．2．1顺序搜索187

10．2．2二分搜索187

10．3小结189

第11章算法模式190

11．1递归190

11．1．1JavaScript调用栈大小的限制191

11．1．2斐波那契数列191

11．2动态规划193

11．2．1最少硬币找零问题194

11．2．2背包问题196

11．2．3最长公共子序列198

11．2．4矩阵链相乘200

11．3贪心算法202

11．3．1最少硬币找零问题203

11．3．2分数背包问题204

11．4函数式编程简介205

11．4．1函数式编程与命令式编程205

11．4．2ES2015和函数式编程206

11．4．3JavaScript函数式工具箱——

map、filter和reduce207

11．4．4JavaScript函数式类库和数据结构209

11．5小结209

第12章算法复杂度210

12．1大O表示法210

12．1．1理解大O表示法210

12．1．2时间复杂度比较212

12．1．3NP完全理论概述214

12．2用算法娱乐身心216

12．3小结217

JavaScript,计算机,算法,web,Web前端开发,Web前端