数据结构——＞稀疏数组

一、稀疏数组

1、定义

稀疏数组也叫稀疏矩阵，是普通数组的压缩，在这里我们可以说普通数组的无效数据量远远大于有效数据量

有效数据：在下方的例子中，非0数字就是有效数据

普通数组：

其稀疏数组表现形式为：

如果第一个例子没看懂，那我们再来举个例子

普通数组

在这一堆妹子里你是不是只想要杨x和赵x，你不想要凤x吧

稀疏数组

2、储存

上面我们说到稀疏数组是由普通数组压缩而来，那为什么我们要压缩呢？

1、原数组中存在大量无效数据，占用了大量存储空间，而真正有用的数据又少。
2、压缩可以减少不必要的空间浪费，加快磁盘IO

3、储存方式

1、普通储存

第一行就是数组的 总行数 总列数 总的非零数据个数
往下各行是 非0数据所在行 所在列 具体值

例如

解释：
7 7 7 代表这个数组是7行7列，有四个有效数字
1 2 1 代表在第一行，第二列，有效数据的值是1
往后同理

4、代码实现

a、普通数组——>稀疏数组

1. 先遍历二维数组 得到非0数据的个数
2. 创建对应的稀疏数组
3. 遍历二维数组，将非0的值存放到 sparseArr中

public class SparseArray{
    public static void main(String[] args) {
        //创建一个原始的7*7的数组
        int chessArr1[][] = new int[7][7];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 3;
        chessArr1[5][6] = 4;
        // 输出原始的二维数组
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        // 将二维数组————>稀疏数组
        // 1. 先遍历二维数组 得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 2. 创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        // 给稀疏数组赋值
        sparseArr[0][0] = 7;
        sparseArr[0][1] = 7;
        sparseArr[0][2] = sum;

        // 遍历二维数组，将非0的值存放到 sparseArr中
        int count = 0; //count 用于记录是第几个非0数据
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    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();
    }
}

这里说几行关键代码

这里的[sum+1][3]
代表稀疏数组的行，sum代表你这个稀疏数组里的有效数据的个数，加的一代表稀疏数组第0行，也就是稀疏数组的行数，列数，有效数据个数这一行。

b、稀疏数组——>普通数组

//稀疏数组————>二维数组
        //1、先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        //2. 在读取稀疏数组后几行的数据(从第二行开始)，并赋给 原始的二维数组
        for(int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        // 输出恢复后的二维数组
        System.out.println();
        System.out.println("恢复后的二维数组");

        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

思路：