数据结构-稀疏数组
源码：
https://gitee.com/smallpage/data-structure-and-algorithm.git
案例分析
我们通过一个五子棋案例，来解说稀疏数组数据结构，假设现在需要制作一个五子棋游戏，需要实现功能保存当前棋盘信息，下次可以通过读取上一次保存信息继续上一次的对局
左侧可以看到有一个11X11的棋盘，棋盘上面有2个棋子，要保存棋盘记录最简单的方法将着个棋盘转为二维数组，1代表黑色棋子，2代表蓝色棋子，这样下次通过读取这个数组并且渲染成棋盘即可
问题分析：可以发现转换后的二维数组有很多位置还是默认值0，比较浪费空间，有没有办法把该数组压缩一下呢，让他更加的节省空间，那么就需要使用到稀疏数组了
什么是稀疏数组
当一个数组大部分元素为0，或为同一个值的数组，可以使用稀疏数组来保存该数组
稀疏数组的主要
- 记录数组共有几行几列，以及有多少非0的值
- 把所有非0的值的具体位置记录在一个小规模的数组中，从而缩小规模
通过稀疏数组优化后原本11X11的数组，最后优化为3X3的数组，大量的节省了存储空间
代码示例
public class SpareArray {
public static void main(String[] args) {
/**基础实现*/
//初始化一个11*11的棋盘
//0:没有棋子，1:黑棋子，2:蓝棋子
int[][] chessArr = new int[11][11];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
//打印棋盘内容
System.out.println("打印棋盘原始二维数组内容");
println(chessArr);
//将二维棋盘 转 稀疏数组
System.out.println("二维数组棋盘转稀疏数组");
//获取二维数组长宽，以及不为零的总数
int row = chessArr.length;
int column = chessArr[0].length;
int sum = 0;
//合计非零数目
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (chessArr[i][j] != 0){
sum++;
}
}
}
System.out.println("行："+row+" 列："+column+" 非零数："+sum);
//创建稀疏数组
int[][] sparseArr = new int[sum + 1][3];
//第一行存放，棋盘长宽、非零总数
sparseArr[0][0] = row;
sparseArr[0][1] = column;
sparseArr[0][2] = sum;
//遍历棋盘，将来非零数据的位置保存到稀疏数组中
int index = 0;//记录当前插入非零数据的下班
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (chessArr[i][j] != 0){
index++;
sparseArr[index][0] = i; //行下标
sparseArr[index][1] = j; //列下标
sparseArr[index][2] = chessArr[i][j]; //数据本身
}
}
}
//打印棋盘内容
System.out.println("打印稀疏数组内容");
println(sparseArr);
//稀疏数组恢复为二维数组
System.out.println("稀疏数组恢复为二维数组");
//获取二维数组行列
int[][] sparseArr2chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
//填充非零位置
int len = sparseArr[0][2];
for (int i = 1; i <= len; i++) {
sparseArr2chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("稀疏数组恢复为二维数组后内容");
println(sparseArr2chessArr);
/**扩展练习，将稀疏数组保存到文件中在解析出来*/
System.out.println("\n\n提升练习:将稀疏数组写入到文件中别去解析出来");
System.out.println("使用IO流把稀疏数组写入到：sparseArr.txt文件中");
outputFile(sparseArr);
System.out.println("将sparseArr.txt文件中，稀疏数组导入进来");
int[][] inputFile = InputFile();
System.out.println("打印稀疏数组内容");
println(inputFile);
}
//打印
private static void println(int[][] array){
for (int[] row : array) {
for (int data : row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
//导出成文件
private static void outputFile(int[][] array){
File file = new File("src/main/resources/sparseArr.txt");
try(FileOutputStream os = new FileOutputStream(file)) {
if (!file.exists()){
file.createNewFile();
}
for (int[] row : array) {
for (int data : row) {
os.write((data+",").getBytes(StandardCharsets.UTF_8));
}
os.write("@".getBytes(StandardCharsets.UTF_8));
}
}catch (Exception e){
e.printStackTrace();
}
}
//导入成文件
private static int[][] InputFile(){
File file = new File("src/main/resources/sparseArr.txt");
try(FileInputStream is = new FileInputStream(file)) {
Scanner scanner = new Scanner(is).useDelimiter("@");
String[] row1 = scanner.next().split(",");
int sum = Integer.parseInt(row1[2]);
int[][] res = new int[sum+1][3];
res[0][0] = Integer.parseInt(row1[0]);
res[0][1] = Integer.parseInt(row1[1]);
res[0][2] = Integer.parseInt(row1[2]);
for (int i = 1; i <= sum; i++) {
String[] split = scanner.next().split(",");
res[i][0] = Integer.parseInt(split[0]);
res[i][1] = Integer.parseInt(split[1]);
res[i][2] = Integer.parseInt(split[2]);
}
return res;
}catch (Exception e){
e.printStackTrace();
}
return null;
}
}