学习《JavaScript 数据结构与算法》读书笔记

第2章数组

2.2 创建和初始化数组

访问元素和迭代数组

求斐波那契数列的前二十个数字。已知斐波那契数列中第一个数字是1，第二个是2，从第三项开始，每一项都等于前两项之和：

var fibonacci = [];
fibonacci[1] = 1; /* 这里确实是从数组第二位开始，略过了第一位 */
fibonacci[2] = 2;

for(var i = 3; i < 20; i++) {
	fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}

for(var i = 1; i < fibonacci.length; i++) {
	console.log(fibonacci[i])
}

其实斐波那契数列是 1 1 2 3 ... ，大概这就是为什么要略过第一位？

2.7 JavaScript 的数组方法参考

方法名	描述
`concat`	连接2个或更多数组，并返回结果
`every`	对数组中的每一项运行给定函数，如果该函数对每一项都返回`true`，则返回`true`
`filter`	对数组中的每一项运行给定函数，返回该函数会返回`true`的项组成的数组
`forEach`	对数组中的每一项运行给定函数，这个方法没有返回值
`join`	将所有的数组元素连接成一个字符串
`indexof`	返回第一个与给定参数相等的数组元素的索引，没有找到则返回`-1`
`lastIndexOf`	返回在数组中搜索到的与给定参数相等的元素的索引里最大的值
`map`	对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组
`reverse`	颠倒数组中元素的顺序，原先第一个元素现在变成最后一个，同样原先的最后一个元素变成了现在的第一个
`slice`	传入索引值，将数组里对应索引范围内的元素作为新数组返回
`some`	对数组中的每一项运行给定函数，如果任一项返回`true`，则返回`true`
`sort`	按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数
`toString`	将数组作为字符串返回
`valueOf`	和`toString`类似，将数组作为字符串返回
`push`	把元素添加到数组的末尾
`pop`	删除数组里最靠后的元素
`shift`	移除数组里的第一个元素
`unshift`	把元素插入到数组的首位
`splice`	该方法接收的第一个参数，表示想要删除或插入的元素的索引值。第二个参数是删除元素的个数（不删除时传入0）。第三个元素往后，就是要添加数组里的值

通过 push 和 pop 方法，就能用数组来模拟栈

通过 shift 和 unshift 方法，就能用数组模拟基本的队列数据结构

2.7.2 迭代器函数

JavaScript内置了许多数组可用的迭代方法。对于本节的离例子，我们需要数组和函数。加入有一个数组，它值是从1到15，如果数组里的元素可以被2整除（整数），函数就返回true ，否则返回 false 。

var isEven = function(x) {
	console.log(x);
	return (x % 2 == 0) ? true : false;
};
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

return (x % 2 == 0) ? true : false 也可以写成 return (x % 2 == 0)

1. 用 `every` 方法迭代

every 方法会迭代数组中的每个元素，直到返回 false ：

1	numbers.every(isEven);

在这个例子里，数组 numbers 的第一个元素是1，它不是2的倍数，因此 isEven 函数返回 false ，然后 every 执行结束。

2. 用 `some` 方法迭代

它和 every 的行为类似，不过 some 方法会迭代数组中的每个元素，直到返回 true ：

1	numbers.some(isEven);

在这个例子里，数组 numbers 中第一个偶数是2（第二个元素）。第一个被迭代的元素是1。 isEven 会返回 false 。第二个被迭代的元素是2， isEven 返回 true ，迭代结束。

3. 用 `forEach` 方法迭代

如果要迭代整个数组，可以用 forEach 方法。它和使用for循环的结果相同：

1
2
3

numbers.forEach(function(x) {
	console.log((x % 2 == 0));
});

这里为什么要套两层括号，难道是为了好看？

4. 用 `map` 和 `filter` 方法

JavaScript还有两个会返回新数组的遍历方法。第一个是 map :

1	var myMap = numbers.map(isEven);

数组 myMap 里的值是：

1	[false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]

