稀疏数组的实现

女爷i 2024-03-09 06:41 107阅读 0赞

## 文章目录 ##

**目录**

文章目录

前言

一 什么是稀疏数组?

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

三 稀疏数组的实现

总结

--------------------

## 前言 ##

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

--------------------

## 一 什么是稀疏数组? ##

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

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

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

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

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

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

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

图解:

![465faa0af36f464daa90c09eadd0945a.png][]

![d31b0ef4347a49deb48ff6a51be34af3.png][]

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

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

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

## 三 稀疏数组的实现 ##

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

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();
>     }

看着是不是挺简单的,我也这么觉得![aebe91237a024764b637258d079672e2.jpeg][]

--------------------

## 总结 ##

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

[465faa0af36f464daa90c09eadd0945a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/09/b77af6f2125b43b3bf80daed84546a8c.png
[d31b0ef4347a49deb48ff6a51be34af3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/09/f6bad00f860e4e698673785df9bc398f.png
[aebe91237a024764b637258d079672e2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/09/b6b1a7fc58cf46ff94a24eb2af685d13.png