二维数组⇌稀疏数组⇌数据文件

发表于 | 更新于 | 分类于

数据结构与算法

稀疏数组SparseArray

1. 什么是稀疏数组

一个数组含有大量重复的值的时候，可以把它转化为稀疏数组来表示，这样会大量节省空间占用。

稀疏数组：

  • 是个二维数组，只有3列，分别对应：行row、列col、值value

  • 第一行表示原数组的行数、列数、有效值个数。（注意，0是第一行）

  • 从第二行开始，每行都会对应一个有效值。

    • 用row（第一列）表示有效值是在原数组中的第几行
    • 用col（第二列）表示有效值是在原数组中的第几列
    • 用value（第三列）表示有效值在原数组中的值
  • 行数为原数组有效值个数+1

示例：

原数组

0，0，0，0，0

1，0，2，0，0

0，0，0，0，0

0，0，0，1，0

对应的稀疏数组：

4，5，3 //表示原数组有4行、5列、3个有效值

1，0，1 //表示一个有效值，位置在原数组的第2行、第1列、值为1

1，2，2 //同上，表示位置在原数组第2行、第3列、值为2

3，3，1 //表示位置在原数组第4行、第4列、值为1

2. 二维数组⇌稀疏数组

java代码演示，相互转换的过程。

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
package SparseArray;

import java.util.Arrays;

public class SparseArray {

    public static void main(String[] args) {

        //1. 新建一个二维数组
        int[][] array1 = new int[4][5];

        //2. 给数组赋一些值
        array1[1][0]=1;
        array1[1][2]=2;
        array1[3][3]=1;

        //3. 格式化输出数组
        for (int i=0;i<array1.length;i++){//array1.length是行数
            for (int j=0;j<array1[0].length;j++){//array1[0].length是第0行的列数
//            System.out.print(array1[i][j]+"\t");
            }
//            System.out.println();
        }

        //4. 更好的输出方式foreach
        System.out.println("##############这是原数组1");
        for (int[] row:array1){
            for (int value:row){
                System.out.print(value+"\t");
            }
            System.out.println();
        }

        //5. 转为稀疏数组，首先需要得到原数组中的有效值个数
        System.out.println("##############");
        int num=0;
        for (int[] row:array1){
            for(int value:row){
                if (value!=0){
                    num++;
                }
            }
        }
        System.out.println("原数组1有："+num+"个有效值");

        //6. 创建稀疏数组，因为稀疏数组第一行是对原数组大小的描述，其他行都是对有效值的描述，
        //所以，稀疏数组行数是 原数组有效值个数+1。
        int [][] sparseArray=new int[num+1][3];

        //7. 对稀疏数组的第一行赋值，对应原数组的行数、列数、有效值个数
        sparseArray[0][0]=4;
        sparseArray[0][1]=5;
        sparseArray[0][2]=3;

        //8. 为稀疏数组赋值，对原数组进行遍历，需要明确第几行第几列
        int n=1;
        for (int i=0;i<array1.length;i++){
            for (int j=0;j<array1[0].length;j++){
                if (array1[i][j]!=0){
                    sparseArray[n][0]=i;
                    sparseArray[n][1]=j;
                    sparseArray[n][2]=array1[i][j];
                    n++;
                }
            }
        }

        //9. 输出稀疏数组
        System.out.println("##############这是转换后的稀疏数组");
        for (int[] row:sparseArray){
            for (int value:row){
                System.out.print(value+"\t");
            }
            System.out.println();
        }

        //10. 再恢复成原数组
        // 创建一个原数组2，原数组2的行数，是稀疏数组的第一行第一列的值
        // 原数组2的列数，是稀疏数组的第一行第二列的值
        int[][] array2=new int[sparseArray[0][0]][sparseArray[0][1]];

        //11. 把稀疏数组中的有效值读出，赋给原数组2，
        // 只需付给原数组2有效值，i从1开始，也就是第二行开始，
        // 稀疏数组第i行，第1列是有效值的行数，第2列是有效值的列数，第3列是有效值的值
        // 因为稀疏数组固定只有3列，一个循环即可
        for (int i=1;i<sparseArray.length;i++){
            array2[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }

        //12. 输出回复后的原数组2
        System.out.println("##############这是恢复后的原数组2");
        for (int[] row:array2){
            for (int value:row){
                System.out.print(value+"\t");
            }
            System.out.println();
        }

    }

}

输出结果：

##############这是原数组1
0 0 0 0 0
1 0 2 0 0
0 0 0 0 0
0 0 0 1 0

##############
原数组1有：3个有效值

##############这是转换后的稀疏数组
4 5 3
1 0 1
1 2 2
3 3 1

##############这是恢复后的原数组2
0 0 0 0 0
1 0 2 0 0
0 0 0 0 0
0 0 0 1 0

3. 稀疏数组⇌数据文件

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
//13. 将稀疏数组存入本地文件
       File file =new File("D:\\aria2\\SparseArray.data");
       Writer writer=new FileWriter(file);
       for (int[] row:sparseArray){
           for (int value:row){
               writer.write(value+"\t");
           }
           writer.write("\r\n");
       }
       writer.close();


//14. 从本地文件读取稀疏数组
       System.out.println("##############这是从文件恢复的稀疏数组2");
       //1.创建源
       File src = new File("D:\\aria2\\SparseArray.data");
       //2.选择流
       BufferedReader in = new BufferedReader(new FileReader(src));
       //3.1进行数据的搬移，但是数组首要考虑的事情是数组要多大？
       int row =0;//用于创建要创建的二维稀疏数组的大小确定
       String line; //一行数据
       //逐行读取，并将每个数组放入到数组中
       while ((line = in.readLine()) != null) {
           row++;
       }
       int sparseArr2[][] = new int [row][3];
       //3.2文本数据转移到稀疏数组中
       int rowtmp = 0;
       //由于读取完毕整个文本文档，重启流
       in.close();
       in = new BufferedReader(new FileReader(src));
       while ((line = in.readLine()) != null) {
           String[] temp = line.split("\t");
           for (int j = 0; j < temp.length; j++) {
               sparseArr2[rowtmp][j]=Integer.parseInt(temp[j]);
           }
           rowtmp++;
       }
       //4.关闭流
       in.close();
       //验证文件读取是否正确
       for(int[]temp1:sparseArr2) {
           for (int temp2 : temp1) {
               System.out.printf("%d\t", temp2);
           }
           System.out.println();
       }

参考文章：稀疏数组转换、稀疏数组到文件、array[0].length、\r\n的区别