数据结构与算法-稀疏数组

数据结构与算法之稀疏数组

首先先介绍一下线性结构与非线性结构

• 线性结构

1. 线性结构是比较常用的数据结构，特点就是数据元素是一对一的关系。
2. 线性结构有两种不同的存储结构，即顺序存储结构（数组）和链式存储结构（链表）。顺序存储的线性表称为顺序表，顺序表中存储的元素是连续的。
3. 链式存储的线性表称为链表，链表中存储的元素不一定是连续的，元素节点中存放数据以及相邻元素的地址信息。
4. 线性结构常见的有：数组，队列，链表和栈。

• 非线性结构

1. 非线性结构常见的有：二维数组，多维数组，广义表，树结构，图结构。

稀疏数组

言归正传，下面正式介绍稀疏数组

基本介绍

当一个数组中大部分元素是0，或者为同一个值的数组时，可以用稀疏数组来保存该数组。
简言之就是将一个大部分都是同一个值的二维数组进行压缩。

二维数组转稀疏数组的处理方法

1. 首先遍历二维数组，找到多少行，多少列，多少个不同的值，这里计作sum
2. 声明一个二维数组，比如int类型的int[sum+1][3] 的数组
3. 第一行分别存放，原数组的行数，列数，不同数
4. 第二行以后面分别存放，原数组不同值所在的位置，行数，列数，本身值

稀疏数组转二维数组的处理方法

1. 先读取到稀疏数组的第一行，根据第一行，创建二维数组。
2. 从第二行开始遍历稀疏数组，获取到位置与值，然后赋值给刚才创建的二维数组。

示例

二维数组的样子
0 0 0 2 0 5 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 4 0 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
转为稀疏数组的样子
6 7 8
0 3 2
0 5 5
1 1 1
3 1 4
4 5 1
数据量从 $6 \times 7 = 42$6×7=42 变为了 $3 \times 6 = 18$3×6=18，数据量缩小了

代码示例

//二维转稀缺
int[][] arr = {{0,0,1,0},{0,1,0,0},{0,0,0,0},{1,0,0,0}};
int sum = 0;
for (int[] ints : arr) {
    for (int anInt : ints) {
        if(anInt != 0){
            sum++;
        }
    }
}
int[][] sparseMatrix = new int[sum+1][3];
sparseMatrix[0][0] = arr.length;
sparseMatrix[0][1] = arr[0].length;
sparseMatrix[0][2] = sum;
int sparseMatrixIndex = 1;
for (int i = 0; i < arr.length; i++) {
    int[] ints = arr[i];
    for (int i1 = 0; i1 < ints.length; i1++) {
        int anInt = ints[i1];
        if(anInt != 0){
            sparseMatrix[sparseMatrixIndex][0] = i;
            sparseMatrix[sparseMatrixIndex][1] = i1;
            sparseMatrix[sparseMatrixIndex][2] = anInt;
            sparseMatrixIndex++;
        }
    }
}
for (int[] matrix : sparseMatrix) {
    System.out.println(Arrays.toString(matrix));
}
ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("d://map.data"));
objectOutputStream.writeObject(sparseMatrix);
objectOutputStream.flush();
objectOutputStream.close();
System.out.println("-----------------------------------");
ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("d://map.data"));
int[][] mapData = (int[][]) objectInputStream.readObject();
objectInputStream.close();
//稀缺转二维
int[][] arr2 = new int[mapData[0][0]][mapData[0][1]];
for (int i = 1; i < mapData.length; i++) {
    arr2[mapData[i][0]][mapData[i][1]] = mapData[i][2];
}
for (int[] ints : arr2) {
    System.out.println(Arrays.toString(ints));
}

上面的例子，展示了将二维数组转化为稀疏数组并序列化到磁盘中，然后从磁盘中读取数据，恢复数据的整个流程。