第⼀章：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.Fixed(2));
2.判断结构
根据布尔表达式的值，判断结构让程序可以执⾏到那句可以执⾏的程序的语句。常⽤的有if和switch语句
if有如下三种形式
javascript全局数组简单的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
var mid = 25;
var height = 50;
var low = 1;
var current = 13;
var found = -1;
if (current < mid) {
mid = (current - low) / 2;
} else if (current > mid) {
mid = (current + height) /2
} else {
found = current
}
另外⼀个判断结构是switch语句，在有多个简单选择时，使⽤该语句的代码更加清晰。
3.循环结构
常⽤的两种循环结构:while循环和for循环。
如果希望条件为真时，只执⾏⼀组语句，就选择while循环，下⾯展⽰了while循环的⼯作原理
while循环
var number = 1;
var sum = 0;
while (number < 11) {
sum += number;
++number
}
console.log(sum) //55
如果希望按执⾏次数执⾏⼀组语句，就选择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)//144
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)) //120
当⼀个函数递归调⽤时，当递归没有完成时，函数的计算结果暂时会被挂起。为了说明这个过程，这⾥⽤⼀副图展⽰以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的处理能⼒，这时候，我们就需要寻求改算法的⼀种迭代⽅式的解决⽅案了。任何可以被递归定义的函数，都可以被改写为迭代的程序，这点要牢记于⼼。
对象和⾯向对象编程
数据结构都被要实现为对象。javascript提供了很多种⽅式来创建和使⽤对象。下⾯做展⽰，创建对象，并⽤于创建和使⽤对象中的⽅法和属性。
对象通过如下⽅式创建：定义包含属性和⽅法声明的构造函数，并在构造函数后紧跟⽅法的定义。下⾯是⼀个检查银⾏账户对象的构造函数：
function Checking(amount){
this.balance = amount; //属性
this.deposit = deposit; //⽅法
this.withdraw = withdraw;//⽅法
}
this关键字⽤来将⽅法和属性绑定到⼀个对象的实例上，下⾯看看我们对上⾯声明过的⽅法是如何定义的
function deposit(amount) {
this.balance += amount;
}
function withdraw(amount) {
if (amount <= this.balance) {
this.balance -= amount;
}
if (amount > this.balance) {
console.log("Insufficient funds");
}
}
function toString(){
return "Balance:" + this.balance;
}
这⾥，我们⼜⼀次的使⽤this关键字和balance属性，以便让javascript解释器指定我们引⽤的是那个对象的balance属性
下⾯给出checking对象的完整定义和测试
function Checking(amount){
this.balance = amount; //属性
this.deposit = deposit; //⽅法
this.withdraw = withdraw;//⽅法
}
function deposit(amount) {
this.balance += amount;
}
function withdraw(amount) {
if (amount <= this.balance) {
this.balance -= amount;
}
if (amount > this.balance) {
console.log("余额不⾜");
}
}
function toString(){
return "余额:" + this.balance;
}
var account = new Checking(500);
account.deposit(1000);
console.String());//余额:1500
account.withdraw(750);
console.String());//余额:750
account.withdraw(800); //余额不⾜
console.String());//余额:750
ps：编写出让⼈容易阅读的代码和编写出让计算机能正确执⾏的代码同等重要，作为负责任的程序员，必须将这⼀点牢记于⼼。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。