1. 全栈程序员必看首页

数组 – 稀疏数组

全栈程序员-用户IM • • 未分类

一，稀疏数组1.定义稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组形如：00000000000001000000000000200000000000000…

大家好，又见面了，我是你们的朋友全栈君。

文章目录

一，稀疏数组

1.定义

稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组

形如：

              0 0 0 0 0 0 0 0 0 0 0
              0 0 1 0 0 0 0 0 0 0 0
              0 0 0 0 2 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0 0 0 0

其稀疏数组形式：

              11 11 2
              1  2  1
              2  4  2

2.存储

刚说到稀疏数组是一种压缩后的数组，为什么要进行压缩存储呢？

  • 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少

  • 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率

3.存储方式

1.普通存储

第一行存储原始数据总行数，总列数，总的非0数据个数

接下来每一行都存储非0数所在行，所在列，和具体值

形如：

    rows cols n
    r1   c1   val1
    r2   c2   val2
    .    .     .
    .    .     .
    rn   cn   valn

eg :

              11 11 2
              1  2  1
              2  4  2

2.链式存储

以这个为例：

        0 0 0 0 
        0 1 0 0
        0 0 2 0
        0 0 3 0

a.普通链式存储

# 一，稀疏数组

b.行式链式存储

在这里插入图片描述

c.十字链式存储

在这里插入图片描述

4.代码实现

