作者：格罗纳（Loiane Groner）
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
学习JavaScript数据结构与算法试读：
前言
JavaScript是当下最流行的编程语言。由于浏览器的原生支持（无需安装任何插件），JavaScript也被称作“互联网语言”。JavaScript的应用非常广泛，不仅被用于前端开发，也被用到服务器（Node.js）和数据库（MongoDB）环境中。
对任何专业技术人员来说，理解数据结构都非常重要。作为软件开发者，我们要能够用编程语言和数据结构来解决问题。编程语言和数据结构是这些问题解决方案中不可或缺的一部分。如果选择了不恰当的数据结构，可能会影响所写程序的性能。因此，了解不同数据结构和它们的适用范围十分重要。
算法在计算机科学中扮演着非常重要的角色。解决一个问题有很多种方法，但有些方法会比其他方法更好。因此，了解一下最著名的算法也很重要。
快乐地编码吧！
本书结构
第1章“JavaScript简介”，讲述了JavaScript的基础知识，它们可以帮助你更好地学习数据结构和算法，同时还介绍了如何搭建开发环境来运行书中的代码示例。
第2章“数组”，介绍了如何使用数组这种最基础且最常用的数据结构。这一章演示了如何对数组声明、初始化、添加和删除其中的元素，还讲述了如何使用JavaScript语言本身支持的数组方法。
第3章“栈”，介绍了栈这种数据结构，示范了如何创建栈，以及怎样添加和删除元素，还讨论了如何用栈解决计算机科学中的一些问题。
第4章“队列”，详述了队列这种数据结构，演示了如何创建队列，如何添加和删除队列中的元素，还讨论了如何用队列解决计算机科学中常见的问题，以及栈和队列的主要区别。
第5章“链表”，讲解如何用对象和指针从头创建链表这种数据结构。这一章除了讨论如何声明、创建、添加和删除链表元素之外，还介绍了不同类型的链表，例如双向链表和循环链表。
第6章“集合”，介绍了集合这种数据结构，讨论了如何用集合存储非重复性的元素。此外，还详述了对集合的各种操作以及相应代码的实现。
第7章“字典和散列表”，深入讲解字典、散列表及它们之间的区别。这一章介绍了这两种数据结构是如何声明、创建和使用的，还探讨了如何解决散列冲突，以及如何创建更高效的散列函数。
第8章“树”，讲解了树这种数据结构和它的相关术语，重点讨论了二叉搜索树，以及如何在树中搜索、遍历、添加和删除节点。如果想更深入地学习树（包括相关的算法），这一章还给出了一些建议。
第9章“图”，介绍了图这种数据结构和它的适用范围。这一章讲述了图的常用术语和不同表现方式，探讨了如何使用深度优先算法和广度优先算法遍历图，以及图的适用范围。
第10章“排序和搜索算法”，探讨了常用的排序算法，如冒泡排序（包括改进版）、选择排序、插入排序、归并排序和快速排序。另外还介绍了搜索算法中的顺序搜索和二分搜索。
第11章“算法补充知识”，主要讨论其他一些常用的算法和著名的大 O 表示法。这一章讲解了什么是递归，介绍了一些高级算法，如动态规划和贪心算法，还介绍了大 O 表示法和相关概念。最后，讨论了如何进一步学习算法的相关知识。
附录详尽列出了书中所授算法的复杂度列表（使用大 O 表示法）。
准备工作
为学习本书，你可以设置三种不同的开发环境。你不需要设置所有这三种环境，可以选择其一，也可以逐一尝试。
方法一，你需要一个浏览器，请在下面列表中选择其一：● Chrome（https://www.google.com/chrome/browser/）● Firefox（https://www.mozilla.org/en-US/firefox/new/）
方法二，你需要：● 安装方法一中的任意一个浏览器；● 安装一个Web服务器。如果你电脑里没有安装过Web服务器，推
荐安装XAMPP（https://www.apachefriends.org）。
方法三，如果想安装一个纯JavaScript的环境，你需要完成下面几步。● 安装步骤一中的任意浏览器● 安装Node.js（http://nodejs.org/）● 安装好Node.js后，安装http-server开发包：npm install http-server -g
第1章还会对此进行更详细的介绍。
读者对象
本书的目标读者包括计算机科学专业的学生、刚刚开启职业生涯的技术人员，以及想学习基于JavaScript语言的数据结构和算法的朋友。如果想学好书中的数据结构和算法，编程知识和逻辑思维是必需的。
本书为数据结构和算法初学者所写，也为熟悉数据结构和算法，但想在JavaScript语言中使用它们的人所写。
排版约定
在本书中，你会发现一些不同的文本样式，用以区别不同种类的信息。下面举例说明。
正文中的代码、用户输入这样表示：“在script标签里，编写JavaScript代码。”
代码段的格式如下：console.log("num: "+ num);console.log("name: "+ name);console.log("trueValue: "+ trueValue);console.log("price: "+ price);console.log("nullVar: "+ nullVar);console.log("und: "+ und);
如果我们想让你重点关注代码段中的某个部分，会加粗显示：
所有的命令行输入或输出的格式如下：npm install http-server –g
新术语和重点词汇以楷体标示。屏幕、目录或对话框上的内容这样表示：“Node Packages Modules（https://www.npmjs.org/）也在呈指数级增长。” 这个图标表示警告或需要特别注意的内容。
这个图标表示提示或者技巧。
读者反馈
欢迎提出反馈。如果你对本书有任何想法，喜欢它什么，不喜欢它什么，请让我们知道。要写出真正对大家有帮助的书，了解读者的反馈很重要。
一般的反馈，请发送电子邮件至feedback@packtpub.com，并在邮件主题中包含书名。
如果你有某个主题的专业知识，并且有兴趣写成或帮助促成一本书，请参考我们的作者指南http://www.packtpub.com/authors。
客户支持
现在，你是一位自豪的Packt图书的拥有者，我们会尽全力帮你充分利用你手中的书。
下载示例代码
你可以用你的账户从http://www.packtpub.com下载所有已购买Packt图书的示例代码文件。如果你从其他地方购买本书，可以访问http://www.packtpub.com/support并注册，我们将通过电子邮件把文件发送给你。
下载彩色插图
我们还提供了一份PDF文档，里面是本书中用到的彩色截图和图表。这些彩图能帮你更好地理解输出的变化。你可以从https://www.packtpub.com/sites/default/files/downloads/4874OS_ColoredImages.pdf下载。
勘误表
虽然我们已尽力确保本书内容正确，但出错仍旧在所难免。如果你在我们的书中发现错误，不管是文本还是代码，希望能告知我们，我们不胜感激。这样做可以减少其他读者的困扰，帮助我们改进本书的后续版本。如果你发现任何错误，请访问http://www.packtpub.com/submit-errata提交，选择你的书，点击勘误表提交表单的链接，并输入详细说明。勘误一经核实，你的提交将被接受，此勘误将上传到本公司网站或添加到现有勘误表。从http://www.packtpub.com/support选择书名就可以查看现有的勘误表。
侵权行为
互联网上的盗版是所有媒体都要面对的
问题
。Packt非常重视保护版权和许可证。如果你发现我们的作品在互联网上被非法复制，不管以什么形式，都请立即为我们提供位置地址或网站名称，以便我们可以寻求补救。请把可疑盗版材料的链接发到copyright@packtpub.com。
非常感谢你帮助我们保护作者，以及保护我们给你带来有价值内容的能力。问题
如果你对本书内容存有疑问，不管是哪个方面，都可以通过questions@packtpub.com联系我们，我们将尽最大努力来解决。第1章JavaScript简介
JavaScript是一门非常强大的编程语言。它是最流行的编程语言，也是网络应用里最卓越的语言之一。在GitHub（世界上最大的代码托管站点，https://github.com）上，托管了400 000多个JavaScript代码仓库（用JavaScript开发的项目数量也是最多的，参看http://goo.gl/ZFx6mg），并且还在逐年增长。
JavaScript不仅可用于前端开发，也适用于后端开发，Node.js就是这样一种技术。Node包（http://www.npmjs.org/）的数量也呈指数级增长。
要成为一名Web开发工程师，掌握JavaScript必不可少。
在本书中，你将学习最常用的数据结构和算法。为什么用JavaScript来学习这些数据结构和算法呢？我们已经回答了这个问题。JavaScript非常受欢迎，作为函数式编程语言，它非常适合用来学习数据结构和算法。通过它来学习数据结构比C或Java这些标准语言更简单，学习新东西也会变得很有趣。谁说数据结构和算法是只为C或Java这样的语言而生？在前端开发当中，你可能也需要实现它们。
学习数据结构和算法十分重要。首要原因是数据结构和算法可以很高效地解决常见问题，这对你今后的代码质量至关重要（也包括性能，要是用了不恰当的数据结构或算法，很可能会产生性能问题）。其次，对于计算机科学，算法是最基础的概念。最后，如果你想入职最好的IT公司（如谷歌、亚马逊、eBay等），数据结构和算法是面试问题的重头戏。1.1 环境搭建
相比其他语言，JavaScript的优势之一在于不用安装或配置任何复杂的环境就可以开始学习。每台计算机上都已具备所需的环境，哪怕使用者从未写过一行代码。有浏览器足矣！
为了运行书中的示例代码，建议你做好如下准备：安装Chrome或Firefox浏览器（选择一个你最喜欢的即可），选择一个喜欢的编辑器（如Sublime Text），以及一个Web服务器（XAMPP或其他你喜欢的，这一步是可选的）。这些软件在Windows、Linux和Mac OS上均可以使用。
如果你使用Firefox，推荐你安装Firebug插件（https://getfirebug.com）。
接下来将介绍搭建环境的三种方案。1.1.1 浏览器
浏览器是最简单的开发环境。
你也可以使用Firefox加Firebug。安装好Firebug后，在浏览器的右上角会看到如下图所示的图标。
点击Firebug图标，打开它，可以看到Console标签，我们可以在其命令行区域中编写所有JavaScript代码，如下图所示（执行源代码请按Run按钮）。
也可以扩展命令行，来适应Firebug插件的整个可用区域。
你还可以使用谷歌Chrome，它已经集成了Google Developer Tools（谷歌开发者工具）。打开Chrome，点击设置及控制图标，选中Tools|Developer Tools，如下图所示。
然后，就可以在Console标签页中编写JavaScript测试代码，如下所示。1.1.2 使用Web服务器（XAMPP）
你可能想要安装的第二个环境是XAMPP，它的安装过程也很简单，但比只使用浏览器麻烦点儿。
安装XAMPP（https://www.apachefriends.org）或者你偏爱的其他Web服务器。然后，在XAMPP安装文件夹下找到htdocs目录。在该目录下新建一个文件夹，就可以在里面执行本书中所讲述的源代码；或者是直接将示例代码下载后提取到此目录，如下所示。
接下来，在启动XAMPP服务器之后，你就可以通过localhost这个URL，用浏览器访问源码，如下图所示（别忘了打开Firebug或谷歌开发者工具查看输出）。 执行示例代码时，请不要忘记打开谷歌开发者工具或Firebug查看输出结果。1.1.3 使用Node.js搭建Web服务器
第三种选择就是100%的JavaScript，我们可以使用Node.js来搭建一个JavaScript服务器，不使用XAMPP搭建的Apache服务器。
首先要到http://nodejs.org/下载和安装Node.js。然后，打开终端应用（如果你用的是Windows操作系统，打开Node.js的命令行），输入如下命令：npm install http-server -g
最好手动输入这些命令，复制粘贴可能会出错。
也可以用管理员身份执行上述命令。对于Linux和Mac操作系统，使用如下命令：sudo npm install http-server -g
这条命令会在你的机器上安装一个JavaScript服务器：http-server。要启动服务器并在终端应用上运行本书中的示例代码，请将工作路径更改至示例代码文件夹，然后输入http-server，如下图所示，整个环境就搭建好了！
为执行示例，打开浏览器，通过http-server命令指定的端口访问：下载示例代码在官网（http://www.packtpub.com）购买的所有Packt图书，均可以下载到对应的示例代码。如果你并非在官网购买的本书，请访问http://www.packtpub.com/support并注册你的邮箱，对应的代码文件就会发送给你。本书的代码也可以在GitHub上找到，资源库地址为：https://github.com/loiane/javascriptdatastructures-algorithms。1.2 JavaScript基础
在深入学习各种数据结构和算法前，让我们先大概了解一下JavaScript。本节教大家一些相关的基础知识，有利于学习后面各章。
首先来看在HTML中编写JavaScript的两种方式：
第一种方式如上面的代码所示。创建一个HTML文件，把代码写进去。在这个例子里，我们在HTML中声明了script标签，然后把JavaScript代码都写进这个标签。
第二种方式，我们需要创建一个JavaScript文件（比如01-HelloWorld.js），在里面写入如下代码：alert('Hello, World!');
然后，我们的HTML文件看起来如下：
第二个例子展示了如何将一个JavaScript文件引入HTML文件。
这两个例子，无论执行哪个输出都是一样的。但第二个例子是最佳实践。 可能你在网上的一些例子里看到过JavaScript的include语句，或者放在head标签中的JavaScript代码。作为最佳实践，我们会在关闭body标签前引入JavaScript代码。这样浏览器就会在加载脚本之前解析和显示HTML，有利于提升页面的性能。1.2.1 变量
变量保存的数据可以在需要时设置、更新或提取。赋给变量的值都有对应的类型。JavaScript的类型有数字、字符串、布尔值、函数和对象。还有undefined和null，以及数组、日期和正则表达式。下面的例子介绍如何在JavaScript里使用变量。var num = 1; //{1}num = 3; //{2}var price = 1.5; //{3}var name = 'Packt'; //{4}var trueValue = true; //{5}var nullVar = null; //{6}var und; //{7}
在行{1}，我们展示了如何声明一个JavaScript变量（声明了一个数字类型）。虽然关键字var不是必需的，但最好每次声明一个新变量时都加上。
在行{2}， 我们更新了已有变量。JavaScript不是强类型语言。这意味着你可以声明一个变量并初始化成一个数字类型的值，然后把它更新成字符串或者其他类型的值，不过这并不是一个好做法。
在行{3}，我们又声明了一个数字类型的变量，不过这次是十进制浮点数。在行{4}， 声明了一个字符串；在行{5}，声明了一个布尔值；在行{6}，声明了一个null；在行{7}， 声明了undefined变量。null表示变量没有值，undefined表示变量已被声明，但尚未赋值：console.log("num:" + num);console.log("name:" + name);console.log("trueValue:" + trueValue);console.log("price:" + price);console.log("nullVar:" + nullVar);console.log("und:" + und);
如果想看我们声明的每个变量的值，可以用console.log来实现，就像上面代码片段中那样。 书中示例代码会使用三种方式输出JavaScript的值。第一种是alert（'My text here'），将输出到浏览器的警示窗口；第二种是console.log（'My text here'），将把文本输出到调试工具的Console标签（谷歌开发者工具或是Firebug，根据你使用的浏览器而定）；第三种方式是直接输出到HTML页面里并被浏览器呈现，通过document.write（'My text here'）。可以选择你喜欢的方式来调试。
console.log方法能接收多个参数，除了console.log("num: " + num)还可以写成console.log("num: ", num)。
稍后我们会讨论函数和对象。
变量作用域
作用域指在编写的算法函数中，我们能访问的变量（在使用时，函数作用域也可以是一个函数）。有本地变量和全局变量两种。
让我们看一个例子：var myVaribale = 'global';myOtherVaribale = 'global';function myFunction() { var myVariable = 'local'; return myVaribale;}function myOtherFunction() { myOtherVariable = 'local'; return myOtherVariable;}console.log(myVariable); //{1}console.log(myFunction()); //{2}console.log(myOtherVariable); //{3}console.log(myOtherFunction()); //{4}console.log(myOtherVariable); //{5}
行{1}输出global，因为它是一个全局变量。行{2}输出local，因为myVariable是在myFunction函数中声明的本地变量，所以作用域仅在myFunction内。
行{3}输出global，因为我们引用了在第二行初始化了的全局变量myOtherVariable。行{4}输出local。在myOtherFunction函数里，因为没有使用var关键字修饰，所以这里引用的是全局变量myOtherVariable并将它赋值为local。因此，行{5}会输出local（因为在myOtherFunction里修改了myOtherVariable的值）。
你可能听其他人提过在JavaScript里应该尽量少用全局变量，这是对的。通常，代码质量可以用全局变量和函数的数量来考量（数量越多越糟）。因此，尽可能避免使用全局变量。1.2.2 操作符
编程语言里都需要操作符。在JavaScript里有算数操作符、赋值操作符、比较操作符、逻辑操作符、位操作符、一元操作符和其他操作符。我们来看一下这些操作符：var num = 0; //{1}num = num + 2;num = num * 3;num = num / 2;num++;num--;num += 1; //{2}num -= 2;num *= 3;num /= 2;num %= 3;console.log('num == 1 : ' + (num == 1)); // {3}console.log('num === 1 : ' + (num === 1));console.log('num != 1 : ' + (num != 1));console.log('num > 1 : ' + (num > 1));console.log('num < 1 : ' + (num < 1));console.log('num >= 1 : ' + (num >= 1));console.log('num <= 1 : ' + (num <= 1));console.log('true && false : ' + (true && false)); // {4}console.log('true || false : ' + (true || false));console.log('!true : ' + (!true));
在行{1}，我们用了算数操作符。在下面的表格里，列出了这些操作符及其描述。算数操作符描述+加法-减法乘法*/除法%取余++递增--递减
在行{2}，我们使用了赋值操作符，在下面的表格里，列出了赋值操作符及其描述。赋值操作符描述=赋值+=加/赋值 (x += y) == (x = x + y)-=减/赋值 (x -= y) == (x = x - y)乘/赋值 (x *= y) == (x = x * y)*=/=除/赋值 (x /= y) == (x = x / y)%=取余/赋值 (x %= y) == (x = x % y)
在行{3}，我们使用了比较操作符。在下面的表格里，列出了比较操作符及其描述。比较操作符描述==相等===全等!=不等>大于>=大于等于<小于<=小于等于
在行{4}，我们使用了逻辑操作符。在下面的表格里，列出了逻辑操作符及其描述。逻辑操作符描述&&与||或!非
JavaScript也支持位操作符，如下所示：console.log('5 & 1:', (5 & 1));console.log('5 | 1:', (5 | 1)); console.log('~ 5:', (~5)); console.log('5 ^ 1:', (5 ^ 1)); console.log('5 << 1:', (5 << 1)); console.log('5 >> 1:', (5 >> 1));
下面的表格对位操作符做了更详细的描述。位操作符描述&与|或~非异或^<<左移>>右移
typeof操作符可以返回变量或表达式的类型。我们看下面的代码：console.log('typeof num:', typeof num);console.log('typeof Packt:', typeof 'Packt');console.log('typeof true:', typeof true);console.log('typeof [1,2,3]:', typeof [1,2,3]);console.log('typeof {name:John}:', typeof {name:'John'});
输出如下：typeof num: numbertypeof Packt: stringtypeof true: booleantypeof [1,2,3]: objecttypeof {name:John}: object
JavaScript还支持delete操作符，可以删除对象里的属性：var myObj = {name: 'John', age: 21};delete myObj.age;console.log(myObj); // 输出对象{name: "John"}
这些操作符在后面的算法学习中都会用到。1.2.3 真值和假值
在JavaScript中，true和false有些复杂。在大多数编程语言中，布尔值true和false仅仅表示true/false。在JavaScript中，如"Packt"这样的字符串值，也可以看作true。
下面的表格能帮助我们更好地理解true和false在JavaScript中是如何转换的。数值类型转换成布尔值undefinedfalsenulfalse布尔值true是true，false是false数字+0、-0和NaN都是false，其他都是true如果字符串是空的（长度是0）就是false，其他字符串都是true对象true
我们来看一些代码，用输出来验证上面的总结：function testTruthy(val){ return val ? console.log('truthy') : console.log('falsy'); }testTruthy(true); //truetestTruthy(false); //falsetestTruthy(new Boolean(false)); //true (对象始终为true)testTruthy(''); //falsetestTruthy('Packt'); //truetestTruthy(new String('')); //true (对象始终为true)testTruthy(1); //truetestTruthy(-1); //truetestTruthy(NaN); //falsetestTruthy(new Number(NaN)); //true (对象始终为true)testTruthy({}); //true (对象始终为true)var obj = {name:'John'};testTruthy(obj); //truetestTruthy(obj.name); //truetestTruthy(obj.age); //false (年龄不存在)1.2.4 相等操作符（==和===）
当使用这两个相等操作符时，可能会引起一些困惑。
使用==时，不同类型的值也可以被看作相等。这样的结果可能会使那些资深的JavaScript开发者都感到困惑。我们用下面的表格给大家分析一下不同类型的值用相等操作符比较后的结果。类型（x）类型（y）结果nullundefinedtrueundefinednulltruex == toNumber(y)数字字符串toNumber(x) == y字符串数字toNumber(x) == y布尔值任何类型x == toNumber(y)任何类型布尔值x == toPrimitive(y)字符串或数字对象toPrimitive(x) == y对象字符串或数字
如果 x 和 y 是相同类型，JavaScript会比较它们的值或对象值。其他没有列在这个表格中的情况都会返回false。
toNumber和toPrimitive方法是内部的，并根据以下表格对其进行估值。
toNumber方法对不同类型返回的结果如下：值类型结果undefinedNaNnull0布尔值如果是true，返回1；如果是false，返回0数字数字对应的值将字符串解析成数字。如果字符串中包含字母，字符串返回NaN；如果是由数字字符组成的，转换成数字Number(toPrimitive(vale))对象
toPrimitive方法对不同类型返回的结果如下：值类型结果如果对象的valueOf方法的结果是原始值，返回原对象始值；如果对象的toString方法返回原始值，就返回这个值；其他情况都返回一个错误
用例子来验证一下表格中的结果。首先，我们知道下面的代码输出 true（字符串长度大于1）：console.log('packt' ? true : false);
那么这行代码的结果呢？console.log('packt' == true);
输出是false，为什么会这样呢？
(1) 首先，布尔值会被toNumber方法转成数字，因此得到packt == 1。
(2) 其次，用toNumber转换字符串值。因为字符串包含有字母，所以会被转成NaN，表达式就变成了NaN == 1，结果就是false。
那么这行代码的结果呢？console.log('packt' == false);
输出也是false。步骤如下所示。
(1) 首先，布尔值会被toNumber方法转成数字，因此得到packt == 0。
(2) 其次，用toNumber转换字符串值。因为字符串包含有字母，所以会被转成NaN，表达式就变成了NaN == 0，结果就是false。
那么===操作符呢？简单多了。如果比较的两个值类型不同，比较的结果就是false。如果比较的两个值类型相同，结果会根据下表判断。类型（x）值结果x 和 y 数值相同（但不是NaN）数字truex 和 y 是相同的字符true字符串布尔值x 和 y 都是true或falsetruex 和 y 引用同一个对象对象true
如果 x 和 y 类型不同，结果就是false。
我们来看一些例子：console.log('packt' === true); //falseconsole.log('packt' === 'packt'); //truevar person1 = {name:'John'};var person2 = {name:'John'};console.log(person1 === person2); //false，不同的对象1.3 控制结构
JavaScript的控制结构和C与Java里的类似。条件语句支持if...else和switch。循环支持while、do...while和for。1.3.1 条件语句
首先我们看一下如何构造if...else条件语句。有几种方式。
如果想让一个脚本仅当条件是true时执行，可以这样写：var num = 1;if (num === 1) { console.log("num is equal to 1");}
如果想在条件为true的时候执行脚本A，其他情况下都执行脚本B，可以这样写：var num = 0;if (num === 1) { console.log("num is equal to 1");} else { console.log("num is not equal to 1, the value of num is " +num);}
if...else语句也可以用三元操作符替换，例如下面的if...else语句：if (num === 1){ num--;} else { num++;}
可以用三元操作符替换为：(num === 1) ? num-- : num++;
如果我们有多个脚本，可以多次使用if...else，根据不同的条件执行不同的语句：var month = 5;if (month === 1) { console.log("January");} else if (month === 2){ console.log("February");} else if (month === 3){ console.log("March");} else { console.log("Month is not January, February or March");}
最后，还有switch语句。如果要判断的条件和上面的一样（但要和不同的值进行比较），可以使用swtich语句：var month = 5;switch(month) { case 1: console.log("January"); break; case 2: console.log("February"); break; case 3: console.log("March"); break; default: console.log("Month is not January, February or March");}
对于switch语句来说，case和break关键字的用法很重要。case判断当前switch的值是否和case分支语句的值相等。break会中止switch语句的执行。没有break会导致执行完当前的case后，继续执行下一个case，直到遇到break或switch执行结束。最后，还有default关键字，在表达式不匹配前面任何一种情形的时候，就执行default中的代码（如果有对应的，就不会执行）。1.3.2 循环
在处理数组元素时会经常用到循环（数组是下一章的主讲内容）。在我们的算法中也会经常用到for循环。
JavaScript中的for循环与C和Java中的一样。循环的计数值通常是一个数字，然后和另一个值比较（如果条件成立就会执行for循环中的代码），之后这个数值会递增或递减。
在下面的代码里，我们用了一个for循环。当i小于10时，会在控制台中输出其值。i的初始值是0，因此这段代码会输出0到9。for (var i=0; i<10; i++) { console.log(i);}
我们要关注的下一种循环是while循环。当while的条件判断成立时，会执行循环内的代码。下面的代码里，有一个初始值为0的变量i，我们希望在i小于10时输出它的值。输出会是0到9：var i = 0;while(i<10){ console.log(i); i++;}
do...while循环和while循环很相似。区别是在while循环里，先进行条件判断再执行循环体中的代码，而在do...while循环里，是先执行循环体中的代码再判断循环条件。do...while循环至少会让循环体中的代码执行一次。下面的代码同样会输出0到9：var i = 0;do { console.log(i); i++;} while (i<10)1.4 函数
在用JavaScript编程时，函数很重要。在我们的例子里也用了函数。
下面的代码展示了函数的基本语法。它没有用到参数或return语句：function sayHello() { console.log('Hello!');}
要执行这个函数，只需要这样调用一下：sayHello();
我们也可以传递参数给函数。参数是会被函数使用的变量。下面的代码展示了如何在函数中使用参数：function output(text) { console.log(text);}
我们可以通过以下代码使用该函数：output('Hello!');
你可以传递任意数量的参数，如下所示：output('Hello!', 'Other text');
在这个例子中，函数只使用了传入的第一个参数，第二个参数被忽略。
函数也可以返回一个值，例如：function sum(num1, num2) { return num1 + num2;}
这个函数计算了给定两个数字之和，并返回结果。我们可以这样使用：var result = sum(1,2);output(result);1.5 面向对象编程
JavaScript里的对象就是普通名值对的集合。创建一个普通对象有两种方式。第一种方式是：var obj = new Object();
第二种方式是：var obj = {};
也可以这样创建一个完整的对象：obj = { name: { first: 'Gandalf', last: 'the Grey' }, address: 'Middle Earth'};
在面向对象编程（OOP）中，对象是类的实例。一个类定义了对象的特征。我们会创建很多类来表示算法和数据结构。例如我们声明了一个类来表示书：function Book(title, pages, isbn){ this.title = title; this.pages = pages; this.isbn = isbn;}
用下面的代码实例化这个类：var book = new Book('title', 'pag', 'isbn');
然后，我们可以访问和修改对象的属性：console.log(book.title); //输出书名book.title = 'new title'; //修改书名console.log(book.title); //输出新的书名
类可以包含函数。可以声明和使用函数，如下所示：Book.prototype.printTitle = function(){ console.log(this.title);};book.printTitle();
也可以直接在类的定义里声明函数：function Book(title, pages, isbn){ this.title = title; this.pages = pages; this.isbn = isbn; this.printIsbn = function(){ console.log(this.isbn); }}book.printIsbn(); 在原型的例子里，printTitle方法只会创建一次，在Book类的所有实例中共享。如果是在定义类的内部结构时声明，每个类的实例都会有一份该方法的副本。使用原型方法可以节约内存和降低实例化的开销。最好在声明公共方法时使用基于原型的方法。生成私有方法时用在类定义时内部声明的方式，这样其他实例不会访问到这个方法。你可能注意到了，在上面的例子中我们是在定义类内部结构时声明方法（因为我想让这些属性和方法为各个实例单独拥有），但还是尽量使用基于原型的方法定义更好些。
现在，我们已经学完了本书所需的所有JavaScript基础知识，接下来就可以学习数据结构和算法了。1.6 调试工具
除了学会如何用JavaScript编程外，还需要了解如何调试代码。调试对于找到代码中的错误十分有帮助，也能让你低速执行代码，看到所有发生的事情（方法被调用的栈、变量赋值等）。极力推荐你花一些时间学习一下如何调试书中的源码，查看算法的每一步（这样也会让你对算法有深刻的理解）。
Firefox和Chrome都支持调试。这里有一个了解谷歌开发者工具的好教程，地址是https://developer.chrome.com/devtools/docs/javascript-debugging。
除了你喜好的编辑器外，这里推荐其他几个工具，可以提升编写JavaScript的效率。● Aptana：这是一个开源的免费IDE，支持JavaScript、CSS3和
HTML5以及其他语言（http://www.aptana.com）。● WebStorm：这是一个很强大的IDE，支持最新的Web技术和框架。
它不是免费的，但你可以下载一个30天试用版本体验一下（http://www.jetbrain.com/webstorm）。● Sublime Text： 这是一个轻量级的文本编辑器，可以自定义插件。
可以买它的许可证来支持这个工具的开发，也可以免费使用（试
用版不过期），http://www.sublimetext.com/。1.7 小结
本章主要讲述了如何搭建开发环境，有了这个环境就可以编写和运行书中的示例代码。
本章也讲了JavaScript语言的基础知识，这些知识会在接下来的数据结构和算法学习过程中用到。
下一章，我们要学习第一种数据结构：数组。许多语言都对数组有原生的支持（当然也包括JavaScript）。第2章数组
几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。JavaScript里也有数组类型，虽然它的第一个版本并没有支持数组。本章中，我们将深入学习数组数据结构和它的能力。
数组存储一系列同一种数据类型的值。但在JavaScript里，也可以在数组中保存不同类型的值。但我们还是要遵守最佳实践，别这么做（大多数语言都没这个能力）。2.1 为什么用数组
假如有这样一个需求：保存所在城市每个月的平均温度。可以这么做：var averageTempJan = 31.9;var averageTempFeb = 35.3;var averageTempMar = 42.4;var averageTempApr = 52;var averageTempMay = 60.8;
当然，这肯定不是最好的方案。按照这种方式，如果只存一年的数据，我们能管理12个变量。但要多存几年的平均温度呢？幸运的是，我们可以用数组来解决，更加简洁地呈现同样的信息：averageTemp[0] = 31.9;averageTemp[1] = 35.3;averageTemp[2] = 42.4;averageTemp[3] = 52;averageTemp[4] = 60.8;
数组averageTemp里的内容如下图所示：2.2 创建和初始化数组
用JavaScript声明、创建和初始化数组很简单，就像下面这样：var daysOfWeek = new Array(); //{1}var daysOfWeek = new Array(7); //{2}var daysOfWeek = new Array('Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'); //{3}
使用new关键字，就能简单地声明并初始化一个数组（行{1}）。用这种方式，还可以创建一个指定长度的数组（行{2}）。另外，也可以直接将数组元素作为参数传递给它的构造器（行{3}）。
其实，用new创建数组并不是最好的方式。如果你想在JavaScript中创建一个数组，只用中括号（[]）的形式就行了，如下所示：var daysOfWeek = [];
也可使用一些元素初始化数组，如下：var daysOfWeek = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];
如果想知道数组里已经存了多少个元素，可以使用数组的length属性。以下代码的输出是7：console.log(daysOfWeek.length);
要访问数组里特定位置的元素，可以用中括号传递数值位置，得到想知道的值或者赋新的值。假如我们想输出数组daysOfWeek里的所有元素，可以通过循环遍历数组，打印元素，如下所示：for (var i=0; i 我们来看另一个例子：求斐波那契数列的前20个数字。已知斐波那契数列中第一个数字是1，第二个是2，从第三项开始，每一项都等于前两项之和：var fibonacci = []; //{1}fibonacci[1] = 1; //{2}fibonacci[2] = 2; //{3}for(var i = 3; i < 20; i++){ fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]; ////{4}}for(var i = 1; i 在行{1}处，我们声明并创建了一个数组。在行{2}和行{3}，把斐波那契数列中的前两个数字分别赋给了数组的第二和第三位（在JavaScript中，数组的第一位是0，这里我们略过，从第二位开始分别保存斐波那契数列中对应位置的元素）。 然后，我们需要做的就是想办法得到斐波那契数列的第三到第二十位的数字（前两个值我们已经初始化过了）。我们可以用循环来处理，把数组中前两位上的元素相加，结果赋给当前位置上的元素（行{4}——从数组中的索引3到索引19）。 最后，看看输出（行{6}），我们只需要循环遍历数组的各个元素（行{5}）。 示例代码里，我们用console.log来输出数组中对应索引位置的值（行{5}和行{6}），也可以直接用console.log(fibonacci)输出数组。大多数浏览器都可以用这种方式，清晰地输出数组。 现在如果想知道斐波那契数列其他位置上的值是多少，要怎么办呢？ 很简单，把之前循环条件中的终止变量从20改成你希望的值就可以了。2.3 添加和删除元素 从数组中添加和删除元素也很容易，但有时也会很棘手。假如我们有一个数组numbers，初始化成0到9：var numbers = [0,1,2,3,4,5,6,7,8,9]; 如果想要给数组添加一个元素（比如10），只要把值赋给数组中最后一个空位上的元素即可。numbers[numbers.length] = 10; 在JavaScript中，数组是一个可以修改的对象。如果添加元素，它就会动态增长。在C和Java等其他语言里，我们要决定数组的大小，想添加元素就要创建一个全新的数组，不能简单地往其中添加所需的元素。 另外，还有一个push方法，能把元素添加到数组的末尾。通过push方法，能添加任意个元素：numbers.push(11);numbers.push(12, 13); 如果输出numbers的话，就会看到从0到13的值。 现在，我们希望在数组中插入一个值，不像之前那样插入到最后，而是放到数组的首位。为了实现这个需求，首先我们要腾出数组里第一个元素的位置，把所有的元素向右移动一位。我们可以循环数组中的元素，从最后一位+1 （长度）开始，将其对应的前一个元素的值赋给它，依次处理，最后把我们想要的值赋给第一个位置（-1）上。for (var i=numbers.length; i>=0; i--){ numbers[i] = numbers[i-1];}numbers[0] = -1; 下面这张图描述了我们刚才的操作过程： 在JavaScript里，数组有一个方法叫unshift，可以直接把数值插入数组的首位：numbers.unshift(-2);numbers.unshift(-4, -3); 那么，用unshift方法，我们就可以在数组的开始处添加值-2， 然后添加-3、-4等。这样数组就会输出数字-4到13。 目前为止，我们已经学习了如何给数组的开始和结尾位置添加元素。下面我们来看一下怎样从数组中删除元素。 要删除数组里最靠后的元素，可以用pop方法：numbers.pop(); 通过push和pop方法，就能用数组来模拟栈，你将会在下一章看到这部分内容。 现在，数组输出的数字是-4到12，并且数组的长度是17。 如果要移除数组里的第一个元素，可以用下面的代码：for (var i = 0, l < numbers.length; i++){ numbers[i] = numbers[i+1];} 下面这张图呈现了这段代码的执行过程： 我们把数组里所有的元素都左移了一位。但数组的长度依然是17，这意味着数组中有额外的一个元素（值是undefined）。在最后一次循环里，i + 1引用了一个数组里还未初始化的位置（在其他一些语言里，这样写可能就会抛出异常了，因此不得不在 numbers.length - 1处停止循环）。 可以看到，我们只是把数组第一位的值用第二位覆盖了，并没有删除元素（因为数组的长度和之前还是一样的，并且了多一个未定义元素）。
试读结束[说明：试读内容隐藏了图片]