1. Actual needs

Written in the gobang program, there is a save disk exit and continued on the disk function.

To analyze problems

Because many of the values in this two-dimensional array are default values of 0, a lot of meaningless data is recorded.

2. Basic introduction

A sparse array can be used to store an array when most of its elements are 0, or when it is an array of the same value.

Sparse array processing is as follows:

    1. How many rows, how many columns, how many different values are in the array
    1. Reduce the size of the program by recording the columns and columns of elements with different values in a small array

3. Application examples

  1. Use sparse arrays to preserve two-dimensional arrays like the ones above (checkerboards, maps, etc.)

  2. Save the sparse array to disk, and can be restored to the original two-dimensional array number

4. Code implementation

public static void main(String[] args) {
        // Create a primitive two-dimensional array 11 * 11
        // 0: indicates that there are no chessmen, and 1 indicates that there are no black pieces and 2 blue pieces
        int chessArr1[][] = new int[11] [11];
        chessArr1[1] [2] = 1;
        chessArr1[2] [3] = 2;
        chessArr1[4] [5] = 2;

        // Outputs the original two-dimensional array
        System.out.println("Original two-dimensional array ~~");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }


        // Convert a two-dimensional array to a sparse array
        // 1. Get the number of non-zero data by iterating through the array
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if(chessArr1[i][j] ! =0) { sum++; }}}// 2. Create a sparse array
        int sparseArr[][] = new int[sum + 1] [3];
        // Assign to the sparse array
        sparseArr[0] [0] = 11;
        sparseArr[0] [1] = 11;
        sparseArr[0] [2] = sum;

        // Iterate over the two-dimensional array and store non-zero values in sparseArr
        int count = 0; //count is used to record the number of non-zero data points
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if(chessArr1[i][j] ! =0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j]; }}}// Outputs a sparse array
        System.out.println();
        System.out.println("The resulting sparse array is ~~~~");
        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();
        
        // Restore the sparse array -- to the original two-dimensional array
        /* * 1. Read the first row of the sparse array. From the first row, create the original two-dimensional array, such as * 2 above. After reading a few rows of the sparse array, assign to the original two-dimensional array. */

        //1. Read the first row of the sparse array and create the original two-dimensional array based on the data in the first row

        int chessArr2[][] = new int[sparseArr[0] [0]][sparseArr[0] [1]].//2. Read the next few lines of the sparse array (starting with the second line) and assign to the original two-dimensional array
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }


        // Output the restored two-dimensional array
        System.out.println();
        System.out.println("Restored two-dimensional array");

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