任务要求

把棋盘当作一个稀疏矩阵,0表示没棋,1表示黑棋,2表示蓝棋。

把该稀疏矩阵压缩以三元组形式表示并以文件形式保存,再写另一个程序读取文件中的信息把压缩后的三元组还原成原来的稀疏矩阵。

其中三元组的第一行用来存储原始稀疏矩阵的行数、列数和有效的数据个数,其余行用来存储有效的非0数据

思路分析

稀疏矩阵的压缩

  1. 遍历原始的稀疏矩阵,得到有效的数据个数sum
  2. 根据sum创建三元组new int [sum+1] [3](即sum+1行3列的二维数组)
  3. 将二维数据的有效数据存入三元组中

稀疏矩阵的解压

  1. 先读取三元组的第一行,根据第一行的数据创建一个二维数组
  2. 再读取三元组的后面几行,并赋值给该二维数组即可

代码实现

稀疏矩阵的压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package zone.lxy.sparsearray;

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;

/*
* 把稀疏矩阵压缩成三元组
* */
public class Compress {
public static void main(String[] args) throws IOException {
// 创建一个稀疏矩阵11*11
// 0表示没有棋子
// 1表示黑子
// 2表示白子
int[][] chessArr1 = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;

// 输出原始的稀疏矩阵
System.out.println("原始的稀疏矩阵:");
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
System.out.print(chessArr1[i][j] + " ");
}
System.out.println();
}
// 对稀疏矩阵压缩存储
// 1.先遍历稀疏矩阵记录非0元素的个数
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];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;

// 3.把稀疏矩阵中的非0元素放到三元组中
int count = 1;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr1[i][j];
count++;
}
}
}

// 输出生成的三元组
System.out.println("得到压缩后的三元组:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%-2d %-2d %-2d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}
// 把该三元组以文件形式保存起来,压缩完成
FileOutputStream fos = new FileOutputStream("map.data");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(sparseArr);
oos.close();
fos.close();
}
}
// 输出结果
原始的稀疏矩阵:
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

稀疏矩阵的解压

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package zone.lxy.sparsearray;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;

/*
* 把三元组还原成稀疏矩阵
* */
public class DeCompress {
public static void main(String[] args) throws IOException, ClassNotFoundException {
// 读取文件并赋值
FileInputStream fis = new FileInputStream("map.data");
ObjectInputStream ois = new ObjectInputStream(fis);
int[][] sparseArr = (int[][]) ois.readObject();
ois.close();
fis.close();
// 输出文件中的存储的三元组
System.out.println("得到压缩后的三元组:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%-2d %-2d %-2d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}
// 先读取三元组的第一行,根据第一行数据创建原始的稀疏矩阵
int row = sparseArr[0][0];
int col = sparseArr[0][1];
int[][] chessArr = new int[row][col];

// 从第二行开始读取三元组并赋值给稀疏矩阵
for (int a = 1; a <sparseArr.length; a++) {
int i = sparseArr[a][0];
int j = sparseArr[a][1];
int val = sparseArr[a][2];
chessArr[i][j] = val;
}
// 输出解压后的稀疏矩阵
System.out.println("解压后的二维数组:");
for (int[] i : chessArr) {
for (int item : i) {
System.out.printf("%d ", item);
}
System.out.println();
}
}
}
// 输出结果
得到压缩后的三元组:
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

__END__

三国小梦
文章作者:三国小梦
文章出处java实现稀疏矩阵的压缩与解压
作者签名:简单地活着, 肆意又精彩.
关于主题Hexo - Live For Code
版权声明:文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处