前端学习总结（二十二）——常见数据结构与算法javascript实现

写在前面

作为前端开发者而言，可能不会像后端开发那样遇到很多的算法和数据结构问题，但是不论是做前端、 服务端还是客户端， 任何一个程序员都会开始面对更加复杂的问题， 这个时候算法和数据结构知识就变得不可或缺，它是编程能力中很重要的一部分。

如今的前端技术发展飞快，再也不像以前那样只负责视图层了，更多的交互和数据逻辑需要前端来做，这个时候对于算法和数据结构就有着更高的要求。此外，前端还可以去做node端，做数据可视化，做WebGL，三维建模，VR/AR等，这些新兴的领域对算法和数据有着更高的要求，所以想要成为一名高水平的前端工程师，就需要在数据和算法方面做更多的积累。

最近读完了一本书，是O’Reilly出本社出版的《数据结构与算法JavaScript描述》，这本书使用javascript描述了常见的各种数据结构与算法，可谓是js界的《算法导论》，前端工程师如果想要提升算法数据结构方面的基础，个人觉得这本书是非常好的选择，下面是我学习过程中的一些收获和总结。

PS:这里我把学习的一些总结都写在了代码的注释里，这也是我个人学东西的一个习惯，一边学一边跑代码，把重要的一些总结写在注释里。这样很有助于技术学习的沉淀，之后查起来也很方便，所以请留意注释中的内容。

一 开发环境

这里使用的是火狐官方的一个工具js shell,安装之后可以使用js命令来在命令行中执行js脚本，执行的环境是Google V8引擎。

下载:
https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Introduction_to_the_JavaScript_shell

将命令安装到全局就能使用，我用的是mac，安装的时候把二进制程序和依赖的包拷到/usr/local/bin，就可以在命令行中使用js命令了。

可以使用readline()从命令行中获取输入，使用print()输出结果。

比如，一个简答的a+b的程序 a+b.js：

var line;
while(line = readline()){line = line.split(' ');print(parseInt(line[0]) + parseInt(line[1]));
}

命令行中运行（文件路径注意写对，是绝对路径）

js /myproject/algorithms/a+b.js

就可以在命令行中输入参数，回车得到结果了，是不是很像用 C++ 命令行解算法题，没错，就是这么方便。

当然也可以使用 Node.js 环境来执行，具体参考Node.js官方文档即可。

二 对象和面向对象编程

js中5种数据类型，并没有定义更多的数据类型，但是运用js中一切皆对象的思想，可以自己很方便的去构造出各种复杂的数据类型对象。

这里讨论到的数据结构都被实现为对象。 JavaScript 提供了多种方式来创建和使用对象。 这里通过如下方式创建：

定义包含属性和方法声明的构造函数， 并在构造函数后紧跟方法
的定义。

下面是一个检查银行账户对象的构造函数：

//该数据对象的构造函数，相当于是一个类
function Checking(amount) {
this.balance = amount; // 属性
this.deposit = deposit; // 方法
this.withdraw = withdraw; // 方法
this.toString = toString; // 方法
}

this 关键字用来将方法和属性绑定到一个对象的实例上。 下面我们看看对于前面声明过的方法是如何定义的：

function deposit(amount) {
this.balance += amount;
} function withdraw(amount) {
if (amount <= this.balance) {
this.balance -= amount;
} 
if (amount > this.balance) {
print("Insufficient funds");
}
} function toString() {
return "Balance: " + this.balance;
}

使用时这样：

//注意这里通过： new 构造函数（传入的参数）生成了一个对象实例
var account = new Checking(500);
account.deposit(1000);
print(account.toString()); //Balance: 1500
account.withdraw(750);
print(account.toString()); // 余额： 750
account.withdraw(800); // 显示 " 余额不足 "
print(account.toString()); // 余额： 750

这就是一个定义数据对象的方法，下面构建各种数据结构也是使用这样的方式（除过数组，因为js本身定义了数组类型；其次，其他的数据结构的定义有很多事使用数据作为基础数据结构进行数据存储的）。

