稀疏数组
实际需求
- 编写的五子棋程序中,有存盘退出和续上盘的功能
- 因为该二维数组的很多值是默认值 0 ,因此记录了很多没有意义的数据,我们将其转为稀疏数组进行存储
稀疏数组应用
稀疏数组处理方法
稀疏数组把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
稀疏数组也是二维数组,行数由原数组的数据决定,列数一般为 3 列
稀疏数组的
第一行
记录原数组一共有几行几列,有多少个不为零的值
- 第一列:原数组的行数
- 第二列:原数组的列数
- 第三列:原数组有多少个不为零的值
之后的行记录原数组中
不为零(x)的值
所在的行数、列数以及 x 的值
- 第一列:x 在原数组中的行数
- 第二列:x 在原数组中的列数
- 第三列:x 的值
举例说明
思路分析
- 使用稀疏数组, 来保留类似前面的二维数组(棋盘、 地图等等)
- 把稀疏数组存盘, 并且可以从新恢复原来的二维数组数
代码实现
1 | package sparsearray; |
打印结果
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 原始的二维数组~
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 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
sum>>>3
1---2--1
2---3--2
3---4--3
4
得到的稀疏数组为如下形式
11 11 3
1 2 1
2 3 2
3 4 2
从文件中读取稀疏数组
11 11 3
1 2 1
2 3 2
3 4 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 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
Process finished with exit code 0