稀疏数组

首先, 看一个🌰. 现在有一个五子棋程序, 其中有一个存盘退出和续上盘的功能.

二维数组记录棋盘

从上面这张图就能看到, 很多值就是默认值(0), 也就是说记录了很多没有意义的值, 所以就引出了稀疏数组.

基本介绍

当一个数组中大部分元素都是同一个值的数组时, 可以使用稀疏数组来保存该数组.

稀疏数组的处理方法是:

1. 记录数组一共几行几列, 有多少个不同的值
2. 把有不同值的元素的行列及值记录在一个小规模的数组中, 从而所辖程序的规模

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 一个正常的二维数组, 一共有7行8列, 其中大部分都是0
int[][] array = {
  {0,1,0,0,0,0,0,0},
  {0,0,0,2,0,0,0,0},
  {0,0,0,0,0,0,3,0},
  {0,-4,0,0,0,-5,0,0},
  {0,0,0,0,0,0,0,0},
  {0,0,0,0,-6,0,0,0},
  {0,0,7,0,0,0,0,0},
}

表中第一行记录了一共几行几列以及多少个非零值

从上面这个🌰就能看出来, 将原本需要7*8=56个空间变为了3*8=24个空间.

实现思路

1. 二维数组 转 稀疏数组

   1. 遍历原始的二维数组, 得到有效数据的个数sum

   2. 根据sum就可以创建稀疏数组int[sum+1][3]

   3. 将二维数组的有效数据存入到稀疏数组

2. 稀疏数组 转 二维数组

   1. 先读取稀疏数组第一行, 根据第一行的数组创建原始二维数组
   2. 在读取稀疏数组后面的数据, 并赋值给二维数组