1.1. Sparse array

Linear structure

• 1) Linear structure is the most commonly used data structure , Its characteristic is between data elements There is one-on-one The linear relationship of ;
• 2) Linear structures have two different storage structures , namely Sequential storage structure ( Array ) and Chain storage structure ( Linked list ). A linear table stored sequentially is called a sequential table surface , The storage elements in the sequence table are continuous
• 3) A linear list in chain storage is called a linked list , Storage in linked list Elements are not necessarily continuous , The place where data elements and adjacent elements are stored in the element node Address information
• 4) The common linear structures are ： Array , queue , Lists and stacks , We will explain in detail later .

Nonlinear structure

Nonlinear structures include : Two dimensional array , Multidimensional arrays , Generalized table , Tree structure , The graph structure

1.1、 sparse sparsearray Array

1.1.1、 First look at a real need

In the program of Gobang , It has the function of saving, exiting and continuing .

To analyze problems :
Because many of the values of this 2D array are default values 0, So a lot of meaningless data was recorded .-> Sparse array .

1.1.2、 Basic introduction

When most of the elements in an array are 0, Or an array of the same value , It can be used Sparse array To save the array .

The way to deal with sparse arrays is :

• 1) There are several rows and columns in the record array , How many different values
• 2) Record the columns and values of elements with different values in a small array , thus Shrink program The scale of
  

1.1.3 Application example

• 1) Use sparse arrays , To keep a two-dimensional array similar to the one before ( The board 、 Maps, etc )
• 2) Save the sparse array , And can restore the original two-dimensional array number from the new
• 3) Analysis of the overall thinking :
  
• 4) Code implementation

 public class SparseArray {
    

	public static void main(String[] args) {
    
		//  Create an original two-dimensional array  11 * 11
		// 0:  No chess pieces , 1  Express   The spots  2  Watch blue son 
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		chessArr1[4][5] = 2;
		//  Output the original two-dimensional array 
		System.out.println(" The original two-dimensional array ~~");
		for (int[] row : chessArr1) {
    
			for (int data : row) {
    
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}

		//  Put two-dimensional array   turn   Sparse array thinking 
		// 1.  First, traverse the two-dimensional array   Get the blame 0 Number of data 
		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 the corresponding sparse array 
		int sparseArr[][] = new int[sum + 1][3];
		//  Assign values to sparse arrays 
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = sum;
		
		//  Traversing a two-dimensional array , Will not 0 The value of is stored in  sparseArr in 
		int count = 0; //count  It's the number one non 0 data 
		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];
				}
			}
		}
		
		//  Output sparse array form 
		System.out.println();
		System.out.println(" Get the sparse array as ~~~~");
		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();
		
		// Will sparse array  --》  Return to   The original two-dimensional array 
		/* * 1.  First read the first row of the sparse array , According to the data in the first line , Create the original two-dimensional array , Like the one above  chessArr2 = int [11][11] 2.  After reading the sparse array a few lines of data , And give it to   The original two-dimensional array   that will do . */
		
		//1.  First read the first row of the sparse array , According to the data in the first line , Create the original two-dimensional array 
		
		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
		
		//2.  After reading the sparse array a few lines of data ( Start with the second line ), And give it to   The original two-dimensional array   that will do 
		
		for(int i = 1; i < sparseArr.length; i++) {
    
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}
		
		//  Output the recovered 2D array 
		System.out.println();
		System.out.println(" Recovered 2D array ");
		
		for (int[] row : chessArr2) {
    
			for (int data : row) {
    
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
	}

}