稀疏数组详解

柔情只为你懂 2023-05-22 13:28 24阅读 0赞

在编写一个五子棋的程序当中，要实现存盘退出和续上盘的功能，如下图所示：存在一个棋盘  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
退出保存的时候如何保存呢？使用一个二维数组，1表示红棋，2表示黑棋，0表示没有下过的格子。  
因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据，这个时候就可以使用到 **稀疏数组。**

稀疏数组

基本介绍  
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。  
稀i疏数组的处理方法是:

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

具体使用的效果如下图所示：同比与二维数组的 6X8 到稀疏数组的 3X10是节省了更多的空间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
在最开始的棋盘当中将二维数组转换为稀疏数组。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
二维数组转稀疏数组的思路

1.  遍历原始的二维数组，得到有效数据的个数sum
2.  根据sum就可以创建稀疏数组`sparseArr=int[sum+1] [3]`
3.  将二维数组的有效数据数据存入到稀疏数组

稀疏数组转原始的二维数组的思路

1.  先读取稀疏数组的第一行， 根据第一-行的数据 ，创建原始的二维数组，比如上面的`Arr=int[5][5]`
2.  在读取稀疏数组后几行的数据，并赋给原始的二维数组即可.

实现代码：  
1创建一个二维数组，并且输出。就是上方的棋盘数组。

//创建一个二维数组 5*5
    int Array1[][]=new int[5][5];
    Array1[1][1]=1;
    Array1[2][2]=2;
    //输出原二维数组
    for (int[] row : Array1) { 
    	for(int data :row) { 
    		System.out.printf("%d\t",data);
    	}
    	System.out.println();
    }

![在这里插入图片描述][20200418113008369.png]  
在转换为稀疏数组的时候，需要给定一个value，即二维数组当中一共有多少个不为0的数值。很显然这里的sum为2。

int sum=0;
    for (int i = 0; i <5; i++) { 
    	for (int j = 0; j < 5; j++) { 
    		if (Array1[i][j]!=0)
    			sum++;
    	}
    }

创建一个稀疏数组：第一行的值直接赋值过去，二维数组的行列，以及不为0的个数

int spraseArr[][]=new int [sum+1][3];
    //赋值
    spraseArr[0][0]=5;
    spraseArr[0][1]=5;
    spraseArr[0][2]=sum;

后面的值赋值：每一个值对应一行数据，切定义一个count记录这是第几个数据。

int count =0;
    for (int i = 0; i <5; i++) { 
    	for (int j = 0; j < 5; j++) { 
    		if (Array1[i][j]!=0) { 
    			count++;
    			spraseArr[count][0]=i;
    			spraseArr[count][1]=j;
    			spraseArr[count][2]=Array1[i][j];
    		}
    	}
    }

最后对稀疏数组进行输出：

for (int i = 0; i < spraseArr.length; i++) { 
    			System.out.printf("%d\t%d\t%d\t\n",spraseArr[i][0],spraseArr[i][1],spraseArr[i][2]);
    		}

![在这里插入图片描述][2020041811350540.png]  
最后再将稀疏数组转换为二维数组：  
先定义一个数组，获取稀疏数组上存放的行和列的数据

int Array2 [] []=new int[spraseArr[0][0]][spraseArr[0][1]];

并且对稀疏数组上下面的每一行数据进行遍历出来：

for (int i = 1; i < spraseArr.length; i++) { 
    	Array2[spraseArr[i][0]][spraseArr[i][1]]=spraseArr[i][2];
    }

最后使用二维数组的变量方法对数组进行遍历输出：

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

最后分享一条文案：

要知道  
到站了就要下车  
空出来的位置  
迟早会有人替

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230521/6b39b9e365754d50b2a7d2c2b23ea117.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230521/9731f2bb703f40b2839f61ba5ce5f972.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: /images/20230521/df4d917b55384dd7bd6c26e3ce1697ca.png
[20200418113008369.png]: /images/20230521/df9bb4d373c045ac81d1199e5c524f32.png
[2020041811350540.png]: /images/20230521/1ee00f5c18464b00918f5abf7e07f18b.png