介绍

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

稀疏数组的处理方法是:

1)记录数组一共有几行几列，有多少个不同的值

2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

二维数组

索引 0 1 2 3 4 5 6
0 0 0 0 22 0 0 15
1 0 11 0 0 0 17 0
2 0 0 0 -6 0 0 0
3 0 0 0 0 0 39 0
4 91 0 0 0 0 0 0
5 0 0 28 0 0 0 0

稀疏数组

行(row) 列(col) 值(value)
[0] 6 7 8
[1] 0 3 22
[2] 0 6 15
[3] 1 1 11
[4] 1 15 17
[5] 2 3 -6
[6] 3 5 39
[7] 4 0 91
[8] 5 2 28

第一行记录原二维数组的大小，和拥有值的个数

应用实例

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)，把稀疏数组存盘，并且可以从新恢复原来的二维数组数。（棋盘保存复盘）

image-20200823211041879

创建二维数组

根据上图所示创建二维数组11*11

image-20200823211554494

1
2
3
4
5
6
7
8
9
10
11
12
13
//原始二维数组11*11
int chessArr1[][] = new int[11][11];
//1代表黑子，2代表蓝子
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//遍历二维数组
System.out.println("原始二维数组");
for (int[] ints : chessArr1) {
    for (int anInt : ints) {
        System.out.print(anInt + "\t");
    }
    System.out.println();
}

image-20200823211712137

二维数组存放原始棋盘成功！

获取稀疏数组

遍历原始数组

遍历原始数组得到二维数组也就是棋盘中当前的棋子个数有多少(值不为0的个数)，用变量count表示

image-20200823212111079

1
2
3
4
5
6
7
8
9
//将二维数组转换为稀疏数组
//1.先遍历二维数组，得到非0的数据个数。
int count = 0;
for (int i = 0; i < chessArr1.length; i++) {
    for (int j = 0; j < chessArr1.length; j++) {
        //不为零代表有棋子
        if (chessArr1[i][j] != 0) count++;
    }
}

创建稀疏数组

根据遍历原始二维数组获取到当前棋子的个数count，创建稀疏数组，行为count+1(有一行记录原始二维数组的行，列数，值数),列为3(行，列，值)。

image-20200823212528267

1
2
3
4
5
6
//2.创建对应的稀疏数组,存放的数据个数+1行，列为固定3列即可，分别记录row，column，value
int[][] sparseArr = new int[count + 1][3];
//给稀疏数组赋值
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = count;

第一行记录原始二维数组的行，列数，值数

  • sparseArr[0][0] = chessArr1.length;行数
  • sparseArr[0][1] = chessArr1[0].length;列数
  • sparseArr[0][2] = count;值数

稀疏数组赋值

遍历原始二维数组给稀疏数组赋值，当原始二维数组值不为0时，代表此位置有值，将其行列数和值存放到稀疏数组中。

image-20200823213521559

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//2.给稀疏数组赋值
int sum = 0;
for (int i = 0; i < chessArr1.length; i++) {
    for (int j = 0; j < chessArr1[i].length; j++) {
        if (chessArr1[i][j] != 0) {
            sum++;
            sparseArr[sum][0] = i;//存放原数组中row
            sparseArr[sum][1] = j;//存放原数组中column
            sparseArr[sum][2] = chessArr1[i][j];//存放原数组中该位置的value值
        }
    }
}

//遍历稀疏数组
System.out.println();
System.out.println("稀疏数组");
for (int i = 0; i < sparseArr.length; i++) {
    for (int j = 0; j < sparseArr.length; j++) {
        System.out.print(sparseArr[i][j] + "\t");
    }
    System.out.println();
}

sum++放在最前头，是初始值为0，而我们稀疏数组0行中的值已经存放了原始数组的信息，从1行中开始存放棋子

sparseArr[sum][0] = i;//存放原数组中row
sparseArr[sum][1] = j;//存放原数组中column
sparseArr[sum][2] = chessArr1[i][j];//存放原数组中该位置的value值

image-20200823213907811

还原原始数组

创建二维数组

得到稀疏数组中第0行中存放有关原始二维数组的数据，row，column，value。通过row和column创建出还原的二维数组。(这里的value值可以为0，我没用到这个存放值)

image-20200823214845530

1
2
3
4
5
//将稀疏数组转换为二维数组
//1.得到稀疏数组中的第一行存放有关二维数组的值
int row = sparseArr[0][0];//原二维数组的行
int column = sparseArr[0][1];//原二维数组的列
int value = sparseArr[0][2];//原二维数组的存放的值个数

遍历稀疏数组

从(0开始)第1行开始遍历稀疏数组，得到每行中存放的row，column,value。再根据row和column即可代入新的二维数组中定位到位置，将value赋值给该点即可。

image-20200823215106565

row = sparseArr[i][0];
column = sparseArr[i][1];
value = sparseArr[i][2];
chessArr2[row][column] = value;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//还原而成的二维数组
int[][] chessArr2 = new int[row][column];
//遍历稀疏数组存放的值，将其按对应顺序存放到二维数组中。没赋值的初始化默认为0
for (int i = 1; i <sparseArr.length ; i++) {
    for (int j = 1; j <sparseArr[i].length ; j++) {
        //遍历稀疏数组存放的值，将其按对应顺序存放到二维数组中
        row = sparseArr[i][0];
        column = sparseArr[i][1];
        value = sparseArr[i][2];
        chessArr2[row][column] = value;
    }
}

