稀疏矩阵的压缩存储方式有哪些?

什么是稀疏矩阵:

在矩阵中,我们常见的都是稠密矩阵,即非0元素数目占大多数时;若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵。与之相区别的是,如果非零元素的分布存在规律(如上三角矩阵、下三角矩阵、对角矩阵),则称该矩阵为特殊矩阵。

下图1为一个稀疏矩阵的示例

1.png

稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素,则稀疏因子δ的计算公式如下:δ=t/(n∗m), 当这个值小于等于0.05时,可以认为是稀疏矩阵

稀疏矩阵的存储方式

存储矩阵的一般方法是采用二维数组,其优点是可以随机地访问每一个元素,因而能够较容易地实现矩阵的各种运算。但对于稀疏矩阵而言,若用二维数组来表示,会重复存储了很多个0了,浪费空间,而且要花费时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。

稀疏矩阵的压缩存储,数据结构提供有 3 种具体实现方式:

  • 三元组顺序表;

  • 行逻辑链接的顺序表:可以看作是三元组顺序表的升级版,即在三元组顺序表的基础上改善了提取数据的效率。

  • 十字链表;

    使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。

想要了解更多相关知识,请关注 html中文网!!

以上就是稀疏矩阵的压缩存储方式有哪些?的详细内容,更多请关注web前端其它相关文章!

赞(0) 打赏
未经允许不得转载:web前端首页 » 其他答疑

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

前端开发相关广告投放 更专业 更精准

联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