稀疏数组sparsearray

文章目录

1. 1. 需求
2. 2. 分析问题
3. 3. 稀疏数组基本介绍
4. 4. 稀疏数组处理方法
5. 5. 稀疏数组举例说明
6. 6. 应用实例
7. 7. 整体思路分析
8. 8. 代码实现

需求

编写的五子棋程序中，有存盘退出和续上盘的功能。

分析问题

因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据

稀疏数组基本介绍

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

稀疏数组处理方法

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

稀疏数组举例说明

应用实例

1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
2. 把稀疏数组存盘，并且可以重新恢复原来的二维数组数

整体思路分析

原始的二维数组 –> 稀疏数组的思路

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

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

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

稀疏数组 –> 原始的二维数组的思路

1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如 int[][] chessArr = new int[11][11]

2. 在读取稀疏数组后几行的数据，并赋给原始的二维数组

代码实现

public class SparseArray {

    public static void main(String[] args) {
        // 创建原始的二维数组 11 * 11
        // 0表示没有棋子，1表示黑棋，2表示蓝棋
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;

        // 输出原始的二维数组
        System.out.println("原始的二维数组----------");
        for (int[] ints : chessArr) {
            for (int data : ints) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 原始的二维数组 --> 稀疏数组的思路
        // 1、遍历二维数组，得到非 0 数据的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 2、创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // 3、遍历二维数组，将非 0 数据存入 sparseArr
        // count 用于记录是第几个非 0 数据
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[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();

        // 稀疏数组 --> 原始的二维数组的思路
        // 1.  先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如 int[][] chessArr = new int[11][11]
        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[] ints : chessArr2) {
            for (int data : ints) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}