稀疏数组的实现

稀疏的作用:把原有数组有意义(不为空)的数据压缩在一个小规模的数组里,减少储存空间

应用:记录五子棋的棋盘情况,并保存在文件中

基本介绍

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

0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 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 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 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 3
3 5 2
6 3 1
6 9 1

处理

第一行(下标0)记录数组一共有几行几列,有多少不同的值

后面的都是记录放在第几行、第几列和它的值

下标
0 11 11 3
1 3 5 2
2 6 3 1
3 6 9 1
代码测试
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
package 线性表;

import java.util.ArrayList;
import java.util.Random;

/**
* 稀疏数组的实现
*/
public class SparseArray {
public static void main(String[] args) {
int arry1[][] = new int [11][11];
arry1[3][5] =2;
arry1[6][9]=1;
arry1[6][3]=1;
System.out.println("数组初始化:");
for (int i = 0; i < arry1.length; i++) {
for (int j = 0; j < arry1[0].length; j++) {
System.out.print(arry1[i][j]+"\t");
}
System.out.println();
}
int sum = 0;
ArrayList list = new ArrayList();
for (int i = 0; i < arry1.length; i++) {
for (int j = 0; j < arry1.length; j++) {
if (arry1[i][j]!=0)
sum++;

}
}
//稀疏数组的初始化
int arry2[][] = new int [sum+1][3];
arry2[0][0] = 11;
arry2[0][1] = 11;
arry2[0][2] = sum;

//稀疏数组的存放
int count =1;
for (int i = 0; i < arry1.length; i++) {
for (int j = 0; j < arry1.length; j++) {
if (arry1[i][j]!=0){

arry2[count][0] = i;
arry2[count][1] = j;
arry2[count][2] = arry1[i][j];
count++;
}
}
}

System.out.println("打印稀疏数组");
for (int i = 0; i < arry2.length; i++) {
System.out.println(arry2[i][0]+"\t"+arry2[i][1]+"\t"+arry2[i][2]+"\t");
}


System.out.println("恢复原有数组");
int arry3[][]= new int[arry2[0][0]][arry2[0][1]];
for (int i = 1; i < arry2.length; i++) {
arry3[arry2[i][0]][arry2[i][1]] = arry2[i][2];
}

for (int i = 0; i < arry3.length; i++) {
for (int j = 0; j < arry3[0].length; j++) {
System.out.print(arry3[i][j]+"\t");
}
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
数组初始化:
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 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 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 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 3
3 5 2
6 3 1
6 9 1
恢复原有数组
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 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 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

Process finished with exit code 0