Java数据结构之稀疏数组

稀疏数组适用于一个数组中元素大部分为0，或者为同一个值的数组，使用稀疏数组可以减少数组中的重复部分而起到提高效率的目的，以棋盘与棋子为例，我们具体看看如何实现它。
假设在一个11*11的棋盘中，第二行第三列有一颗黑子，第三行第四列有一颗白子，用一张简单的图如下：

此时我们用一个二维数组来表示该棋盘上的情况，0为该位置上没有棋子，1为该位置上有黑子，2为该位置上有白子，声明一个二维数组，并输出它：

 //创建一个原始的二维数组11*11
        //0：表示没有旗子，1表示黑子，2表示白子
        int chessArr1[][]=new int[11][11];
        chessArr1[1][2]=1;
        chessArr1[2][3]=2;
        //输出
        System.out.println("原始的二维数组：");
        for (int [] row:chessArr1) {
            for (int data:row) {
                System.out.printf("%d\t",data);
            }
            System.out.println("\t");

运行结果：

从图上我们能看出，该数组虽然长度为11，但绝大部分元素都是0 ，而我们实际需要的值只有1和2，稀疏数组的作用，就是将具有不同值的元素所在的行列值记录在一个小规模的数组中，从而达到减少规模的目的，接下来开始创建稀疏数组。

首先得了解稀疏数组存储元素的规则，拿上面的例子来说，该二维数组转化为稀疏数组后，会得到一个小的二维数组，该二维数组的长度为原数组中有效值的个数+1，即3，而该数组中每个一维数组的长度为3，即该稀疏数组为：int sparseArray[][]=new int[3][3];

为了更好解释，先对其进行输出：

其中第一行分别存储的是原数组的长度、原数组中每个一位数组的长度以及原数组中不同值的个数，第二行、第三行分别存储每个不同值在原数组中的x、y位置以及值。接下来便开始生成稀疏数组。

第一步：得到原二维数组中不同值的个数：

//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 sparseArray[][]=new int[sum+1][3];
        //给稀疏数组赋值
        sparseArray[0][0]=11;
        sparseArray[0][1]=11;
        sparseArray[0][2]=sum;
        

第三步：给稀疏数组赋值：

//遍历二维数组，将非0的值存放到稀疏数组中
        int count=0;//用于记录是第几个非0数据
        for (int i = 0; i <11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] !=0){
                    count ++;
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=chessArr1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println("\n得到的稀疏数组为：");
        for (int [] row:sparseArray) {
            for (int data1:row) {
                    System.out.printf("%d\t",data1);
            }
            System.out.println("\t");
        }

运行结果：

接下来，看看如何将稀疏数组还原：

第一步：读取稀疏数组的第一行，根据第一行的数据创建原始二维数组

		 //1.读取稀疏数组的第一行，根据第一行的数据创建原始二维数组
		int chessArray2[][]=new int[sparseArray[0][0]][sparseArray[0][1]];

第二步：读取稀疏数组后几行，并赋给原始的二维数组

 //2.读取稀疏数组后几行，并赋给原始的二维数组
        for (int i = 1; i <sparseArray.length; i++) {//从稀疏数组第二行开始
          chessArray2[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }
         //输出
        System.out.println("\n恢复后的二维数组是：");
        for (int [] row:chessArray2) {
            for (int data:row) {
                System.out.printf("%d\t",data);
            }
            System.out.println("\t");
        }

运行结果：