欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2-数据结构稀疏数组存储方式和代码实现

程序员文章站 2022-06-06 20:39:03
...

视频课程: 尚硅谷韩顺平Java数据结构与算法

稀疏数组(sparsearray)


稀疏数组问题引入

五子棋程序中,存盘退出和继续上盘的功能

2-数据结构稀疏数组存储方式和代码实现

存在问题:将棋盘映射成一个二维数组后,数组中的许多值是0;数组中记录了许多没有意义的数据。

稀疏数组基本介绍

当一个数组中的大部分元素为0,或者为同一个值的数组,可以使用稀疏数组来保存该数组
稀疏数组的列固定为3列(行,列,值)

稀疏数组的存储方法

  1. 稀疏数组第一行记录原数组一共有几行几列,有多少个不同的值。
  2. 稀疏数组其他行记录原数组中有意义值的行列和值的大小,
稀疏数组图解

2-数据结构稀疏数组存储方式和代码实现

二维数组与稀疏数组的转换

  • 二维数组转稀疏数组步骤

    1. 遍历二维数组获取二维数组中有效值的个数count

    2. 创建稀疏数组 根据count;sparseArr int[count+1][3];

    3. 将二维数组中的有效值存储到稀疏数组中

  • 稀疏数组转二维数组

    1. 读取稀疏数组的第一行,根据第一行的数据,创建二维数组
    2. 读取稀疏数组的后几行数据,赋值给二维数组
  • 代码实现

//将二维数组转为稀疏数组
public  static int[][] toSparseArr(int[][] arr) {
        int count = 0;
        //1-遍历二维数组,获取二维数组中有效数据的个数
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0){
                    count++;
                }
            }
        }
        //2-根据count创建稀疏数组(稀疏数组恒定3列)
        //sparseArr定义为count+1行,因为稀疏数组第一行要存储二维数组行列信息
        int[][] sparseArr = new int[count+1][3];

        //3-将二维数组的有效值赋给稀疏数组
        //3-1-稀疏数组第一行
        sparseArr[0][0] = arr.length;  //存储二维数组的行数
        sparseArr[0][1] = arr[0].length; //存储二维数组的列数
        sparseArr[0][2] = count;
        //3-2-稀疏数组的其它行
        int row = 0; //用于定位稀疏数组的当前行
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0){
                    row++;
                    sparseArr[row][0] = i;
                    sparseArr[row][1] = j;
                    sparseArr[row][2] = arr[i][j];
                }
            }
        }
        return sparseArr;
    }
//将稀疏数组还原回二维数组
public static int[][] toArray(int[][] sparseArr) {
        //1-根据稀疏数组第一行创建二维数组
        int row = sparseArr[0][0];
        int col = sparseArr[0][1];
        int count = sparseArr[0][2];

        int[][] arr = new int[row][col];
        //2-遍历稀疏数组(从下标1开始) 给二维数组赋值
        for (int i = 1; i < sparseArr.length; i++) {
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }