JavaScript数据结构和算法：数组

数组的基本使用

为什么使用数组?

假如有这样一个需求：保存自己多个朋友的名字。可以这么做：

// 保存班级中所有学生的名字
var name1 = 'Tom'
var name2 = 'Lily'
var name3 = 'Lucy'
var name4 = 'Lilei'
var name5 = 'Coderwhy'

这不是一个好的解决方案
- 因为假如班级有 100 个学生, 那么我们就需要有 100 个变量.
- 100 个变量的是非常不方便管理的, 而且当我们需要找到某一个学生时, 从 100 个变量中去搜索也是一个问题.

很明显, 这种情况下, 我们通常会使用数组来解决:

1 2	// 使用数组来保存学生名字 var names = ['Tom', 'Lily', 'Lucy', 'Lilei', 'Coderwhy']

创建和初始化数组

用 JavaScript 声明、创建和初始化数组很简单，就像下面这样：

// 创建和初始化数组
var daysOfWeek = new Array()
var daysOfWeek = new Array(7)
var daysOfWeek = new Array(
  'Sunday',
  'Monday',
  'Tuesday',
  'Wednesday',
  'Thursday',
  'Friday',
  'Saturday'
)

代码解析:
- 使用new关键字，就能简单地声明并初始化一个数组
- 用这种方式，还可以创建一个指定长度的数组.
- 另外，也可以直接将数组元素作为参数传递给它的构造器
- 用new创建数组并不是最好的方式。如果你想在 JavaScript 中创建一个数组，只用中括号（[]）的形式就行了

使用中括号（[]）创建数组

var daysOfWeek = [
  'Sunday',
  'Monday',
  'Tuesday',
  'Wednesday',
  'Thursday',
  'Friday',
  'Saturday',
]

数组长度和遍历数组

如果我们希望获取数组的长度, 有一个 length 属性
1
2
// 获取数组的长度
alert(daysOfWeek.length)

也可以通过下标值来遍历数组:

// 普通for方式遍历数组
for (var i = 0; i < daysOfWeek.length; i++) {
  alert(daysOfWeek[i])
}

// 通过foreach遍历数组
daysOfWeek.forEach(function (value) {
  alert(value)
})

我们来做一个练习:

求菲波那切数列的前 20 个数字, 并且放在数组中.
菲波那切数列数列第一个数字是 1, 第二个数字也是 1, 第三项是前两项的和

// 求菲波那切数列的前20个数字
var fibonacci = []
fibonacci[0] = 1
fibonacci[1] = 1

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

alert(fibonacci)

数组的常见操作

数组中常见的操作有: 添加元素、删除元素、修改元素、获取元素.

添加元素

JavaScript 中, 进行我们上述的操作都比较简单: 因为语言本身都已经封装好了这些特定.

假如我们有一个数组: numbers, 初始化 0~9

1 2	// 初始化一个数组 var numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

添加一个元素到数组的最后位置:

// 添加一个元素到数组的最后位置
// 方式一:
numbers[numbers.length] = 10

// 方式二:
numbers.push(11)
numbers.push(12, 13)

alert(numbers)

在数组首位插入一个元素:

// 在数组首位插入一个元素
for (var i = numbers.length; i > 0; i--) {
  numbers[i] = numbers[i - 1]
}
numbers[0] = -1
alert(numbers) // -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

上面代码实现的原理是怎样的呢?

考虑上面代码实现的性能怎么呢?
- 性能并不算非常高
- 这也是数组和链表(后面我们会学习到)相对比的一个劣势: 在中间位置插入元素的效率比链表低.

当然, 我们在数组首位插入数据可以直接使用 unshift 方法

// 通过unshift在首位插入数据
numbers.unshift(-2)
numbers.unshift(-4, -3)
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

删除元素

如果希望删除数组最后的元素, 可以使用 pop()方法

1
2
3

// 删除最后的元素
numbers.pop()
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12

如果我们希望移除的首位元素, 自己实现代码:

// 删除首位的元素
for (var i = 0; i < numbers.length; i++) {
  numbers[i] = numbers[i + 1]
}
numbers.pop()
alert(numbers)

当然, 我们可以直接使用 shift 方法来实现:
1
2
numbers.shift()
alert(numbers)

任意位置

任意位置?
- 前面我们学习的主要是在数组的开头和结尾处添加和删除数据.
- 那如果我们希望在数组的中间位置进行一些操作应该怎么办呢?
一方面, 我们可以自己封装这样的函数, 但 JS 已经给我们提供了一个 splice 方法

