『数据结构与算法』稀疏数组

微信搜索：码农StayUp
主页地址：https://gozhuyinglong.github.io
源码分享：https://github.com/gozhuyinglong/blog-demos

五子棋游戏的存取需求

在介绍稀疏数组前我们先来引入一个需求，下面是一个五子棋的棋盘（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 推荐阅读

《 数组 》

《 稀疏数组 》

《 链表（单链表、双链表、环形链表） 》

《 栈 》

《 队列 》

《 树 》

《 二叉树 》

《 二叉查找树（BST） 》

《 AVL树（平衡二叉树） 》

《 B树 》

《 散列表（哈希表） 》