1. 需求：编写五子棋程序，有存盘和读盘的功能。
image.png
当一个数组中大部分元素是0，或者为同一个值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法：
- 记录数组一共有几行几列，有多少个不同的值
-
把具有不同值的元素的行列以及值记录在一个小规模的数组中，从而缩小程序的规模。
例子：
image.png
6行7列变成了9行3列，稀疏数组固定都是3列。
2. 应用实例
使用稀疏数组来表示棋盘的二维数组来存盘，再将稀疏数组恢复成二维数组棋盘实现读盘。
row col value
11 11 2 -- 11行11列，2个有效数字
1 2 1 -- 第一行第二列，值为1
2 3 2 -- 第二行第三列，值为2
二维数组转稀疏数组思路：
- 遍历二维数组，得到有效值的个数sum
- 根据sum创建稀疏数组sparse-array int[sum + 1][3]
- 将二维数组的有效数据存入到稀疏数组
稀疏数组转二维数组思路：
- 先读取稀疏数组第一行，根据第一行的数据创建原始的二维数组（第一行的前两个值就是行数和列数）
- 再读取稀疏数组后几行的数据，并赋给原始的二维数组
3. 代码
用vscode写的，文件是utf8的，但是注释却是gbk的，不知道为什么，就是javac的时候老报错，只能删了注释来运行。
-- 查了下资料，“由于JDK是国际版的，我们在用javac编译时，编译程序首先会获得我们操作系统默认采用的编码格式（GBK），然后JDK就把Java源文件从GBK编码格式转换为Java内部默认的Unicode格式放入内存中，然后javac把转换后的Unicode格式的文件编译成class类文件，此时，class文件是Unicode编码的，它暂存在内存中，紧接着，JDK将此以Unicode格式编码的class文件保存到操作系统中形成我们见到的class文件。当我们不加设置就编译时，相当于使用了参数：javac -encoding GBK Test.java，就会出现不兼容的情况。”
https://github.com/toyranger/data_structure_algorithm.git
package com.ds.sparse.array;
public class SparseArray {
public static void main(String[] args) {
int[][] chessArray = genChessArray();
printArray(chessArray);
System.out.println("------------------------------");
int[][] trans2SparseArr = trans2SparseArr(chessArray);
printArray(trans2SparseArr);
System.out.println("------------------------------");
int[][] trans2ChessArr = trans2ChessArr(trans2SparseArr);
printArray(trans2ChessArr);
}
/***
* 生成原始的棋盘二维数组
* @return
*/
private static int[][] genChessArray() {
int[][] chessArray = new int[11][11];
chessArray[1][2] = 1;
chessArray[2][3] = 2;
return chessArray;
}
/***
* 遍历打印数组
* @param array
*/
private static void printArray(int[][] array) {
for (int[] tmpArr : array) {
for (int value : tmpArr) {
System.out.printf("%d\t", value);
}
System.out.println();
}
}
/***
* 获取二维数组中有效值个数
* @param array
* @return
*/
private static int getValidValueCnt(int[][] array) {
int cnt = 0;
for (int[] tmpArr : array) {
for (int tmpVal : tmpArr) {
if (0 != tmpVal) {
cnt++;
}
}
}
return cnt;
}
/***
* 二维数组转成稀疏数组
* @param chessArr
* @return
*/
private static int[][] trans2SparseArr(int[][] chessArr) {
int valueCnt = getValidValueCnt(chessArr);
int[][] sparseArr = new int[valueCnt + 1][3];
// 第一行是原始二维数组的行数列数和有效值
int rowCnt = chessArr.length;
int colCnt = chessArr[0].length;
sparseArr[0][0] = rowCnt;
sparseArr[0][1] = colCnt;
sparseArr[0][2] = valueCnt;
// 遍历棋盘数组，每找到一个有效值，对应稀疏数组的行数加一，并且把有效值的行和列以及值存入该行
int sparseRow = 1;
for (int row = 0; row < rowCnt; row++) {
for (int col = 0; col < colCnt; col++) {
int value = chessArr[row][col];
if (0 != value) {
sparseArr[sparseRow][0] = row;
sparseArr[sparseRow][1] = col;
sparseArr[sparseRow][2] = value;
sparseRow++;
}
}
}
return sparseArr;
}
/***
* 稀疏数组还原成二维数组
* @param sparseArr
* @return
*/
private static int[][] trans2ChessArr(int[][] sparseArr) {
int rowCnt = sparseArr[0][0];
int colCnt = sparseArr[0][1];
int[][] chessArr = new int[rowCnt][colCnt];
// 从第二行开始遍历稀疏数组，把有效值填入棋盘数组对应的行和列位置
for (int rowNumOfSparse = 1; rowNumOfSparse < sparseArr.length; rowNumOfSparse++) {
int rowNum = sparseArr[rowNumOfSparse][0];
int colNum = sparseArr[rowNumOfSparse][1];
int value = sparseArr[rowNumOfSparse][2];
chessArr[rowNum][colNum] = value;
}
return chessArr;
}
}
