稀疏数组
稀疏数组的介绍
当一个数组的大部分元素为0，或者为同一种元素时，可以用稀疏数组来保存该数组
稀疏数组的处理方式：
- 记录数组有多少行多少列，记录有多少个不同值
- 把具有不同值的元素和行列还有元素记录在一个小规模的数组中，从而减少程序的规模
如下图：左边是原数组，右边是稀疏数组
比如第一条数据[0] 6 7 8表示：这是一个六行七列并且有8个有效值的数组
第二条[1] 0 3 22表示：第一个有效值是在第0行第3列值是22
第三条[2] 0 6 15表示：第二个有效值是在第0行第6列值是15
稀疏数组的使用
- 需求：编写五子棋游戏中，有存盘退出和续上盘的功能
- 分析问题：因为改二维数组的很多默认值为0，因此记录了很多没有意义的数据，存盘的时候占用太多空间
- 解决方法：稀疏数组
如果将这个二维数组改为稀疏数组存盘时占用空间就会小很多，改为稀疏数组：
代码示例：
System.out.println("=========================================");
// 转换为稀疏数组
// 获取有效值的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (Array[i][j] != 0){
sum++;
}
}
}
System.out.println("有效值的个数:"+sum);
// 创建一个稀疏数组
int[][] Sparse = new int[sum+1][3];
// 赋值
Sparse[0][0] = 11; // 行数
Sparse[0][1] = 11; // 列数
Sparse[0][2] = sum; // 有效值的个数
// 遍历二维数组 将非零的元素放到稀疏数组
int count = 0;
for (int i = 0; i < Array.length; i++) {
for (int j = 0; j < Array[i].length; j++) {
if (Array[i][j] != 0){
count++;
Sparse[count][0] = i;
Sparse[count][1] = j;
Sparse[count][2] = Array[i][j];
}
}
}
稀疏数组的还原
等再次读取的时候再进行还原
还原代码示例：
System.out.println("还原稀疏数组");
// 1、读取稀疏数组
int[][] Restore_Sparse = new int[Sparse[0][0]][Sparse[0][1]];
// 2、给其中的元素还原值
for (int i = 1; i < Sparse.length; i++) {
Restore_Sparse[Sparse[i][0]][Sparse[i][1]] = Sparse[i][2];
}
// 3,输出还原的数组
for (int[] ints : Restore_Sparse) {
for (int anInt:ints){
System.out.print(anInt+"\t");
}
System.out.println();
}
这样就从稀疏数组转换成原来的数组了
全部代码
package Java;
public class Array_Sparse {
public static void main(String[] args) {
// 创建一个二维数组 0：没有棋子 1：黑子 2：白子
int[][] Array = new int[11][11];
Array[1][2] = 1; // 黑子
Array[2][3] = 2; // 白子
// 原始数组
System.out.println("输出原始数组:");
for (int[] ints : Array) {
for (int anInt : ints) {
System.out.print(anInt+"\t");
}
System.out.println();
}
System.out.println("=========================================");
// 转换为稀疏数组
// 获取有效值的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (Array[i][j] != 0){
sum++;
}
}
}
System.out.println("有效值的个数:"+sum);
// 创建一个稀疏数组
int[][] Sparse = new int[sum+1][3];
// 赋值
Sparse[0][0] = 11; // 行数
Sparse[0][1] = 11; // 列数
Sparse[0][2] = sum; // 有效值的个数
// 遍历二维数组 将非零的元素放到稀疏数组
int count = 0;
for (int i = 0; i < Array.length; i++) {
for (int j = 0; j < Array[i].length; j++) {
if (Array[i][j] != 0){
count++;
Sparse[count][0] = i;
Sparse[count][1] = j;
Sparse[count][2] = Array[i][j];
}
}
}
System.out.println("=========================================");
System.out.println("转换成稀疏数组:");
System.out.println(" 行 列 值");
for (int i = 0,j = 0; i < Sparse.length; i++) {
System.out.println("["+j+"] "+Sparse[i][0]+"\t"
+Sparse[i][1]+"\t"
+Sparse[i][2]+"\t");
j++;
}
System.out.println("=========================================");
System.out.println("还原稀疏数组");
// 1、读取稀疏数组
int[][] Restore_Sparse = new int[Sparse[0][0]][Sparse[0][1]];
// 2、给其中的元素还原值
for (int i = 1; i < Sparse.length; i++) {
Restore_Sparse[Sparse[i][0]][Sparse[i][1]] = Sparse[i][2];
}
// 3,输出还原的数组
for (int[] ints : Restore_Sparse) {
for (int anInt:ints){
System.out.print(anInt+"\t");
}
System.out.println();
}
}
}
