Java数据结构实现二维数组与稀疏数组转换详解

一、二维数组与稀疏数组

在介绍二维数组与稀疏数组的转换之前，需要先了解它们的定义和特点。

1.二维数组

二维数组是一个由多个一维数组组成的数组。可以将它理解为是一个由行和列构成的矩阵。其中，行和列的数量是固定的，而且必须预先指定。

二维数组的声明方式为：

数据类型[][] 数组名;

例：

int[][] arr;

二维数组的初始化方式有两种：

1.静态初始化：在声明的同时为数组元素赋初值。

数据类型[][] 数组名 = {{元素1,元素2,...},{元素1,元素2,...},...};

例：

int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};

2.动态初始化：在声明数组时只指定数组元素的类型和数量，然后再分别为每个数组元素赋初值。

数据类型[][] 数组名 = new 数据类型[行数][列数];

例：

int[][] arr = new int[3][3];
arr[0][0] = 1;
arr[0][1] = 2;
...

2.稀疏数组

稀疏数组是一种压缩存储的数组。它通常应用在当数组中大部分的元素值为默认值或者某一个值的情况下。稀疏数组通常由3列组成，分别为：行数、列数以及具体数值。通常情况下，稀疏数组的行数为原数组中有效元素的个数+1，列数为3。

稀疏数组的转换过程如下：

1.遍历原数组，得到有效元素的个数count；
2.根据count+1创建一个稀疏数组sparse_arr；
3.将sparse_arr的第一行赋值为原数组的行数、列数和有效元素的个数；
4.遍历原数组，将每个非0的元素的行列和值存入稀疏数组sparse_arr中。

示例：

原始数组为：

int[][] arr = {{0,0,0,0,0},
               {0,0,1,0,0},
               {0,0,0,2,0},
               {0,0,3,0,0},
               {0,0,0,0,0}};

转换为稀疏数组后的结果为：

sparse_arr = {{5,5,3},
              {1,3,1},
              {2,4,2},
              {3,2,3}}

二、Java实现二维数组与稀疏数组的转换

1.生成原始数组

前文示例已经给出。

2.生成稀疏数组

代码如下：

public static int[][] toSparseArr(int[][] arr) {
    // 遍历原数组得到非零元素个数num
    int num = 0;
    for (int[] row : arr) {
        for (int data : row) {
            if (data != 0) {
                num++;
            }
        }
    }

    // 创建稀疏数组sparseArr
    int[][] sparseArr = new int[num + 1][3];

    // 给稀疏数组sparseArr的第一行赋值
    sparseArr[0][0] = arr.length;
    sparseArr[0][1] = arr[0].length;
    sparseArr[0][2] = num;

    // 遍历二维数组，将非零的值存放到sparseArr中
    int count = 0; // count用于记录是第几个非零数据
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[0].length; j++) {
            if (arr[i][j] != 0) {
                count++;
                sparseArr[count][0] = i;
                sparseArr[count][1] = j;
                sparseArr[count][2] = arr[i][j];
            }
        }
    }
    return sparseArr;
}

3.生成原始数组

代码如下：

public static int[][] toNormalArr(int[][] sparseArr) {
    // 读取稀疏数组的行列信息
    int row = sparseArr[0][0];
    int col = sparseArr[0][1];
    int num = sparseArr[0][2];

    // 创建原始二维数组
    int[][] normalArr = new int[row][col];

    // 根据稀疏数组的值，还原原始二维数组
    for (int i = 1; i <= num; i++) {
        int r = sparseArr[i][0];
        int c = sparseArr[i][1];
        int val = sparseArr[i][2];
        normalArr[r][c] = val;
    }

    return normalArr;
}

三、示例

1.将示例二维数组转换成稀疏数组

int[][] arr = {{0,0,0,0,0},
               {0,0,1,0,0},
               {0,0,0,2,0},
               {0,0,3,0,0},
               {0,0,0,0,0}};
int[][] sparseArr = toSparseArr(arr);

输出结果：

5 5 3
1 3 1
2 4 2
3 2 3

2.将示例稀疏数组还原成原始二维数组

int[][] sparseArr = {{5,5,3},
                     {1,3,1},
                     {2,4,2},
                     {3,2,3}};
int[][] normalArr = toNormalArr(sparseArr);

输出结果：

0 0 0 0 0
0 0 1 0 0
0 0 0 2 0
0 0 3 0 0
0 0 0 0 0

四、总结

本文介绍了Java实现二维数组与稀疏数组的转换过程，并给出了相关的示例代码。需要注意的是，稀疏数组的转换过程可以运用到实际项目中进行数据的压缩和存储。