锐客网

  1. 首页 > 睿知 > it技术 > >

『数据结构与算法』稀疏数组（这样来节省存储空间）

IT知识数据结构稀疏数组存储空间

我自横刀向天笑，去留肝胆两昆仑。这篇文章主要讲述『数据结构与算法』稀疏数组：这样来节省存储空间相关的知识，希望能为你提供帮助。

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


五子棋游戏的存取需求


在介绍稀疏数组前我们先来引入一个需求，下面是一个五子棋的棋盘（15 * 15），玩到中途时想要保存离开，希望下次打开还可以继续玩。我们怎么实现呢？





从对棋盘的观察来看，我们可以使用??int??型的二维数组进行存储，将未落子的地方存储0，白子存储1，黑子存储2，那么我们的数组可能是这样的：






可以看出，使用二维数组是能解决这个需求的。但我们也发现了一个问题，上面存储相同数值的0比较多，这对空间造成了浪费，有没有另外一种存储方式呢？答案是可以使用稀疏数组，下面我们来看稀疏数组是怎么实现的！


稀疏数组（Sparse Array）


当一个数组中大部分元素是0，或者是一个相同的值时，可以使用稀疏数组来保存该数组。稀疏数组的处理方式是：
  1. 记录数组一共有几行几列，以及不同值的数量
  2. 把具有不同值元素的行列及其值记录在一个小规模的数组中，从而缩小数据的规模。
【『数据结构与算法』稀疏数组（这样来节省存储空间）】那我们把上面二维数组转为稀疏数组存储，看是什么样子的。





第一行（即：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 = https://www.songbingjia.com/android/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;

    推荐阅读


    上一篇：性能工具之Taurus入门（安装篇）

    下一篇：Office365混合部署进阶系列教程二（混合环境下的PTA直通身份认证）