当前位置: 首页 > >

稀疏矩阵的压缩与还原(Java实现)

发布时间:

稀疏矩阵的压缩与还原(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 ",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 ",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]+" ");
count1++;
if (count1%3==0){
writer.write("
");
}
}
}
} 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 ",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 ",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]+" ");
count1++;
if (count1%3==0){
writer.write("
");
}
}
}
} 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(" ");
for (int i=0;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 ",sparseArr[i][j]);
}
System.out.println();
}


//1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组

int[][] chessArr2=new int[sparseArr[0][0]][sparseArr[0][1]];
//2.遍历稀疏矩阵,给二维数组赋值
for(int i=1;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 ",chessArr2[i][j]);
}
System.out.println();

}

}
}


4.总结

目前在跟着尚硅谷的韩顺*老师学*图解数据结构和算法(Java版),刚学完第一个知识点,受益匪浅,故作此篇,与各位学*交流!
2019/8/29



友情链接: