图灵社区会员 sumika([email protected]) 专享 尊重版权 图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 图灵社区会员 sumika([email protected]) 专享 尊重版权 图灵社区会员 sumika([email protected]) 专享 尊重版权 图灵程序设计丛书 Learning JavaScript Data Structures and Algorithms Second Edition 学习JavaScript数据结构与算法 （第 2 版） 邓钢 [巴西] Loiane Groner 著 孙晓博 袁源 吴双 陈迪 译 人民邮电出版社 北 京 图灵社区会员 sumika([email protected]) 专享 尊重版权 内 容 提 要 本书首先介绍了 JavaScript 语言的基础知识以及 ES6 和 ES7 中引入的新功能，接下来讨论了数组、栈、 队列、链表、集合、字典、散列表、树、图等数据结构，之后探讨了各种排序和搜索算法，包括冒泡排序、 选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索， 然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程，最后还介绍了如何计算算法的复杂度。 本书适用于前端 Web 开发人员，以及所有对 JavaScript 数据结构与算法感兴趣的读者。 [巴西] Loiane Groner 译 邓 钢 孙晓博 吴 双 陈 迪 袁 源 责任编辑 岳新欣 责任印制 彭志环 北京市丰台区成寿寺路11号 ◆ 人民邮电出版社出版发行 ◆ 著 邮编 100164 网址 http://www.ptpress.com.cn 北京 电子邮件 [email protected] 印刷 ◆ 开本：800×1000 1/16 印张：14.5 字数：342千字 印数：5 601 — 9 100册 著作权合同登记号 2017年 9 月第 2 版 2017年 9 月北京第 1 次印刷 图字：01-2017-5589号 定价：49.00元 读者服务热线：(010)51095186转600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广登字 20170147 号 图灵社区会员 sumika([email protected]) 专享 尊重版权 错误！文档中没有指定样式的文字。 1 1 版权声明 2 3 Copyright © 2016 Packt Publishing. First published in the English language under the title Learning JavaScript Data Structures and Algorithms, Second Edition. Simplified Chinese-language edition copyright © 2017 by Posts & Telecom Press. All rights reserved. 4 5 本书中文简体字版由Packt Publishing授权人民邮电出版社独家出版。未经出版者书面许可， 不得以任何方式复制或抄袭本书内容。 版权所有，侵权必究。 6 7 8 9 10 11 12 13 14 图灵社区会员 sumika([email protected]) 专享 尊重版权 160 前 言 致 谢 我要感谢父母这些年来对我的教育、指导和建议，帮助我成为一个更好、更专业的人。特别 要感谢我的丈夫给予我的耐心、支持和鼓励。我要感谢Packt出版社给我机会，让我能够就自己 真正钟爱的话题写书。感谢在图书创作、审阅和出版过程中帮助过我的所有人。 我还要感谢这本书以及我撰写的其他书的读者，感谢你们的支持和反馈。你们的反馈非常宝 贵，帮助我成长为一名更优秀的作者和专业人士。非常感谢！ 图灵社区会员 sumika([email protected]) 专享 尊重版权 前 言 1 1 前 言 2 3 JavaScript是当下最流行的编程语言之一。由于浏览器的原生支持（无需安装任何插件）， JavaScript也被称作“互联网语言”。JavaScript的应用非常广泛，不仅被用于前端开发，也被用到 服务器（Node.js）和数据库（MongoDB）环境中。 对任何专业技术人员来说，理解数据结构都非常重要。作为软件开发者，我们要能够借助编 程语言来解决问题，而数据结构是这些问题的解决方案中不可或缺的一部分。如果选择了不恰当 的数据结构，可能会影响所写程序的性能。因此，了解不同数据结构和它们的适用范围十分重要。 算法在计算机科学中扮演着非常重要的角色。解决一个问题有很多种方法，但有些方法会比 其他方法更好。因此，了解一下最著名的算法也很重要。 本书为数据结构和算法初学者所写，也为熟悉数据结构和算法，但想在JavaScript语言中使用 它们的人所写。 快乐地编码吧！ 4 5 6 7 8 本书结构 9 第1章“JavaScript简介”，讲述了JavaScript的基础知识，它们可以帮助你更好地学习数据结 构和算法，同时还介绍了如何搭建开发环境来运行书中的代码示例。 第2章“数组”，介绍了如何使用数组这种最基础且最常用的数据结构。这一章演示了如何 对数组声明、初始化、添加和删除其中的元素，还讲述了如何使用JavaScript语言本身支持的数 组方法。 第3章“栈” ，介绍了栈这种数据结构，演示了如何创建栈以及怎样添加和删除元素，还讨论 了如何用栈解决计算机科学中的一些问题。 第4章“队列” ，详述了队列这种数据结构，演示了如何创建队列，以及如何添加和删除队列 中的元素，还讨论了如何用队列解决计算机科学中的一些问题，以及栈和队列的主要区别。 第5章“链表” ，讲解如何用对象和指针从头创建链表这种数据结构。这一章除了讨论如何声 图灵社区会员 sumika([email protected]) 专享 尊重版权 10 11 12 13 2 前 言 明、创建、添加和删除链表元素之外，还介绍了不同类型的链表，例如双向链表和循环链表。 第6章“集合” ，介绍了集合这种数据结构，讨论了如何用集合存储非重复性的元素。此外， 还详述了对集合的各种操作以及相应代码的实现。 第7章“字典和散列表”，深入讲解字典、散列表及它们之间的区别。这一章介绍了这两种 数据结构是如何声明、创建和使用的，还探讨了如何解决散列冲突，以及如何创建更高效的散 列函数。 第8章“树” ，讲解了树这种数据结构和它的相关术语，重点讨论了二叉搜索树，以及如何在 树中搜索、遍历、添加和删除节点。如果想更深入地学习树（包括相关的算法），这一章还给出 了一些建议。 第9章“图” ，介绍了图这种数据结构和它的适用范围。这一章讲述了图的常用术语和不同表 示方式，探讨了如何使用深度优先算法和广度优先算法遍历图，以及它们的适用范围。 第10章“排序和搜索算法” ，探讨了常用的排序算法，如冒泡排序（包括改进版） 、选择排序、 插入排序、归并排序和快速排序。另外还介绍了搜索算法中的顺序搜索和二分搜索。 第11章“算法模式”，介绍了一些算法技巧和一些著名的算法。这一章讲解了什么是递归， 介绍了一些高级算法，如动态规划和贪心算法。 第12章“算法复杂度”，介绍了大O表示法的概念，以及本书实现算法的复杂度列表。这一 章还介绍了NP完全问题和启发式算法。最后，讲解了提升算法能力的诀窍。 准备工作 为学习本书，你可以设置三种不同的开发环境。你不需要设置所有这三种环境，可以选择其 一，也可以逐一尝试。 方法一，你需要一个浏览器，请从下面二选一：  Chrome（https://www.google.com/chrome/browser/）  Firefox（https://www.mozilla.org/en-US/firefox/new/） 方法二，你需要：  安装方法一中的任意一个浏览器；  安 装 一 个 Web 服 务 器 。 如 果 你 的 电 脑 里 没 有 安 装 过 Web 服 务 器 ， 推 荐 安 装 XAMPP （https://www.apachefriends.org）。 方法三，如果想安装一个纯JavaScript的环境，你需要完成下面几步。 图灵社区会员 sumika([email protected]) 专享 尊重版权 前 言 3  安装步骤一中的任意浏览器  安装Node.js（http://nodejs.org/） 1  安装好Node.js后，安装http-server开发包： npm install http-server -g 2 第1章还会对此进行更详细的介绍。 3 读者对象 本书的目标读者包括计算机科学专业的学生、刚刚开启职业生涯的技术人员，以及想探索 JavaScript最优能力的朋友。要想学好书中的算法，需要对JavaScript和编程逻辑有基本的了解。 4 5 排版约定 在本书中，你会发现一些不同的文本样式，用以区别不同种类的信息。下面举例说明。 6 正文中的代码、用户输入这样表示：“用isEmpty方法就可以判断内部数组的长度是否为0。 ” 代码段的格式如下： function Stack() { //这里是属性和方法 } 如果我们想让你重点关注代码段中的某个部分，会加粗显示： class Stack { constructor () { this.items = []; //{1} } push(element){ this.items.push(element); } //其他方法 } 7 8 9 10 所有的命令行输入或输出的格式如下： stack.push(5); stack.push(8); 新术语和重点词汇以黑体标示。 11 12 这个图标表示警告或需要特别注意的内容。 13 图灵社区会员 sumika([email protected]) 专享 尊重版权 4 前 言 这个图标表示提示或者技巧。 读者反馈 欢迎提出反馈。如果你对本书有任何想法，喜欢它什么，不喜欢它什么，请让我们知道。要 写出真正