数据结构与算法(Java)——稀疏数组

文章目录

• 一、五子棋案例
• 二、稀疏数组
• • 1.基本介绍
  • 2.代码实现
• 总结

一、五子棋案例

假如我们要开发一款五子棋程序，使用一个二维数组对棋盘数据进行维护是常见的思路。下面以常见的15x15五子棋盘举例，左图是棋盘，右图则是维护它的一个二维数组。

其中1代表白子，2代表黑子，0代表没有棋子。

使用二维数组维护棋盘数据有一个问题是：在很多时候，此二维数组存放了大量无实际意义的0。

二、稀疏数组

1.基本介绍

当一个数组中大部分元素为0或者为同一个值时，可以使用稀疏数组来替换该数组，以达到节约存储空间和运算时间的目的。

稀疏数组思路：

1. 记录数组一共有几行几列、有多少个不同的值
2. 把不同值的元素和对应的行和列存放在一个小规模数组中

稀疏数组的存储表示：

其中第一行，即[0]，用于存储原始二维数组共有多少行、多少列以及多少个不同的值。

后面的行，如[1][2][3] …等，则存放对应那些不同值的元素所在行、所在列以及具体的值。

在上述的五子棋案例中，棋盘共有15行、15列、6颗棋子(即6个不同的值)，那么就可以将上述维护棋盘数据的二维数组转换为如下的稀疏数组：

2.代码实现

1.创建原始二维数组[15][15]，并在相应行列放置棋子，1代表白子，2代表黑子。

int dataCount=0;   //记录有效数据的个数
int [][] chessArr1 = new int[15][15];
chessArr1[5][5]=1;
chessArr1[5][6]=1;
chessArr1[6][5]=1;
chessArr1[6][6]=2;
chessArr1[6][7]=2;
chessArr1[7][6]=2;
           

2.遍历原始数组，确定有效数据的个数

for (int [] row : chessArr1){
	for (int data : row){
		System.out.printf("%d\t",data);
        if (data!=0)
            dataCount++;
    }
    System.out.println();
}
           

3.将原始数组转换为稀疏数组

int [][] sparseArr = new int[dataCount+1][3]; //稀疏数组行数=有效数据个数+1个记录行
sparseArr[0][0]=chessArr1.length;//第1行第1列的值为原始数组的行数
sparseArr[0][1]=chessArr1[0].length;//第1行第2列的值为原始数组的列数
sparseArr[0][2]=dataCount;//第1行第3列的值为原始数组中有效数据的个数
int rowIndex=1;  //行游标，有效数据从第1行开始记录
for (int i=0;i<chessArr1.length;i++){
    for (int j=0;j<chessArr1[0].length;j++){
        if (chessArr1[i][j]!=0){
            sparseArr[rowIndex][0]=i;
            sparseArr[rowIndex][1]=j;
            sparseArr[rowIndex][2]=chessArr1[i][j];
            rowIndex++;
        }
    }
}
           

4.从稀疏数组复原原始数组

int [][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for(int i=1;i<=sparseArr[0][2];i++){
    chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
           

总结

当一个数组中大部分元素为0或者为同一个值时，可以使用稀疏数组来替换该数组，以达到节约存储空间和运算时间的目的。