三 数组

1.字符串分割为数组split与数组元素拼接转字符串join

var sentence = "the quick brown fox jumped over the lazy dog";
/**1.* 字符串.split(分隔符) 将字符串生成为数组* */
var words = sentence.split(" ");
for (var i = 0; i < words.length; ++i) {print("word " + i + ": " + words[i]);
}
/**2.* 数组转字符串* .join(分隔符)* 数组各元素间放分隔符并连接成一个字符串* join("") 就是 直接将数组个元素拼接起来生字符串* .toString()连接成字符串后 默认中间会用,隔开* */

2.indexOf-查找数组是否存在某元素及下标

var names = ["David","Cynthia","Raymond","Clayton","Jennifer"];
putstr("Enter a name to search for: ");
var name = readline();
/**1.* 数组.indexOf(参数值) 参数值是否存在于数组,* 存,返第一个出现该元素的下标;* 不存,返-1;** 数组.lastIndexOf(参数值)* 反序找第一个的下标(如果出现,否则返-1)** */
var position = names.indexOf(name);
if (position >= 0) {print("Found " + name + " at position " + position);
}
else {print(name + " not found in array.");
}

3.数组中间添加和删除修改元素splice

直接上代码，总结见注释：

/*** 1.splice() 将现有数组进行截取,返回所截取生成出来的数组,且现有数组改变,是截取后的数组* 可用于为一个数组增加或移除或修改元素* 参数一:截取(删除)的起始索引(0是第一个元素)* 参数二:截取(删除)的元素的个数* 参数三:删除截取后要添加进数组的元素(可以是个数组)* *//**2.* 数组中间插入元素(放在数组里插入)* */
var nums = [1,2,3,7,8,9];
var newElements = [4,5,6];
nums.splice(3,0,newElements);
print(nums); // 1,2,3,4,5,6,7,8,9/**3.* 要插入数组的元素不必组织成一个数组， 它可以是任意的元素序列* */
var nums = [1,2,3,7,8,9];
nums.splice(3,0,4,5,6);
print(nums);/**4.* 从数组中删除元素* */
var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
print(nums); // 1,2,3,4,5

4.不生成新数组的迭代器方法-forEach每个元素都操作-every所有都满足-some有一个满足-reduce累计操作

直接上代码，总结见注释：

/*** Created by chenhaoact on 16/8/13.*/
/*** 1. 数组.forEach(func) 对数组每个元素执行某操作* 它接受一个函数作为参数，对数组中的每个元素使用该函数* */
function squareFunc(num) {print(num, num * num); //打印多个字符的时候自动中间会加空格
}var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
nums.forEach(squareFunc);/*** 2. 数组.every(func)， 检查数组中每个元素是否满足某条件* 它接受一个返回值为布尔类型的函数， 对数组中的每个元素使用该函数。* 如果对于所有的元素，该函数均返回 true， 则该方法返回 true** 数组.some(func)* 是否存在一个元素满足* 也接受一个返回值为布尔类型的函数， 只要有一个元素使得该函数返回 true，* 该方法就返回 true* */
function isEven(num) {return num % 2 == 0;
}
var nums = [2, 4, 6, 8, 10];
var even = nums.every(isEven);
if (even) {print("all numbers are even");
} else {print("not all numbers are even");
}/*** 3.* reduce() 数组中的各个元素累计进行操作* 它接受一个函数， 返回一个值。 该方法会从一个累加值开始， 不断对累加值和* 数组中的后续元素调用该函数， 直到数组中的最后一个元素， 最后返回得到的累加值。* *///使用 reduce() 方法为数组中的元素求和：
function add(runningTotal, currentValue) {return runningTotal + currentValue;
}
var nums = [1,2,3,4,5,6,7,8,9,10];
var sum = nums.reduce(add); //
print(sum); // 显示 55//reduce() 方法也可以用来将数组中的元素连接成一个长的字符串
function concat(accumulatedString, item) {return accumulatedString + item;
}
var words = ["the ", "quick ","brown ", "fox "];
var sentence = words.reduce(concat);
print(sentence); // 显示 "the quick brown fox"/*** 4.reduceRight() 方法，从右到左执行。* 下面的程序使用 reduceRight() 方法将数组中的元素进行翻转：* */
function concat(accumulatedString, item) {return accumulatedString + item;
}
var words = ["the ", "quick ","brown ", "fox "];
var sentence = words.reduceRight(concat);
print(sentence); // 显示 "fox brown quick the"

