数组 – 稀疏数组

一,稀疏数组1.定义稀疏数组可以看做是普通数组的压缩,但是这里说的普通数组是值无效数据量远大于有效数据量的数组形如:00000000000001000000000000200000000000000…

大家好,又见面了,我是你们的朋友全栈君。

一,稀疏数组

1.定义

稀疏数组可以看做是普通数组的压缩,但是这里说的普通数组是值无效数据量远大于有效数据量的数组

形如:

              0 0 0 0 0 0 0 0 0 0 0
              0 0 1 0 0 0 0 0 0 0 0
              0 0 0 0 2 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0

其稀疏数组形式:

              11 11 2
              1  2  1
              2  4  2

2.存储

刚说到稀疏数组是一种压缩后的数组,为什么要进行压缩存储呢?

  • 原数组中存在大量的无效数据,占据了大量的存储空间,真正有用的数据却少之又少

  • 压缩存储可以节省存储空间以避免资源的不必要的浪费,在数据序列化到磁盘时,压缩存储可以提高IO效率

3.存储方式

1.普通存储

第一行存储原始数据总行数,总列数,总的非0数据个数

接下来每一行都存储非0数所在行,所在列,和具体值

形如:

    rows cols n
    r1   c1   val1
    r2   c2   val2
    .    .     .
    .    .     .
    rn   cn   valn

eg :

              11 11 2
              1  2  1
              2  4  2

2.链式存储

以这个为例:

        0 0 0 0 
        0 1 0 0
        0 0 2 0
        0 0 3 0

a.普通链式存储

# 一,稀疏数组

b.行式链式存储

在这里插入图片描述

c.十字链式存储

在这里插入图片描述

4.代码实现

/** * @Description: 稀疏数组 ---> 数组中有很多无效数据,压缩数组 * @Author: Kevin * @CreateDate: 2019/7/2 22:39 * @UpdateUser: Kevin * @UpdateDate: 2019/7/2 22:39 * @UpdateRemark: 修改内容 * @Version: 1.0 */
public class SparseArray { 
   

    /** * <p> * 稀疏数组可以简单的看作为是压缩,在开发中也会使用到。比如将数据序列化到磁盘上,减少数据量,在IO过程中提高效率等等。 * * <p> * 为什么要进行压缩? * - 由于稀疏矩阵中存在大量的“空”值,占据了大量的存储空间,而真正有用的数据却少之又少, * - 且在计算时浪费资源,所以要进行压缩存储以节省存储空间和计算方便。 * </p> * * </p> * @param args */

    public static void main(String[] args) { 
   

        /** * 初始化二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
        //初始化原数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][4] = 2;
        for(int[] row : array){ 
   
            for(int item : row){ 
   
                System.out.printf("%d\t",item);
            }
        }

        System.out.println("---------> 二维数组转稀疏数组");

        /** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
        //得到非0数据数
        int sum = 0;
        for (int i = 0;i<11;i++){ 
   
            for(int j = 0;j<11;j++){ 
   
                if(array[i][j] != 0){ 
   
                    sum++;
                }
            }
        }
        //创建稀疏数组
        int[][] sparseArray = new int[sum+1][3];
        //给稀疏数组赋值
        sparseArray[0][0] = 11;
        sparseArray[0][1] = 11;
        sparseArray[0][2] = sum;
        //将非0的数放入稀疏数组
        //count:标识第几个非0数
        int count = 0;
        for (int i = 0;i<11;i++){ 
   
            for(int j = 0;j<11;j++){ 
   
                if(array[i][j] != 0){ 
   
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = array[i][j];
                }
            }
        }
        //遍历稀疏数组
        for(int i = 0;i<sparseArray.length;i++){ 
   
            System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
        }

        System.out.println("----------->稀疏数组转回原始数组");

        /** * 恢复的二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */

        int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
        //将原来非0的数填充回去
        for(int i = 1;i<=count;i++){ 
   
          oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        //遍历刚转回的原始数组
        for(int[] row : oldArray){ 
   
            for(int item : row){ 
   
                System.out.printf("%d\t",item);
            }
        }
    }
}

3.将稀疏数组存到此磁盘中

我们可以使用java的IO流将稀疏数组存放到磁盘中,原数组和稀疏数组比较,肯定是稀疏数组体积更小,占用空间更小