/** * @Description: 稀疏数组 ---> 数组中有很多无效数据，压缩数组 * @Author: Kevin * @CreateDate: 2019/7/2 22:39 * @UpdateUser: Kevin * @UpdateDate: 2019/7/2 22:39 * @UpdateRemark: 修改内容 * @Version: 1.0 */
public class SparseArray { 

/** * <p> * 稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO过程中提高效率等等。 * * <p> * 为什么要进行压缩？ * - 由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少， * - 且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。 * </p> * * </p> * @param args */
public static void main(String[] args) { 

/** * 初始化二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
//初始化原数组
int[][] array = new int[11][11];
array[1][2] = 1;
array[2][4] = 2;
for(int[] row : array){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
System.out.println("---------> 二维数组转稀疏数组");
/** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
//得到非0数据数
int sum = 0;
for (int i = 0;i<11;i++){ 

for(int j = 0;j<11;j++){ 

if(array[i][j] != 0){ 

sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3];
//给稀疏数组赋值
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//将非0的数放入稀疏数组
//count：标识第几个非0数
int count = 0;
for (int i = 0;i<11;i++){ 

for(int j = 0;j<11;j++){ 

if(array[i][j] != 0){ 

count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
}
}
}
//遍历稀疏数组
for(int i = 0;i<sparseArray.length;i++){ 

System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
}
System.out.println("----------->稀疏数组转回原始数组");
/** * 恢复的二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){ 

oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//遍历刚转回的原始数组
for(int[] row : oldArray){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
}
}

3.将稀疏数组存到此磁盘中

我们可以使用java的IO流将稀疏数组存放到磁盘中，原数组和稀疏数组比较，肯定是稀疏数组体积更小，占用空间更小

        /** * 将稀疏数组存入磁盘（文件） * */
public static void sparseArrayToIo(int[][] sparseArray) throws Exception { 

File file = new File("sparseArray.txt");
if(!file.exists()){ 

file.createNewFile();
}
FileWriter writer = new FileWriter(file);
for(int i =0; i < sparseArray.length; i++) { 

for(int j = 0; j < 3; j++) { 

writer.write(sparseArray[i][j]);
}
}
writer.flush();
writer.close();
}

4.从磁盘中读取稀疏数组

在这里有个缺陷就是我不能动态的知道稀疏数组一共有几行，所以我选择传参的方式，这样其实是不太友好的

        /** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
public static int[][] sparseArrayFromIo(int lineNums) throws Exception { 

FileReader reader = new FileReader("sparseArray.txt");
int getNum = 0;
int[][] sparseArray = new int[lineNums][3];
for(int i = 0;i < lineNums;i++) { 

for (int j = 0; j < 3; j++) { 

getNum = reader.read();
sparseArray[i][j] = getNum;
}
}
return sparseArray;
}

恢复原数组

            System.out.println("----------->稀疏数组转回原始数组");
//读取磁盘中的稀疏数组
try { 

int[][] sparseArrayFromIo = sparseArrayFromIo(3);
int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){ 

newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
}
//遍历刚转回的原始数组
for(int[] row : newOldArray){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
} catch (Exception e) { 

e.printStackTrace();
}

5.完整代码

public class SparseArray { 

/** * <p> * 稀疏数组可以简单的看作为是压缩，在开发中也会使用到。比如将数据序列化到磁盘上，减少数据量，在IO过程中提高效率等等。 * * <h> * 为什么要进行压缩？ * - 由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少， * - 且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。 * </h> * * </p> * @param args */
public static void main(String[] args) { 

/** * 初始化二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
//初始化原数组
int[][] array = new int[11][11];
array[1][2] = 1;
array[2][4] = 2;
for(int[] row : array){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
System.out.println("---------> 二维数组转稀疏数组");
/** * 稀疏数组 * <p> * 11 11 2 * 1 2 1 * 2 4 2 * </p> */
//得到非0数据数
int sum = 0;
for (int i = 0;i<11;i++){ 

for(int j = 0;j<11;j++){ 

if(array[i][j] != 0){ 

sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum+1][3];
//给稀疏数组赋值
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//将非0的数放入稀疏数组
//count：标识第几个非0数
int count = 0;
for (int i = 0;i<11;i++){ 

for(int j = 0;j<11;j++){ 

if(array[i][j] != 0){ 

count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
}
}
}
//遍历稀疏数组
for(int i = 0;i<sparseArray.length;i++){ 

System.out.printf("%d%d%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
}
try { 

//将稀疏数组写入文件
sparseArrayToIo(sparseArray);
} catch (Exception e) { 

e.printStackTrace();
}
System.out.println("----------->稀疏数组转回原始数组");
/** * 恢复的二维数组 * <p> * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 0 * 0 0 0 0 2 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 0 * </p> */
int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){ 

oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//遍历刚转回的原始数组
for(int[] row : oldArray){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
System.out.println("----------->稀疏数组转回原始数组");
//读取磁盘中的稀疏数组
try { 

int[][] sparseArrayFromIo = sparseArrayFromIo(3);
int[][] newOldArray = new int[sparseArrayFromIo[0][0]][sparseArrayFromIo[0][1]];
//将原来非0的数填充回去
for(int i = 1;i<=count;i++){ 

newOldArray[sparseArrayFromIo[i][0]][sparseArrayFromIo[i][1]] = sparseArrayFromIo[i][2];
}
//遍历刚转回的原始数组
for(int[] row : newOldArray){ 

for(int item : row){ 

System.out.printf("%d\t",item);
}
}
} catch (Exception e) { 

e.printStackTrace();
}
}
/** * 将稀疏数组存入磁盘（文件） * */
public static void sparseArrayToIo(int[][] sparseArray) throws Exception { 

File file = new File("sparseArray.txt");
if(!file.exists()){ 

file.createNewFile();
}
FileWriter writer = new FileWriter(file);
for(int i =0; i < sparseArray.length; i++) { 

for(int j = 0; j < 3; j++) { 

writer.write(sparseArray[i][j]);
}
}
writer.flush();
}
/** * 读文件获取稀疏数组(获取指定行数的稀疏数组)【不足】 * @return */
public static int[][] sparseArrayFromIo(int lineNums) throws Exception { 

FileReader reader = new FileReader("sparseArray.txt");
int getNum = 0;
int[][] sparseArray = new int[lineNums][3];
for(int i = 0;i < lineNums;i++) { 

for (int j = 0; j < 3; j++) { 

getNum = reader.read();
sparseArray[i][j] = getNum;
}
}
return sparseArray;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/125468.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号