文章目录

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

---

一、五子棋案例

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

其中1代表白子，2代表黑子，0代表没有棋子。 使用二维数组维护棋盘数据有一个问题是：在很多时候，此二维数组存放了大量无实际意义的0。

二、稀疏数组

1.基本介绍

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

稀疏数组思路：

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

稀疏数组的存储表示：

其中第一行，即[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或者为同一个值时，可以使用稀疏数组来替换该数组，以达到节约存储空间和运算时间的目的。