[关闭]
@Bios 2018-12-10T08:46:10.000000Z 字数 5328 阅读 767

JavaScript数据结构与算法

js 数据结构 算法

算法 + 数据结构 = 程序

数组（最常见的数据结构）

数组是计算机编程世界里最常见的数据结构。
数组的标准定义：一个存储元素的线性集合（collection）,元素可以通过索引来任意存取，索引通常是数字（也可以是其他字符）。

创建数组

  1. var arr = [];
  2. var arr = [1,2,3,4,5];
  3. var arr = new Array();
  4. var arr = new Array(10); // 10为数组的长度

存取函数

查找元素

indexOf

indexOf()函数是最常用的存取函数之一，用来查找传进来的>参数再目标数组中是否存在。

  1. var names = ['David', 'Cynthia', 'Raymond', 'Clayton', 'Jennifer'];
  2. putstr("Enter a name to search for:")；
  3. var name = readline();
  4. var position = names.indexOf(name);
  5. if (position >= 0) {
  6.     print("Found" + name + "at position" + position);
  7. } else {
  8.     print(name + "not found in array.");
  9. }

数组字符串表示

join & toString

有两个方法可以将数组转化为字符串：join()和toString()。这两个方法都返回一个包含数组所有元素的字符串，各个元素之间用逗号分隔开。

  1. var names = ['David', 'Cynthia', 'Raymond', 'Clayton', 'Jennifer'];
  2. var namestr = names.join();
  3. print(namestr); // David, Cynthia, Raymond, Clayton,Jennifer

事实上，当直接对一个数组使用print()函数时，系统会>>自动调用那个数组的toString()方法

由已有数组创建新数组

concat()和splice()方法允许通过已有数组创建新数组。concat()方法可以合并多个数组创建一个新数组，splice()方法截取一个数组的子集创建一个新数组。

concat
  1. var cisDept = ['Mike', 'Clayton', 'Terrill', 'Danny', 'Jennifer'];
  2. var dmpDept = ['Raymond', 'Cynthia', 'Bryan'];
  3. var itDiv = cisDept.concat(dmpDept);
  4. itDiv //Mike, Clayton, Terrill, Danny, Jennifer, Raymond, Cynthia, Bryan

concat()作为参数的数组，其中的元素都被连接到调用concat()方法的数组后面

splice
  1. var itDept = ['Mike', 'Clayton', 'Terrill', 'Danny', 'Jennifer', 'Raymond'];
  2. var dmpDept = itDept.splice(3, 3);
  3. var cisDept = itDept;
  4. print(dmpDept); // Danny, Jennifer, Raymond
  5. print(cisDept); // Mike, Clayton

注释：splice()该方法会改变原始数组。

可变函数

为数组添加元素

push()和unshift()

push

push()将一个元素添加到数组末尾：

  1. var nums = [1,2,3,4,5];
  2. print(nums); // 1,2,3,4,5
  3. nums.push(6);
  4. print(nums); // 1,2,3,4,5,6
unshift

unshift()方法可以将元素添加在数组的开头

如果不利用数组提供的可变函数，则新的元素添加进来后，需要把后面的每个元素都相应地向后移一个位置

  1. ar nums = [2,3,4,5];
  2. var newnum = 1;
  3. var N = nums.length;
  4. for (var i = N; i >= 0; --i) {
  5. nums[i] = nums[i-1];
  6. }
  7. nums[0] = newnum;
  8. print(nums); // 1,2,3,4,5

unshift()

  1. var nums = [2,3,4,5];
  2. print(nums); // 2,3,4,5
  3. var newnum = 1;
  4. nums.unshift(newnum);
  5. print(nums); // 1,2,3,4,5
  6. nums = [3,4,5];
  7. nums.unshift(newnum,1,2);
  8. print(nums); // 1,2,3,4,5

从数组中删除元素

pop

使用pop()方法可以删除数组末尾的元素：

  1. var nums = [1,2,3,4,5,9];
  2. nums.pop();
  3. print(nums); // 1,2,3,4,5
shift

shift()方法可以删除数组的第一个元素:

  1. var nums = [9,1,2,3,4,5];
  2. nums.shift();
  3. print(nums); // 1,2,3,4,5

从数组中间位置添加和删除元素

splice

使用splice()方法为数组添加元素，需提供如下参数：
• 起始索引（也就是你希望开始添加元素的地方）；
• 需要删除的元素个数（添加元素时该参数设为 0）；
• 想要添加进数组的元素。

  1. var nums = [1,2,3,7,8,9];
  2. var newElements = [4,5,6];
  3. nums.splice(3,0,newElements);
  4. print(nums); // 1,2,3,4,5,6,7,8,9

为数组排序

reverse

第一个方法是reverse()，该方法将数组中元素的顺序进行翻转。

  1. var nums = [1,2,3,4,5];
  2. nums.reverse();
  3. print(nums); // 5,4,3,2,1
sort

如果元素是字符串类型，那么数组的可变方法
sort() 就非常好使：

  1. var names = ["David","Mike","Cynthia","Clayton","Bryan","Raymond"];
  2. names.sort();
  3. print(names); // Bryan,Clayton,Cynthia,David,Mike,Raymond

但是如果数组元素是数字类型，sort()方法的排序结果就不能让人满意了：

  1. var nums = [3,1,2,100,4,200];
  2. nums.sort();
  3. print(nums); // 1,100,2,200,3,4

