第一章：javascript：数据结构与算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在前端工程师中，常常有一种声音，我们为什么要学数据结构与算法，没有数据结构与算法，我们一样很好的完成工作。
实际上，算法是一个宽泛的概念，我们写的任何程序都可以称为算法，甚至往冰箱里放大象，也要通过开门，放入，关门这样的规划，我们也可以视作为一种算法。可以说：简单的算法是人类的本能。而算法的知识的学习则是吸取前人的经验。对于复杂的问题进行归类，抽象，帮助我们脱离刀耕火种的时代，系统掌握一个算法的过程。

随着自身知识的增长，不论是做前端，服务端还是客户端，任何一个程序员都会开始面对更加复杂的问题，算法和数据结构就变得更不可或缺了。

前端工程师应该是最需要重视算法和数据结构基础的人。数据结构和算法的又没有照顾到入门的需要，所以前端工程师如果自身不重视算法和数据结构这样的基础知识，很可能陷入一直重复劳动很少有成长的这样职业发展困境。未来的网页UI，绝不是靠几个选择器操作加链接就能应付的。越来越复杂的产品和基础库，需要坚实的数据结构与算法才能驾驭。

在过去的几年中，得益于Node.js和SpiderMonkey等平台，javascript越来越多的用于服务器端编程，介于javascript已经走出了浏览器，程序员发现他们需要更多的传统语言（比如C++和JAVA），提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等）也包括传统的排序和查找算法。本系列博文在使用javascript进行服务器端编程时，如何使用这些数据结构和算法。

javascript程序员会发现本系列内容很有用，因为本书讨论了在javascript语言的限制下，如何实现数据结构和算法。这些限制包括：数组即对象，无处不在的全局变量，基于原型的对象模型等。javascript作为一种编程语言，名声不大好，本系列博文将展示javascript好的一面，去实现如何高效的数据结构和算法。

在那些学校没有学习过计算机的程序员来说，唯一熟悉的数据结构就是数组。在处理一些问题时，数组无疑是很好的选择，但对于很多复杂的问题，数组就显得太过简陋。大多数程序员都原因承认这样一个事实：对于很多编程问题，当他们提出一个合适的数据结构，设计和实现解决这些问题的算法就变得手到擒来。

二叉查找数(BST)就是这样一个例子。设计二叉差找树的目的就是为了方便查找一组数据中的最小值和最大值，由于这个数据结构自然引申出一个查找算法，该算法比目前最好的查询算法效率还高。不熟悉二叉查找树的程序员可能会使用一个更简单的数据结构，但效率上就打了个折扣。

学习算法非常重要，因为解决同样的问题，往往可以使用多种算法。对于高效程序员来说，知道那种算法效率高非常重要。比如，现在至少有六七种排序算法，如果知道快速排序比选择排序效率更高，那么就会让排序过程变得高效。又比如，实现一个线性查找的算法很简单，但是如果知道有时二分查找可能比线性查找快两倍以上，那么你势必会写出一个更好的程序。

深入学习数据结构和算法，不仅可以知道那种数据结构和算法更高效，还会知道如何找出最适合解决手头问题的数据结构和算法。写程序，尤其适用javascript写程序时，经常要权衡。

javascript的编程环境和模型

本章描述了javascript编程环境和基本的编程模块，后续章节将使用这些知识定义数据结构和实现各种算法。

1.javascript历来都是在浏览器里运行的程序语言，然而在过去的几年中，这些情况发生了变化，javascript可以作为桌面程序执行。或者在服务器上执行。介绍一种编程环境：javascript shell，这是MOzilla提供的综合javascript编程环境SpiderMonkey中的一部分。

2.声明和初始化变量

javascript变量默认是全局变量，严格的说，甚至不需要在使用前进行声明。如果对一个事先未声明的javascript变量进行初始化，该变量就变成了一个全局变量。所有，我们在编程中，遵循c++或java等编译型语言的习惯，在使用变量前进行声明，这样做的好处就是：声明的变量都是局部变量。本章稍后将部分详细讨论变量的作用域。

在javascript中声明变量，需要使用关键字var,后面跟变量名，或后面跟随一个赋值表达式。

var number;
var name;
var rate = 1.2;
var greeting = "hello world!";
var flag = false;

3.javascript中的算术运算符和数学库函数

javascript使用标准的算术运算符

+ 加， - 减， * 乘， / 除， % 去余

javascript同时拥有一个数学库，用来完成一些高级运算，比如平方根，绝对值和三角函数。算术运算符遵循标准的运算顺序，可以用括号来改变运算顺序。

var x = 3;
var y = 1.1;
console.log(x + y)
console.log(x * y)
console.log((x + y) * (x - y));
var z = 9;
console.log(Math.sqrt(z));
console.log(Math.abs(y/x))

如果计算精度不必像上面那样精确，可以将数字转换为固定精度

var x = 3;
var y = 1.1;
var z = x * y;
console.log(z.toFixed(2));

2.判断结构

