专业团队
2020-08-21
445
原创

数据结构与算法---稀疏数组


稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是指无效数据量远大于有效数据量的数组。刚说到稀疏数组是一种压缩后的数组，为什么要进行压缩存储呢？

  1. 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
  2. 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率

1.问题引出

将一个普通数组转换成一个稀疏数组，再将稀疏数组转换回普通数组。

avatar

【说明】：稀疏数组第一行：原数组的行、列、非0元素个数；剩下行：非0元素的行索引、列索引、值。

2.创建一个二维数组

public class SparesArray {
	public static void main(String[] args) {
		//--------------------创建二维数组-----------------------
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		// 输出原始二维数组
		for(int[] row : chessArr1){
			for(int data : row){
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
	}
}

【输出】：

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

3.二维数组 ---> 稀疏数组

//--------------------将二维数组 转 稀疏数组--------------------
// 1.先遍历二维数组，得到非0数据个数sum
int sum = 0;
for(int i = 0; i < 11; i++){
	for(int j = 0; j <11; j++){
		if(chessArr1[i][j] != 0){
			sum++;
		}
	}
}	

// 2.创建对应的稀疏数组
int sparseArr[][] = new int[sum + 1][3];

// 3.为稀疏数组赋值
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;

// 遍历二维数组，将非0的数据存放在稀疏数组中
int count = 0; 
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];
		}
	}
}

// 4.输出稀疏数组
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]);
}

【输出】：

得到的稀疏数组为：
11	11	2	
1	 2	 1	
2	 3	 2

4.稀疏数组 ---> 二维数组

//--------------------将稀疏数组 恢复 二维数组--------------------
// 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

// 2.从稀疏数组的第二行读取，并赋给 原始的二维数组
for(int i = 1; i < sparseArr.length; i++){
	chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}

// 3.输出恢复后的二维数组
for(int[] row : chessArr2){
	for(int data : row){
		System.out.printf("%d\t", data);
	}
	System.out.println();
}

【输出】：

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

5.代码重构

public class SparesArray {
	public static void main(String[] args) {
		//--------------------创建二维数组-----------------------
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		for(int[] row : chessArr1){
			for(int data : row){
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
		
		//--------------------将二维数组 转 稀疏数组--------------------
		// 1.先遍历二维数组，得到非0数据个数sum
		int sum = 0;
		for(int i = 0; i < 11; i++){
			for(int j = 0; j <11; j++){
				if(chessArr1[i][j] != 0){
					sum++;
				}
			}
		}
		System.out.println("=======================================")
		// 2.创建对应的稀疏数组
		int sparseArr[][] = new int[sum + 1][3];

		// 3.为稀疏数组赋值
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = sum;
		// 遍历二维数组，将非0的数据存放在稀疏数组中
		int count = 0; 
		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];
				}
			}
		}
		
		// 4.输出稀疏数组
		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]);
		}
		System.out.println("=======================================")
		
		//--------------------将稀疏数组 恢复 二维数组--------------------
		// 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
		
		// 2.从稀疏数组的第二行读取，并赋给 原始的二维数组
		for(int i = 1; i < sparseArr.length; i++){
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}
		
		// 3.输出恢复后的二维数组
		for(int[] row : chessArr2){
			for(int data : row){
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}	
		
	}
}

【输出】：

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	
=================================================================================
得到的稀疏数组为：
11	11	2	
1	2	1	
2	3	2	
=================================================================================
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
Java
数据结构与算法
  • 作者：李延松(联系作者)
  • 发表时间：2020-08-21 10:53
  • 版本声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 公众号转载:请在文末添加作者公众号二维码

评论

留言