「Java数据结构」：手撕二维数组和稀疏数组相互转换。

àì夳堔傛蜴生んèń 2023-10-02 20:17 25阅读 0赞

**目录**

一、稀疏数组

1、什么是稀疏数组

2、图示

3、稀疏数组的表达方式

二、二维数组→稀疏数组

第一步：创建二维数组

第二步：创建稀疏数组，并赋值

第三步：遍历二维数组并赋值给稀疏数组

完整代码

三、 稀疏数组→二维数组

第一步：创建新的二维数组

第二步：循环遍历并赋值

完整代码

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

## 一、稀疏数组 ##

> ### 1、什么是稀疏数组 ###
> 
> 当一个数组中大部分元素为0，或者为同一个值的数组时，可以用稀疏数组来保存该数组。稀疏数组，记录一共有几行几列，有多少个不为零的值或相同的值。  
> 简单来说就是将大规模的数组缩小成小规模的数据，从而减少空间浪费。
> 
> ### 2、图示 ![b53c1a6428e24e0e94e3fa8cf2489d72.png][] ###
> 
> 上面的图示中，左侧是二维数组，右侧是稀疏数组，将二维数组转成稀疏数组，明显的可以看出空间减少了，可以有效的节约空间，提高效率。那么二维数组怎么生成稀疏数组呢？其实很简单，因为二维数组有特定的格式，按格式将二维数组中的数据放入稀疏数组即可。
> 
> ### 3、稀疏数组的表达方式 ###
> 
> ![b48f19b5fc944721a611b16b2e6e1355.png][]
> 
> 稀疏数组的列是固定的，只有三列，第一列表示二维数组的行，第二列表示二维数组的列，第三列表示二维数组非零数的个数。稀疏数组的第一行是固定的，用来表示总行数，总列数，总个数。其余行数根据个数而定。

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

## 二、二维数组→稀疏数组 ##

> ![b2d030c6d61b4941a2f5104b511f7fbe.png][]
> 
> **根据上图所示：**
> 
> ### 第一步：创建二维数组 ###
> 
>     //首先创建二维数组
>     int[][] ChessArr1 = new int[11][11];
>     
>     //赋值
>     ChessArr1[1][2] = 1;
>     ChessArr1[2][3] = 2;
>     
>     //循环遍历得到非零个数
>     int num = 0;
>     for(int[] row : ChessArr1) {
>        for(int data : row) {
>            if(data != 0) {
>                num++;
>             }
>        }
>     }
> 
> 上面用到了增强for循环，第一个增强for循环表示每一个row代表一行（二维数组的行）也就相当与一维数组，第二个增强for循环再遍历一维数组得到每一个数据data来进行判断是否是非零数。
> 
> --------------------
> 
> ### 第二步：创建稀疏数组，并赋值 ###
> 
>     int[][] SparseArr = new int[num + 1][3];
>     //第一行赋值
>     SparseArr[0][0] = 11;
>     SparseArr[0][1] = 11;
>     SparseArr[0][2] = num;
> 
> 前面分析的时候说了，第一行是固定的，二维数组的大小是知道的，所以行列的总数可以直接赋值，总有效个数也求了，也可以直接赋值。
> 
> --------------------
> 
> ### 第三步：遍历二维数组并赋值给稀疏数组 ###
> 
>     int count = 0;
>             for(int i = 0; i < 11; i++) {
>                 for(int j = 0; j < 11; j++) {
>                     if(ChessArr1[i][j] != 0) {
>                         count++;
>                         SparseArr[count][0] = i;
>                         SparseArr[count][1] = j;
>                         SparseArr[count][2] = ChessArr1[i][j];
>                     }
>                 }
>             }
> 
> 遍历二维数组，判断条件是这个数不等于零，此处需要一个计数变量，每符合一个非零数，计数变量就加一，可以用来表示稀疏数组的第几行，稀疏数组的列数是固定的，所以找到后直接进行赋值操作。
> 
> 最后打印稀疏数组即可。
> 
> --------------------
> 
> ### 完整代码 ###
> 
>     //首先创建二维数组
>             int[][] ChessArr1 = new int[11][11];
>             //赋值
>             ChessArr1[1][2] = 1;
>             ChessArr1[2][3] = 2;
>     
>             //将原始数组转 换成 稀疏数组
>             //1、先遍历原始数组得到非0数的个数
>             int num = 0;
>             for(int[] row : ChessArr1) {
>                 for(int data : row) {
>                     if(data != 0) {
>                         num++;
>                     }
>                 }
>             }
>     
>             //2、创建 稀疏数组
>             int[][] SparseArr = new int[num + 1][3];
>             //3、第一行赋值
>             SparseArr[0][0] = 11;
>             SparseArr[0][1] = 11;
>             SparseArr[0][2] = num;
>     
>             //4、循环赋非0值
>             int count = 0;
>             for(int i = 0; i < 11; i++) {
>                 for(int j = 0; j < 11; j++) {
>                     if(ChessArr1[i][j] != 0) {
>                         count++;
>                         SparseArr[count][0] = i;
>                         SparseArr[count][1] = j;
>                         SparseArr[count][2] = ChessArr1[i][j];
>                     }
>                 }
>             }
>     
>             //5、打印稀疏数组
>             System.out.println("\n===打印稀疏数组===");
>             for(int[] row : SparseArr) {
>                 for(int data : row) {
>                     System.out.printf("%d\t",data);
>                 }
>                 System.out.println();
>             }

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

