JavaScript Algorithms and Data Structures(五)

发表于 分类于 ， 本文字数： 9.4k 阅读时长 ≈ 9 分钟

freeCodeCamp —- JavaScript Algorithms and Data Structures

基础数据结构

1.使用数组存储不同类型的数据

以下是最简单的数组（Array）示例： 这是一个一维数组（one-dimensional array），它只有一层，或者说它里面没有包含其它数组。 可以观察到，这个数组中只包含了布尔值（booleans）、字符串（strings）、数字（numbers）以及 JavaScript 中的其他数据类型

1
2
let simpleArray = ['one', 2, 'three', true, false, undefined, null];
console.log(simpleArray.length);

调用 console.log 显示 7。

所有数组都有一个表示长度的属性，我们可以通过 Array.length 来访问它。 下面是一个关于数组的更复杂的例子。 这是一个多维数组 （multi-dimensional Array），或者说是一个包含了其他数组的数组。 可以注意到，在它的内部还包含了 JavaScript 中的对象（objects）结构。 我们会在后面的小节中讨论该数据结构，但现在你只需要知道数组能够存储复杂的对象类型数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let complexArray = [
  [
    {
      one: 1,
      two: 2
    },
    {
      three: 3,
      four: 4
    }
  ],
  [
    {
      a: "a",
      b: "b"
    },
    {
      c: "c",
      d: "d"
    }
  ]
];

2. 使用方括号访问数组的元素

所有数据结构的基本特性是，它们不仅可以存储数据，还可以让我们按需访问存放在其中的数据。 我们已经学习了如何创建数组，现在让我们来学习如何访问数组中的数据。

我们先定义一个包含 3 个元素的数组：

1
let ourArray = ["a", "b", "c"];

在数组中，内部的每个元素都有一个与之对应的索引（index）。 索引既是该元素在数组中的位置，也是我们访问该元素的引用。 需要注意的是，JavaScript 数组的索引是从 0 开始的（这种从 0 开始的规则叫做 zero-indexed），即数组的第一个元素是在数组中的第 0 个位置，而不是第 1 个位置。 要从数组中获取一个元素，我们可以在数组字面量后面加一个用方括号括起来的索引。不过习惯上，我们会通过表示数组的变量名来访问，而不是直接通过字面量。 这种从数组中读取元素的方式叫做方括号表示法（bracket notation）。 如果我们要从数组 ourArray 中取出数据 a 并将其赋值给另一个变量，可以这样写：

1
let ourVariable = ourArray[0];

现在，变量 ourVariable 的值也为 a。

通过索引，我们不仅可以获取某个元素值，还可以用类似的写法来设置一个索引位置的元素值：

1
ourArray[1] = "not b anymore";

在上面的代码中，我们用方括号表示法把索引为 1 的元素从 b 改成了 not b anymore。 现在 ourArray 的值是 ["a", "not b anymore", "c"]。

3. 使用 push() 和 unshift() 为数组添加元素

数组的长度与数组能包含的数据类型一样，都是不固定的。 数组可以包含任意数量的元素，可以不限次数地往数组中添加元素或者从中移除元素。 总之，数组是可变的（mutable）。 在本挑战中，我们要学习两种修改数组的方法：Array.push() 和 Array.unshift()。

这两个方法都接收一个或多个元素作为参数，并会将参数中的元素添加到该数组中。 push() 方法会将元素插入到数组的末尾，而 unshift() 方法会将元素插入到数组的开头。 请看以下例子：

1
2
3
4
let twentyThree = 'XXIII';
let romanNumerals = ['XXI', 'XXII'];

romanNumerals.unshift('XIX', 'XX');

romanNumerals 的值就变成了 ['XIX', 'XX', 'XXI', 'XXII']。

1
romanNumerals.push(twentyThree);

romanNumerals 的值现在就变成了 ['XIX', 'XX', 'XXI', 'XXII', 'XXIII']。 请注意这里，我们也可以使用变量作为参数，这让我们在动态修改数组数据时更加灵活。

4.使用 pop() 和 shift() 从数组中删除元素

push() 和 unshift() 都有一个与它们作用相反的函数：pop() 和 shift()。 与插入元素相反，pop() 会从数组的末尾移除一个元素，而 shift() 会从数组的开头移除一个元素。 pop() 和 shift() 与 push() 和 unshift() 的关键区别在于，用于删除元素的方法不接收参数，而且每次只能删除数组中的一个元素。

