稀疏数组的实现原理及应用场景

2024-03-01 09:25:52

稀疏数组

引子：

下图是一个11行11列的围棋棋盘，使用二维数组展示出来，此时用户要保存该棋局，有两种方式存储该棋局，第一种是使用该二维数组原封不动的存储到磁盘中，第二种方式是将其转换为稀疏数组存储到磁盘中，当下次打开时再将该稀疏数组还原为二维数组。

稀疏数组的原型图：

说明：

第一行：第1列代表原始二维数组有几行，第2列代表原始二维数组有几列，第3列代表原始二维数组中与初始值不相同的元素有几个（在本例子中表示黑子和白子的总数量是多少个？）

第二行：第1列代表第一个与初始值不相同的元素所在的行，第2列代表第一个与初始值不相同的元素所在的列，第3列代表第一个与初始值不相同的元素的值。

第三行：与第二行相类似

……

该稀疏数组的第一行的第3列的值 + 1就是该稀疏数组的行数，稀疏数组的列数固定为三列。

实现思路：

一、由原始二维数组转换为稀疏数组的思路：

1 遍历原始二维数组，统计出与默认值不相同的元素的个数num

2 创建稀疏数组，其为[num+1]行，[3]列的一个二维数组

3 稀疏数组的第一行的三个值分别为原始二维数组的行、列、[num]

4 再次遍历原始二维数组，将与原始值不相同的元素依次存入到稀疏数组的第二行到第[num+1]行。每一行的第1列存的是该元素所在行的索引，第2列存的是该元素所在列的索引，第3列存的是该元素的值。

二、由稀疏数组还原为原始二维数组的思路：

1 取出稀疏数组的第一行的第1列和第2列的值，分别为原始二维数组的行和列的个数，然后创建二维数组。

2 从第二行开始遍历稀疏数组，并还原为整个原始的二维数组。每一行的第1列为该元素在原始二维数组中的行的索引，第2列为该元素在原始二维数组中的列的索引，第3列为该元素的值。

代码实现：

public class ArithmeticChess {
    @Test
    public void testChess(){
        int length = 11;
        int[][] arrChess1 = new int[length][length];
        System.out.println("=================原始数组===============");
        arrChess1[5][5] = 1;
        arrChess1[5][7] = 2;
        arrChess1[6][6] = 1;
        int sum = 0;
        for (int[] arr : arrChess1) {
            for (int i : arr) {
                System.out.printf("%3d",i);
                if (i != 0){
                    sum++;
                }
            }
            System.out.println();
        }
        System.out.println("=================稀疏数组===============");
        int[][] sparse = new int[sum + 1][3];
        sparse[0][0] = length;
        sparse[0][1] = length;
        sparse[0][2] = sum;
        int count = 0;
        for (int i = 0; i < arrChess1.length; i++) {
            for (int j = 0; j < arrChess1[i].length; j++) {
                if (arrChess1[i][j] != 0){
                    count++;
                    sparse[count][0] = i;
                    sparse[count][1] = j;
                    sparse[count][2] = arrChess1[i][j];
                }
            }
        }
        for (int[] arr : sparse) {
            for (int i : arr) {
                System.out.printf("%3d",i);
            }
            System.out.println();
        }
        System.out.println("=================稀疏数组转换原始数组===============");
        int[][] arrChess2 = new int[sparse[0][0]][sparse[0][1]];
        for (int i = 1; i < sparse.length; i++) {
            arrChess2[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }
        for (int[] arr : arrChess2) {
            for (int i : arr) {
                System.out.printf("%3d",i);
            }
            System.out.println();
        }

    }
}

测试输出结果：

=================原始数组===============
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  1  0  2  0  0  0
  0  0  0  0  0  0  1  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
=================稀疏数组===============
 11 11  3
  5  5  1
  5  7  2
  6  6  1
=================稀疏数组转换原始数组===============
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  1  0  2  0  0  0
  0  0  0  0  0  0  1  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0

稀疏数组的应用场景：

1 棋盘存储

2 矩阵存储

源码地址：

https://gitee.com/wang-hailei/arithmetic/tree/main

码农公寓