数据结构与算法之java语言实现(一):稀疏数组

一、概念&引入

什么是稀疏数组?

稀疏数组是面对一个二维数组中有众多重复元素的情况下,为了节省磁盘空间,将此二维数组转化为更加节省空间的一种数组,我们叫他稀疏数组。

  只是听概念或许会看不明白,我们来用图来演示一下:

数据结构与算法之java语言实现(一):稀疏数组

如图模拟为一个五子棋棋盘,其中1代表黑子,2代表白子(蓝子),我们在将其存入磁盘中,如果只是单纯的用文件io的方式将此二维数组存入磁盘,必然会造成磁盘空间的大大浪费,这时候就需要我们的稀疏数组出场了,咱们先看一下他是什么样子:

 行(row)列(col)值(value)
[0]11112
[1]121
[2]232

我们看到了一个三行两列的二维数组,首先我们看第一行,第一行的第一列(row)代表原数组有多少行,第一列的第二行(row)代表原数组有多少列,第一行第三列则代表原数组总共有多少个数据,在这个具体的例子里面,原数组是11*11,有两个值非零的值,所以第一列第三行的value值为2。

刚刚讲了第一行存储了什么东西,我们可以简单概括一下,第一行存储了原数组的整体信息,保留行,列,以及有多少个非零数值,下面我们来分析第二行。第一行存储了整体的结构,下面应当就是具体的数值,我们或许可以大致根据表格上面的文字可以猜到,第一行是存储具体的某个数据的行,第二列用于存储某个具体数值的列,第三列则用于存储具体的数值,例如:我们从上往下找发现第2行第3列为第一个非零的数值,我们这时候就可以将其存入稀疏数组中,由于Java中数组的元素存储是从零开始,所以我们第二行第三列的数据存储到具体的数组中是1,2,1,分别代表行,列,值。第三行同理,你也可以自己思考一下如何填入数据。

tips:需要强调一点:我们在填入数据的时候应当是有个count来进行计数,计数完了之后将其存入第一行的value中,我们通过value的值来维护数组的使用,如果有删除或者插入操作,我们对value的值进行修改,从而完成对数据的读取。

二、代码实现

public  static final int sparseRow = 3;public static void main(String[] args) {    int[][] oriArray = {            {0,0,0,0},            {0,1,0,0},            {0,0,1,0},            {2,0,0,0},            {0,0,0,2}                };//静态来创建    int count = 0;
for(int[] arr : oriArray) {        for(int i :arr) {            System.out.print(i+" ");            if(i != 0) {                count ++;            }        }        System.out.println("");    }        System.out.println("********************");        //init sparse     int[][] sparse = new int[count+1][sparseRow];    //init the first row     sparse[0][0] = oriArray.length;    sparse[0][1] = oriArray[0].length;    sparse[0][2] = count;    System.out.println("count:"+count);        //通过value进行赋值,value就相当于稀疏数组的行(row)    int value = 0;    for(int m=0;m<oriArray.length;m++) {        for(int n=0;n<oriArray[m].length;n++) {            if(oriArray[m][n]!=0) {                sparse[++value][0] = m;                sparse[value][1] = n;                sparse[value][2] = oriArray[m][n];            }        }    }        //查看稀疏数组    System.out.println("sparse: ");    for(int[] row:sparse) {        for(int col:row) {            System.out.print(col+" ");        }        System.out.println(" ");

相关推荐