二维数组与稀疏数组的转换dataStructures

首先我们看一个需求

在11 * 11 的五子棋的棋盘中 我们使用0代表十字交叉点也是无效的数据 用1代表黑棋 用2代表蓝棋
那么所看到的棋盘如下

改用数字显示后就如一下样式

现在我们需要将怎个棋盘存储起来，但是又发现有很多为0 的无效数据，那么我们就需要考虑将有效的数据存储无效的数据不用存储起来
这样我们就可以使用稀疏数组将数据存储起来

稀疏数组

稀疏数组有一定会有三行，列是随有效数据的个数而变化的，先看一个稀疏数组的大概样子

二维数组转换为稀疏数组的思路

• 第一部 需要遍历稀疏数组，获取有效数据的个数（sum），改个数可以用来确定稀疏数组的行数，那么稀疏数组的行数就是（sum + 1）【因为稀疏数组的第一行是原始二维数组已经确定好了的】

//统计原始二维数组中的有效数据的个数,sum代表二维数组中有效数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr.length; j++) {
                if (chessArr[i][j] != 0){
                    sum++;
                }
            }
        }
        System.out.println("有效数据的个数为：" + sum);

• 第二部 创建一个稀疏数组 int[][] sparseArr[sum +1 ][3]

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

• 第三部 遍历稀疏数组中的有效数据的索引和值，并将有效数据存入稀疏数组中

         //给稀疏数组的第一行复制
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;              --sum（有效数据的个数）
        //2. 给稀疏数组赋值,count用于计数，计算该稀疏数组的第几行
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr.length; j++) {
                if (chessArr[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }

稀疏数组转换为二维数组的思路

• 第一部 读取稀疏数组的第一行，利用第一行的数据，创建出没有有效数据的二维数组 reChessArr = int[sparseArr[0][0]][sparseArr[0][1]];
  int reChessArr[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
• 第二部 遍历稀疏数组的后几行数据，并且赋值给 reChessArr， 这样就还原了有数据的二维数组

       //给还原后的二维数组赋值
        for (int i = 1; i < sparseArr.length; i++) {
            reChessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

全部代码地址

码云（gitee）： dataStructures-sparseArray

github： dataStructures-sparseArray