//遍历根据稀疏数组转换的二维数组
System.out.println();
System.out.println("新二维数组");
for (int[] ints : chessArr2) {
    for (int anInt : ints) {
        System.out.print(anInt+"\t");
    }
    System.out.println();
}

image-20200823215643900

存放稀疏数组

写入文件

在通过遍历原始二维数组创建稀疏数组之后，通过io流将稀疏数组写到chess.data文件

image-20200824095214889

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
FileOutputStream fileOutputStream = null;

try {
    fileOutputStream = new FileOutputStream(new File("chess.data"));
    //遍历稀疏数组
    System.out.println();
    System.out.println("稀疏数组");
    for (int i = 0; i < sparseArr.length; i++) {
        for (int j = 0; j < sparseArr[i].length; j++) {
            fileOutputStream.write(sparseArr[i][j]);
            System.out.print(sparseArr[i][j] + "\t");
        }
        System.out.println();
    }
} catch (FileNotFoundException e) {
    e.printStackTrace();
} catch (IOException e) {
    e.printStackTrace();
} finally {
    if (fileOutputStream != null) {
        try {
            fileOutputStream.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

读取文件

通过读取先前写入到硬盘中chess.data文件，创建出稀疏数组，从而通过稀疏数组还原原始二维数组。

image-20200824095600549

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
FileInputStream fileInputStream = null;
int sparseArr2[][] = null;
try {
    //将稀疏数组从磁盘的文件中读取出来
    fileInputStream = new FileInputStream(new File("chess.data"));
    sparseArr2 = new int[count + 1][3];
    for (int i = 0; i < sparseArr2.length; i++) {
        for (int j = 0; j < sparseArr2[i].length; j++) {
            sparseArr2[i][j] = fileInputStream.read();
        }

    }
} catch (IOException e) {
    e.printStackTrace();
} finally {
    if (fileInputStream != null) {
        try {
            fileInputStream.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

image-20200824095659616

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
import java.io.*;

public class sparseArrayIO {

    public static void main(String[] args) {
        //原始二维数组11*11
        int chessArr1[][] = new int[11][11];
        //1代表黑子，2代表蓝子
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        //遍历二维数组
        System.out.println("原始二维数组");
        for (int[] ints : chessArr1) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }

        //将二维数组转换为稀疏数组
        //1.先遍历二维数组，得到非0的数据个数。
        int count = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                //不为零代表有棋子
                if (chessArr1[i][j] != 0) count++;
            }
        }
        //2.创建对应的稀疏数组,存放的数据个数+1行，列为固定3列即可，分别记录row，column，value
        int[][] sparseArr = new int[count + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = count;

        //2.给稀疏数组赋值
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                    sparseArr[sum][0] = i;//存放原数组中row
                    sparseArr[sum][1] = j;//存放原数组中column
                    sparseArr[sum][2] = chessArr1[i][j];//存放原数组中该位置的value值
                }
            }
        }

        FileOutputStream fileOutputStream = null;

        try {
            fileOutputStream = new FileOutputStream(new File("chess.data"));
            //遍历稀疏数组
            System.out.println();
            System.out.println("稀疏数组");
            for (int i = 0; i < sparseArr.length; i++) {
                for (int j = 0; j < sparseArr[i].length; j++) {
                    fileOutputStream.write(sparseArr[i][j]);
                    System.out.print(sparseArr[i][j] + "\t");
                }
                System.out.println();
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fileOutputStream != null) {
                try {
                    fileOutputStream.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        FileInputStream fileInputStream = null;
        int sparseArr2[][] = null;
        try {
            //将稀疏数组从磁盘的文件中读取出来
            fileInputStream = new FileInputStream(new File("chess.data"));
            sparseArr2 = new int[count + 1][3];
            for (int i = 0; i < sparseArr2.length; i++) {
                for (int j = 0; j < sparseArr2[i].length; j++) {
                    sparseArr2[i][j] = fileInputStream.read();
                }

            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fileInputStream != null) {
                try {
                    fileInputStream.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        System.out.println();
        System.out.println("从磁盘中读取的稀疏数组");
        for (int[] is : sparseArr2) {
            for (int i : is) {
                System.out.print(i + "\t");

            }
            System.out.println();
        }
        System.out.println();


        //将稀疏数组转换为二维数组
        //1.得到稀疏数组中的第一行存放有关二维数组的值
        int row = sparseArr[0][0];//原二维数组的行
        int column = sparseArr[0][1];//原二维数组的列
        int value = sparseArr[0][2];//原二维数组的存放的值个数

        int[][] chessArr2 = new int[row][column];
        //遍历稀疏数组存放的值，将其按对应顺序存放到二维数组中。没赋值的初始化默认为0
        for (int i = 1; i < sparseArr.length; i++) {
            for (int j = 1; j < sparseArr[i].length; j++) {
                //遍历稀疏数组存放的值，将其按对应顺序存放到二维数组中
                row = sparseArr[i][0];
                column = sparseArr[i][1];
                value = sparseArr[i][2];
                chessArr2[row][column] = value;
            }
        }

        //遍历根据稀疏数组转换的二维数组
        System.out.println();
        System.out.println("新二维数组");
        for (int[] ints : chessArr2) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}