数据结构与算法-稀疏数组
# 数据结构与算法-稀疏数组
# 1. 先看一个实际的需求
# 需求
编写的五子棋程序中,有存盘退出和续上盘的功能。
# 分析
因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据=>稀疏数组。
# 2. 基本介绍
数组: 参考
二维数组:
# 概述
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
- 记录数组一共有几行几列,有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
# 举例说明
- 原数组6x7
- 转换为稀疏数组后,变为9x3
- 第一行:第一列记录行数;第二列记录列数;第三列记录非零值有几个。
- 其余行记录第一行第三列中查询出的所有非零值的位置。
# 3. 应用
# 应用实例
使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等);把稀疏数组存盘,并且可以从新恢复原来的二维数组数
# 思路分析
二维数组转稀疏数组的思路
- 遍历
原始的二维数组
,得到有效数据的个数sum - 根据sum 就可以创建 稀疏数组
sparseArr int[sum + 1] [3]
。【数组的行数不确定,列数确定为3】 - 将二维数组的有效数据数据存入到 稀疏数组
稀疏数组转原始的二维数组的思路
- 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的
chessArr2 = int [11] [11]
- 在读取稀疏数组后几行的数据,并赋给原始的二维数组 即可.
# 代码实现
点击查看
/**
* 稀疏数组 【注意:请配合图使用!请配合图使用!请配合图使用!重要的事情说三遍;重要的事情说三遍;重要的事情说三遍】
* 棋盘:使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等);把稀疏数组存盘,并且可以从新恢复原来的二维数组数
*
* @author cnlxc
* @date 2023/4/3 21:48
*/
public class SparseArray01 {
/**
* 功能:
* 1. 将二维数组转换为稀疏数组
* 2. 将稀疏数组恢复为二维数组
*
* @author cnlxc
* @date 2023/4/3 22:28
*/
public static void main(String[] args) {
/*
1. 将二维数组转换为稀疏数组
a. 遍历`原始的二维数组`,得到有效数据的个数sum
b. 根据sum 就可以创建 稀疏数组 `sparseArr int[sum + 1] [3]`。【数组的行数不确定,列数确定为3】
c. 将二维数组的有效数据数据存入到 稀疏数组
*/
// 1.1 创建原始二维数组
int[][] chessArrayOne = createChessArrayOne();
// 1.2 将二维数组转换为稀疏数组 (通过遍历形式)
int[][] sparseArray = chessArrayToSparseArray(chessArrayOne);
// 1.3 输出稀疏数组
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
System.out.println();
}
System.out.println();
/*
2. 将稀疏数组恢复为二维数组
a. 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 `chessArr2 = int [11] [11]`
b. 在读取稀疏数组后几行的数据,并赋给原始的二维数组 即可.
*/
// 2.1 稀疏数组恢复为二维数组
int[][] chessArrayTwo = sparseArrayToChessArray(sparseArray);
// 2.2 打印输出二维数组 chessArrayTwo
/*// 遍历方式二
System.out.println("------ 新的二维数组 ------");
for (int i = 0; i < chessArrayTwo.length; i++) {
for (int j = 0; j < chessArrayTwo[i].length; j++) {
System.out.printf("%d\t", chessArrayTwo[i][j]);
}
System.out.println();
}*/
// 遍历方式二
for (int[] row : chessArrayTwo) { // 每行
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
/**
* 稀疏数组恢复为二维数组
* @param sparseArray
* @return
*/
private static int[][] sparseArrayToChessArray(int[][] sparseArray) {
// 2.1 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
// 稀疏数组第一行第一列就是二维数组的行数;
int chessArrayRowNum = sparseArray[0][0];
// 稀疏数组第一行第二列就是二维数组的列数。
int chessArrayColNum = sparseArray[0][1];
// 原始数组
int[][] chessArrayTwo = new int[chessArrayRowNum][chessArrayColNum];
// 2.2 在读取稀疏数组后几行的数据,并赋给原始的二维数组 即可.(遍历稀疏数组数组, 从第二行开始)
for (int i = 1; i < sparseArray.length; i++) {
// 读取数据每行: 第一列为二维数组的第几行的索引;第二列为二维数组第几列的索引,第三列为二维数组第几行第几列具体值。
chessArrayTwo[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
return chessArrayTwo;
}
/**
* 将二维数组转换为稀疏数组
*
* @return int[][]
* @author cnlxc
* @date 2023/4/3 22:43
*/
private static int[][] chessArrayToSparseArray(int[][] chessArrayOne) {
System.out.println();
System.out.println("------ 稀疏数组 ------");
// 1. 通过遍历的形式获取二维数组中非0的个数 (在二维数组中,直接使用 length 属性获取的是数组的行数,在指定的索引后加上 length(如 array[0].length)表示的是该行拥有多少个元素,即列数。)
int sum = 0; // 获取
for (int i = 0; i < chessArrayOne.length; i++) {
for (int j = 0; j < chessArrayOne[i].length; j++) {
// 稀疏数组获取不为0的数的个数
if (chessArrayOne[i][j] != 0) {
sum++;
}
}
}
System.out.println("获取二维数组不为0的个数:" + sum);
// 2. 创建对应的稀疏数组
int[][] sparseArray = new int[sum + 1][3];
// 3. 稀疏数组赋值
// 3.1 稀疏数组第一行赋值 (行数、列数、非零值个数)
sparseArray[0][0] = chessArrayOne.length; // 第一行第一列
sparseArray[0][1] = chessArrayOne[0].length; // 第一行第二列
sparseArray[0][2] = sum; // 第一行第二列
// 3.2 遍历二维数组,将非0的值存入稀疏数组
int count = 0; // 用于记录第几个非0数据(计数器)
for (int i = 0; i < chessArrayOne.length; i++) {
for (int j = 0; j < chessArrayOne[i].length; j++) {
// 稀疏数组获取不为0的数的个数
if (chessArrayOne[i][j] != 0) {
count++;
sparseArray[count][0] = i; // 第n行读一列
sparseArray[count][1] = j; // 第n行读二列
sparseArray[count][2] = chessArrayOne[i][j]; // 第n行读三列
}
}
}
return sparseArray;
}
/**
* 创建原始二维数组
*
* @return int[][]
* @author cnlxc
* @date 2023/4/3 21:57
*/
private static int[][] createChessArrayOne() {
// 1. 创建一个原始的二维数组 11*11 0: 表示没有棋子 1: 表示黑子 2: 表示白子
int[][] chessArrayOne = new int[11][11];
chessArrayOne[1][2] = 1; // 1: 表示黑子
chessArrayOne[2][3] = 2; // 2: 表示白子
chessArrayOne[4][5] = 2; // 2: 表示白子
// 2. 输出原始的二维数组
System.out.println("------ 原始的二维数组 ------");
for (int[] row : chessArrayOne) { // 每行
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
return chessArrayOne;
}
}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
结果
------ 原始的二维数组 ------
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 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的个数:3
11 11 3
1 2 1
2 3 2
4 5 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 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
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
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
# 扩展-增加读写操作:
- 在前面的基础上,将稀疏数组保存到磁盘上,比如 data.txt
- 恢复原来的数组时,读取 data.txt 进行恢复
点击查看
/**
* 稀疏数组 【注意:请配合图使用!请配合图使用!请配合图使用!重要的事情说三遍;重要的事情说三遍;重要的事情说三遍】
* 棋盘:使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等);把稀疏数组存盘,并且可以从新恢复原来的二维数组数
*
* @author cnlxc
* @date 2023/4/3 21:48
*/
public class SparseArray02 {
/**
* 功能:
* 1. 将二维数组转换为稀疏数组 (通过遍历形式);
* 2. 将稀疏数组写入文件 data.txt
* 3. 从文件 data.txt 读取数据,恢复稀疏数组。
* 4. 稀疏数组恢复为二维数组
*
* @author cnlxc
* @date 2023/4/3 22:28
*/
public static void main(String[] args) {
// 文件路径
String filePath = "D://data.txt";
// 1. 将二维数组转换为稀疏数组 (通过遍历形式)
int[][] sparseArray = chessArrayToSparseArray();
// 2. 将稀疏数组写入文件 data.txt
sparseArrayWriterFile(sparseArray, filePath);
// 3. 从文件 data.txt 读取数据,恢复稀疏数组。
int[][] fileReadSparseArray = fileReadSparseArray(filePath);
// 4. 稀疏数组恢复为二维数组
if (fileReadSparseArray != null) {
sparseArrayToChessArray(fileReadSparseArray);
}
}
/**
* 稀疏数组恢复为二维数组
* a. 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 `chessArr2 = int [11] [11]`
* b. 在读取稀疏数组后几行的数据,并赋给原始的二维数组 即可.
*
* @param sparseArray 稀疏数组
* @return int[][]
* @author cnlxc
* @date 2023/4/3 22:43
*/
private static int[][] sparseArrayToChessArray(int[][] sparseArray) {
// 2.1 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
// 稀疏数组第一行第一列就是二维数组的行数;
int chessArrayRowNum = sparseArray[0][0];
// 稀疏数组第一行第二列就是二维数组的列数。
int chessArrayColNum = sparseArray[0][1];
// 原始数组
int[][] chessArrayTwo = new int[chessArrayRowNum][chessArrayColNum];
// 2.2 在读取稀疏数组后几行的数据,并赋给原始的二维数组 即可.(遍历稀疏数组数组, 从第二行开始)
System.out.println();
System.out.println("------ 恢复后的二维数组 ------");
for (int i = 1; i < sparseArray.length; i++) {
// 读取数据每行: 第一列为二维数组的第几行的索引;第二列为二维数组第几列的索引,第三列为二维数组第几行第几列具体值。
chessArrayTwo[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
// 2.3 打印输出二维数组 chessArrayTwo
for (int[] row : chessArrayTwo) { // 每行
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
return chessArrayTwo;
}
/**
* 从文件 data.txt 读取数据,恢复稀疏数组。
*
* @param filePath 文件路径
* @return int[][]
* @author cnlxc
* @date 2023/4/3 22:43
*/
private static int[][] fileReadSparseArray(String filePath) {
BufferedReader bufferedReader = null;
try {
// 读取文件data.txt
bufferedReader = new BufferedReader(new FileReader(filePath));
// 获取二维数组行数
int sum = 0;
while (bufferedReader.readLine() != null) {
sum++;
}
// 创建对应的稀疏数组
int[][] fileToSparseArray = new int[sum][3];
bufferedReader = new BufferedReader(new FileReader(filePath));
// 一次读取一行
String line;
int count = 0;
while ((line = bufferedReader.readLine()) != null) {
// 获取稀疏数组每行的数据
String[] lineArray = line.split(" ");
for (int i = 0; i < lineArray.length; i++) {
fileToSparseArray[count][i] = Integer.parseInt(lineArray[i]);
}
count++;
}
System.out.println("------ 从文件中获取的稀疏数组 ------");
for (int i = 0; i < fileToSparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t", fileToSparseArray[i][0], fileToSparseArray[i][1], fileToSparseArray[i][2]);
System.out.println();
}
return fileToSparseArray;
} catch (Exception e) {
e.printStackTrace();
} finally {
if (bufferedReader != null) {
try {
bufferedReader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return null;
}
/**
* 将稀疏数组写入文件 data.txt
*
* @param sparseArray 稀疏数组
* @param filePath 文件路径
* * @author cnlxc
* * @date 2023/4/3 22:43
*/
private static void sparseArrayWriterFile(int[][] sparseArray, String filePath) {
BufferedWriter bufferedWriter = null;
try {
// 读写的文件
File file = new File(filePath);
if (!file.exists()) {
file.createNewFile();
} else {
file.delete();
file.createNewFile();
}
String charset = "UTF-8";
// 创建字符缓冲输出流输出流 1. ture表示追加写入。如果不需要追加写入就直接去掉这个参数就行 2. 设置编码 3. 缓冲写入流
bufferedWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file), charset));
for (int i = 0; i < sparseArray.length; i++) {
// 写入数据
String content = sparseArray[i][0] + " " + sparseArray[i][1] + " " + sparseArray[i][2];
bufferedWriter.write(content);
bufferedWriter.newLine();
}
} catch (Exception e) {
e.fillInStackTrace();
} finally {
// 关闭流
if (bufferedWriter != null) {
try {
bufferedWriter.flush();
bufferedWriter.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
/**
* 将二维数组转换为稀疏数组
* a. 遍历`原始的二维数组`,得到有效数据的个数sum
* b. 根据sum 就可以创建 稀疏数组 `sparseArr int[sum + 1] [3]`。【数组的行数不确定,列数确定为3】
* c. 将二维数组的有效数据数据存入到 稀疏数组
*
* @return int[][]
* @author cnlxc
* @date 2023/4/3 22:43
*/
private static int[][] chessArrayToSparseArray() {
// 1. 创建原始二维数组
// 1.1 创建一个原始的二维数组 11*11 0: 表示没有棋子 1: 表示黑子 2: 表示白子
int[][] chessArrayOne = new int[11][11];
chessArrayOne[1][2] = 1; // 1: 表示黑子
chessArrayOne[2][3] = 2; // 2: 表示白子
chessArrayOne[4][5] = 2; // 2: 表示白子
// 1.2 输出原始的二维数组
System.out.println("------ 原始的二维数组 ------");
for (int[] row : chessArrayOne) { // 每行
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 2. 二维数组转换为稀疏数组
System.out.println();
System.out.println("------ 稀疏数组 ------");
// 2.1 通过遍历的形式获取二维数组中非0的个数 (在二维数组中,直接使用 length 属性获取的是数组的行数,在指定的索引后加上 length(如 array[0].length)表示的是该行拥有多少个元素,即列数。)
int sum = 0; // 获取
for (int i = 0; i < chessArrayOne.length; i++) {
for (int j = 0; j < chessArrayOne[i].length; j++) {
// 稀疏数组获取不为0的数的个数
if (chessArrayOne[i][j] != 0) {
sum++;
}
}
}
System.out.println("获取二维数组不为0的个数:" + sum);
// 2.2 创建对应的稀疏数组
int[][] sparseArray = new int[sum + 1][3];
// 2.3 稀疏数组赋值
// 稀疏数组第一行赋值 (行数、列数、非零值个数)
sparseArray[0][0] = chessArrayOne.length; // 第一行第一列
sparseArray[0][1] = chessArrayOne[0].length; // 第一行第二列
sparseArray[0][2] = sum; // 第一行第二列
// 遍历二维数组,将非0的值存入稀疏数组
int count = 0; // 用于记录第几个非0数据(计数器)
for (int i = 0; i < chessArrayOne.length; i++) {
for (int j = 0; j < chessArrayOne[i].length; j++) {
// 稀疏数组获取不为0的数的个数
if (chessArrayOne[i][j] != 0) {
count++;
sparseArray[count][0] = i; // 第n行读一列
sparseArray[count][1] = j; // 第n行读二列
sparseArray[count][2] = chessArrayOne[i][j]; // 第n行读三列
}
}
}
// 3. 输出稀疏数组
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
System.out.println();
}
System.out.println();
return 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
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
结果:
------ 原始的二维数组 ------
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 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的个数:3
11 11 3
1 2 1
2 3 2
4 5 2
------ 从文件中获取的稀疏数组 ------
11 11 3
1 2 1
2 3 2
4 5 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 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
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
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
上次更新: 2023/04/06, 09:20:23