数据结构与算法--稀疏数组

1.引入

比如在编写五子棋时要实现存盘退出和继续上盘的功能。

如果使用二维数组来记录，每行每列，白子对应2，黑子对应1，默认值对应0.然后这里黑子对应二维数组a[1][2]。白子对应二维数组a[2][3]。

如果棋子很少，那么这么大的棋盘中只有这几个棋子，对应的二维数组中有很多0，可以说是没有意义的数据。那么可以用稀疏数组对这个二维数组进行压缩。

2.基本介绍

当一个数组中大部分元素为0或者为同一个值时，可以用稀疏数组来保存这个数组。

稀疏数组的处理方法：

记录数组共有几行几列，有多少个不同的值
把具有不同值的元素的行列以及元素的值记录在一个小规模的数组中，从而缩小程序的规模

简单点说就是稀疏数组只记录有数据的行和列。

3.举例：

这里数组中有8个非0数据，有6行7列

[0]这里存放原来数组的行列数以及非0数据的个数。

下面[1]到[8]就对应非0元素的行和列的下标以及值。比如原来的a[0][3]是22，这里就存0，3，22

那么就是9行3列，9*3=27，6*7=42.确实占用空间变少了。

4.再来看开始的棋盘

用稀疏数组的话，可以变成这样

[0]处为11行，11列，2个非元素

第一个非0元素在[1][2]处，row为1，col为2，val为1

第二个非0元素在[2][3]处，row为2，col为3，val为2

原来的二维数组规模为11*11，现在为3*3

5.二维数组与稀疏数组转化思路

要把二维数组转化为稀疏数组：

先遍历原始的二维数组，得到有效的数据的个数sum
再根据这个sum创建稀疏数组sparseArr int[sum+1][3] （行数不确定，要看有多少个有效数据，再加上第0行的统计这行。列数固定为3）
将二维数组的有效数据存入到稀疏数组

要把稀疏数组恢复为二维数组：

先读取稀疏数组的第一行，因为第一行记录了二维数组的行和列。读取后创建原始的二维数组。如chessArr2=int[11][11]
再读取后几行的数据，赋值给原始的二维数组。（如果无效值为0的话，因为二维数组没有赋值时也是默认为0，就直接通过sparseArr将二维数组中对应的赋值，就不用多层循环了，像下面这样）

6.代码

public class SparseArray {
    public static void main(String[] args) {
        //创建原始二维数组，0表示默认没有棋子，1表示黑子，2表示白子
        int chessArr1[][]=new int[11][11];
        chessArr1[1][2]=1;
        chessArr1[2][3]=2;
        //用增强for循环输出原始的二维数组
        System.out.println("二维数组");
        for(int[] row : chessArr1){
            for(int data:row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        //转为稀疏数组，先遍历二维数组得到非0数据个数
        int sum=0;
        for(int i=0;i<11;i++){
            for(int j=0;j<11;j++){
                if(chessArr1[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println("非0值有"+sum+"个");
        //创建稀疏数组
        int sparseArr[][]=new int[sum+1][3];
        //给稀疏数组赋值
        sparseArr[0][0]=11;
        sparseArr[0][1]=11;
        sparseArr[0][2]=sum;
        //加个计数器，用来记录是第几个非0元素
        int count=0;
        //遍历二维数组，将非0值存到稀疏数组
        for(int i=0;i<11;i++){
            for(int j=0;j<11;j++){
                if(chessArr1[i][j]!=0){
                    count++;//遇到非0就加一
                    sparseArr[count][0]=i;
                    sparseArr[count][1]=j;
                    sparseArr[count][2]=chessArr1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println();
        System.out.println("稀疏数组");
        for(int i=0;i<sparseArr.length;i++){
            System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
        }
        //将稀疏数组恢复成二维数组
        System.out.println("恢复为二维数组");
        int row=sparseArr[0][0];
        int col=sparseArr[0][1];
        int val=sparseArr[0][2];
        //先找到行和列长度
        int chessArr2[][]=new int[row][col];
        //从稀疏数组第二行开始遍历，赋值给二维数组
        for(int t=1;t<=val;t++){
            chessArr2[sparseArr[t][0]][sparseArr[t][1]]=sparseArr[t][2];
        }
        //输出
        for(int[] row1 : chessArr2){
            for(int data:row1){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}

代码中要注意的一点就是我是取t<=val，然后t从1开始。如果是用sparseArr.length的话就是t<sparseArr.length

然后下面这里是增强for