数据结构-数组

数组是一种最为常见和应用广泛的数据结构, 不用语言的数组不太一样, 对于 js 的数组来说, 和 python 的列表极其类似, 都是可动态拓展值和类型的, 还是来大致总结一下这个基础数据结构.

创建数组

let arr1 = new Array('a', 'b', 66)
let arr2 = ['a', 'b', 66]

console.log(arr1, arr2);

数组访问和迭代

• 递归
• for 索引
• for / of 值

const fibArr = []
fibArr[1] = 1
fibArr[2] = 1

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

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

console.log(fibArr);

更多场景是我们直接遍历数组元素, 类似的结构是: arr = [ {}, {}, {} ...] 推荐用 for ... of

const arr = [1, 2, 3, {'name': 'cj', age: 18}]

for (let item of arr) {
  console.log(item);
}

PS F:\algorithms> node .\array.js
1
2
3
{ name: 'cj', age: 18 }

添加元素

• push
• unshift
• Array.prototype. xxx = function (value) =>

let arr = []

// 尾插
arr.push(666)
arr[arr.length] = 888

console.log(arr);

// 头插
Array.prototype.insertHead = function(value) {
  for (let i = this.length; i >= 0; i--) {
    this[i] = this[i-1]
  }
  this[0] = value 
}

arr.unshift(2, 3)

arr.insertHead(111)
console.log(arr);

PS F:\algorithms> node .\array.js
[ 666, 888 ]
[ 2, 3, 111, 666, 888 ]

删除元素

• pop
• shift
• Array.prototype.xxx = function(value) =>

let arr = [1, 2, 3, 4, 'cj', 'nb']

// 尾删
item = arr.pop()
// 头删
item2 = arr.shift()

console.log(item, item2, arr);

nb 1 [ 2, 3, 4, 'cj' ]

当然从头部删除也可以通过如下两个步骤:

• 创建一个 reIndex 的方法, 接收一个数组, 然后过滤掉 undefined 的元素, 返回新数组
• 通过索引方式手动删除原数组第一个元素, 然后将这个结果丢到 reIndex 中即可

// 将数组中的中 undefined 元素过滤
Array.prototype.reIndex = function (arr) {
  const newArr = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] != undefined) newArr.push(arr[i])
  }
  return newArr
}

// 手动删除第一个元素并排序
Array.prototype.removeHead = function() {
  for (let i = 0; i < this.length; i++) {
    this[i] = this[i+1]
  }
  return this.reIndex(this)
}


let arr = [1, 2, 3, 4, 'cj', 'nb']
console.log(arr.removeHead());

[ 2, 3, 4, 'cj', 'nb' ]

在任意位置添加或者删除元素

• splice (start, deleteCount, item1, item2, ...))
• 可增, 可删, 可替换

两个值的时候, 就是删除

arr = [1, 2, 3, 4, 5, 6]

// 从索引 2 的位置, 删除 2个元素
arr.splice(2, 2)

console.log(arr)

[ 1, 2, 5, 6 ]

多个值的时候, 可以是新增, 比如在索引为 2 的位置, 往前新增两个元素, 10, 11

arr = [1, 2, 3, 4, 5, 6]

// 索引为 2 的位置, 往前新增两个元素, 10, 11
arr.splice(2, 0, 10, 11)

console.log(arr)

[ 1, 2, 10, 11, 3, 4,  5,  6 ]

同样, 如果是要将索引为 2 的位置删掉, 再替换也是一样的, deleteCount 设置为 1 即可.

arr.splice(2, 1)         // 表示删掉索引为 2 的元素
arr.splice(2, 1, 10, 11) // 表示删掉索引为 2 的元素, 并原地插入 10, 11

多维数组

类似, 矩阵, 多层级的 json 等都基本可以通过一维数组方式实现, 在实际应用中用得最多的就是二维数组. 这里我们以矩阵来做一个演示.

以两天监测的平均华氏气温为例:

let avgTempDay01 = [ 72, 75, 79, 79, 81, 81]
let avgTempDay02 = [ 81, 79, 75, 75, 73, 72]

显然这样来存储是比较分散的, 通过矩阵或者二维数组的方式则更好一些.

let avgTempArr = []
// day01
avgTempArr[0] = []
avgTempArr[0][0] = 72
avgTempArr[0][1] = 75
avgTempArr[0][2] = 79
avgTempArr[0][3] = 79
avgTempArr[0][4] = 81
avgTempArr[0][5] = 81

// day02
avgTempArr[1] = []
avgTempArr[1][0] = 81
avgTempArr[1][1] = 79
avgTempArr[1][2] = 75
avgTempArr[1][3] = 75
avgTempArr[1][4] = 73
avgTempArr[1][5] = 72

console.log(avgTempArr);

PS F:\algorithms> node .\array.js
[ [ 72, 75, 79, 79, 81, 81 ], [ 81, 79, 75, 75, 73, 72 ] ]

当然也可以简写成这样:

let avgTempArr = []

avgTempArr[0] = [ 72, 75, 79, 79, 81, 81]
avgTempArr[1] = [ 81, 79, 75, 75, 73, 72]

二维数组迭代

• 嵌套 for 循环即可, 先行后列的方式

function printMatrix(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      console.log('pos:', [i, j], matrix[i][j])
    }
  }
}


let avgTempArr = []
avgTempArr[0] = [ 72, 75, 79, 79, 81, 81]
avgTempArr[1] = [ 81, 79, 75, 75, 73, 72]

console.log(avgTempArr);
printMatrix(avgTempArr)

PS F:\algorithms> node .\array.js
[ [ 72, 75, 79, 79, 81, 81 ], [ 81, 79, 75, 75, 73, 72 ] ]

pos: [ 0, 0 ] 72
pos: [ 0, 1 ] 75
pos: [ 0, 2 ] 79
pos: [ 0, 3 ] 79
pos: [ 0, 4 ] 81
pos: [ 0, 5 ] 81
pos: [ 1, 0 ] 81
pos: [ 1, 1 ] 79
pos: [ 1, 2 ] 75
pos: [ 1, 3 ] 75
pos: [ 1, 4 ] 73
pos: [ 1, 5 ] 72

数组常用方法

在JavaScript里，数组是经过改进的对象，这意味着创建的每个数组都有一些可用的方法。数组很有趣，因为它十分强大，和 Python 里面的列表类似的. 且相比其他语言中的数组，JavaScript中的数组有许多很好用的方法.

数组/对象的深拷贝

数组是引用类型, 在更多应用中会将一些数据包装成数组或对象形式传给后端接口, 通常就浅拷贝就行, 如果不会在多个应用中共用的话:

• arr2 = [ ...arr ]
• arr2 = Array.from(arr)
• arr2 = arr.slice()
• arr2 = arr.map(item => item)

就浅拷贝不胜枚举. 但我们更多的是关注深拷贝.

第一种深拷贝的简单粗暴方法是用 JSON.parse(JSON.stringify( ) ) 即先将数组序列化字符串, 再进行反序列化成数组.

const arr = [1, 2, 3, {'name': 'cj', age: 18}]

const arr2 = JSON.parse(JSON.stringify(arr))

arr[3].name = 'ccc'
console.log('arr: ', arr)
console.log('arr2: ', arr2)

PS F:\algorithms> node .\array.js
arr:  [ 1, 2, 3, { name: 'ccc', age: 18 } ]
arr2:  [ 1, 2, 3, { name: 'cj', age: 18 } ]

第二种方法是通过 递归 的方式层层遍历数组元素:

• 先定义一个空数组, 或者空对象
• 遍历数组元素, 判断当类型为 Array 时候, 再继续递归遍历
• 判断当类型为 Object 时候, 再继续递归遍历
• 当为普通元素时, 添加进数组 (递归终止条件)

function deepClone(obj) {
  // 先要判断 obj 是数组, 对象, 还是基本类型
  // 优先数组处理, 因为数组也是对象

  if (Array.isArray(obj)) {
    // 数组
    var ret = []
    for (var item of obj) {
      ret.push(deepClone(item))
    }
  } else if (typeof obj == 'object') {
    // 对象
    var ret = {}
    for (var key in obj) {
      ret[key] = deepClone(obj[key])
    }
  } else {
    // 基本类型直接输出, 作为递归出口
    var ret = obj
  }
  return ret 
}


const arr = [1, [{'a': 55}, 9], 3, {'name': 'cj', age: 18}]

const arr2 = deepClone(arr)

arr[3].name = 'ccc'
console.log('arr: ', arr)
console.log('arr2: ', arr2)

PS F:\algorithms> node .\array.js
arr:  [ 1, [ { a: 55 }, 9 ], 3, { name: 'ccc', age: 18 } ]
arr2:  [ 1, [ { a: 55 }, 9 ], 3, { name: 'cj', age: 18 } ]

数组排序

先是反序的 reverse 原地方法.

const arr = [1, 2, 3, 'cj']
arr.reverse()
console.log(arr);

PS F:\algorithms> node .\array.js
[ 'cj', 3, 2, 1 ]

然后是数组排序的 sort 方法. 当不传函数时候, 就默认以字符排序, 注意不是数值哦, 一定要记得穿一个比较函数进去!!!

const arr = [1, 2, 80, 9]
arr.sort()
console.log(arr);

PS F:\algorithms> node .\array.js
[ 1, 2, 80, 9 ]

默认是字符排序, 所以进行升序或者降序的时候, 必须要传入一个compareFn .

const arr = [1, 2, 3, 1, 0, 'cj']
// a -b 升序默认, b-a 降序
arr.sort((a, b) => b -a )

console.log(arr);

PS F:\algorithms> node .\array.js
[ 3, 2, 1, 1, 0, 'cj' ]

至此, 关于 javascript 的数组结构就差不多到这了.