数组

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构，大多数编程语言的数组只能允许存储同一类型的值，少部分语言（JavaScript）允许任意类型的元素。并且大多数语言的数组长度是固定的，无法动态改变，少部分语言的数组长度是可以动态改变的

动态数组

由于数组本身的局限性，有必要进行封装以提供更好的功能，通常又被称为顺序表或动态数组，特点是逻辑相邻的元素，物理地址也是相邻的

由于存储位置与起始位置都相差一个常数，只要确定了起始位置，计算偏移量，数组中的任意位置都可以随机存取。一些高级语言的数组类型也具有随机存取的特性，所以通常使用数组来实现，虽然很多传统的编程语言都提供了数组，但它们大部分都无法修改容量，实现顺序存储的线性表等于将一个数组封装成一个动态的扩容数组，并提供一些操作它的方法

相对于链式存储的优势：

内存空间连续，允许随机访问元素
存储密度大，空间利用率高

劣势：

插入和删除元素需要移动元素
不能确定元素个数，产生额外的空间浪费

多维数组

当数组元素都是数组，即为多维数组

这是二维数组

const arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

也存在三维数组，或者更多维度的数组

const arr = [
  [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
  ],
  [
    [10, 11, 12],
    [13, 14, 15],
    [16, 17, 18]
  ],
  [
    [19, 20, 21],
    [22, 23, 24],
    [25, 26, 27]
  ],
];

矩阵

使用二维数组即可形成矩阵，如何遍历二维数组中的每个元素是一个需要关注的点，根据行和列的不同方式可分为行遍历和列遍历

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

// 行遍历
for (let i = 0; i < matrix.length; i++) {
  for(let j = 0; j < matrix[i].length; j++) {
    console.log(matrix[i][j]);
  }
}

// 列遍历
for (let i = 0; i < matrix[i].length; i++) {
  for (let j = 0; j < matrix.length; j++) {
    console.log(matrix[j][i]);
  }
}

稀疏矩阵和稠密矩阵

在矩阵中，为 0 的元素的数量远远大于非 0，并且非 0 元素的排列没有规律即为稀疏矩阵，反之为稠密矩阵

const matrix = [
  [0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 1],
  [0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1],
  [0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
  [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 2, 0, 0, 1, 0, 2, 0, 0, 0]
];

/* 计算稀疏性：0 的元素个数 / 元素总数 */
function sparsity(matrix) {
  let zero = 0;
  let count = 0;
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] == 0) {
        zero++;
      }
      if (i == matrix.length - 1) {
        count = (i + 1) * (j + 1);
      }
    }
  }
  return zero / count;
}

由于稀疏矩阵含有许多为 0 的元素，这些为 0 的元素不会包含任何信息，所以要进一步的处理，以便于压缩矩阵的内存空间加速计算