它保存了 map 方法的 isEven 函数的运行结果

还有一个是 filter 方法。它返回的新数组由使函数返回 true 的元素组成

1	var evenNumbers = numbers.fliter(isEven);

在这个例子里，evenNumbers 数组中的元素都是偶数：

1	[2, 4, 6, 8, 10, 12, 14]

5. 使用 `reduce` 方法

最后是 reduce 方法。 reduce 方法接收一个函数作为参数，这个函数有四个参数： previousValue 、 currentValue 、 index 、 array 。这个函数会返回一个将被叠加到累加器的值， reduce 方法停止执行后会返回这个累加值。如果要对一个数组中的所有元素求和，这就很有用：

1
2
3

numbers.reduce(function(previous, current, index) {
	return previous + current;
});

输出将会是120。

2.7.3 ECMAScript 6 和数组的新功能

方法名	描述
`@@iterator`	返回一个包含数组键值对的迭代器对象，可以同步调用数组元素的键值对
`copyWithin`	复制数组中一系列元素到同一数组指定的起始位置
`entries`	返回包含数组所有键值对的`@@iterator`
`includes`	如果数组中存在某个元素则返回 `true` ，否则返回 `false` 。 ES7新增
`find`	根据回调函数给定的条件从数组中查找元素，如果找到则返回该元素
`findIndex`	根据回调函数给定的条件从数组中查找元素，如果找到则返回该元素在数组中的索引
`fill`	用静态值填充数组
`from`	根据已有数组创建一个新数组
`keys`	返回包含数组所有索引的`@@iterator`
`of`	根据传入的参创建一个新数组
`values`	返回包含数组中所有值的`@@iterator`

除了这些新的方法，还有一种用 for...of 循环来迭代数组的新做法，以及可以从数组实例得到的迭代器对象。

1. 使用 `forEach` 和箭头函数迭代

numbers.forEach(function(x) {
	console.log(x % 2 === 0);
});

numbers.forEach(x => {
	console.log(x % 2 === 0);
});

2. 使用 `for...of` 循环迭代

1
2
3

for(let i of numbers) {
	console.log((n % 2 === 0) ? 'even' : 'odd');
}

3. 使用 ES6 新的迭代器（@@iterator）

ES6 还为 Array 类增加了一个 @@iterator 属性，需要通过 Symbol.iterator 来访问。

let iterator = numbers[Symbol.iterator]();
console.log(iterator.next().value); /* 1 */
console.log(iterator.next().value); /* 2 */
console.log(iterator.next().value); /* 3 */
console.log(iterator.next().value); /* 4 */
console.log(iterator.next().value); /* 5 */

数组的 `entries` 、 `keys` 和 `values` 方法

entries 方法返回包含键值对的 @@iterator

let aEntries = numbers.entries(); /* 得到键值对的迭代器 */
console.log(aEntries.next().value); /* [0, 1] - 位置0的值为1 */
console.log(aEntries.next().value); /* [1, 2] - 位置1的值为2 */
console.log(aEntries.next().value); /* [2, 3] - 位置2的值为3 */

keys 方法返回包含数组索引的 @@iterator

let aKeys = numbers.keys(); /* 得到数组索引的迭代器 */
console.log(aKeys.next()); /* {value: 0, done: false} */
console.log(aKeys.next()); /* {value: 1, done: false} */
console.log(aKeys.next()); /* {value: 2, done: false} */

keys 方法会返回 numbers 数组的索引。一旦没有可迭代的值，aKeys.next() 就会返回一个 value 属性为 undefined，done 属性为 true 的对象。如果 done 属性的值为 false，就意味着还有可迭代的值。

values 方法返回的 @@iterator 则包含数组的值

let aValues = numbers.values();
console.log(aValues.next()); /* {value: 1, done: false} */
console.log(aValues.next()); /* {value: 2, done: false} */
console.log(aValues.next()); /* {value: 3, done: false} */

4. 使用 `from` 方法

Array.from 方法根据已有的数组创建一个新数组

