稀疏矩阵的压缩与还原（Java实现）
1.稀疏矩阵的概念
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵，如：
2.稀疏矩阵的压缩
如果要把一个含有如此多0元素的稀疏矩阵存储到计算机中，这些没有意义的0同样地会消耗掉计算机的内存，那么这势必造成计算机内存的浪费。那么，对于稀疏矩阵的存储，我们应该如何去处理呢？下面介绍一个例子：
例： 现在要模拟一个11*11的五子棋棋盘的存档和续局。棋盘上有黑、白两种棋子，分别用1、2来表示，没有棋子的地方，则用0来表示。假设这个棋盘是只有3颗棋子，2颗白棋子，1颗黑棋子，则该棋盘抽象出来，就是一个稀疏矩阵，其中非0元素只有3个，分别是1，2，2。现在，不想下棋了，那么要保存这个棋盘，也就是保存这个稀疏矩阵。
图解思路：
棋盘上的状态如图
我们从图所得到的信息：棋盘矩阵是11 * 11的，有3颗棋子
黑子所在的位置是矩阵的第3行第3列,值是1
白子所在的位置是矩阵的第6行第2列、第4行第5列，值都为2
转化成数组的存储，就是：
黑子所在的位置是矩阵的第2行第2列,值是1
白子所在的位置是矩阵的第5行第1列、第3行第4列，值都为2（因为数组的下标是从0开始的）
那么，我们可以将上面的信息抽象成一个新的二维数组：
这样就实现了稀疏矩阵的压缩
下面是代码实现：
import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; public class SparseArray { public static void main(String[] args) throws IOException { //创建一个原始的二维数组11*11 //0：表示无棋子，1表示黑子，2表示白子 int[][] chessArr1=new int[11][11]; chessArr1[2][2]=1; chessArr1[5][1]=2; chessArr1[3][4]=2; //输出原始的二维数组 System.out.println("原始的二维数组："); for (int[] row:chessArr1){ for (int data:row){ System.out.printf("%d\t",data); } System.out.println();//每打印一行就换一行 } //将二维数组 转 稀疏数组 //1.先遍历二维数组，得到非0数据的个数 int count=0; for(int[] row:chessArr1){ for (int data:row){ if (data!=0){ count++; } } } System.out.println("非0的元素个数为："+count); //2.创建稀疏数组 int[][] sparseArr=new int[count+1][3]; //3.给稀疏数组赋值 sparseArr[0][0]=11; sparseArr[0][1]=11; sparseArr[0][2]=count; //4.遍历二维数组，将非0的值存放到sparseArr中 int row=1;//用于记录是第几个非0数据 for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr1[i][j]!=0){ sparseArr[row][0]=i; sparseArr[row][1]=j; sparseArr[row][2]=chessArr1[i][j]; row++; } } } //6.输出稀疏数组 System.out.println("得到的稀疏数组为："); for (int[] row1:sparseArr){ for (int data:row1){ System.out.printf("%d\t",data); } System.out.println(); } //7.将稀疏数组写入到文件中 FileWriter writer=null; try { writer=new FileWriter(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt")); int count1=0;//用于控制换行 for (int i = 0; i < sparseArr.length; i++) { for (int j = 0; j < sparseArr[i].length; j++) { writer.write(sparseArr[i][j]+"\t"); count1++; if (count1%3==0){ writer.write("\n"); } } } } catch (IOException e) { e.printStackTrace(); }finally { if (writer!=null) { writer.close(); } }
输出结果如下：
控制台输出结果：
由于需求是棋盘存档，显然要把压缩后的数组保存到文件中，那么上面代码得到的data.txt文件内容如下：
棋盘存档成功！
3.稀疏矩阵的还原
还原的话就很简单了，利用压缩后的数组的第0行信息来构建新的二维数组（11 * 11），然后读取第一行以后的信息，把非0元素的行、列和值对应地赋值到新二维数组就可以了。
整个需求的完整代码实现如下：
package cn.Day01.demo2; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; public class SparseArray { public static void main(String[] args) throws IOException { //创建一个原始的二维数组11*11 //0：表示无棋子，1表示黑子，2表示白子 int[][] chessArr1=new int[11][11]; chessArr1[2][2]=1; chessArr1[5][1]=2; chessArr1[3][4]=2; //输出原始的二维数组 System.out.println("原始的二维数组："); for (int[] row:chessArr1){ for (int data:row){ System.out.printf("%d\t",data); } System.out.println();//每打印一行就换一行 } //将二维数组 转 稀疏数组 //1.先遍历二维数组，得到非0数据的个数 int count=0; for(int[] row:chessArr1){ for (int data:row){ if (data!=0){ count++; } } } System.out.println("非0的元素个数为："+count); //2.创建稀疏数组 int[][] sparseArr=new int[count+1][3]; //3.给稀疏数组赋值 sparseArr[0][0]=11; sparseArr[0][1]=11; sparseArr[0][2]=count; //4.遍历二维数组，将非0的值存放到sparseArr中 int row=1;//用于记录是第几个非0数据 for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr1[i][j]!=0){ sparseArr[row][0]=i; sparseArr[row][1]=j; sparseArr[row][2]=chessArr1[i][j]; row++; } } } //6.输出稀疏数组 System.out.println("得到的稀疏数组为："); for (int[] row1:sparseArr){ for (int data:row1){ System.out.printf("%d\t",data); } System.out.println(); } //7.将稀疏数组写入到文件中 FileWriter writer=null; try { writer=new FileWriter(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt")); int count1=0;//用于控制换行 for (int i = 0; i < sparseArr.length; i++) { for (int j = 0; j < sparseArr[i].length; j++) { writer.write(sparseArr[i][j]+"\t"); count1++; if (count1%3==0){ writer.write("\n"); } } } } catch (IOException e) { e.printStackTrace(); }finally { if (writer!=null) { writer.close(); } } //根据稀疏矩阵来还原二维数组 //0.将稀疏数组从文件中读取出来: /** * */ FileReader reader=new FileReader(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt")); BufferedReader bfreader=new BufferedReader(reader); String temp; String[] temps=null; int lineArr=0; while ((temp= bfreader.readLine())!=null){ temps=temp.split("\t"); for (int i=0;i<temps.length;i++){ sparseArr[lineArr][i]=Integer.parseInt(temps[i]); } lineArr++; } System.out.println("还原后的稀疏矩阵为："); for (int i = 0; i < sparseArr.length; i++) { for (int j = 0; j < sparseArr[i].length; j++) { System.out.printf("%d\t",sparseArr[i][j]); } 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.输出原二维数组 System.out.println("还原后的数组为："); for (int i = 0; i < chessArr2.length; i++) { for (int j = 0; j < chessArr2[i].length; j++) { System.out.printf("%d\t",chessArr2[i][j]); } System.out.println(); } } }
4.总结
目前在跟着尚硅谷的韩顺平老师学习图解数据结构和算法（Java版），刚学完第一个知识点，受益匪浅，故作此篇，与各位学习交流！