通过 splice 删除数据

1
2
3

// 删除指定位置的几个元素
numbers.splice(5, 3)
alert(numbers) // -4,-3,-2,-1,0,4,5,6,7,8,9,10,11,12,13

代码解析:
- 上面的代码会删除索引为 5, 6, 7 位置的元素.
- 第一个参数表示索引起始的位置为 5(其实是第 6 个元素, 因为索引从 0 开始的), 删除 3 个元素.

如果我们希望使用 splice 来插入数据呢?

1
2
3

// 插入指定位置元素
numbers.splice(5, 0, 3, 2, 1)
alert(numbers) // -4,-3,-2,-1,0,3,2,1,4,5,6,7,8,9,10,11,12,13

代码解析:
- 上面的代码会从索引为 5 的位置开始插入数据. 其他数据依次向后位移.
- 第一个参数依然是索引值为 5(第六个位置)
- 第二个参数为 0 时表示不是删除数据, 而是插入数据.
- 后面紧跟的是在这个位置要插入的数据, 可以是其他类型, 比如”a”, “b”, “c”.

如果我们希望使用 splice 来修改数据呢?

1
2
3

// 修改指定位置的元素
numbers.splice(5, 3, 'a', 'b', 'c')
alert(numbers) // -4,-3,-2,-1,0,a,b,c,4,5,6,7,8,9,10,11,12,13

代码解析:
- 上面的代码会从索引 5 的位置开始修改数据, 修改多少个呢? 第二个参数来决定的.
- 第一个参数依然是索引的位置为 5(第六个位置)
- 第二个参数是要将数组中多少个元素给替换掉, 我们这里是 3 个(也可以使用 3 个元素来替换 2 个, 可以自己尝试一下)
- 后面跟着的就是要替换的元素.

数组的其他操作

上面学习的是对数组的一些基本操作.

JavaScript 中添加了很多方便操作数据的方法, 我们一些来简单回顾一下.

常见方法

我们先对常见的方法简单来看一下

方法名	方法描述
`concat`	连接 2 个或更多数组，并返回结果
`every`	对数组中的每一项运行给定函数，如果该函数对每一项都返回 `true`，则返回`true`, 否则返回`false`
`filter`	对数组中的每一项运行给定函数，返回该函数会返回 `true`的项组成的数组
`forEach`	对数组中的每一项运行给定函数。这个方法没有返回值
`join`	将所有的数组元素连接成一个字符串
`indexOf`	返回第一个与给定参数相等的数组元素的索引，没有找到则返回-1
`lastIndexOf`	返回在数组中搜索到的与给定参数相等的元素的索引里最大的值
`map`	对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组
`reverse`	颠倒数组中元素的顺序，原先第一个元素现在变成最后一个，同样原先的最后一个元素变成了现在的第一个
`slice`	传入索引值，将数组里对应索引范围内的元素作为新数组返回
`some`	对数组中的每一项运行给定函数，如果任一项返回 `true`，则结果为`true`, 并且迭代结束
`sort`	按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数
`toString`	将数组作为字符串返回
`valueOf`	和 `toString`类似，将数组作为字符串返回

数组合并

数组的合并非常简单, 使用 concat 即可(也可以直接+进行合并)

// 数组的合并
var nums1 = [1, 2, 3]
var nums2 = [100, 200, 300]
var newNums = nums1.concat(nums2)
alert(newNums) // 1,2,3,100,200,300

newNums = nums1 + nums2
alert(newNums) // 1,2,3,100,200,300

迭代方法

为了方便操作数组, JS 提供了很多迭代器方法, 我们来回顾一下
every()方法
- every()方法是将数组中每一个元素传入到一个函数中, 该函数返回 true/false.
- 如果函数中每一个元素都返回 true, 那么结果为 true, 有一个为 false, 那么结果为 false

every()练习:

判断一组元素中是否都包含某一个字符

// 定义数组
var names = ['abc', 'cb', 'mba', 'dna']

// 判断数组的元素是否都包含a字符
var flag = names.every(function (t) {
  return t.indexOf('a') != -1
})
alert(flag)

some()方法
- some()方法是将数组中每一个元素传入到一个函数中, 该函数返回 true/false
- 但是和 every 不同的是, 一旦有一次函数返回了 true, 那么迭代就会结束. 并且结果为 true

some()练习

// 定义数组
var names = ['abc', 'cb', 'mba', 'dna']

