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

稀疏数组

当一个数组大部分元素是0,或者为同一个值的数组时，可以使用稀疏数组保存

---

一、存储

稀疏数组是一种压缩后的数组，压缩存储可以节省存储空间以避免资源的不必要浪费，在数据序列化到磁盘时压缩存储可以提高IO效率。

1.存储方式

第一行存储原始数据总行数，总列数，总的非零个数。
接下来每一行都存储非零数所在行，所在列，和具体值。

二、将稀疏数组存在磁盘中

使用IO流将稀疏数组存放到磁盘中，原数组和稀疏数组比较，肯定是稀疏数组体积比较小占用空间更少。

三、代码示例

package sparsearray;//稀疏数组

import java.awt.Desktop;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

//课后练习
/*
 * 要求：
 * 1）在前面的基础上，将稀疏数组保存在磁盘上，比如map.data
 * 2)恢复原来的数组时读取map.data进行恢复
 */

public class SparseArray {
	public static void main(String[] arg) throws Exception {
		//创建一个原始的二维数组11*11
		//0；表示没有棋子，1表示黑子2蓝子
		int chessArr1[][] = new int [11][11];
		chessArr1[1][2]=1;
		chessArr1[2][3]=2;
		chessArr1[4][5]=2;
		//输出原始的二维数组
		System.out.println("原始的二维数组");
		for(int[] row:chessArr1) {
			for(int data:row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		// 将二维数组转稀疏数组的思路 
		//1.先遍历二维数组得到非零数据个数
		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("sum="+sum);
		//2.创建对应的稀疏数组
		int sparseArr[][]=new int[sum+1][3];
		//给稀疏数组赋值
		sparseArr[0][0]=11;
		sparseArr[0][1]=11;
		sparseArr[0][2]=sum;
		//遍历二维数组，将非0的值存放到sparArr中
		int b=0;//b用于记录稀疏数组个数
		for(int i=0;i<11;i++) {
			for(int j=0;j<11;j++) {
				if(chessArr1[i][j]!=0) {
					b++;
					sparseArr[b][0]=i;
					sparseArr[b][1]=j;
					sparseArr[b][2]=chessArr1[i][j];
					
				}
			}
			
		}
	//保存稀疏数组
	File file=new File("C:\\Users\\86199\\eclipse-workspace\\DataStructures\\map.data");
	FileOutputStream fos=new FileOutputStream(file);
	OutputStreamWriter write=new OutputStreamWriter(fos,"UTF-8");
	//输出稀疏数组的形式
	System.out.println();
	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]);
		if (i == sparseArr.length - 1) {
			write.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2]);
		} else {
			write.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ",");
		}
	

	
	}
	System.out.println("写入文件中。。。"); 
	write.close();
	fos.close();
	
	System.out.println("打开文件中。。。");
	Desktop.getDesktop().open(file);
	System.out.println("-------------读取_map.data");
	// 创建 FileReader 对象
	FileInputStream fis = new FileInputStream(file);

	InputStreamReader reader = new InputStreamReader(fis, "UTF-8");
	StringBuffer sb = new StringBuffer();
	while (reader.ready()) {
		sb.append((char) reader.read());// 转成char加到StringBuffer对象中
	}

	System.out.println(sb.toString());
	reader.close();// 关闭读取流
	fis.close();// 关闭输入流,释放系统资源

	//将稀疏数组---》恢复成原始的二维数组
	/*
	 * 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
	 * 2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可。
	 */
	//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];
	}
	
	
	//输出恢复后的二维数组
	System.out.println();
	System.out.println("恢复后的二维数组");
	for(int[] row:chessArr2) {
		for(int data:row) {
			System.out.printf("%d\t",data);
		}
		System.out.println();
	}
			
			
	}

}