GitHub 源码分享
我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/array
五子棋游戏的存取需要
在介绍稠密数组前咱们先来引入一个需要，上面是一个五子棋的棋盘（15 * 15），玩到中途时想要保留来到，心愿下次关上还能够持续玩。咱们怎么实现呢？
从对棋盘的察看来看，咱们能够应用 int 型的二维数组进行存储，将未落子的中央存储 0，白子存储 1，黑子存储 2，那么咱们的数组可能是这样的：
能够看出，应用二维数组是能解决这个需要的。但咱们也发现了一个问题，下面存储雷同数值的 0 比拟多，这对空间造成了节约，有没有另外一种存储形式呢？答案是能够应用稠密数组，上面咱们来看稠密数组是怎么实现的！
稠密数组（Sparse Array）
当一个数组中大部分元素是 0，或者是一个雷同的值时，能够应用稠密数组来保留该数组。
稠密数组的解决形式是：
- 记录数组一共有几行几列，以及不同值的数量
- 把具备不同值元素的行列及其值记录在一个小规模的数组中，从而放大数据的规模。
那咱们把下面二维数组转为稠密数组存储，看是什么样子的。
第一行（即：0 行）比拟非凡，row 存储总行数，col 存储总列数，value 存储非零（不同值）元素的数量；
其余行构造雷同，每一行存储一条非零元素信息，row 存储元素所在行，col 存储元素所在列，value 存储元素的值。
代码实现
咱们应用代码来实现二维数组与稠密数组的互相转换，上面是具体的实现！
public class SparseArrayDemo {public static void main(String[] args) {System.out.println("----------------------- 一般数组");
int[][] initialArray = initArray();
printArray(initialArray);
System.out.println("----------------------- 一般数组 --> 稠密数组");
int[][] sparseArray = arrayConvertSparseArray(initialArray);
printArray(sparseArray);
System.out.println("----------------------- 稠密数组 --> 一般数组");
int[][] array = sparseArrayConvertArray(sparseArray);
printArray(array);
}
/**
* 初始化五子棋数组
*
* @return
*/
static int[][] initArray() {
// 0 为空，1 为白子，2 为黑子
int[][] array = new int[15][15];
array[3][11] = 1;
array[4][10] = 2;
array[5][9] = 2;
array[6][8] = 2;
array[6][7] = 1;
array[7][8] = 1;
array[7][7] = 2;
array[8][6] = 1;
return array;
}
/**
* 打印二维数组
*
* @param array
*/
static void printArray(int[][] array) {for (int[] row : array) {for (int data : row) {System.out.printf("%s\t", data);
}
System.out.println();}
}
/**
* 统计非零值数量
*
* @param array
* @return
*/
static int valueCount(int[][] array) {
int count = 0;
for (int[] row : array) {for (int data : row) {if (data != 0) {count++;}
}
}
return count;
}
/**
* 一般数组转为稠密数组
*
* @param array
* @return
*/
static int[][] arrayConvertSparseArray(int[][] array) {
int rowNum = array.length;
int colNum = array[0].length;
int valueNum = valueCount(array);
int[][] sparseArray = new int[valueNum + 1][3];
sparseArray[0][0] = rowNum;
sparseArray[0][1] = colNum;
sparseArray[0][2] = valueNum;
int rowCount = 1;
for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {int value = array[i][j];
if (value != 0) {sparseArray[rowCount][0] = i;
sparseArray[rowCount][1] = j;
sparseArray[rowCount][2] = value;
rowCount++;
}
}
}
return sparseArray;
}
/**
* 稠密数组转为一般数组
*
* @param sparseArray
* @return
*/
static int[][] sparseArrayConvertArray(int[][] sparseArray) {int rowNum = sparseArray[0][0];
int colNum = sparseArray[0][1];
int valueNum = sparseArray[0][2];
int[][] array = new int[rowNum][colNum];
for (int i = 1; i < valueNum + 1; i++) {int row = sparseArray[i][0];
int col = sparseArray[i][1];
int value = sparseArray[i][2];
array[row][col] = value;
}
return array;
}
}输入后果：
----------------------- 一般数组
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 1 0 0 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 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 2 1 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 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
----------------------- 一般数组 --> 稠密数组
15 15 8
3 11 1
4 10 2
5 9 2
6 7 1
6 8 2
7 7 2
7 8 1
8 6 1
----------------------- 稠密数组 --> 一般数组
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 1 0 0 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 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 2 1 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 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