需求
编写一个五子棋程序, 要有存盘退出和续上盘的功能，怎么保存棋盘数据?
棋盘
编程思路:
创建一个二维数组, 数字0代表没有棋子, 1表示黑子, 2表示蓝子, 来保存棋盘数据
但是这样会有一个问题？
二维数组中会存在很多值是默认值0, 因此记录了很多没有意义的数据
怎么解决？
我们可以尝试使用稀疏数组来解决这个问题, 使用稀疏数组的解决方法就是记录数组有多少行多少列，有多少个值，把不同的值的元素的行列和值记录在一个小规模的数组中, 看下图
解决方案
我们可以使用稀疏数组来保存棋盘数据，把稀疏数组存盘，使用的时候再把稀疏数组转为二维数组。
原始数组和对应的稀疏数组
二维数组和稀疏数组互转
- 二维数组转稀疏数组思路
- 遍历原始数组, 得到有效数据的个数num
- 根据行数、列数和元素个数num创建稀疏数组
- 将二位数组的有效数据存入到稀疏数组
- 稀疏数组转二位数组思路
- 先根据稀疏数组的第一行数据创建原始的二维数组
- 再读取稀疏数组后几行的数据, 并赋值给原始二维数组即可
代码实现
- Java
public class Sparse {
/**
* 原始数组转稀疏数组
* @param arr 原始数组
* @return 稀疏数组
*/
static int[][] Array2Sparse(int[][] arr){
//1. 原始二维数组几行几列
int row = arr.length;
int column = arr[0].length;
//2. 一共几个有效元素
int num = 0;
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
if(arr[i][j] != 0){
num ++;
}
}
}
//3. 创建稀疏数组
int[][] sparseArr = new int[num+1][3];
//4. 二维数组转稀疏数组
sparseArr[0][0] = row;
sparseArr[0][1] = column;
sparseArr[0][2] = num;
int count = 0;
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
if(arr[i][j] != 0){
count ++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = arr[i][j];
}
}
}
return sparseArr;
}
/**
* 稀疏数组转二维数组
* @param sparseArr 稀疏数组
* @return 原始数组
*/
static int[][] Sparse2Arr(int[][] sparseArr){
//1. 创建二维数组
int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
//2. 稀疏数组转二维数组
for(int i=1; i<sparseArr.length; i++){
arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return arr;
}
/**
* 控制台输出二维数组
* @param arr
*/
static void printArr(int[][] arr){
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
System.out.printf("%d\t", arr[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//1. 初始化一个二维数组
int[][] arr = new int[11][11];
arr[1][2] = 1;
arr[2][5] = 3;
arr[4][6] = 5;
//2. 二维数组转稀疏数组
int[][] sparseArr = Array2Sparse(arr);
System.out.println("原始数组:");
printArr(arr);
System.out.println("稀疏数组:");
printArr(sparseArr);
//3. 稀疏数组转二维数组
int[][] arr1 = Sparse2Arr(sparseArr);
System.out.println("原始数组:");
printArr(arr1);
}
}
输出:
原始数组:
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 0 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 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 5 3
4 6 5
原始数组:
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 0 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
