Java数据结构-稀疏数组的实现[用最简单的语言理解最复杂的问题]

前言:

    本系列博客中,主要是对常用的数据结构进行讲解,本篇博客主要讲解的是**稀疏数组,**这是最基础的数据结构之一,抢先预言,下一章(队列的实现)

    依旧是从 **应用场景-->代码思路-->具体做法-->代码实现-->代码分析-->总结**,着手去理解领略神秘的数据结构,做不一样的程序猿.

应用场景:

    在新手程序员学习编程的时候,一定绕不过会创建一个二维数组,去写扫雷等项目,但是,存在一个**问题**,当我们要*保存这个棋盘(二维数组)*,是否会感觉到空间没有被充分利用,导致**占用内存过大**等问题,为了解决这一情况,我们引出了稀疏数组的创建.

    **使用前提**:传统二维数组中存在大量相同的元素,且该元素在传统二维数组中只起占位的作用

稀疏数组的作用:

    在我们引出稀疏数组的概念之前,我们需要了解其作用

• 通过稀疏数组,可以将传统二维数组的状态保存在稀疏数组中,通过存储稀疏数组从而间接的存储传统二维数组,从而减少内存占用
• 稀疏数组的使用与我们传统的压缩文件是一个概念

代码思路:

• 建立一个稀疏数组,稀疏数组的本质是一个二维数组,存储形式如下

indexROWCOLVALUE0数组总行数组总列有效值个数1下标1下标2值2下标1下标2值3下标1下标2值

• 遍历传统二维数组统计有效值个数
• 将读取到的有效值和数组信息,放入稀疏数组指定位置(如上图)
• 遍历传统二维数组,将有效值放入稀疏数组

具体做法(注意为代码分析)

• 遍历二维数组,定义一个变量valueOfSum,用于记录有效元素个数

for (int i = 0; i < tArrays.length; i++) {
            for (int j = 0; j < tArrays[i].length; j++) {
                if(tArrays[i][j] != 0) {
                    valueOfSum++;
                }
            }
        }

注意:Java中的length属性是字符串长度,其他语言可用其他方法去改变

    tArrrays表示原始二维数组

• 创建一个稀疏数组

 var sparseArrays = new int[valueOfSum+1][3];
        sparseArrays[0][0] = tArrays.length;
        sparseArrays[0][1] = tArrays[0].length;
        sparseArrays[0][2] = valueOfSum;

注意:因为稀疏数组的列固定为3.所以列写成3.且稀疏数组的行的多少取决于有多少个有效值,再加上第一行的统计,所以要创建多一行

    第一行记录的是稀疏数组的属性,可参考代码思路中的表格

• 转化为稀疏数组

        int row = 1;
        int col = 0;
        for (int i = 0; i < tArrays.length; i++) {
            for (int j = 0; j < tArrays[i].length; j++) {
                if(tArrays[i][j] != 0) {
                    sparseArrays[row][col++] = i;
                    sparseArrays[row][col++] = j;
                    sparseArrays[row][col] = tArrays[i][j];
                    row++;
                    col=0;
                }
            }
        }

注意:因为第一行是记录已有属性,所以row从第二行开始即下标为1

    通过**遍历原始二维数组**.只要发现是有效值就放进去

• 转化为传统二维数组

        var ttArrays = new int[sparseArrays[0][0]][sparseArrays[0][1]];
        for (int i = 1; i < sparseArrays.length; i++) {
            int j = 0;
            ttArrays[sparseArrays[i][j++]][sparseArrays[i][j++]] = sparseArrays[i][j];
        }
        

注意:因为第一行记录了传统二维数组的属性,所以根据属性创建对应的二维数组

ttArrays[sparseArrays[i][j++]][sparseArrays[i][j++]] = sparseArrays[i][j];

代码目的:根据++后置的原理,先读取到某一行到某一列,再赋予某个值

完整代码实现

var tArrays = new int[11][11];
        tArrays[1][2] = 1;
        tArrays[2][4] = 2;
        // 转稀疏数组
        int valueOfSum = 0;
        for (int i = 0; i < tArrays.length; i++) {
            for (int j = 0; j < tArrays[i].length; j++) {
                if(tArrays[i][j] != 0) {
                    valueOfSum++;
                }
            }
        }
        var sparseArrays = new int[valueOfSum+1][3];
        sparseArrays[0][0] = tArrays.length;
        sparseArrays[0][1] = tArrays[0].length;
        sparseArrays[0][2] = valueOfSum;
        int row = 1;
        int col = 0;
        for (int i = 0; i < tArrays.length; i++) {
            for (int j = 0; j < tArrays[i].length; j++) {
                if(tArrays[i][j] != 0) {
                    sparseArrays[row][col++] = i;
                    sparseArrays[row][col++] = j;
                    sparseArrays[row][col] = tArrays[i][j];
                    row++;
                    col=0;
                }
            }
        }
        //转原始数组
        var ttArrays = new int[sparseArrays[0][0]][sparseArrays[0][1]];
        for (int i = 1; i < sparseArrays.length; i++) {
            int j = 0;
            ttArrays[sparseArrays[i][j++]][sparseArrays[i][j++]] = sparseArrays[i][j];
        }

结论:

    作为数据结构的入门之作,稀疏数组还是比较简单的,总结为从记录传统二维数组属性->写入属性的简单步骤

    相信看到最后的小伙伴都收获颇丰,望给作者一个素质四联(点赞,收藏,关注,评论),我会给大家带来更好的内容的