根据布尔表达式的值，判断结构让程序可以执行到那句可以执行的程序的语句。常用的有if和switch语句

if有如下三种形式

简单的if语句
if-else语句
if-else-if语句

下面演示简单的if语句

var mid = 25;
var height = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
mid = (current - low) / 2
}

下面演示if - else语句

var mid = 25;
var height = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
mid = (current - low) / 2;
} else {
mid = (current + height) / 2;
}

下面演示if - else -if

另外一个判断结构是switch语句，在有多个简单选择时，使用该语句的代码更加清晰。

3.循环结构

常用的两种循环结构:while循环和for循环。

如果希望条件为真时，只执行一组语句，就选择while循环，下面展示了while循环的工作原理

while循环

var number = 1;
var sum = 0;
while (number < 11) {
sum += number;
++number
}
console.log(sum) //

如果希望按执行次数执行一组语句，就选择for循环。下面是for循环求1到10的整数累加和

var number = 1;
var sum = 0;
for (var number =1 ; number < 11; number++){
sum += number;
}
console.log(sum)

访问数组时，经常使用到for循环，如下：

var number = [3,7,12,22,100];
var sum = 0;
for (var i = 0; i < number.length; ++i) {
sum += number[i];
}
console.log(sum)//

4.函数
javascript提供了两种自定义函数的方式，一种有返回值，一种没有返回值（这种函数有时叫做子程或者void函数）。

下面展示了如何自定义一个有返回值的函数如何在javascript调用该函数。

function factorial (number) {
var product = 11;
for (var i = number; i >= 1; --i) {
product *= 1
}
return product;
}
console.log(factorial(4))

下面的例子展示如何定义一个没有返回值的函数，使用该函数并不是为了得到它的返回值，而是为了执行函数中定义的操作。

javascript中的子程或者void函数

function curve(arr, amount) {
for (var i = 0; i < arr.length; ++i) {
arr[i] += amount;
}
} var grades = [77,73,74,81.90];
curve(grades,5);
console.log(grades)

javascript中，函数的参数传递方式都是按值传递，没有按引用传递的参数。但是javascript有保存引用的对象，比如数组，如上例，它们是按引用传递的。

5.变量作用域

变量的作用域是指一个变量在程序中那些对象可以访问。javascript中的变量作用域被定义为函数作用域。
这是指变量的值在定义该变量的函数内是可见的。并且定义在该函数内的嵌套函数也可以访问该变量。

在主程序中，如果在函数的外部定义一个变量，那么该变量拥有全局作用域，这是指可以在包括函数体内的程序的任何部分访问该变量。下面用一段简短的程序展示作用域的工作原理。

function showScope(){
return scope;
}
var scope = "global";
console.log(scope); //global
console.log(showScope()); //global

showScope()函数内定义的变量scope拥有局部作用域，而在主程序中定义变量scope是一个全局变量。尽管两个变量名字相同，但它们的作用域不同，在定义他们的地方访问时得到的值也不一样。

这些行为都是正常且符合预期的，但是如果在定义变量时省略了关键字var,那么一切都变了。javascript允许在定义变量时不使用关键字var，但是这样做的后果是定义的变量自动拥有了全局作用域，即使你在一个函数内定义该变量，它也是全局变量。

下面的例子是滥用全局变量的恶果。

function showScope(){
scope = "local";
return scope;
} scope = "global";
console.log(scope); //global
console.log(showScope()); //local
console.log(scope) //local

上面的例子中，由于showScope()函数内定义变量scope时省略了关键字var。所以在将字符串"local"赋值给该变量时，实际上是改变了主程序中scope变量的值。因此，在定义变量时，应该总是var开始，避免发生类似错误。

前面我们提到，javascript拥有的是函数作用域，其含义是javascript没有块级作用域，这一点有别于其它很多现代的编程语言。使用块级作用域，可以在一段代码中定义变量，该变量只在块内可见，离开这段代码块就不见了。在C++或者java的for循环中，我们经常看到这样的例子

for (int i = 1; i <= 10; ++i) {
count << "hello world!" << end;
}

虽然javascript没有块级作用域，但在我们写for循环时，我们假设它有：

for (var i = 1; i <=10; ++i) {
console.log("hello,world!")
}

这样做的原因是，不希望自己养成坏编程习惯的帮手！

6.递归

javascript中允许函数递归调用，前面定义过的factorial()函数也可以使用递归方式定义

function factorial(number) {
if (number == 1) {
return number
} else {
return number * factorial(number - 1)
}
} console.log(factorial(5)) //

当一个函数递归调用时，当递归没有完成时，函数的计算结果暂时会被挂起。为了说明这个过程，这里用一副图展示以5作为参数，调用factorial()函数时函数执行的过程。

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

对于大多数情况，javascript有能力处理层次较深的递归调用；但保不齐有些算法需要的递归深度超出了javascript的处理能力，这时候，我们就需要寻求改算法的一种迭代方式的解决方案了。任何可以被递归定义的函数，都可以被改写为迭代的程序，这点要牢记于心。