数据结构之稀疏数组的实现

数据结构之稀疏数组的实现

一、概述

当我们编写一个二维数组时，可能会存在着许多数据重复的情况，如下图：

这样可能会造成程序的运行缓慢，不够简洁。那么我们是否能有一种方式，将这个数组压缩，使其化简为一个简洁、不冗余的二维数组呢？ 下面就引出我们稀疏数组的概念。

二、概念

下图为原二维数组转换为稀疏数组的样式：

1. 其第一行第一列代表原二维数组的行数
2. 其第一行第二列代表原二维数组的列数
3. 其第一行第三列代表原二维数组的不同元素的个数
4. 第二行与第三行则代表不同元素在原数组中的位置

也是比较好理解的呀~

下面就是实现的思路了

三、思路

将二维数组转化成稀疏数组：

1.首先我们遍历原数组，可以得到原数组中不同数据的个数，我们假设为sum；
2.接下来我们根据sum，就可以相对应的创建一个稀疏数组 Arr int[sum+1][3];
(注：sum+1 是因为我们的稀疏数组第一行存的是原始数组的行、列以及不同数据个数
后面的 3 列 是因为我们仅仅只需要三列数据）
3.将原始二维数组中的有效数据存放到稀疏数组中。

这样我们的第一步就大功告成了~
但是我们转换成稀疏数组后，也要想办法将其转换回来呀！

将稀疏数组转换成二维数组：

1.首先我们读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组。
2.接下来继续读取稀疏数组剩下的几行，然后赋值给原始的二维数组就行。

最后，上代码。详细说明。

四、代码实现

首先

将二维数组转化成稀疏数组：

将稀疏数组转换成二维数组：

五、结语

整体的思路流程我觉得挺清晰的。而且我觉得这个知识点，在未来的开发中也会起到挺大的帮助（尽管我现在还没用到）。能够极大的提高代码的运行效率，以及质量。

做个笔记，自己日后遗忘的时候，也能够翻出来看看~
也希望能够帮助到其他的小伙伴呀~