数据结构与算法（Java版） | 稀疏数组的一个实际应用案例

提出需求：使用稀疏数组来保存类似棋盘或者地图等等映射而来的二维数组，然后存盘，并且希望可以重新恢复为原来的二维数组

通过上一讲的学习，我们知道了使用稀疏数组即可保存类似下面的二维数组，当然，现在大家可能都知道了该二维数组是由五子棋棋盘映射而来的，但是在实际应用中，它也有可能是由一个地图而映射来的哟！

于是，问题就来了，既然我们知道可以使用稀疏数组来保存类似上面的二维数组（比如棋盘或者地图等等）了，那么接下来我们是不是就可以考虑这样一个需求——将稀疏数组存盘，并且希望可以重新恢复为原来的二维数组了呢？

话不多说，下面我们就来分析一下这个需求。

还是以我们之前的五子棋棋盘为例，如下图所示，可以看到棋盘上有一个黑子和一个蓝子。

然后，我们将其映射成如下这样一个二维数组。

走到这一步，相信大家应该都没有什么问题吧！

然而，如果你仔细查看以上二维数组的话，那么你会发现它里面竟有一大堆的0（也即默认值），非常可惜，这些都是些没有意义的数据，因此接下来我们就要将以上二维数组转成一个稀疏数组了。这个稀疏数组长什么样呢？就长下面这样。

可以看到，这个稀疏数组总是一个行数不确定，但列数是3的这么一个动态数组。知道这个之后，下面我就要来给大家说一下这个稀疏数组的每一行所记录的究竟是些什么了。

1. 第一行记录的是原始二维数组一共有几行几列，以及有多少个不同的值。

   很明显，原始二维数组一共有11行11列，2个有效数据，而且它们分别是1和2。

2. 第二行记录的是第一个有效数据所在的行和列，以及其值。

   从以上原始二维数组中不难看出，第一个有效数据是1，且其在原始二维数组的第2行第3列上，也就是说它所在的行是1，列是2，相信这个大家都能看出来！

3. 第三行记录的是第二个有效数据所在的行和列，以及其值。

   同上，这里我就不再赘述了。

至此，一个原始的11*11的二维数组经过处理就变成了一个3*3的稀疏数组。很明显，变小了，而这也刚好说明了使用稀疏数组的好处，即可以缩小原始二维数组的规模。

原始二维数组转变成稀疏数组之后，接下来我们就要考虑将稀疏数组再重新恢复成原始的二维数组了，是这样吧！不知道大家还记不记得五子棋游戏中那个续上局的操作，记得的话，那你就应该知道该操作所做的正是这样一件事，即重新将稀疏数组再恢复成原始的二维数组。

虽然我上面讲了这么多，但是我还是有一件事没跟大家讲明白，什么事呢，原始二维数组与稀疏数组它俩之间转换的思路，因此接下来我就要来给大家讲一讲这个思路了。

整体思路分析

原始二维数组转稀疏数组的思路

原始二维数组转稀疏数组的大体思路如下：

1. 遍历原始二维数组，得到要保存的有效数据的个数，假定为sum。

   为什么要得到有效数据的个数呢？因为我们只有在知道有效数据的个数之后才能知道将来的稀疏数组有多大。

2. 根据sum创建稀疏数组int[sum + 1][3] sparseArr。

   这个稀疏数组，大家应该知道它是行不确定（即sum + 1，取决于有效数据的个数），而列是固定（即3）的这个样子的吧！

3. 将原始二维数组的有效数据存入到稀疏数组中。

   注意，稀疏数组的第一行还得存储原始二维数组的行和列，以及有多少个不同的值哟！

其实，以上有一个过程我给省略掉了，眼尖的同学应该能看出来，什么过程呢，就是稀疏数组存盘的这个过程，说白了，就是稀疏数组最终还是得保存到磁盘文件中，例如chess.data，很显然，这一过程会牵扯到IO。但是，由于我忽略掉了这一过程，所以我在代码中肯定就不会去实现它了，当然，不除非有部分同学会感兴趣，如果真是这样的话，那你就得自个私下去实现这一过程了。

稀疏数组转原始二维数组的思路

稀疏数组转原始二维数组的大体思路如下：

1. 先读取稀疏数组的第一行，然后根据第一行记录的数据创建原始二维数组，比如我们就叫int chessArr2[11][11]。
2. 再读取稀疏数组后几行记录的数据，然后赋给原始二维数组。

注意，在将稀疏数组恢复成原始二维数组前，其实有一个过程我给忽略掉了，什么过程呢，就是你得先把稀疏数组存盘的那个文件读取为稀疏数组，然后你才能将稀疏数组恢复成原始二维数组，是这样吧！当然，不除非有部分同学会感兴趣，如果真是这样的话，那你就得自个私下去实现这一过程了。

代码实现

分析完毕原始二维数组转稀疏数组和稀疏数组转原始二维数组的大体思路之后，接下来我们就要准备用代码来实现这一思路了。

不过，在代码实现之前，有句话我还得给大家说一下，就是我们写一段代码，本身其实是并不难的，难的是之前的思路分析，就是你怎么想到能够这样去处理的，而这个就是算法的力量。总之，别人费劲巴拉设计出来一个数据结构之后，我们所需要做的只是将这种数据结构应用到实际的开发中，用以提高我们程序的一个效率，俗话说就是“如果说我看得远，那是因为我站在巨人的肩上”。

下面，我们就要正式来写代码将上面我们所分析的原始二维数组转稀疏数组和稀疏数组转原始二维数组的大体思路予以实现了。

package com.meimeixia.sparsearray;

/**
 * @author liayun
 * @create 2023-04-22 10:05
 */
public class SparseArray {

    public static void main(String[] args) {
        /**
         * 创建一个原始的二维数组。
         *
         * 注意，这个原始的二维数组是由五子棋盘映射而来的，而且我们还是这样来表示棋盘上的棋子的：
         * 0：表示没有棋子
         * 1：表示黑子
         * 2：表示蓝子
         */
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 2;
        // 原始二维数组创建好并赋值之后，我们便来输出一下它
        System.out.println("原始的二维数组就长这样：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        /**
         * 将原始二维数组转成稀疏数组。
         */
        // 1. 遍历原始二维数组，以期得到有效数据（即非0数据）的个数。
        // 不知道大家会不会有这样一个困惑，就是为啥非得先这样做呢？这是因为如果你不先通过遍历原始二维数组的方式把有效数据的个数得到，
        // 那么接下来你就无法创建出对应的稀疏数组了，除非你使用集合，但是这里我又要求大家只能使用数组，故大家就只能这样处理了！
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 2. 创建对应的稀疏数组。
        int sparseArr[][] = new int[sum + 1][3];
        // 3. 为稀疏数组赋值。
        // (1) 不用我说，相信大家应该都知道稀疏数组的第一行记录的是原始二维数组的行、列以及有效数据的个数吧！
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // (2) 再次遍历原始二维数组，并将非0数据存放到稀疏数组中。
        int count = 0; // 计数器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];
                }
            }
        }

        // 稀疏数组创建完毕之后，咱们再来输出一下，好给大家看看它究竟长啥样。
        System.out.println();
        System.out.println("得到的稀疏数组为：");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }

        System.out.println();

        /**
         * 将稀疏数组恢复成原始的二维数组。
         */
        // 1. 先读取稀疏数组的第一行，然后根据第一行记录的数据创建原始二维数组，比如我们就叫int chessArr2[11][11]。
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 2. 再读取稀疏数组后几行记录的数据，然后赋给原始二维数组。
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // 咱们输出一下恢复后的原始二维数组，看看它长什么样子。
        System.out.println();
        System.out.println("恢复后的原始二维数组长这样：");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

}

以上便是稀疏数组的一个应用实例。

我希望大家通过以上稀疏数组的应用实例能深刻理解这一点，就是原始二维数组在经过稀疏数组的处理之后，数据量相应地就会变得很小，如此一来，便能起到一个缩小原始二维数组规模的效果。当然，要是我们在实际开发中有遇到类似这样的需求，那么使用该小技巧无形中就能节省我们的内存空间，提高效率也说不定。

最后，有一点我还得给大家说一下，就是我写的以上代码并没有实现将稀疏数组保存到磁盘文件上这一功能，这一点相信大伙都能看得出来。于是，接下来你就有了这样一个任务，即在我上面写的代码基础之上，将稀疏数组保存到磁盘文件中，比如map.data；而至于恢复为原来的二维数组嘛，那你就得读取map.data文件进行恢复了。

以上任务难吗？不难，因为你当初学Java基础的时候肯定是学过IO流的，而这个任务仅仅只是需要用到一点点IO流的知识而已，你要是完成不了那就太说不过去了，该打屁股，哈哈哈😂，当然，这里我并没有去完成这样一个任务，主要是我觉得二维数组与稀疏数组之间转换的核心代码才是大家应该掌握的重点，至于以上任务嘛，那就纯纯是属于IO流的部分了，相信只要学过Java的同学应该都能完成，因为并不难啊！