让我们来看以下的例子：

1
2
3
let greetings = ['whats up?', 'hello', 'see ya!'];

greetings.pop();

greetings 值为 ['whats up?', 'hello']。

1
greetings.shift();

greetings 值为 ['hello']。

这些用于删除数组元素的方法会返回被删除的元素：

1
let popped = greetings.pop();

greetings 值为 []，popped 值为 hello。

5.使用 splice() 删除元素

使用 splice() 方法， splice() 可以让我们从数组中的任意位置连续删除任意数量的元素。

splice() 最多可以接受 3 个参数，但现在我们先关注前两个。 splice() 的前两个参数是整数，表示数组中调用 splice() 的项的索引或位置。 别忘了，数组的索引是从 0 开始的，所以我们要用 0 来表示数组中的第一个元素。 splice() 的第一个参数代表从数组中的哪个索引开始移除元素，而第二个参数表示要从数组中的这个位置开始删除多少个元素。 例如：

1
2
3
let array = ['today', 'was', 'not', 'so', 'great'];

array.splice(2, 2);

这里我们移除 2 个元素，首先是第三个元素（索引为 2）。 array 会有值 ['today', 'was', 'great']。

splice() 不仅会修改调用该方法的数组，还会返回一个包含被移除元素的数组：

1
2
3
let array = ['I', 'am', 'feeling', 'really', 'happy'];

let newArray = array.splice(3, 2);

newArray 值为 ['really', 'happy']。

6. 使用 splice() 添加元素

 splice() 方法最多可以接收 3 个参数, 第三个参数可以是一个或多个元素，这些元素会被添加到数组中。 这样，我们能够便捷地将数组中的一个或多个连续元素换成其他的元素。

1
2
3
4
5
6
const numbers = [10, 11, 12, 12, 15];
const startIndex = 3;
const amountToDelete = 1;

numbers.splice(startIndex, amountToDelete, 13, 14);
console.log(numbers);

第二个 12 已被删除，我们在同一索引处添加 13 和 14。 numbers 数组现在将会是 [ 10, 11, 12, 13, 14, 15 ]。

在上面的代码中，数组一开始包含了若干数字。 接着，我们调用 splice() 方法，索引为 (3) 的地方开始删除元素，删除的元素数量是 (1)。然后，(13, 14) 是在删除位置插入的元素。 可以在 amountToDelete 后面传入任意数量的元素（以逗号分隔），每个都会被插入到数组中。

7. 使用 slice() 复制数组元素

接下来我们要介绍 slice() 方法。 slice() 不会修改数组，而是会复制，或者说提取（extract）给定数量的元素到一个新数组。 slice() 只接收 2 个输入参数：第一个是开始提取元素的位置（索引），第二个是提取元素的结束位置（索引）。 提取的元素中不包括第二个参数所对应的元素。 如下示例：

1
2
3
let weatherConditions = ['rain', 'snow', 'sleet', 'hail', 'clear'];

let todaysWeather = weatherConditions.slice(1, 3);

todaysWeather 值为 ['snow', 'sleet']，weatherConditions 值仍然为 ['rain', 'snow', 'sleet', 'hail', 'clear']。

在上面的代码中，我们从一个数组中提取了一些元素，并用这些元素创建了一个新数组。

8. 使用展开运算符复制数组

slice() 可以让我们从一个数组中选择一些元素来复制到新数组中，而 ES6 中又引入了一个简洁且可读性强的语法：展开运算符（spread operator），它能让我们方便地复制数组中的所有元素。 展开语法写出来是这样：...

我们可以用展开运算符来复制数组：

1
2
let thisArray = [true, true, undefined, false, null];
let thatArray = [...thisArray];

thatArray 等于 [true, true, undefined, false, null]。 thisArray 保持不变， thatArray 包含与 thisArray 相同的元素。

9. 使用展开运算符合并数组

展开语法（spread）的另一个重要用途是合并数组，或者将某个数组的所有元素插入到另一个数组的任意位置。 我们也可以使用 ES5 的语法连接两个数组，但只能让它们首尾相接。 而展开语法可以让这样的操作变得极其简单：

1
2
3
let thisArray = ['sage', 'rosemary', 'parsley', 'thyme'];

