当前位置 博文首页 > 想要上南大的同学的博客：第 3 章：稀疏数组和队列
场景：
当一个数组中大部分元素为０（属于没有意义的数据，要压缩），或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
稀疏数组把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
稀疏数组也是二维数组，行数由原数组的数据决定，列数一般为 3 列
稀疏数组的第一行记录原数组一共有几行几列，有多少个不为零的值
第一列：原数组的行数
第二列：原数组的列数
第三列：原数组有多少个不为零的值
之后的行记录原数组中不为零（x）的值所在的行数、列数以及 x 的值
第一列：x 在原数组中的行数
第二列：x 在原数组中的列数
第三列：x 的值
思路：
二维数组 ——> 稀疏数组
- 遍历原始的二维数组， 得到有效数据的个数 sum；
- 根据 sum 就可以创建 稀疏数组 sparseArr int[ sum + 1 ][ 3 ]；
- 将二维数组的有效数据存入到 稀疏数组 中。（遍历稀疏数组，将值存入）
稀疏数组 ——> 原始的二维数组
- 先读取稀疏数组 的第一行， 根据第一行数据， 创建原始的二维数组， 比如上面的 chessArr2 = [ 11 ][ 11 ]；
- 在读取稀疏数组后几行的数据， 并赋给 原始的二维数组 即可。
使用稀疏数组， 来保留类似前面的二维数组(棋盘、 地图等等)；
把稀疏数组存盘， 并且可以从新恢复原来的二维数组数。
代码：
package Practices;
public class SparseArray {
public static void main(String[] args) {
//准备阶段：
// 创建一个原始的二位数组 11 * 11
// 0：表示没有， 1：表示有
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();//换行，你可以理解为打印"\r\n"
}
//1 二维数组——》稀疏数组
// 1.1 遍历数组得到 非0量 个数
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++;
}
}
}
System.out.println("非0量个数: " + sum);
// 1.2 创建 稀疏数组
int sparseArr[][] = new int[sum + 1][3];
// 1.3 给 稀疏数组 提供材料(也就是第一行的三个数)
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 1.4 遍历 二维数组 将 稀释数组 中的值改变
int count = 0;//count: 记录是第几个 非0数
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr1[i][j];//改变值
}
}
}
// 1.5 输出 稀疏数组
System.out.println("输出 稀疏数组：");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}
// 2 稀疏数组 ——> 二维数组
// 2.1 新建 一个 二维数组
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2.2 在读取 稀疏数组 后几行的数据(从第二行开始)， 并赋给 原始的二维数组 即可
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
// 2.2 输出恢复后的二维数组
System.out.println();
System.out.println("恢复的二维数组：");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
程序运行结果：
原始的二维数组~~
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 3
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
