js数据结构与算法
2016-09-06 本文已影响0人
kakuqo
变量作用域
作用域指在编写的算法函数中，我们能访问的变量。有本地变量和全局变量两种。
var myVaribale = 'global';
myOtherVaribale = 'global';
function myFunction(){
var myVaribale = 'local';
return myVaribale;
}
function myOtherFunction(){
myOtherVaribale = 'local';
return myOtherVaribale;
}
console.log(myVariable);//'global'
console.log(myFunction());//'local'
console.log(myOtherVaribale);//'global'
console.log(myOtherFunction());//'local'
console.log(myOtherVaribale);//'local'
操作符
编程语言里都需要操作符。在JS里有算数操作符、赋值操作符、比较操作符、逻辑操作符、位操作符、一元操作符和其他操作符。
//算数操作符 //赋值操作符
+ 加法 = 赋值
- 减法 += 加/赋值(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)
-- 递减
//比较操作符 //逻辑操作符
== 相等 && 与
=== 全等 || 或
！= 不等 ！ 非
> 大于
>= 大等于
< 小于
<= 小等于
真值假值
数值类型 转换成布尔值
undefined false
null false
布尔值 true--true,false ---false
数字 0和NaN----false,其他都是true
字符串 空字符串为 false,其他都是true
对象 true
注：new 出来的为对象始终为true （new String('') ---- true）
相等操作符
类型（x） 类型（y） 结果
null undefined true
数字 字符串 x == toNumber(y)
布尔值 任何类型 toNumber(x) == y
字符串或数字 对象 x == toPrimitive(y)
面向对象
创建普通对象有两种方式：
1、var obj = new Object();
2、var obj = {};
创建完成对象：
obj = {
name:{
first:'Gandalf'
}
}
在OOP中，对象是类的实例。一个类定义了对象的特征。我们会创建很多类来表示算法和数据结构。
function Book(title, pages, isbn){
this.title = title;
this.pages = pages;
this.isbn = isbn;
}
实例化这个类：
var book = new Book('title','pag','isbn');
修改对象的属性：
book.title = 'new title';
原型里声明和使用函数：
Book.prototype.printTitle = function(){
console.log(this.title);
};
直接在类的定义里声明函数：
function Book(title, pages, isbn){
this.title = title;
this.pages = pages;
this.isbn = isbn;
this.printIsbn = function(){
console.log(this.isbn);
}
}；
在原型的例子里，printTitle方法只会创建一次，在Book类的所有实例中共享。如果在定义类的内部结构时声明，每个类的实例都会有一份该方法的副本。最好在声明公共方法时使用基于原型的方法。
数组
创建斐波那契数列，第一个数字是1，第二个是2，第三项开始，每一项等于前两项之和：
var fibonacci = [];
fibonacci[0] = 1;
fibonacci[1] = 2;
for(var i = 2; i<20;i++){
fibonacci[i] = fibonnacci[i-1] + fibonnacci[i-2];
}
数组方法：
1、array.push:往数组末尾添加任意元素
2、array.unshift:往数组首位添加任意元素
3、array.pop：删除数组最后一位元素，并返回这个元素
4、array.shift:删除数组第一位元素，并返回这个元素
5、array.splice:往数组任意位置删除或添加任意元素
PS: --array.splice(1,3)--- 在数组第二位删除3项元素,并以数组形式返回被删除元 素；
--array.splice(1,0,2,3,4)---往数组的第二位添加2,3,4三项元素,若删除元素为 0，则返回空数组;
6、array.concat:连接2个或更多数组，并返回结果；
7、array.every：对数组中的每一项运行给定函数，直到返回false，如果每一项都返回true，则返回true；
PS:--array.every(function(x){
return (x % 2 == 0)
}) --------返回true 或者 false
8、array.some:该方法和every方法类似，对数组中的每一项运行给定函数，如果任一项返回true，则返回true；
PS:--array.some(function(x){
return (x % 2 == 0)
}) --------返回true 或者 false
9、array.forEach:对数组中的每一项运行给定函数，该方法没有返回值；
10、array.map:对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组；
PS:--var a = [1,2,3,4,5];
a.map(function(x){
return x +1
}) ----------返回数组[2,3,4,5,6],注：a数组不变；
11、array.filter:对数组中的每一项运行给定函数，返回该函数会返回true的项组成的数组；
PS:--var a =[1,2,3,4,5];
a.filter(function(x){
return (x % 2 == 0);
}) --------返回数组[2,4],a数组不变
12、array.reduce:该方法可接收一个函数作为参数和一个初始值，第一次调用函数会将初始值作为参数而非数组值，这个函数有四个参数： previousValue、currentValue、index和array。这个函数会返回一个将被叠加到累加器的值，reduce方法停止执行后会返回这个累加器。如果要对一个数组中的所有元素求和，这就很有用;
PS：--function process(previousArray,currentValue){
var nextArray;
if(currentValue >= 1 && currentValue <= 10){
nextArray = previousArray.push(currentValue);
}else{
nextArray = previousArray
}
return nextArray;
}
var numbers = [20,1,-4,6,30,5,8],emptyArray = [];
numbers .reduce(process,emptyArray);--------返回数组[1,6,5,8]
13、array.reverse:反序排列数组，原先数组最后一位元素变成第一位；
14、array.sort:按照字母顺序对数组进行排列，支持传入指定排序方法的函数作为参数
PS: ----var numbers = [2,3,5,7,1,6,8];
numbers.sort(function(a,b){
return a-b
})-----返回numbers数组[1,2,3,5,6,7,8],a-b为升序排列，b-a为降序排列；若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值,做升序排列。
15、array.indexOf:返回与参数匹配的第一个元素的索引，若参数不在数组里则返回-1；
16、array.lastIndexOf:返回与参数匹配的最后一个元素的索引。
17、array.toString:把数组里的所有元素输出为一个字符串；
PS:---var numbers = [1,2,3,4,5];
numbers.toString() ----- 返回字符串'1,2,3,4,5',不改变原数组；
18、array.join:把数组里的所有元素用参数拼接；
PS：---var numbers = [1,2,3,4,5];
numbers.join('-') ---- 返回'1-2-3-4-5',不改变原数组；
推荐资源：
1、http://www.w3schools.com/js/js_arrays.asp;
2、http://www.w3schools.com/js/js_array_methods.asp；
3、Mozilla的数组及其方法的页面
4、数组库：Underscore: http://underscorejs.org/ Lo-Dash: http://lodash.com/
栈
栈是一种遵从后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，就元素都接近栈底。
栈的创建
我们创建一个类来表示栈：
function Stack(){};
首先，我们需要一种数据结构来保存栈里的元素。可以选择数组：
var items = [];
接下来，要为我们的栈声明一些方法：
1、push(element(s)):添加一个（或几个）新元素到栈顶。
2、pop():移除栈顶的元素，同时返回被移除的元素。
3、peek():返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
4、isEmpty():如果栈里没有任何元素就返回true，否则返回false。
5、clear():移除栈里的所有元素。
6、size():返回栈里的元素个数。这个方法和数组的length属性很类似。
首先，我们要实现的第一个方法是push。这个方法往栈里添加新元素，只添加元素到栈顶，也就是栈的末尾。
this.push = function(element){
items.push(element);
};
因为我们使用了数组来保存栈里的元素，所以我们可以使用数组里的push方法来实现。
接着，我们实现第二个方法pop。这个方法主要用来移除栈里的元素。栈遵循后进先出的原则，因此移除的是最后添加进去的元素,所以我们可以使用数组里的pop方法来实现。
this.pop = function(){
return items.pop();
}
只能用push和pop方法添加和删除栈中元素，这样一来，我们的栈自然就遵从了lifo原则。
现在，为我们的类实现一些额外的辅助方法。如果想知道栈里面最后添加的元素是什么，可以用peek方法。
this.peek = function(){
return items[items.length-1];
}
接着要实现的方法是isEmpty,如果栈为空的话就返回true，否则就返回false；
this.isEmpty = function(){
return items.length == 0;
}
类似于数组的length属性，我们也能实现栈的长度方法size；
this.size = function(){
return items.length;
}
最后，我们来实现clear方法，用来移除栈里所有的元素。
this.clear = function(){
items = [];
}
这样栈就实现了，为了检查栈里的内容，我们来实现一个辅助方法，叫print，它会把栈里的元素都输出到控制台。
this.print = function(){
console.log(items.toString());
}
这样，我们就完整创建了栈！
使用栈
现在我们就来实现一个十进制转化成二进制的过程：
function divideBy2(decNumber){
var remStack = new Stack(),rem,binaryString = '';
while(decNumber >0){
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2)
}
while(!remStack.isEmpty()){
binaryString += remStack.pop().toString();
}
return binaryString;
}
这样，我们修改下上面的算法，就能把十进制转换成任何进制。
function baseConverter(decNumber,base){
var remStack = new Stack(),rem,baseString='',digits='0123456789ABCDEF';
while(decNumber >0){
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(!remStack.isEmpty()){
baseString += digits[remStack.pop()];
}
return baseString;
}
队列
队列和栈非常类似，但是使用了不同的原则，其是遵从先进先出原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素，最新添加的元素必须排在队列的末尾。
队列的创建
我们创建一个类来表示队列：
function Queue(){};
首先，我们需要一个用于存储队列中元素的数据结构。我们可以使用数组，就像在上一章Stack类中那样使用：
var items = [];
接下来，我们声明一些队列可用的方法：
1、enqueue(element(s)):向队列尾部添加一个（或多个）新的项。
2、dequeue():移除队列的第一项，并返回被移除的元素。
3、front():返回队列中第一个元素----最先被添加，也将是最先被移除的元素，队列不做任何变动。
4、isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
5、clear()：移除队列里的所有算数。
6、size():返回队列包含的元素个数，与数组的length属性类似。
首先要实现的是enqueue方法，这个方法往队列里添加新元素，只添加到队列末尾：
this.enqueue = function(element){
items.push(element);
}
接下来要实现的是dequeue方法，这个方法删除队列里的第一项：
this.dequeue = function(){
return items.shift();
}
只有enqueue方法和dequeue方法可以添加和移除元素，这样就确保了Queue类遵从先进先出原则。
现在，为我们的类实现一些额外的辅助方法，如果想知道队列最前面的项是什么，可以用front方法：
this.front = function(){
return items[0]
}
接着要实现isEmpty方法，如果队列为空返回true，否则就返回false。
this.isEmpty = function(){
return items.length == 0;
}
接着是size方法，来获取队列的长度。
this.size = function(){
return items.length;
}
最后来实现clear方法。
this.clear = function(){
items = [];
}
这样队列就实现了，也可以像Stack类一样增加一个print方法：
this.print = function(){
console.log(items.toString());
}
这样，我们就实现了一个队列！
优先队列
优先队列中，元素的添加和移除是基于优先级的。一个现实的例子就是医院的急诊，要实现优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。
我们创建一个类来表示优先队列：
function PriorityQueue(){
var items = [];
//创建一个队列元素类,在接下来的添加元素方法中会使用到
function QueueElement(element,priority){
this.element = element;
this.priority = priority;
}
};
接下来我们实现enqueue方法，在队列的正确位置添加元素。
this.enqueue = function(element,priority){
var queueElement = new QueueElement(element,priority);
if(this.isEmpty()){//this指向该优先队列，这里直接调用判断队列是否为空的方法
items.push(queueElement);
}else{
var added = false;
for (var i; i<items.length;i++){
if(queueElement.priority < items[i].priority){
items.splice(i,0,queueElement);
added = true;
break;
}
}
if(!added){
items.push(queueElement);
}
}
}
这样就完成按照优先级在正确的位置添加元素了，优先队列里的元素都有优先级该属性，通过优先级的判断然后在正确的位置添加元素。我们这里实现的优先队列称为最小优先队列因为优先级的值较小的元素被放置在队列最前面（1代表更高的优先级）。最大优先队列与之相反，把优先级的值较大的元素放置在队列最前面。
循环队列
循环队列的一个例子就是击鼓传花游戏，在这个游戏里，孩子们围成一个圈，把花尽快的传递给旁边的人。某一时刻花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。
下面，我们实现一个模拟的击鼓传花游戏：
function hotPotato (nameList,num){
var queue = newQueue();
for(var i=0;i<nameList.length;i++){
queue.enqueue(nameList[i]);
}
var eliminated = ' ';//被淘汰的对象
while(queue.size() >1){
for(var i=0;i<num;i++){
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();//当i等于给定的数字num时，被淘汰的元素
}
return queue.dequeue();//最后剩下一个为胜利者
}