        /** * 将稀疏数组存入磁盘(文件) * */
        public static void sparseArrayToIo(int[][] sparseArray) throws Exception { 
   
            File file = new File("sparseArray.txt");
            if(!file.exists()){ 
   
                file.createNewFile();
            }
            FileWriter writer = new FileWriter(file);
            for(int i =0; i < sparseArray.length; i++) { 
   
                for(int j = 0; j < 3; j++) { 
   
                    writer.write(sparseArray[i][j]);
                }
            }
            writer.flush();
            writer.close();
        }

4.从磁盘中读取稀疏数组

在这里有个缺陷就是我不能动态的知道稀疏数组一共有几行,所以我选择传参的方式,这样其实是不太友好的

        /** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
        public static int[][] sparseArrayFromIo(int lineNums) throws Exception { 
   

            FileReader reader = new FileReader("sparseArray.txt");
            int getNum = 0;
            int[][] sparseArray = new int[lineNums][3];
            for(int i = 0;i < lineNums;i++) { 
   
                for (int j = 0; j < 3; j++) { 
   
                    getNum = reader.read();
                    sparseArray[i][j] = getNum;
                }
            }
            return sparseArray;
        }

恢复原数组

            System.out.println("----------->稀疏数组转回原始数组");
            //读取磁盘中的稀疏数组
            try { 
   
                int[][] sparseArrayFromIo = sparseArrayFromIo(3);
                int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
                //将原来非0的数填充回去
                for(int i = 1;i<=count;i++){ 
   
                    newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
                }
                //遍历刚转回的原始数组
                for(int[] row : newOldArray){ 
   
                    for(int item : row){ 
   
                        System.out.printf("%d\t",item);
                    }
                }
            } catch (Exception e) { 
   
                e.printStackTrace();
            }

5.完整代码

public class SparseArray { 
   

        /** * <p> * 稀疏数组可以简单的看作为是压缩,在开发中也会使用到。比如将数据序列化到磁盘上,减少数据量,在IO过程中提高效率等等。 * * <h> * 为什么要进行压缩? * - 由于稀疏矩阵中存在大量的“空”值,占据了大量的存储空间,而真正有用的数据却少之又少, * - 且在计算时浪费资源,所以要进行压缩存储以节省存储空间和计算方便。 * </h> * * </p> * @param args */