// 判断数组中是否包含有a字符的字符
var flag = names.some(function (t) {
  alert(t)
  return t.indexOf('a') != -1
})
alert(flag)

forEach()方法
- forEach()方法仅仅是一种快速迭代数组的方式而已.
- 该方法不需要返回值

forEach 的使用

// 定义数组
var names = ['abc', 'cb', 'mba', 'dna']

// forEach的使用
names.forEach(function (t) {
  alert(t)
})

filter()方法
- filter()方法是一种过滤的函数
- 首先会遍历数组中每一个元素传入到函数中
- 函数的结果返回 true, 那么这个元素会被添加到最新的数组中, 返回 false, 则忽略该元素.
- 最终会形成一个新的数组, 该数组就是 filter()方法的返回值

filter()的练习:

// 定义数组
var names = ['abc', 'cb', 'mba', 'dna']

// 获取names中所有包含'a'字符的元素
var newNames = names.filter(function (t) {
  return t.indexOf('a') != -1
})
alert(newNames)

map()方法
- map()方法提供的是一种映射函数.
- 首先会遍历数组中每一个元素传入到函数中.
- 元素会经过函数中的指令进行各种变换, 生成新的元素, 并且将新的元素返回.
- 最终会将返回的所有元素形成一个新的数组, 该数组就是 map()方法的返回值

map()练习:

// 定义数组
var names = ['abc', 'cb', 'mba', 'dna']

// 在names中所有的元素后面拼接-abc
var newNames = names.map(function (t) {
  return t + '-abc'
})
alert(newNames)

reduce 方法

我们单独拿出 reduce 方法, 因为这个方法相对来说难理解一点
首先, 我们来看这个方法需要的参数:
1
arr.reduce(callback[, initialValue])
参数
- callback（一个在数组中每一项上调用的函数，接受四个函数：）
  - previousValue（上一次调用回调函数时的返回值，或者初始值）
  - currentValue（当前正在处理的数组元素）
  - currentIndex（当前正在处理的数组元素下标）
  - array（调用 reduce()方法的数组）
- initialValue（可选的初始值。作为第一次调用回调函数时传给 previousValue 的值）
有些晦涩难懂, 我们直接看例子
- 求一个数字中数字的累加和

使用 for 实现:

// 1.定义数组
var numbers = [1, 2, 3, 4]

// 2.for实现累加
var total = 0
for (var i = 0; i < numbers.length; i++) {
  total += numbers[i]
}
alert(total) // 10

使用 forEach 简化 for 循环
- 相对于 for 循环, forEach 更符合我们的思维(遍历数组中的元素)
1
2
3
4
5
6
// 3.使用forEach
var total = 0
numbers.forEach(function (t) {
total += t
})
alert(total)

使用 reduce 方法实现

// 4.使用reduce方法
var total = numbers.reduce(function (pre, cur) {
  return pre + cur
})
alert(total)

代码解析:
- pre 中每次传入的参数是不固定的, 而是上次执行函数时的结果保存在了 pre 中
- 第一次执行时, pre 为 0, cur 为 1
- 第二次执行时, pre 为 1 (0+1, 上次函数执行的结果), cur 为 2
- 第三次执行时, pre 为 3 (1+2, 上次函数执行的结果), cur 为 3
- 第四次执行时, pre 为 6 (3+3, 上次函数执行的结果), cur 为 4
- 当 cur 为 4 时, 数组中的元素遍历完了, 就直接将第四次的结果, 作为 reduce 函数的返回值进行返回.
似乎和 forEach 比较没有太大的优势呢?
- 通过这个代码你会发现, 你不需要在调用函数前先定义一个变量, 只需要一个变量来接收方法最终的参数即可.
- 但是这就是优势吗? 不是, 优势在于 reduce 方法有返回值, 而 forEach 没有.
- 这算什么优势? 如果 reduce 方法有返回值, 那么 reduce 方法本身就可以作为参数直接传递给另外一个需要 reduce 返回值的作为参数的函数. 而 forEach 中你只能先将每次函数的结果保存在一个变量, 最后再将变量传入到参数中.
- 没错, 这就是最近非常流行的函数式编程. 也是为了几乎每个可以使用函数式编程的语言都有 reduce 这个方法的原因.
- 关于函数式编程, 不再本次课程的讨论之中, 只是看到了这个函数, 给大家延伸了一下而已.(后面有机会和大家分享函数式编程)
initialValue 还需要讲吗?
- 其实就是第一次执行 reduce 中的函数时, pre 的值.
- 因为默认 pre 第一次执行时为 0.