稀疏数组的实现

文章目录

目录

文章目录

前言

一 什么是稀疏数组? 

二 稀疏数组怎么存储数据?

三 稀疏数组的实现

总结

---

前言

大家好,好久不见了,这篇博客是数据结构的第一篇文章,望大家多多支持!

---

一 什么是稀疏数组? 

稀疏数组（Sparse Array）是一种数据结构，用于表示大部分元素值为默认值的数组。在稀疏数组中，只有非默认值的元素被存储，而默认值的元素则被忽略。这样可以节省存储空间，特别适用于稀疏矩阵等大规模数据结构。

稀疏数组通常由三个部分组成：

1. 原始数组的大小：记录原始数组的行数和列数。
2. 非默认值元素的个数：记录非默认值元素的个数。
3. 非默认值元素的位置和值：以二维数组的形式存储非默认值元素的位置和值。

通过使用稀疏数组，可以在存储和传输数据时减少所需的空间和时间。

简单来说,就是压缩数据时使用,稀疏数组同样也是一种数据结构

二 稀疏数组怎么存储数据?

稀疏数组通常由三个部分组成：

1. 原始数组的大小：记录原始数组的行数和列数。
2. 非默认值元素的个数：记录非默认值元素的个数。
3. 非默认值元素的位置和值：以二维数组的形式存储非默认值元素的位置和值。

图解:

稀疏数组的第一行记录的不是元素,而是原数组的行数,列数,非零元素个数。

稀疏数组其他行记录的是原数组非零元素的行列和值

解释的话难免有些不清楚,大家看图即可!

三 稀疏数组的实现

接下来带大家一步步的来实现稀疏数组(按上面图示实现)!

1.首先创建一个六行七列的二维数组 int[][] arr

2.给原数组赋值并遍历

3.创建稀疏数组SpareArr[][]

这三个没什么难度,大家觉得行的可以尝试一下下面的三个,代码给出

int[][] arr = new int[6][7];// 创建数组存入数据并初始化arr[0][3] = 22;
arr[0][6] = 15;
arr[1][1] = 11;
arr[1][5] = 17;
arr[2][3] = -6;
arr[3][5] =39 ;
arr[4][0] =91 ;
arr[5][2] =28 ;

//遍历打印并记录非零元素的个数
int sum = 0;
for (int[] ints : arr) {for (int j = 0; j < arr[0].length; j++) {System.out.print(ints[j] + " ");if (ints[j] != 0) {sum += 1;}}System.out.println();
}// 创建稀疏数组
// 稀疏数组的行为元素的个数+1 因为稀疏数组的第一行记录的是总的元素个数,而不是某一个元素的值
int[][] SpareArray = new int[sum+1][3];

4.给稀疏数组赋值

// 稀疏数组的第一行比较特殊,因此我们不借助循环,直接进行赋值。
SpareArray[0][0] = arr.length;// 原数组的行
SpareArray[0][1] = arr[0].length;// 原数组的列
SpareArray[0][2] = sum;// 原数组中元素的个数//遍历原数组,并将数组中的元素存入稀疏数组中
int count = 0;
for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {if(arr[i][j] != 0){// 如果元素不为零,就讲该元素存入稀疏数组中count++;SpareArray[count][0] = i;SpareArray[count][1] = j;SpareArray[count][2] = arr[i][j];}}
}

5.将稀疏数组导入\导出文件

// 创建字符缓冲输出流将稀疏数组保存到文件中
FileOutputStream fos = new FileOutputStream("D:\\系统默认\\桌面\\测试.txt");for (int[] ints : SpareArray) {for (int j = 0; j < SpareArray[0].length; j++) {fos.write(ints[j]);}
}
fos.close();FileInputStream fis = new FileInputStream("D:\\系统默认\\桌面\\测试.txt");
int read1 = fis.read();// 行
int read2 = fis.read();// 列
int read3 = fis.read();// 总个数
count = read3;int[][] newArr = new int[read1][read2];
for (int i = 0; i < count; i++) {read1 = fis.read();read2 = fis.read();read3 = fis.read();newArr[read1][read2] = read3;
}
fis.close();for (int i = 0; i < newArr.length; i++) {for (int j = 0; j < newArr[0].length; j++) {System.out.print(newArr[i][j]+" ");}System.out.println();
}

看着是不是挺简单的,我也这么觉得

---

总结

就到这了,感谢大家观看!