数据结构入门教程-稀疏数组

数据结构的学习是一个对自己沉淀的过程，伴随着枯燥。同样也能对我们自身的能力有很大的提升，如果要我来说，一段精髓的代码是算法+数据结构+设计模式+5大开闭原则而构成，正所谓万变不离其宗，关于数据结构和算法的学习我是基于尚硅谷韩顺平老师的教学视频的基础上进行的学习总结过程，我们进入正题。

什么是稀疏数组？

如果一个数组中大部分的元素为同一个值，或者为0，我们我们对该数组进行优化，通过一种方式来对该数组进行重新的存储，这样可以达到节约空间的效果， 也就是我们这里的稀疏数组。

了解了稀疏数组的话，我们通过一个经典案例来分析稀疏数组，题目大概是这样的：

• 如图是一个11*11的棋局，1位白色棋子，2代表蓝色棋子，0代表没有棋子的位置。

  
  image

那么我们的问题分别是：

• 通过稀疏数组首先来记录图中棋子的位置
• 将记录棋子的稀疏数组恢复原来的棋局模式

题意很明确就是需要我们通过稀疏数组来完成，接下里我们解读整个解题的思路

• 既然是11*11的棋局，那么我们将它暂且理解为一个有11行和11列的二维数组，也就是上右2图所示。

• 发现图中为0的地方很多，对于我们来说是没用的，浪费空间，所以这里我们利用稀疏数组的特性对它进行压缩处理，经过手动的处理我们可以处理成如下图的成果：

  
  image

我们通过努力最后将11 * 11的棋局压缩成3* 3的，而且只记录有效数字的位置，哈哈哈，是不是很厉害，前辈们的心血我们需要好好领悟其精髓，我们先来熟悉下3*3的二维数组是如何形成的：

• 对于压缩后的3* 3的数组

1. 第一行记录了原数组有11行11列，其中只有2个有效数字
2. 第二行记录了第一个有效数字在原二维数组的位置，这里的第一个有效数字为1，我们不难发现它在原数组的位置是第一行第二列的位置处，值的话就是1，其它的一次类推

简单的文字描述完之后，我们接下来通过代码的方式来实它：

代码实现

• 创建一个11 * 11的原始棋盘

int chessArray1 [][] = new int[11][11];

• 记录我们的棋子的位置，其中0表示没有棋子，1:表示白子 2:蓝子

  chessArray1[1][2] = 1;
  chessArray1[2][3] = 2;

-我们可以打印下我们的棋盘，看看效果，代码如下：

//输出原始数组
    for (int[] row :chessArray1){
        for (int data :row){
            System.out.printf("%d\t",data);
        }
        System.out.println();
    }

-输出结果如图：

棋盘.png

• 接下来，我们来将二维数组转为稀疏数组：
• 首先我们需要遍历原始数组来获取非0数字的个数

int result = 0;
    for (int i=0; i< chessArray1.length;i++){
        for (int j=0; j<chessArray1.length;j++){
            if (chessArray1[i][j] !=0){
                result ++;
            }
        }
        System.out.println("result="+result);
    }

• 接着我们创建一个稀疏数组，代码如下：

int spareArray2 [][] = new int[result+1][3];

• 注意：为啥要这样 new int[result+1][3]定义稀疏数组，道理很简单，在上面一步中，我们通过遍历原始数组来获取非0的数字的个数，所以很明白了。
• 给我们创建的稀疏数组来赋值，代码如下：

//3.1给稀疏数组的第一行赋值
    spareArray2[0][0] =11;
    spareArray2[0][1] =11;
    spareArray2[0][2] = result;

上述代码很简单能看懂，就是给稀疏数组的第一行来赋值的，接着看：

• 遍历源二维数组，并且将非0的值存放到spareArray2中

int count = 0;  //用于记录是第几个非0数据
    for (int i=0; i< chessArray1.length;i++){
        for (int j=0; j<chessArray1.length;j++){
            if (chessArray1[i][j] !=0){
                count ++;
                spareArray2[count][0]=i;
                spareArray2[count][1]=j;
                spareArray2[count][2]=chessArray1[i][j];
            }

        }

    }

代码不难理解，在稀疏数组中记录我们原数组非0的数字的位置的过程，接着看：

• 我们来看输出结果，代码如下：

System.out.println("稀疏数组的格式如下：");
    for (int k=0;k < spareArray2.length; k++){
        System.out.printf("%d\t%d\t%d\t\n",spareArray2[k][0],spareArray2[k][1],spareArray2[k][2]);
    }

• 运行结果如图：

稀疏数组运行结果图.png

就这样我们将原始数组转为稀疏数组的过程完成了，我们接下来看看逆序的过程怎么样的，具体思路如：

• 先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组，代码如下：

int spareArray3 [][] = new int[spareArray2[0][0]][spareArray2[0][1]];

上述这段代码将会读取到的是11行和11列的大小的棋盘

• 读取稀疏数组（第二行开始遍历）后几行数据并赋值给原来的二维数组

  for (int i=1; i <spareArray2.length; i++){
        spareArray3[spareArray2[i][0]][spareArray2[i][1]] = spareArray2[i][2];
    }

• 输出我们可以看看效果，代码如下：

//遍历输出二维数组
    System.out.println();
    System.out.println("恢复后的二维数组的格式为：");
    for (int[] row :spareArray3){
        for (int data :row){

            System.out.printf("%d\t",data);
        }
        System.out.println();
    }

• 效果如图所示：

恢复后的二维数组.png

那么关于稀疏数组简单的学习总结就到这里，记住一点，不管怎么变，稀疏数组的列是唯一的，大小为3