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

• 稀疏数组
• • 应用场景
  • 二维数组和稀疏数组的互相转换
  • • 对应介绍：
    • 二位数组转换稀疏数组思路
    • 稀疏数组转换原始二维数组
  • 代码实现
  • • 运行结果

稀疏数组就是数组中大部分的内容值都未被使用（为零或同值），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。

大量冗余的相同数据存储

由这张图可以看出：

稀疏数组第一行存放二维数组的行数和列数以及非零值的个数

第二行楷书存放各个值所对应的坐标和值的大小

一般来说所要存放的二维数组比例子中大的多所以使用稀疏数组会更加简单

1. 遍历原始的二维数组获得有效数据的个数sum
2. 根据sum就可以创建稀疏数组 sparseArray int[sum + 1][3]
3. 将二维数组的有效数据存入稀疏数组中

1. 先读取稀疏数组的第一行数据，创建相对应行row和列col的二维数组chessArray[][]
2. 读取稀疏数组后面各行的数据，对chessArray[][]进行赋值

package sparsearray;


public class SparseArrayDemo1 {
    public SparseArrayDemo1() {
    }

    
    public static int getRowFromChessArr(int[][] chessArr) {
        return chessArr.length;
    }

    
    public static int getColFromChessArr(int[][] chessArr) {
        int col = 0;
        for (int row = 0; row < chessArr.length; row++) {
            for (col = 0; col < row; col++) {
            }
        }
        return col;
    }

    
    public static int getSumNum(int[][] chessArr) {
        int sum = 0;
        for (int row = 0; row < getRowFromChessArr(chessArr); row++) {
            for (int col = 0; col < getColFromChessArr(chessArr); col++) {
                if (chessArr[row][col] != 0) {
                    sum++;
                }
            }
        }
        return sum;
    }

    
    public static void printChessArr(int[][] chessArr) {
        for (int[] row : chessArr) {
            for (int col : row) {
                System.out.printf("%dt", col);
            }
            System.out.println();
        }
    }

    
    public static void printSparseArr(int[][] sparseArr) {
        printChessArr(sparseArr);
    }

    
    public static void assignmentToSparseArr(int[][] chessArr, int[][] sparseArr) {
        //给稀疏数组相应位置赋值
        //使用计数器达到换行效果
        int count = 0;
        for (int row = 0; row < getRowFromChessArr(chessArr); row++) {
            for (int col = 0; col < getColFromChessArr(chessArr); col++) {
                if (chessArr[row][col] != 0) {
                    count++;
                    //修改x坐标
                    sparseArr[count][0] = row;
                    //修改y坐标
                    sparseArr[count][1] = col;
                    //修改有效值
                    sparseArr[count][2] = chessArr[row][col];
                }
            }
        }
    }

    
    public static int getRowFromSparseArr(int[][] sparseArr) {
        //稀疏数组中的[0][0]就是原始二维数组的行
        return sparseArr[0][0];
    }

    
    public static int getColFromSparseArr(int[][] sparseArr) {
        //稀疏数组中的[0][1]就是原始二维数组的列
        return sparseArr[0][1];
    }

    
    public static int getSumFromSparseArr(int[][] sparseArr) {
        //稀疏数组中的[0][2]就是原始二维数组的有效值的个数
        return sparseArr[0][2];
    }

    
    public static void assignmentToChessArr(int[][] chessArr, int[][] sparseArr) {
        for (int row = 1; row <= getSumFromSparseArr(sparseArr); row++) {
            chessArr[sparseArr[row][0]][sparseArr[row][1]] = sparseArr[row][2];
        }
    }


    
    public static void main(String[] args) {
        //创建一个二位数组
        //0：表示没有棋子，1：表示黑子 ，2：表示白子

        //创建一个11行10列的二维数组
        int[][] chessArray1 = new int[11][10];
        //对原始二维数组进行赋值
        chessArray1[2][3] = 1;
        chessArray1[3][6] = 1;
        chessArray1[6][1] = 2;
        chessArray1[8][8] = 2;

        System.out.println("原始二维数组:");
        printChessArr(chessArray1);

        //创建对应的稀疏数组
        int sumNum = getSumNum(chessArray1);
        int[][] sparseArray = new int[sumNum + 1][3];
        //给稀疏数组赋值
        sparseArray[0][0] = getRowFromChessArr(chessArray1);
        sparseArray[0][1] = getColFromChessArr(chessArray1);
        sparseArray[0][2] = sumNum;

        assignmentToSparseArr(chessArray1, sparseArray);

        System.out.println("稀疏数组:");
        printSparseArr(sparseArray);

        System.out.println("-------------------------------------");

        //稀疏数组转二维数组
        System.out.println("稀疏数组:");
        printSparseArr(sparseArray);

        //构造一个二维数组
        int[][] chessArray2 = new int[getRowFromSparseArr(sparseArray)][getColFromSparseArr(sparseArray)];
        assignmentToChessArr(chessArray2, sparseArray);
        System.out.println("恢复后的二维数组：");
        printChessArr(chessArray2);
    }
}