稀疏数组的实现

文章目录

目录

文章目录

前言

一 什么是稀疏数组? 

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

三 稀疏数组的实现

总结

---

前言

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

---

一 什么是稀疏数组? 

稀疏数组（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();
}

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

---

总结

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