稀疏数组

一、稀疏数组

1.1 需求引出

假设我们有个五子棋程序，使用1来表示黑子，2表示蓝子，0表示没有棋盘落子，并且需要对棋盘数据进行存储。

• 前端棋盘示意图：

• 需要存储的数据为：

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

• 思考：因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据。
• 解决方式：使用稀疏数组。

1.2 基本介绍

• 使用场景：当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
• 处理方式：
  • 记录数组一共有几行几列，有多少个不同的值。
  • 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
• 存储结构示意图：

1.3 应用实例

• 实现思路分析：

步骤一：将二维数组转稀疏数组。

1. 遍历原始的二维数组，得到有效数据的个数。
2. 根据得到的有效个数，创建相应的稀疏数组行数。
3. 将有效的数据存入稀疏数组当中。

步骤二：将稀疏数组数据存盘，文件名为 data.txt。

步骤三：从磁盘中读取 data.txt 文件，获取稀疏数组数据，将其还原为二维数组。

1. 读取稀疏数组第一行，通过第一行数据得到行和列总数，创建出原始的二维数组。
2. 读取稀疏数组剩下行的数据，将其赋值到二维数组相应的位置即可。

• 代码示例：

public class SparseArray {

    public static void main(String[] args) {

        // 创建原始数据数组。
        int[][] initArray = new int[9][9];
        initArray[1][1] = 1;
        initArray[2][3] = 2;

        // 输出原始数组。
        System.out.println("------初始化的二维数组:------");
        for (int[] data : initArray) {
            for (int d : data) {
                System.out.printf("%d\t", d);
            }
            System.out.println();
        }

        // ------初始化的二维数组:------
        //0	 0	0	0	0	0	0	0	0
        //0	 1	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


        // 创建稀疏数组。
        int row = initArray.length;
        int col = initArray[0].length;
        int sum = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (initArray[i][j] != 0) {
                  	// 记录有效数据的个数。
                    sum++;
                }
            }
        }

        // 创建存值数值的数组。
        int[][] sparse = new int[sum + 1][3];
        sparse[0][0] = row;
        sparse[0][1] = col;
        sparse[0][2] = sum;

        // 填入非0的值。
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (initArray[i][j] != 0) {
                    count++;
                    // 所在行数。
                    sparse[count][0] = i;
                    // 所在列数。
                    sparse[count][1] = j;
                    // 具体的数据。
                    sparse[count][2] = initArray[i][j];
                }
            }
        }

        // 遍历稀疏数组。
        System.out.println();
        System.out.println("------稀疏数组:------");
        for (int i = 0; i < sparse.length; i++) {
            // 输出
            System.out.printf("%d\t%d\t%d\t\n",
                    sparse[i][0],
                    sparse[i][1],
                    sparse[i][2]
            );
        }

        // ------稀疏数组:------
        //9	 9	2	(原始二维数组：共计9行 9列 有效数据条数为2)
        //1	 1	1	(其中第2列，第2行，有效数据的值为1。)
        //2	 3	2 (...)


        // 稀疏数组保存到磁盘。
        Path path = Paths.get("src/main/resources/data.txt");
        try (
                ObjectOutputStream oos = new ObjectOutputStream(
                        Files.newOutputStream(path))
        ) {
            oos.writeObject(sparse);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

        // 读取。
        int[][] arrayFromText;
        try (
                ObjectInputStream ois = new ObjectInputStream(
                        Files.newInputStream(path));
        ) {
            arrayFromText = (int[][]) ois.readObject();

        } catch (IOException | ClassNotFoundException e) {
            throw new RuntimeException(e);
        }

        // 还原为初始数组。
        int arrayRow = arrayFromText[0][0];
        int arrayCol = arrayFromText[0][1];
        // 第一行记录原始二维数组的行和列。
        int[][] rowArray = new int[arrayRow][arrayCol];

        // 从第二行开始获取数据存储的坐标。
        for (int i = 1; i < arrayFromText.length; i++) {
            int r = arrayFromText[i][0];
            int c = arrayFromText[i][1];
            int data = arrayFromText[i][2];
            rowArray[r][c] = data;
        }

        // 打印还原后的数组内容
        System.out.println();
        System.out.println("------还原后的原始数组:------");
        for (int[] ints : rowArray) {
            for (int d : ints) {
                System.out.printf("%d\t", d);
            }
            System.out.println();
        }
    }

    // ------还原后的原始数组:------
    //0	 0	0	0	0	0	0	0	0
    //0	 1	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
}
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
132
133
134
135
136
137
138
139
140
141
142

二、结束语

---

“-------怕什么真理无穷,进一寸有一寸的欢喜。”

微信公众号搜索：饺子泡牛奶。