sort() 方法是按照字典顺序对元素进行排序的，因此它假定元素都是字符串类型，在上一
个例子中，即使元素是数字类型，也被认为是字符串类型。为了让sort()方法也能排序数
字类型的元素，可以在调用方法时传入一个大小比较函数，排序时，sort()方法将会根据
该函数比较数组中两个元素的大小，从而决定整个数组的顺序。
对于数字类型，该函数可以是一个简单的相减操作，从一个数字中减去另外一个数字。如
果结果为负，那么被减数小于减数；如果结果为 0，那么被减数与减数相等；如果结果为
正，那么被减数大于减数。

将这些搞清楚之后，传入一个大小比较函数，再来看看前面的例子：

  1. function compare(num1, num2) {
  2. return num1 - num2;
  3. }
  4. var nums = [3,1,2,100,4,200];
  5. nums.sort(compare);
  6. print(nums); // 1,2,3,4,100,200

sort()函数使用了compare()函数对数组按照数字大小进行排序，而不是按照字典顺序。

迭代器方法

不生成新数组的迭代器方法

我们要讨论的第一组迭代器方法不产生任何新数组，相反，它们要么对于数组中的每个元
素执行某种操作，要么返回一个值。

forEach
  1. function square(num) {
  2.     print(num, num * num);
  3. }
  4. var nums = [1,2,3,4,5,6,7,8,9,10];
  5. nums.forEach(square);

该程序的输出为：

  1. 1 1
  2. 2 4
  3. 3 9
  4. 4 16
  5. 5 25
  6. 6 36
  7. 7 49
  8. 8 64
  9. 9 81
  10. 10 100
every

该方法接受一个返回值为布尔类型的函数，对数组中的每个元素使用该函数。如果对于所有的元素，该函数均返回 true，则该方法返回 true。

  1. function isEven(num) {
  2.     return num % 2 == 0;
  3. }
  4. var nums = [2,4,6,8,10];
  5. var even = nums.every(isEven);
  6. if (even) {
  7.     print("all numbers are even");
  8. }
  9. else {
  10.     print("not all numbers are even");
  11. }
  1. // 输出为：
  2. all numbers are even
  3. // 将数组改为：
  4. var nums = [2,4,6,7,8,10];
  5. // 输出为：
  6. not all numbers are even
some

some() 方法也接受一个返回值为布尔类型的函数，只要有一个元素使得该函数返回true，该方法就返回 true。

  1. function isEven(num) {
  2.     return num % 2 == 0;
  3. }
  4. var nums = [1,2,3,4,5,6,7,8,9,10];
  5. var someEven = nums.some(isEven);
  6. if (someEven) {
  7.     print("some numbers are even");
  8. }
  9. else {
  10.     print("no numbers are even");
  11. }
  12. nums = [1,3,5,7,9];
  13. someEven = nums.some(isEven);
  14. if (someEven) {
  15.     print("some numbers are even");
  16. }
  17. else {
  18.     print("no numbers are even");
  19. }
  1. // 该程序的输出为：
  2. some numbers are even
  3. no numbers are even
reduce

reduce() 方法接受一个函数，返回一个值。该方法会从一个累加值开始，不断对累加值和数组中的后续元素调用该函数，直到数组中的最后一个元素，最后返回得到的累加值。

  1. function add(runningTotal, currentValue) {
  2.     return runningTotal + currentValue;
  3. }
  4. var nums = [1,2,3,4,5,6,7,8,9,10];
  5. var sum = nums.reduce(add);
  6. print(sum); // 显示 55
  1. // reduce()方法和add()函数一起，从左到右，依次对数组中的元素求和，其执行过程如下所示：
  2. add(1,2) -> 3
  3. add(3,3) -> 6
  4. add(6,4) -> 10
  5. add(10,5) -> 15
  6. add(15,6) -> 21
  7. add(21,7) -> 28
  8. add(28,8) -> 36
  9. add(36,9) -> 45
  10. add(45,10) -> 55

生成新数组的迭代器方法

有两个迭代器方法可以产生新数组：map()和 filter()。

map

map() 和forEach()有点儿像，对数组中的每个元素使用某个函数。两者的区别是map() 返回一个新的数组，该数组的元素是对原有元素应用某个函数得到的结果。

  1. function curve(grade) {
  2.     return grade += 5;
  3. }
  4. var grades = [77, 65, 81, 92, 83];
  5. var newgrades = grades.map(curve);
  6. print(newgrades); // 82, 70, 86, 97, 88
  1. function first(word) {
  2. return word[0];
  3. }
  4. var words = ["for","your","information"];
  5. var acronym = words.map(first);
  6. print(acronym.join("")); // 显示 "fyi"

在上面这个例子中，数组 acronym保存了数组 words中每个元素的第一个字母。然而，如果想将数组显示为真正的缩略形式，必须想办法除掉连接每个数组元素的逗号，如果直接调用 toString() 方法，就会显示出这个逗号。使用 join() 方法，为其传入一个空字符串作为参数，则可以帮助我们解决这个问题。

filter

filter() 和every()类似，传入一个返回值为布尔类型的函数。和 every()方法不同的是，
当对数组中的所有元素应用该函数，结果均为 true 时，该方法并不返回true，而是返回一个新数组，该数组包含应用该函数后结果为 true 的元素。

  1. function isEven(num) {
  2.     return num % 2 == 0;
  3. }
  4. function isOdd(num) {
  5.     return num % 2 != 0;
  6. }
  7. var nums = [];
  8. for (var i = 0; i < 20; ++i) {
  9.     nums[i] = i+1;
  10. }
  11. var evens = nums.filter(isEven);
  12. print("Even numbers: ");
  13. print(evens);
  14. var odds = nums.filter(isOdd);
  15. print("Odd numbers: ");
  16. print(odds);
  1. 该程序的执行结果如下：
  2. Even numbers:
  3. 2,4,6,8,10,12,14,16,18,20
  4. Odd numbers:
  5. 1,3,5,7,9,11,13,15,17,19
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注