let thatArray = ['basil', 'cilantro', ...thisArray, 'coriander'];

thatArray 会有值 ['basil', 'cilantro', 'sage', 'rosemary', 'parsley', 'thyme', 'coriander']

使用展开语法，我们就可以很方便的实现一个用传统方法会写得很复杂且冗长的操作。

10.使用 indexOf() 检查元素是否存在

由于数组随时都可以修改或发生 mutated，我们很难保证某个数据始终处于数组中的特定位置，甚至不能保证该元素是否还存在于该数组中。 好消息是，JavaScript 为我们提供了内置方法 indexOf()。 这个方法让我们可以方便地检查某个元素是否存在于数组中。 indexOf() 方法接受一个元素作为输入参数，并返回该元素在数组中的位置（索引）；若该元素不存在于数组中则返回 -1。

例如：

1
2
3
4
5
let fruits = ['apples', 'pears', 'oranges', 'peaches', 'pears'];

fruits.indexOf('dates');
fruits.indexOf('oranges');
fruits.indexOf('pears');

indexOf('dates') 返回 -1，indexOf('oranges') 返回 2，indexOf('pears') 返回 1 (每个元素存在的第一个索引)。

11. 使用 for 循环遍历数组中的全部元素

使用数组时，我们经常需要遍历数组的所有元素来找出我们需要的一个或多个元素，抑或是对数组执行一些特定的操作。 JavaScript 为我们提供了几个内置的方法，它们以不同的方式遍历数组，以便我们可以用于不同的场景（如 every()、forEach()、map() 等等）。 然而，最简单的 for 循环不仅能实现上述这些方法的功能，而且相比之下也会更加灵活。

请看以下的例子：

1
2
3
4
5
6
7
8
9
10
11
function greaterThanTen(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 10) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}

greaterThanTen([2, 12, 8, 14, 80, 0, 1]);

在这个函数中，我们用一个 for 循环来遍历数组，逐一对其中的元素进行判断。 通过上面的代码，我们可以找出数组中大于 10 的所有元素，并返回一个包含这些元素的新数组 [12, 14, 80]。

12. 创建复杂的多维数组

数组的一个强大的特性是，它可以包含其他数组，甚至完全由其他数组组成。 数组中的数组还可以再包含其他数组，即可以嵌套任意多层数组。 通过这种方式，数组可以很快成为非常复杂的数据结构，称为多维（multi-dimensional）数组，或嵌套（nested）数组。 请看如下的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let nestedArray = [
  ['deep'],
  [
    ['deeper'], ['deeper'] 
  ],
  [
    [
      ['deepest'], ['deepest']
    ],
    [
      [
        ['deepest-est?']
      ]
    ]
  ]
];

deep 数组已嵌套 2 层。 deeper 数组嵌套了 3 层。 deepest 数组嵌套了 3 层， deepest-est? 嵌套了 5 层。

虽然这个例子看起来错综复杂，不过，尤其是在处理大量数据的时候，这种数据结构还是会用到的。 尽管结构复杂，不过我们仍可以通过方括号表示法来访问嵌套得最深的数组：

1
console.log(nestedArray[2][1][0][0][0]);

控制台打印的是字符串 deepest-est?。 既然我们知道数据的位置，当然，我们也可以修改它：

1
2
3
nestedArray[2][1][0][0][0] = 'deeper still';

console.log(nestedArray[2][1][0][0][0]);

现在控制台打印的是 deeper still。

13. 将键值对添加到对象中

对象（object）本质上是键值对（key-value pair）的集合。 或者说，一系列被映射到唯一标识符的数据就是对象；习惯上，唯一标识符叫做属性（property）或者键（key）；数据叫做值（value）。 让我们来看一个简单的例子：

1
2
3
4
5
const tekkenCharacter = {
  player: 'Hwoarang',
  fightingStyle: 'Tae Kwon Doe',
  human: true
};

上面的代码定义了一个叫做 tekkenCharacter 的“铁拳”游戏人物对象。 它有三个属性，每个属性都对应一个特定的值。 如果我们想为它再添加一个叫做 origin 的属性，可以这样写：

1
tekkenCharacter.origin = 'South Korea';

上面的代码中，我们使用了点号表示法。 如果我们现在输出 tekkenCharacter 对象，便可以看到它具有 origin 属性。 接下来，因为这个人物在游戏中有着与众不同的橘色头发， 我们可以通过方括号表示法来为它添加这个属性，像这样：

