稀疏矩阵（什么是稀疏矩阵）

本篇文章给大家谈谈稀疏矩阵，以及什么是稀疏矩阵对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

稀疏矩阵

什么是稀疏矩阵

矩阵中有很多零，其中非零元素只是占了一小部分，大部分都是零，这种就叫稀疏矩阵。

稀疏矩阵概念没有严格的界定，0 的个数/在矩阵元素总数中占的百分比没有严格的规定，凭感觉的概念。

在严版数据结构中的定义，这里的零 可以是常数c 。

c是不是零 ，就是概念上的分歧。

三元组表示法

第一行（下标0）：一般不存储任何一个元素

第一个代表非0元素个数，第二个代表行数，第 *** 列数

从下标1开始存储矩阵中的元素，一般按照行优先存储。

当然可以按照列优先，或者存储任意位置 也行，把所有元素存进去即可。

邻接表表示法

定义一个一维数组，数组的下标 对应于 要存储矩阵的行标

数组的元素 是一些指针，每个指针都指向一条链表，链表中的结点就保存了矩阵中的非零元素信息。

其中第一个信息 是非0元素的值，

第二个信息 是非0元素所在的列标

每条链表所在的行标保存了 这条链表中所有元素的行标信息。

每条链表中的结点保存了元素的值和列标信息。

每个十字链表都有一个 头节点，它一共有五个域

第一行：第一个域：行数，第二个域：列数，第三个域：非零元素个数

第二行：两个域引出两个指针，指向两个数组

第四个域：列数组，第五个域：行数组。

两个数组内存储了一些指针，指向表内的非零元素。

给表中的非零元素都申请一个结点

表元素结点类型 和表的头节点类型 是一样的，保存的信息不一样。

元素结点

第一个分量存的：行号

第二个分量存的：列号

第三个分量存的：元素值

第四、五个分量存的：指针

十字链表构造 和 二维数组 是类似的。

只不过是只给非零元素分配存储空间。

行方向上 结点之间的指针是从结点第五个域引出来的。

列方向上 结点之间的指针是从结点第四个域引出来的。

什么是稀疏矩阵

你好，定义如下

非零元素占全部元素的百分比很小(例如5%以下)的矩阵。有的矩阵非零元素占全部元素的百分比较大（例如近50％），但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。

数据结构之稀疏矩阵

用户产品关系矩阵，比如某个公司的所有用户对自己喜爱的产品有一个评分，但是因为该公司用户和产品种类数量繁多，就有可能存在用户通过产品产生的关联性不是很大的情况（没有共同评价过的产品），就产生了稀疏矩阵。

百科的定义：在 矩阵 中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

一般矩阵采用二维数组存储，但是由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少，且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。

一般采用三元组线性表表示，可以采用顺序或链式方式存储，比如上面的稀疏矩阵用三元组表示为(1,3,1),(2,2,2),(3,1,3),(4,4,5),(5,5,6),(6,6,7),(6,7,4)

成员包括矩阵的函数、列数、非零元素的集合,该定义用到了前面讲的线性表的有序顺序存储结构和有序链式存储结构

数据结构之线性表的顺序存储结构

数据结构之有序线性表的顺序存储结构

数据结构之线性表的链式存储结构

数据结构之有序线性表的链式存储结构

插入时间复杂度O(t),所以总时间复杂度为O(t*t) ,t为非零元素个数

更高效的转置

插入时间复杂度O（1），所以总时间复杂度O（n*t）,其中n为列数，t为非零元素个数

测试类及结果

稀疏矩阵定义以及存储格式(COO,CSR,CSC)

百度百科:在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 简单来说,稀疏矩阵就是绝大部分都是0的矩阵 ,只包含很少的非零值.

比如,

上述稀疏矩阵非零元素有9个,26个零值.稀疏性是74%.

稀疏矩阵因为绝大部分都是0元素,如果我们仍然按照普通方式存储,无疑会 浪费很多空间 ;同时如果进行运算时,0元素对最终结果也没有帮助, 增加了许多无效计算 . 因此,我们需要设计出新的存储方式,或者说数据结构来存储稀疏矩阵.比较常见的有:

对于稀疏矩阵的存储,为了达到压缩的目的(节省存储空间),只存储非0元素值,但是也要保留非零元素的位置,方便恢复.所以,我们存储时不仅存储非零元素值,同时存储其坐标位置(row,column). 针对这两者的存储,会出现不同的设计方案.这里主要介绍COO,CSR和CSC存储格式.

我们使用三个数组row,column和data分别用来存储非零元素坐标的row_index,col_index,以及数值.比如:

NNO:The number of nonzero.矩阵非零元素个数. 三个数组的长度都是NNO.data[i]在原稀疏矩阵中的坐标为(row[i],col[i]]).

可以发现,这种存储方式中,row数组和column数组中有一定的重复元素.我们是否可以针对这个冗余特性进一步进行压缩?之后出现CSR,CSC,分别是对row数组和column数组进行了压缩.

对COO稀疏矩阵存储格式的三个数组中的row数组进行压缩.其他两个数组保持不变;三个数组分别是row_ptr,columns和data.其中columns和data数组长度均为NNO(矩阵的非零元素个数). 如何对COO的row进行压缩?

row_ptr存储的是每行的第一个非零元素距离稀疏矩阵第一个元素的偏移位置;

由row_ptr我们可以知道每行非零元素在data中的index范围.第i行的非零元素为data[row_ptr[i]:row_ptr[i+1]],对data数组的切片,不包含data[row_ptr[i+1]];同时第i行非零元素的col坐标分别为columns[row_ptr[i]:row_ptr[i+1]];对data和columns的访问相似,index是相同的.

如上图中,第0行非零元素在data中是data[0:2],就是1,7;列坐标为columns[0:2],就是0,1,第1行非零元素为data[2:4],有两个元素2和8,列坐标分别为columns[2:4],1和2.

方便进行行操作.

和CSR类似.只不过对列进行压缩,row和data保持不变.

方便进行列操作.

稀疏矩阵的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于什么是稀疏矩阵、稀疏矩阵的信息别忘了在本站进行查找喔。