当前位置：首页 > news >正文

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

news 2025/7/8 13:37:48

前言

此文以整型元素的二维数组为例，阐述稀疏数组的思想。
其他类型或许有更适合压缩算法或者其他结构的稀疏数组，此文暂不扩展。

稀疏数组的定义

在一个二维数据数组里，由于大量的元素的值为同一个值，比如 0或者其他已知的默认值，在处理此类数据的数据的时候，为了某种目的(如节省存储空间)而将 0 值或默认剔除方式，使用一个新数组来组织的剩余数据（此文称为存储有效数据，简称有效数），此时将该新数组称为稀疏数组。

简而言之，存储原二维数组中有效数据信息的数组称为稀疏数组。

如下图中的 0 值是最多的元素，可以将 0 值视为要剔除储存的值，此文称为剔除数。
在这里插入图片描述

此处是压缩思想在数组上的应用，稀疏数组一般用于数据的压缩存储，已达到节省空间的目的。

稀疏数组的结构

二维数据的元素是数值

稀疏数据一般为 N*3的矩阵，N 为非剔除数据的个数，行列式的第一行描述元素的结构信息，如行列数，有效数的个数；其他行描述有效数的具体信息，如所在原数组中的位置。

第一列	第二列	第三列
行号	列号	值

第1行，第1列为原始数据的行数
第1行，第2列为原始数据的列数
第1行，第3列为原始数据的有效数的个数 n ，这个决定了稀疏数组的行数N( N= n+1)

第1行（原数组结构信息）	18（原数组的行数）	18（原数组的列数）	68（原数组中有效数的个数）
第2行（原数组中元素的信息）	0（值所在的行）	0（值所在的列）	7（值为 7）

二维数据的元素是字符

稀疏数据一般为 N*3的矩阵，N 为非剔除数据的个数

第1行，第1列为原始数据的行数
第1行，第2列为原始数据的列数
第1行，第3列为原始数据的有效数的个数 n ，这个决定了稀疏数组的行数N( N= n+1)

稀疏数组的应用场景

数据元素中存在相同值较多且需要存储的情况。
网络数据传输的时候，可以根据传输的数据结构，采用稀疏数据的思想

总之，就是可以压缩存储或者压缩传输的时候，都可以考虑此稀疏思想。

案例

该案例演示了一个二维数组（业务数组）和与其匹配的稀疏数组（存储数组），仅为演示二者相互转换，未考虑转换中涉及到的算法优化，仅仅展示存储优化的设计思想。

原始数组大小为：18*18=324
稀疏数组大小为：68*3=204

转换后节省了 (324-204)/324*100%=37%的空间

package com.jj;import org.junit.jupiter.api.Test;public class TestAlgArray {@Testpublic void test() {int countRow = 18;int countCol = 18;int[][] arr = new int[countRow][countCol];for (int i = 0; i < countCol; i++) {arr[0][i] = 8;arr[7][i] = 5;arr[i][0] = 7;arr[i][7] = 3;}//输出int valueCount = 0;for (int i = 0; i < countCol; i++) {for (int j = 0; j < countCol; j++) {System.out.print(arr[i][j] + " ");if (arr[i][j] != 0) {valueCount++;}}System.out.println();}System.out.println("valueCount:" + valueCount);//生成一个稀疏数组int[][] saveData = new int[valueCount + 1][3];saveData[0][0] = countRow;saveData[0][1] = countCol;saveData[0][2] = valueCount;int index = 1;for (int i = 0; i < countCol; i++) {for (int j = 0; j < countCol; j++) {if (arr[i][j] != 0) {saveData[index][0] = i;saveData[index][1] = j;saveData[index][2] = arr[i][j];index++;}}}//输出 saveDatafor (int i = 0; i < saveData.length; i++) {for (int j = 0; j < saveData[i].length; j++) {System.out.print(saveData[i][j] + " ");}System.out.println();}//恢复业务数组int[][] newArr = new int[saveData[0][0]][saveData[0][1]];for (int i = 1; i < saveData.length; i++) {newArr[saveData[i][0]][saveData[i][1]] = saveData[i][2];}//输出业务数组for (int i = 0; i < newArr.length; i++) {for (int j = 0; j < newArr[i].length; j++) {
//                System.out.print(newArr[i][j] + " ");if (newArr[i][j] == 0) {System.out.print(" ");} else {System.out.print(newArr[i][j] + " ");}}System.out.println();}}
}

原始数组（业务数据）:18x18的矩阵

7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 5 5 5 5 5 5 3 5 5 5 5 5 5 5 5 5 5 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0

稀疏数组（存储数据）：68x3 的矩阵

数据恢复

7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 5 5 5 5 5 5 3 5 5 5 5 5 5 5 5 5 5 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0

查看全文

http://www.lryc.cn/news/505783.html