        public static void main(String[] args) { 
   

            /** * 初始化二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
            //初始化原数组
            int[][] array = new int[11][11];
            array[1][2] = 1;
            array[2][4] = 2;
            for(int[] row : array){ 
   
                for(int item : row){ 
   
                    System.out.printf("%d\t",item);
                }
            }

            System.out.println("---------> 二维数组转稀疏数组");

            /** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
            //得到非0数据数
            int sum = 0;
            for (int i = 0;i<11;i++){ 
   
                for(int j = 0;j<11;j++){ 
   
                    if(array[i][j] != 0){ 
   
                        sum++;
                    }
                }
            }
            //创建稀疏数组
            int[][] sparseArray = new int[sum+1][3];
            //给稀疏数组赋值
            sparseArray[0][0] = 11;
            sparseArray[0][1] = 11;
            sparseArray[0][2] = sum;
            //将非0的数放入稀疏数组
            //count:标识第几个非0数
            int count = 0;
            for (int i = 0;i<11;i++){ 
   
                for(int j = 0;j<11;j++){ 
   
                    if(array[i][j] != 0){ 
   
                        count++;
                        sparseArray[count][0] = i;
                        sparseArray[count][1] = j;
                        sparseArray[count][2] = array[i][j];
                    }
                }
            }
            //遍历稀疏数组
            for(int i = 0;i<sparseArray.length;i++){ 
   
                System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
            }
            try { 
   
                //将稀疏数组写入文件
                sparseArrayToIo(sparseArray);
            } catch (Exception e) { 
   
                e.printStackTrace();
            }
            System.out.println("----------->稀疏数组转回原始数组");
            /** * 恢复的二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
            int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
            //将原来非0的数填充回去
            for(int i = 1;i<=count;i++){ 
   
              oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
            }
            //遍历刚转回的原始数组
            for(int[] row : oldArray){ 
   
                for(int item : row){ 
   
                    System.out.printf("%d\t",item);
                }
            }
            System.out.println("----------->稀疏数组转回原始数组");
            //读取磁盘中的稀疏数组
            try { 
   
                int[][] sparseArrayFromIo = sparseArrayFromIo(3);
                int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
                //将原来非0的数填充回去
                for(int i = 1;i<=count;i++){ 
   
                    newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
                }
                //遍历刚转回的原始数组
                for(int[] row : newOldArray){ 
   
                    for(int item : row){ 
   
                        System.out.printf("%d\t",item);
                    }
                }
            } catch (Exception e) { 
   
                e.printStackTrace();
            }
        }

        /** * 将稀疏数组存入磁盘(文件) * */
        public static void sparseArrayToIo(int[][] sparseArray) throws Exception { 
   
            File file = new File("sparseArray.txt");
            if(!file.exists()){ 
   
                file.createNewFile();
            }
            FileWriter writer = new FileWriter(file);
            for(int i =0; i < sparseArray.length; i++) { 
   
                for(int j = 0; j < 3; j++) { 
   
                    writer.write(sparseArray[i][j]);
                }
            }
            writer.flush();
        }

        /** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
        public static int[][] sparseArrayFromIo(int lineNums) throws Exception { 
   

            FileReader reader = new FileReader("sparseArray.txt");
            int getNum = 0;
            int[][] sparseArray = new int[lineNums][3];
            for(int i = 0;i < lineNums;i++) { 
   
                for (int j = 0; j < 3; j++) { 
   
                    getNum = reader.read();
                    sparseArray[i][j] = getNum;
                }
            }
            return sparseArray;
        }

}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/125468.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • [转] 场景管理

    [转] 场景管理

  • 云服务器和虚拟主机有哪些区别

    云服务器和虚拟主机有哪些区别虚机主机就是利用技术把一台服务器分成多个“虚拟”的主机,这些划分出来的主机具有独立的域名,和具有完整的Internet服务器功能,划分出来的虚拟主机共享服务器的宽带和IP。虚机主机之所以使用率较高,是因为相对于购买服务器和租用专线的费用,虚机主机价格便宜,操作简单。但虚机主机没有独立的操作系统,只能通过提供的控制面板操作。虚拟主机由于是共享主机,稳定性较差,访问速度有限。云服务器又叫云主

  • js面试笔试–prototype详解

    js面试笔试–prototype详解对JavaScript中原型模式的理解一:什么是原型对象?有什么优点?   简单的来说,无论何时,我们创建的每一个函数都有一个prototype属性,这个属性是一个指针,指向一个对象,这个对象包含了通过调用该构造函数所创建的对象共享的属性和方法。其实我们平常的叫法就是指:prototype就是通过该构造函数创建的某个实例的原型对象,但是其实prototype是每个构造函数的属性而已,只能说…

  • jav_video_ASP 第三方控件

    jav_video_ASP 第三方控件[控件界面][控件介绍]名称:DotNetTextBoxV2.0WebControl免费无限制版类型:ASP.NET2.0增强型TextBox控件作者:小宝.NET2.0主页:http://www.aspxcn.com.cn演示页面:http://www.aspxcn.cn.NET2.0技术讨论QQ群:12462711、15532207功能:1.功能强大的…

  • Hsql函数下_sql nvl函数

    Hsql函数下_sql nvl函数Hsql函数.下(窗口函数、分析函数、增强group)参考链接:https://blog.csdn.net/scgaliguodong123_/article/details/601353851.窗口函数与分析函数应用场景:(1)用于分区排序(2)动态GroupBy(3)TopN(4)累计计算(5)层次查询1.1、窗口函数FIRST_VALUE:取分组内排序后,…

  • linux的vim显示行号(vim添加行号)

    打开vim的配置文件/etc/vim/vimrcsudovim/etc/vim/vimrc然后找到#setnumber,把注释取消就行了如果没有,就自己加一行转载于:https://www.cnblogs.com/zdj8023/p/10837480.html…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号