## 三、 稀疏数组→二维数组 ##

> ![4b3451850a674af1a051ba59254c7fff.png][]
> 
> ### 第一步：创建新的二维数组 ###
> 
>     //1、定义一个新的二维数组
>     int[][] ChessArr2 = new int[SparseArr[0][0]][SparseArr[0][1]];
> 
> 二维数组的大小来自稀疏数组的第一行第一列和第一行第二列，也就是 SparseArr\[0\]\[0\] 和 SparseArr\[0\]\[1\] ；初始状态下的二维数组数据全为零。
> 
> --------------------
> 
> ### 第二步：循环遍历并赋值 ###
> 
>     //2、赋值
>             for(int i = 1; i <= SparseArr[0][2]; i++) {
>                 ChessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2];
>             }
> 
> 因为除了少数是有效个数，其他全是零，所以我们只需要遍历有效个数。i 表示第几个有效个数也表示当前这个数在稀疏数组中的行，如上图所示：如 i = 1，表示在稀疏数组的第一行，它在二维数组中的位置为 （1,2），数值为 1 ；所以行和列分别是SparseArr\[1\]\[0\]和SparseArr\[1\]\[1\]，数值为SparseArr\[1\]\[2\]。
> 
> 所以赋值表达式为：ChessArr2\[SparseArr\[i\]\[0\]\]\[SparseArr\[i\]\[1\]\] = SparseArr\[i\]\[2\]。
> 
> --------------------
> 
> ### 完整代码 ###
> 
>     //将稀疏数组 转换成 二维数组
>             //1、定义一个新的二维数组
>             int[][] ChessArr2 = new int[SparseArr[0][0]][SparseArr[0][1]];
>     
>             //2、赋值
>             for(int i = 1; i <= SparseArr[0][2]; i++) {
>                 ChessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2];
>             }
>     
>             //3、打印新的二维数组
>             System.out.println("\n===新的二维数组===");
>             for(int[] row : ChessArr2) {
>                 for(int data : row) {
>                     System.out.printf("%d\t",data);
>                 }
>                 System.out.println();
>             }

[b53c1a6428e24e0e94e3fa8cf2489d72.png]: https://img-blog.csdnimg.cn/b53c1a6428e24e0e94e3fa8cf2489d72.png
[b48f19b5fc944721a611b16b2e6e1355.png]: https://img-blog.csdnimg.cn/b48f19b5fc944721a611b16b2e6e1355.png
[b2d030c6d61b4941a2f5104b511f7fbe.png]: https://img-blog.csdnimg.cn/b2d030c6d61b4941a2f5104b511f7fbe.png
[4b3451850a674af1a051ba59254c7fff.png]: https://img-blog.csdnimg.cn/4b3451850a674af1a051ba59254c7fff.png