稀疏数组的应用场景

应用场景

五子棋程序，存盘和续上盘功能

2

分析：

如果使用二维数组，会有很多是默认值0，因此记录了许多没意义的数据，考虑到使用稀疏数组(Sparse array)来优化

稀疏数组介绍

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

1

稀疏数组的处理方法：

  1. 记录数组一共有几行几列，有多少个不同的值；
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模；

稀疏数组转换的思路分析

应用实例

  1. 使用稀疏数组，来保留类似前面的二维数组(地图，棋盘等)
  2. 把稀疏数组存盘，并且可以重新恢复原来的二维数组

整体的思路

0

二位数组转稀疏数组的思路

  1. 遍历原始的二维数组，得到要保存有效数据的个数num;
  2. 根据num可以创建稀疏数组sparseArr1 int[sum+1][3];
  3. 将二维数组的有效数据存入到稀疏数组中；

稀疏数组转二位数组的思路

  1. 先读取稀疏数组的第一行，得到原始二维数组的行和列，来创建原始二维数组；例如：chessArr1 = int[row][col]
  2. 再读取稀疏数组第一行后的所有数据，并赋给原始二维数组；

当然，保存的时候稀疏数组存为文件，读取的时候文件要恢复为稀疏数组，这都是IO流的内容。

稀疏数组的代码实现

实现步骤

实现代码

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
package com.jokerdig.sparseArr;

/**
 * @author Joker大雄
 * @data 2022/9/6 - 14:56
 **/
public class Demo01 {
    public static void main(String[] args) {
        // 创建原始二维数组 11 * 11
        // 0表示没有棋子 1表示黑子 2表示蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出原始原始二维数组
        System.out.println("===============原始二维数组===============");
        for (int[] row : chessArr1) {
            for (int data : row) {
                // 格式化输出
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

        // 将二维数组转为稀疏数组
        // 1. 遍历原始二维数组，得到非零数据的个数
        int num = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if(chessArr1[i][j]!=0){
                    // 拿到非零个数
                    num++;
                }
            }
        }
        // 2. 创建对应的稀疏数组
        int sparseArr1[][] = new int[num+1][3];
        // 给稀疏数组第一行赋值
        sparseArr1[0][0] = chessArr1.length; // 二维数组行
        sparseArr1[0][1] = chessArr1[0].length; // 二维数组列
        sparseArr1[0][2] = num; // 二维数组中有效值
        // 遍历二维数组，将非0的值存放到sparseArr1
        int count = 1; // 计数器
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if(chessArr1[i][j]!=0){
                  sparseArr1[count][0] = i;
                  sparseArr1[count][1] = j;
                  sparseArr1[count][2] = chessArr1[i][j];
                  count++;
                }
            }
        }
        // 输出稀疏数组
        System.out.println("===============稀疏数组===============");
        for (int i = 0; i < sparseArr1.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n",
                    sparseArr1[i][0],
                    sparseArr1[i][1],
                    sparseArr1[i][2]
            );
        }

        // 将稀疏数组恢复为原始二维数组
        int row1 = sparseArr1[0][0];
        int col1 = sparseArr1[0][1];
        int chessArr2[][] = new int[row1][col1];
        for (int i = 1; i <= sparseArr1[0][2]; i++) {

            chessArr2[sparseArr1[i][0]][sparseArr1[i][1]]=sparseArr1[i][2];
        }
        // 遍历回复的二维数组
        System.out.println("===============恢复的原始二维数组===============");
        for (int[] row : chessArr2) {
            for (int data : row) {
                // 格式化输出
                System.out.printf("%d\t",data);
            }
            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
===============原始二维数组===============
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	
===============恢复的原始二维数组===============
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	

Process finished with exit code 0

拓展

通过IO流实现数组存储为chess.data文件，并读取该文件

实现代码

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package com.jokerdig.sparseArr;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author Joker大雄
 * @data 2022/9/6 - 14:56
 **/
public class Demo01 {
    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[] row : chessArr1) {
            for (int data : row) {
                // 格式化输出
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

        // 将二维数组转为稀疏数组
        // 1. 遍历原始二维数组，得到非零数据的个数
        int num = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if(chessArr1[i][j]!=0){
                    // 拿到非零个数
                    num++;
                }
            }
        }
        // 2. 创建对应的稀疏数组
        int sparseArr1[][] = new int[num+1][3];
        // 给稀疏数组第一行赋值
        sparseArr1[0][0] = chessArr1.length; // 二维数组行
        sparseArr1[0][1] = chessArr1[0].length; // 二维数组列
        sparseArr1[0][2] = num; // 二维数组中有效值
        // 遍历二维数组，将非0的值存放到sparseArr1
        int count = 1; // 计数器
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[0].length; j++) {
                if(chessArr1[i][j]!=0){
                  sparseArr1[count][0] = i;
                  sparseArr1[count][1] = j;
                  sparseArr1[count][2] = chessArr1[i][j];
                  count++;
                }
            }
        }
        // 通过IO流存放到本地D盘
        String str = "D:/chess.data";
        File file = new File(str);
        if(!file.exists()){
            // 文件不存在，就创建新的
            file.createNewFile();
        }
        FileWriter fileWriter = new FileWriter(str);
        // 输出稀疏数组，同时写入
        System.out.println("===============稀疏数组===============");
        for (int i = 0; i < sparseArr1.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n",
                    sparseArr1[i][0],
                    sparseArr1[i][1],
                    sparseArr1[i][2]
            );
            fileWriter.write(sparseArr1[i][0]+"\t");
            fileWriter.write(sparseArr1[i][1]+"\t");
            fileWriter.write(sparseArr1[i][2]+"\n");
        }
        // 关闭流
        fileWriter.close();
        System.out.println("文件已存放：D/chess.data");

        // 将chess.data恢复为稀疏数组
        BufferedReader file1 = new BufferedReader(new FileReader(new File(str)));
        String line;  //存放文件中的每一行数据
        // 因为我们不知道文件大小，使用集合存放文件
        List<String> list = new ArrayList<>();
        // 循环读取的值不为空
        while((line = file1.readLine())!=null){
            list.add(line); // 存放到集合
        }
        // 关闭流
        file1.close();
        // 恢复稀疏数组
        // 创建新的稀疏数组
        int sparseArr2[][] = new int[list.size()][3];
        for (int i=0; i < list.size(); i++) {
            // 将list中每一个值按照空格切割，并储存到一个数组中
            String temp[]= list.get(i).split("\t");
            for (int j = 0; j < temp.length; j++) {
                sparseArr2[i][j] = Integer.parseInt(temp[j]);
            }
        }
        // 遍历恢复的稀疏数组
        System.out.println("===============恢复稀疏数组===============");
        for (int i = 0; i < sparseArr2.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n",
                    sparseArr2[i][0],
                    sparseArr2[i][1],
                    sparseArr2[i][2]
            );
        }


        // 将稀疏数组恢复为原始二维数组
        int row1 = sparseArr2[0][0];
        int col1 = sparseArr2[0][1];
        int chessArr2[][] = new int[row1][col1];
        for (int i = 1; i <= sparseArr2[0][2]; i++) {

            chessArr2[sparseArr2[i][0]][sparseArr2[i][1]]=sparseArr2[i][2];
        }
        // 遍历回复的二维数组
        System.out.println("===============恢复的原始二维数组===============");
        for (int[] row : chessArr2) {
            for (int data : row) {
                // 格式化输出
                System.out.printf("%d\t",data);
            }
            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
===============原始二维数组===============
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	
文件已存放：D/chess.data
===============恢复稀疏数组===============
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	

Process finished with exit code 0