Sparse arrays to illustrate Java data structures

In programming, the importance of algorithms is self-evident. Programs without algorithms have no soul. It can be seen that the importance of the algorithm.
However, before learning the algorithm, we need to master the data structure, which is the basis of the algorithm.
When I was in college, the data structure in the school was taught in C language, because I didn't know C language very well, so I didn't master it very well. Some of the learning materials I searched on the Internet were basically taught in C language.
So, starting with this article, I'll introduce data structures in the Java language. Of course, data structures are algorithms later.

Linear and Nonlinear Structures
  1. linear structure
    As the most commonly used data structure, linear structure is characterized by one-to-one linear relationship between data elements.
    There are two different storage structures in linear structure: sequential storage structure and chain storage structure. The linear table stored sequentially is called the sequential table, and the elements stored in the sequential table are continuous.
    The linear list of chain storage is called linked list. The elements stored in the linked list are not necessarily continuous. The address information of data elements and adjacent elements is stored in element nodes.
    Linear structures are common: arrays, queues, linked lists, and stacks
  2. Nonlinear structure
    Nonlinear structures include two-dimensional arrays, multi-dimensional arrays, generalized tables, tree structures and graph structures.
Sparse array

After having a preliminary understanding of the data structure, we began to make a detailed analysis of some specific data structures.
Let's look at a practical need:
This is a Gobang procedure, which has the function of withdrawing and renewing the board. The following figure shows how to save the chess board shown below.

That's a simple question. Many people may think of using two-dimensional arrays for storage.

As shown above, we use 0 to denote childlessness, 1 to denote sunspot, 2 to denote blue, but this program is a big problem, because many values of the two-dimensional array are default values of 0, so we record a lot of meaningless data, then we can use sparse arrays to compress the two-dimensional array.
So what exactly is a sparse array?
Sparse arrays can be used to save an array when most of the elements in an array are 0 or are arrays of the same value.
Sparse arrays are processed by:

  1. There are several rows and columns in the record array, and how many different values are there?
  2. Reduce the size of the program by recording rows and columns of elements with different values and values in a small array

After understanding the concept of sparse array, we can improve the Gobang program by sparse array.

After the compression of sparse array, the original array changed from 11 rows and 11 columns to three rows and three columns.
The first row of the sparse array records the number of rows and columns of the original array and the number of elements.
The next row records the position and value of the valid element, for example, the second row records element 1 at position 1 and 2 in the original array, and the third row records element 2 at position 2 and 3 in the original array.
To sum up, the idea of converting two-dimensional arrays to sparse arrays is as follows:

  1. Traverse the original two-dimensional array to get the number of valid elements to be saved
  2. Create sparse array sparseArr based on the number of valid elements
  3. The effective data of two-dimensional arrays can be stored in sparse arrays.

The idea of converting sparse arrays to original two-dimensional arrays:

  1. First read the first row of the sparse array and create the original two-dimensional array based on the data of the first row.
  2. Read the data of the last few rows of the sparse array and assign it to the original two-dimensional array.

The idea of implementation has been analyzed, and then implemented with code.
Converting two-dimensional arrays to sparse arrays is implemented in code as follows:

public static void main(String[] args) {
        // Create an original two-dimensional array (11 rows and 11 columns)
        // 0: No chess pieces.
        // 1:Represents sunspot
        // 2:Indicate Blue Zi
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;

        System.out.println("Primitive two-dimensional array:");

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

        // Converting a two-dimensional array to a sparse array
        // First traverse two-dimensional arrays to get the number of non-zero elements
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

        // Create the corresponding sparse array
        int sparseArr[][] = new int[sum + 1][3];
        // Assigning values to sparse arrays
        // The first row of a sparse array contains the number of rows, columns, and valid elements of the original array.
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = sum;

        // Traversing two-dimensional arrays, storing non-zero values into sparse arrays
        int count = 0; // The number of non-zero data used for recording
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i; // Location of storage elements
                    sparseArr[count][1] = j; // Location of storage elements
                    sparseArr[count][2] = chessArr1[i][j];// Store element values
                }
            }
        }
        
        //Traversing sparse arrays
        System.out.println();
        System.out.println("Sparse array:");
        for (int[] row : sparseArr) {
            for (Integer value : row) {
                System.out.printf("%d\t", value);
            }
            System.out.println();
        }
    }

The results are as follows:

The original two-dimensional array:
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   

Sparse array:
11  11  2   
1   2   1   
2   3   2   

In this way, we succeed in converting two-dimensional arrays into sparse arrays.

So how do you convert sparse arrays into two-dimensional arrays with code?

        // Converting sparse arrays to two-dimensional arrays
        // First read the first row of the sparse array and create the original array based on the data of the first row
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

        // After reading the sparse array, several rows of data (starting from the second row) are assigned to the original array.
        for (int i = 1; i < sparseArr.length; i++) {
            // The first column and the second column compose the element position, and the third column is the element value.
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // Two-dimensional array after traversal recovery
        System.out.println();
        System.out.println("Restored two-dimensional array:");
        for (int[] row : chessArr2) {
            for (Integer value : row) {
                System.out.printf("%d\t", value);
            }
            System.out.println();
        }

After clearing the thread of thought, the code is very simple to see the effect of the operation:

The original two-dimensional array:
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   

Sparse array:
11  11  2   
1   2   1   
2   3   2   

Restored two-dimensional arrays:
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   

The overall code is as follows:

public static void main(String[] args) {
        // Create an original two-dimensional array (11 rows and 11 columns)
        // 0: No chess pieces.
        // 1:Represents sunspot
        // 2:Indicate Blue Zi
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;

        System.out.println("Primitive two-dimensional array:");

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

        // Converting a two-dimensional array to a sparse array
        // First traverse two-dimensional arrays to get the number of non-zero elements
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

        // Create the corresponding sparse array
        int sparseArr[][] = new int[sum + 1][3];
        // Assigning values to sparse arrays
        // The first row of a sparse array contains the number of rows, columns, and valid elements of the original array.
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = sum;

        // Traversing two-dimensional arrays, storing non-zero values into sparse arrays
        int count = 0; // The number of non-zero data used for recording
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i; // Location of storage elements
                    sparseArr[count][1] = j; // Location of storage elements
                    sparseArr[count][2] = chessArr1[i][j];// Store element values
                }
            }
        }

        // Traversing sparse arrays
        System.out.println();
        System.out.println("Sparse array:");
        for (int[] row : sparseArr) {
            for (Integer value : row) {
                System.out.printf("%d\t", value);
            }
            System.out.println();
        }

        // Converting sparse arrays to two-dimensional arrays
        // First read the first row of the sparse array and create the original array based on the data of the first row
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

        // After reading the sparse array, several rows of data (starting from the second row) are assigned to the original array.
        for (int i = 1; i < sparseArr.length; i++) {
            // The first column and the second column compose the element position, and the third column is the element value.
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // Two-dimensional array after traversal recovery
        System.out.println();
        System.out.println("Restored two-dimensional array:");
        for (int[] row : chessArr2) {
            for (Integer value : row) {
                System.out.printf("%d\t", value);
            }
            System.out.println();
        }
    }

Tags: Java C Programming

Posted on Sun, 25 Aug 2019 21:38:15 -0700 by allyse