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

深碍√TFBOYSˉ_ 2022-12-16 13:20 162阅读 0赞

### 文章目录 ###

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

--------------------

# 一、五子棋案例 #

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MTI1Mjc_size_16_color_FFFFFF_t_70_pic_center]

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

# 二、稀疏数组 #

## 1.基本介绍 ##

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

稀疏数组思路：

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

稀疏数组的存储表示：

![在这里插入图片描述][20201020190151156.png_pic_center]  
其中第一行，即\[0\]，用于存储原始二维数组共有多少行、多少列以及多少个不同的值。  
后面的行，如\[1\]\[2\]\[3\] …等，则存放对应那些不同值的元素所在行、所在列以及具体的值。

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

![在这里插入图片描述][2020102019120788.png_pic_center]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MTI1Mjc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6a925f035d3447bd91fb5e1850be8cd9.png
[20201020190151156.png_pic_center]: /images/20221123/9d26bf1d818e4c62975b954d9a279815.png
[2020102019120788.png_pic_center]: /images/20221123/9190ca9e5a5c421baed577c0fdfdf922.png