1	let numbers2 = Array.from(numbers);

还可以传入一个用来过滤值的函数

1	let evens = Array.from(numbers, x => (x % 2 === 0));

上面的代码会创建一个evens数组，其中只包含numbers数组中的偶数

5. 使用 `Array.of` 方法

Array.of 方法根据传入的参数创建一个新数组

1 2	let numbers3 = Array.of(1); let numbers4 = Array.of(1, 2, 3, 4, 5, 6);

它和下面这段代码的效果一样

1 2	let numbers3 = [1]; let numbers4 = [1, 2, 3, 4, 5, 6];

我们也可以用这个方法复制已有的数组

1	let numbersCopy = Array.of(...numbers4);

6. 使用 `fill` 方法

fill 方法用静态值填充数组

let numbersCopy = Array.of(1, 2, 3, 4, 5, 6);
numbersCopy.fill(0); /* [0, 0, 0, 0, 0, 0] */
/* 我们还可以指定开始填充数组的索引 */
numbersCopy.fill(2, 1); /* [0, 2, 2, 2, 2, 2] */
/* 同时，也可以指定结束填充的索引 */
numbersCopy.fill(1, 3, 5); /* [0, 2, 2, 1, 1, 2] */

创建数组并初始化值的时候，fill 方法非常好用

1	let ones = Array(6).fill(1); /* [1, 1, 1, 1, 1, 1] */

7. 使用 `copyWithin` 方法

copyWithin 方法赋值数组中的一系列元素到同一数组指定的起始位置

let copyArray = [1, 2, 3, 4, 5, 6];
copyArray.copyWithin(0, 3); /* [4, 5, 6, 4, 5, 6] */
copyWithin = [1, 2, 3, 4, 5, 6];
copyArray.copyWithin(1, 3, 5); /* [1, 4, 5, 4, 5, 6] */

2.7.5 搜索

1. ECMAScript 6 `find` 和 `findIndex` 方法

let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
function mutipleOf13(element, index, array) {
	return (element % 13 === 0) ? true : false;
}
console.log(numbers.find(mutipleOf13));
console.log(numbers.findIndex(mutipleOf13));

find 和 findIndex 方法接收一个回调函数，搜索一个满足回调函数条件的值。

find 方法返回第一个满足条件的值， findIndex 方法则返回这个值在数组里的索引。如果没有满足条件的值，则分别返回 undefined 和 -1

2.8 类型数组

与 C 和 Java 等其他语言不同，JavaScript 数组不是强类型的，因此它可以存储任意类型的数据
而类型数组则用于存储单一类型的数据。他的语法是 let myArray = new TypedArray(length) ，其中 TypedArray 需替换为下表所列之一

类型数组	数据类型
`Int8Array`	8位二进制补码整数
`Uint8Array`	8位无符号整数
`Uint8ClampedArray`	8位无符号整数
`Int16Array`	16位二进制补码整数
`Uint16Array`	16位无符号整数
`Int32Array`	32位二进制补码整数
`Uint32Array`	32位无符号整数
`Float32Array`	32位IEEE浮点数
`Float64Array`	64位IEEE浮点数

let length = 5;
let int16 = new Int16Array(length);

let array16 = [];
array16.length = length;

for(let i = 0; i < length; i++) {
	int16[i] = i + 1;
}
console.log(int16);

使用 WebGL API 、进行位操作、处理文件和图像时，类型数组都可以大展拳脚。它用起来和普通数组也毫无二致，本章所学的数组方法和功能都可以用于类型数组。

第2章 数组

2.2 创建和初始化数组

访问元素和迭代数组

2.7 JavaScript 的数组方法参考

2.7.2 迭代器函数

1. 用 every 方法迭代

2. 用 some 方法迭代

3. 用 forEach 方法迭代

4. 用 map 和 filter 方法

5. 使用 reduce 方法

2.7.3 ECMAScript 6 和数组的新功能

1. 使用 forEach 和箭头函数迭代

2. 使用 for...of 循环迭代