侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--稀疏数组(java实现)

林贤钦
2020-04-14 / 0 评论 / 9 点赞 / 638 阅读 / 0 字
温馨提示:
本文最后更新于 2020-06-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1、 稀疏数组

稀疏数组就是当数组中大部分的内容值都未被使用(或者为0),在数组中仅有少部分的空间使用,因此造成内存空间的浪费,为了节省内存空间,并不影响数组中原有的内容,我们可以使用稀疏数组去压缩数据

稀疏数组得处理方法是:

  1. 记录二维数组 一共几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的二维数组中,从而缩小程序的规模
    3)第一行保存二维数组的行数、列数、有效值个数
    4)其他行保存二维数组 有效值所在行数、列数以及值

如图:一共有8个值:22,15、 11、 17、 -4 、39、91、 28

原数组大小:6*7,那么在稀疏数组中的第一行存放数组就是这样

所以就有9行3列(在稀疏数组中,列是固定3)

int sparseArray[][] = new int[8 + 1][3];
sparseArray[0][0]=6;//原数组的行
sparseArray[0][1]=7;//原数组的列
sparseArray[0][2]=8;//原数组非0个数

第二行也就原数组的第一个非0数据22的存放就是:

sparseArray[1][0]=0;//原数组第一个非0数组的行下标
sparseArray[1][1]=3;//原数组第一个非0数组的列下标
sparseArray[1][2]=22;//原数组第一个非0数组的值

依次类推,可得到稀疏数组

sparseArray存放方式

如果这么说,还觉得很抽象,举个经典例子--->五子棋

1、需求:编写五子棋程序,有存盘和续上盘功能(保存和取出使用io)

sparseArray五子棋

2、把稀疏数组保存,并且可以恢复成二维数组

3、整体分析:

在五子棋的棋谱中,我们可以看到只有两个非0值,分别在第二行的第三列和第三行的第四列,值分别为1和2。原棋盘大小11*11,即原数组大小。那么我们可以先把原数组给写出来

//创建一个原始数组 11*11 --->原棋盘大小
//0表示,没有棋子  1表示黑子 2表示白子
int chessArray[][] = new int[11][11];
chessArray[1][2] = 1;//第一个值的位置和值
chessArray[2][3] = 2;//第二个值的位置和值

根据稀疏数组的定义,我们可以先把稀疏数组写出来,然后再思考这么转化。需要的数组:有两个值:1 ,2,所以我们可以确定稀疏数组的大小【值的个数+1】【3】

int sparseArray[][] = new int[3][3];

存放数组则为:

sparseArray[0][0]=11;//原数组的行
sparseArray[0][1]=11;//原数组的列
sparseArray[0][2]=2;//原数组非0个数
sparseArray[1][0]=1;//值==原数组第一个的行下标
sparseArray[1][1]=2;//值==原数组第一个的列下标
sparseArray[1][2]=1;//值==原数组第一个的值
sparseArray[2][0]=2;//值==原数组第二个的行下标
sparseArray[2][1]=3;//值==原数组第二个的列下标
sparseArray[2][2]=2;//值==原数组第二个的值

那么我们如何将原数组转化成稀疏数组?

思路:

1、暴力循环遍历原数组获取到原数组中非0的个数sum,
int sum=0;
for (int[] row : chessArray) {//获取每一行
    for(int data : row){//遍历每一行的值
        //判断,如果是非0,那么sum++
        if(data!=0){
            sum++;
        }
    }
}     
2、根据sum,我们可以创建稀疏数组
int sparseArray[][] = new int [sum+1][3];
3、再次遍历原数组,获取原数组的非0值的行下标,列下表,值,一一赋给稀疏数组
int count = 0;//用来记录行下标
for(int i=0;i<chessArray.length;i++){
    for(int m=0;m<chessArray[0].length;m++){
        //还是先判断非0
        if(chessArray[i][m]!=0){
            count++;
            sparseArray[count][0]=i;
            sparseArray[count][1]=m;
            sparseArray[count][2]=chessArray[i][m];
        }
    }
}

这样,我们就获取了一个稀疏数组3x9,对比原来数组11x11显然小很多。

如何将稀疏数组转化成原来的数组?

用上面的例子来,我们获取了一个稀疏数组

int sparseArray[][] = new int [9][3];

那么我们可以得到结果1:该原数组有8个非空值,我们可以遍历稀疏数组。

1、首先先读取稀疏数组的第一行,获取原数组的行,列,值的个数,创建二维数组
//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];
}
9

评论区