# 一、稀疏数组的定义
稀疏[sparsearray]数组： 可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组。
稀疏数组的应用场景： 五子棋程序，有存盘退出和续上盘的功能，将五子棋盘转化成二维数组如下所示：
分析上述问题： 因为该二维数组默认的地方值为0，因此记录了很多没有意义的数据。当遇到此种情况时，可以使用稀疏数组。
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方法是：
■ 数组的第一行用于记录数组一共有几行几列，有多少个不同的值。
■ 把具有不同值的元素的行列记录在一个小规模的数组中，从而缩小程序的规模。
# 二、应用实例
我们将下图所示的棋盘使用稀疏数组进行存盘退出操作：
【1】将上面类似的二位数组棋盘保存到稀疏数组中，并存放至外部备份文件sparsearray.text中：稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO传输过程中提高效率等等。为什么要进行压缩：因为稀疏矩阵中存在大量的默认值，占据了大量的存储空间，而真正有用的数据却少之又少；且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。
/**
* 将棋盘转化为稀疏数组并备份与外部设配
*/
public class Sparsearray {
//定义一个二维数组
public static void main(String[] args) throws Exception {
//定义成int类型的二维数组，默认值就为0;
int[][] intArr = new int[11][11];
//根据棋盘中显示，存在一个黑子，我们用1表示，蓝子有2表示
intArr[1][2]=1;
intArr[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
*/
for (int i=0;i<intArr.length;i++){
for(int j=0;j<intArr.length;j++){
System.out.print("\t"+intArr[i][j]);
}
System.out.println();
}
//将上面的二位数组，压缩成稀疏数组
int sum = 0; //不为零的个数
for(int[] row: intArr){
for(int data : row){
if(data != 0){
sum++;
}
}
}
//创建一个稀疏数组, sum+1:表示第一行 + 不为零的值，第一行用于存放（行列值：3列数据）
int[][] sparseArray = new int[sum+1][3];
sparseArray[0][0] = intArr.length;
sparseArray[0][1] = intArr[0].length;
sparseArray[0][2] = sum;
//创建一个变量，用于存放稀疏的行数
int num = 0;
//将原数组中不为零的值 存放到 稀疏数组中
for (int i=0;i<intArr.length;i++){
for(int j=0;j<intArr.length;j++){
if(intArr[i][j] != 0){
++num;
sparseArray[num][0]=i;
sparseArray[num][1]=j;
sparseArray[num][2]=intArr[i][j];
}
}
}
/* 稀疏数组输出的矩阵图如下所示:
11 11 2
1 2 1
2 3 2
*/
System.out.println("====分隔符====");
//文件输出
FileOutputStream file = new FileOutputStream("sparsearray.text");
for(int[] row: sparseArray){
for(int data : row){
System.out.print("\t"+data);
file.write(String.valueOf(data+" ").getBytes());
}
System.out.println();
file.write("\n".getBytes());
}
file.flush();
}
}
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
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
【2】稀疏数组输出的sparsearray.text内容如下：
11 11 2
1 2 1
2 3 2
1
2
3
2
3
【3】将稀疏数组文件中的内容恢复至传统的二维数组棋盘；
/**
* 将稀疏数组文件中的内容恢复至传统的二维数组棋盘
*/
public class SparseArrayClass {
public static void main(String[] args) throws Exception {
//读取 sparsearray.text 中的内容
FileInputStream fileInputStream = new FileInputStream("sparsearray.text");
InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream);
BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
//读取文件中的内容 先读取第一行的数据
String s1 = bufferedReader.readLine();
//判断文件第一行是否有值，如果有值则获取，并创建棋盘数组
if(s1 != null){
String[] split = s1.split(" ");
int[][] sparsearray = new int[Integer.valueOf(split[0])][Integer.valueOf(split[1])];
//有多少个稀疏值，则遍历获取多少行
for(int i=1;i<=Integer.valueOf(split[2]);i++){
String line = bufferedReader.readLine();
//获取到的散列数组的1-n 行数据，将其赋值到棋盘数组中
String[] sparse = line.split(" ");
sparsearray[Integer.valueOf(sparse[0])][Integer.valueOf(sparse[1])]=Integer.valueOf(sparse[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
*/
for (int[] i: sparsearray){
for (int j:i){
System.out.print("\t"+j);
}
System.out.println();
}
}
}
}
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
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
← 队列 B树、B+树、B*树 →