5.生成新数组的迭代器方法-map每个元素都执行某操作结果组成的数组-filter数组中满足某条件的元素组成的数组

直接上代码，总结见注释：

/*** Created by chenhaoact on 16/8/13.*/
/*** 1. 数组.map(func)* map() 和 forEach() 有点儿像，* 对数组中的每个元素使用某个函数。 两者的区别是* map() 返回一个新的数组， 该数组的元素是对原有元素应用某个函数得到的结果* */
function curve(grade) {return grade += 5;
}
var grades = [77, 65, 81, 92, 83];
var newgrades = grades.map(curve);
print(newgrades); // 82, 70, 86, 97, 88/*** 2.下面是对一个字符串数组使用 map() 方法的例子：* 数组 acronym 保存了数组 words 中每个元素的第一个字母。* 然而， 如果想将数组显示为真正的缩略形式， 必须想办法除掉连接每个数组元素的逗号，* 如果直接调用 toString() 方法， 就会显示出这个逗号。* 使用 join() 方法， 为其传入一个空字符串作为参数， 则可以帮助我们解决这个问题* */
function first(word) {return word[0];
}
var words = ["for", "your", "information"];
var acronym = words.map(first);
print(acronym)
print(acronym.join("")); // 显示 "fyi"/*** 3.filter() 传入一个返回值为布尔类型的函数。* 和 every() 方法不同的是，* 当对数组中的所有元素应用该函数，该方法并不返回 true，* 而是返回一个新数组， 该数组包含应用该函数后结果为 true 的元素。* */
//下列程序筛选数组中的奇数和偶数元素
function isEven(num) {return num % 2 == 0;
}function isOdd(num) {return num % 2 != 0;
}
var nums = [];
for (var i = 0; i < 20; ++i) {nums[i] = i + 1;
}
var evens = nums.filter(isEven);
print("Even numbers: ");
print(evens);
var odds = nums.filter(isOdd);
print("Odd numbers: ");
print(odds);
//执行结果如下：Even numbers:2,4,6,8,10,12,14,16,18,20 Odd numbers:1,3,5,7,9,11,13,15,17,19//下面使用 filter() 筛选所有成绩及格的分数：
function passing(num) {return num >= 60;
}
var grades = [];
for (var i = 0; i < 20; ++i) {grades[i] = Math.floor(Math.random() * 101);
}
var passGrades = grades.filter(passing);
print("All grades:");
print(grades);
print("Passing grades: ");
print(passGrades);//还可以使用 filter() 方法过滤字符串数组，下面这个例子过滤掉了那些不包含“ cie” 的单词：
function afterc(str) {if (str.indexOf("cie") > -1) {return true;}return false;
}
var words = ["recieve","deceive","percieve","deceit","concieve"];
var misspelled = words.filter(afterc);
print(misspelled); // 显示 recieve,percieve,concieve

6.二维数组和多维数组

直接上代码，总结见注释：

/*** Created by chenhaoact on 16/8/13.*/
/*** 1.创建二维数组* 比较好的方式是遵照 JavaScript: TheGood Parts（ O’Reilly） 一书第 64 页的例子，* 通过扩展 JavaScript 数组对象， 为其增加了一个新方法，* 该方法根据传入的参数， 设定了数组的行数、 列数和初始值* */

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！