数据结构之稀疏数组

系统管理员 2021-05-03 05:02 600阅读 0赞

## 1、典型的应用场景——棋盘(地图)： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1lZQkRFU0hJSklF_size_16_color_FFFFFF_t_70]

## 2、二维数组转换成稀疏数组的思路： ##

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

## 3、稀疏数组转原始的二维数组的思路： ##

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

## 4、代码实现： ##

package saprsearray;
    
    public class SparseArray { 
    
    	public static void main(String[] args) { 
    		//创建一个原始的二维数据11*11做棋盘
    		//0：表示没有棋子，1表示黑子，2表示黑子
    		int chessArr1[][]=new int[11][11];
    		chessArr1[1][2]=1;
    		chessArr1[2][3]=2;
    		chessArr1[5][6]=28;
    		//输出原始的二维数组
    		System.out.println("原始的二维数组:");
    		for(int[] row:chessArr1) { 
    			for(int data:row) { 
    				System.out.printf("%d\t",data);
    			}
    			System.out.println();
    			System.out.println();
    		}
    		 //遍历二维数组，得到非零数据的个数
    		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++;
    				}
    			}
    		}
    		System.out.println("sum="+sum);
    		//创建相应的稀疏数组
    		int sparseArr[][]=new int [sum+1][3];
    		//给稀疏数组赋值
    		sparseArr[0][0]=11;
    		sparseArr[0][1]=11;
    		sparseArr[0][2]=sum;
    		//遍历二维数组，将二维数组的有效数据存入到稀疏数组.
    		int count=0;//用来换行,记录第几个非零数据
    		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;
    					sparseArr[count][1]=j;
    					sparseArr[count][2]=chessArr1[i][j];
    				}
    			}
    		}
    		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]);
    		}
    		//将稀疏数组恢复成二维数组
    		/* * 1、先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组， * 比如上面的`chessArr2=int[11][11]`. * 2、在读取稀疏数组后几行的数据，并赋给原始的二维数组即可. */
    		//先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，
    		int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
    		//在读取稀疏数组后几行的数据(从第二行开始)，并赋给原始的二维数组即可.
    		for(int i=1;i<sparseArr.length;i++) { 
    			chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
    		}
    		//输出恢复后的二维数组
    		System.out.println("恢复后的二维数组:");
    		for(int[] row:chessArr2) { 
    			for(int data:row) { 
    				System.out.printf("%d\t",data);
    			}
    			System.out.println();
    			System.out.println();
    		}
    	}
       
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1lZQkRFU0hJSklF_size_16_color_FFFFFF_t_70]: /images/20210502/9865f034c8994cfa93034d88b3373211.png