你真的懂稀疏数组吗？进来看！

稀疏数组

当一个数组中大部分元素为0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方式是:记录数组一共有几行几列，有多少个不同值把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模。从字面上我们也可以得知，它仍然是一个数组，他的作用就是将一个对应的数组数据进行优化。

1.背景

需求：编写五子棋游戏中，有存盘退出和继续上一盘的功能。

image-20220106235102890

2.二维数组记录棋盘数据

比如，我们可以将棋盘进行抽象化，用一个 11*11 的二维数组来表示，然后用 0 表示空点，用 2 表示白子，用 1表示黑子，于是就可以抽象为如下模样。

image-20220106235314228

不足之处：

整个数组我们用了11*11（共121）个点来保存数据，但其中有119个都是0。实际上我们只需要将黑白棋子的数据保存起来就可以。

把这样没有价值的数据起来，不但会浪费存储空间的大小，如果写入到磁盘中，还会增大 IO 的读写量，影响性能，这就是用普通二维数组来表示棋盘数据的不足之处。

3.稀疏数组记录棋盘数据

当我们使用稀疏数组时，就变成了以下的样子，第0行代表这是一个11行11列且有2个有效值的数组，第1行代表着第一个有效值的位置在第1行第2列和该值的大小为1。（这是事先约定好的）

image-20220107000055005

从这个二维数组你可以看出我们只使用了一个3*3的数组就存储了之前11 * 11的数组存储的数据，这存储效率大大的。

4.二维数组转稀疏数组

下面是详细的代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.Arrays;

public class xishushuzu {
    public static void main(String[] args) {
        //创建一个二维数组11*11  0：表示没棋子 1：表示白棋 2;表示黑棋
        int[][] array1 =new int[11][11];
        array1[1][2] = 1;
        array1[2][3] = 2;
        //输出原始数组
        System.out.println("输出原始数组");
        for (int[] ints : array1) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();  //换行
        }
        //转换为稀疏数组
        int sum = 0;    	//获取有效值的个数
        for (int i = 0; i <11; i++) {
            for (int j = 0; j < 11; j++) {
                if (array1[i][j]!=0){
                    sum++;   //统计有效值个数
                }
            }
        }
        System.out.println("有效值个数"+sum);

        //创建一个稀疏数组
        int[][] array2 = new int[sum+1][3];

        array2[0][0] = 11;   //第0行0列存储原二维数组的行数
        array2[0][1] = 11;   //第0行1列存储原二维数组的列数
        array2[0][2] = sum;  //第0行2列存储原二维数组有效值的个数

        //遍历二维数组，将非零的值存放在稀疏数组中
        int count = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j]!=0){
                    count++;
                    array2[count][0] = i;
                    array2[count][1] = j;
                    array2[count][2] = array1[i][j];
                }
            }
            
        }
        //输出压缩后的稀疏数组
        System.out.println();
        System.out.println("稀疏数组");
        System.out.println("行  列  值");
        for (int[] ints : array2) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();  //换行
        }
        System.out.println("==================");
        //由稀疏数组还原到原数据
        //首先通过数组传值创建新的数组
        int[][] array3 = new int[array2[0][0]][array2[0][1]];  
        for (int i = 1; i < array2.length; i++) {   //遍历稀疏数组 注意这里的i从1开始
            /*array2[i][0]是行
              array2[i][1]是列
              array2[i][2]是值
            */
            array3[array2[i][0]][array2[i][1]] = array2[i][2];
        }
        //打印原数据
        System.out.println("由稀疏数组还原");
        for (int[] ints : array3) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();  //换行
        }
    }
}

本文采用CC-BY-SA-3.0协议，转载请注明出处
作者: Lee