1
tekkenCharacter['hair color'] = 'dyed orange';

如果要设置的属性中存在空格，或者要设置的属性是一个变量，那我们必须使用方括号表示法（bracket notation）来为对象添加属性。 在上面的代码中，我们把属性（hair color）放到引号里，以此来表示整个字符串都是需要设置的属性。 如果我们不加上引号，那么中括号里的内容会被当作一个变量来解析，这个变量对应的值就会作为要设置的属性， 请看这段代码：

1
2
3
const eyes = 'eye color';

tekkenCharacter[eyes] = 'brown';

执行以上所有示例代码后，对象会变成这样：

1
2
3
4
5
6
7
8
{
  player: 'Hwoarang',
  fightingStyle: 'Tae Kwon Doe',
  human: true,
  origin: 'South Korea',
  'hair color': 'dyed orange',
  'eye color': 'brown'
};

14. 改嵌套在对象中的对象

在对象中，我们也可以嵌套任意层数的对象，对象的属性值可以是 JavaScript 支持的任意类型，包括数组和其他对象。 请看以下例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
let nestedObject = {
  id: 28802695164,
  date: 'December 31, 2016',
  data: {
    totalUsers: 99,
    online: 80,
    onlineStatus: {
      active: 67,
      away: 13,
      busy: 8
    }
  }
};

nestedObject 有 3 个属性：id（属性值为数字）、date（属性值为字符串）、data（属性值为嵌套的对象）。 虽然对象中的数据可能很复杂，我们仍能使用上一个挑战中讲到的写法来访问我们需要的信息。 如果我们想把嵌套在 onlineStatus 中 busy 的属性值改为 10，可以用点号表示法来这样实现：

1
nestedObject.data.onlineStatus.busy = 10;

15. 使用方括号访问属性名称

可以在一对方括号中用一个变量作为属性名来访问属性的值。 假设一个超市收银台程序中有一个 foods 对象, 并且有一个函数会设置 selectedFood；如果我们需要查询 foods 对象中，某种食物是否存在， 可以这样实现：

1
2
let selectedFood = getCurrentFood(scannedItem);
let inventory = foods[selectedFood];

上述代码会先读取 selectedFood 变量的值，并返回 foods 对象中以该值命名的属性所对应的属性值。 若没有以该值命名的属性，则会返回 undefined。 有时候对象的属性名在运行之前是不确定的，或者我们需要动态地访问对象的属性值。在这些场景下，方括号表示法就变得十分有用。

16. 使用 delete 关键字删除对象属性

对象是以键值对的形式，灵活、直观地存储结构化数据的一种方式，而且，通过对象的属性查找属性值是速度很快的操作。

如何从一个对象中移除一个键值对。

回顾一下 foods 对象。 如果我们想移除 apples 属性，可以像这样使用 delete 关键字：

1
delete foods.apples;

17. 检查对象是否具有某个属性

JavaScript 为我们提供了两种不同的方式来实现这个功能： 一个是通过 hasOwnProperty() 方法，另一个是使用 in 关键字。 假如我们有一个 users 对象，为检查它是否含有 Alan 属性，可以这样写：

1
2
users.hasOwnProperty('Alan');
'Alan' in users;

这两者结果都应该为 true。

18. 使用 for…in 语句遍历对象

Sometimes you need to iterate through all the keys within an object. You can use a for…in loop to do this. The for…in loop looks like:

1
2
3
4
5
6
7
8
const refrigerator = {
  'milk': 1,
  'eggs': 12,
};

for (const food in refrigerator) {
  console.log(food, refrigerator[food]);
}

This code logs milk 1 and eggs 12, with each key-value pair on its own line.

We defined the variable food in the loop head and this variable was set to each of the object’s keys on each iteration, resulting in each food’s name being printed to the console.

注意：对象中的键是无序的，这与数组不同。 因此，一个对象中某个属性的位置，或者说它出现的相对顺序，在引用或访问该属性时是不确定的。

19. 使用 Object.keys() 生成由对象的所有属性组成的数组

我们可以给 Object.keys() 方法传入一个对象作为参数，来生成包含对象所有键的数组。 这个方法将对象作为参数并返回代表对象中每个属性的字符串数组。 需要注意的是，数组中元素的顺序是不确定的。