精华内容
下载资源
问答
  • 稀疏矩阵的压缩存储

    千次阅读 2017-08-01 22:02:46
    稀疏矩阵的压缩存储

    1.什么是稀疏矩阵
    稀疏矩阵指的是矩阵中的非零元素个数明显小于矩阵元素的个数。
    而稀疏矩阵的压缩存储是指只存储非零元素。

    2.稀疏矩阵的存储方式
    以下是一个稀疏矩阵:
    这里写图片描述
    (1)表示稀疏矩阵非零元素的三元组
    这里写图片描述
    需要一种数据结构来存储非零元素的行数,列数,值。

    public class Triple{
        private int row;//行数
        private int col;//列数
        private int value;//值
    }

    (2)稀疏矩阵三元组顺序表表示
    这里写图片描述
    用顺序表存储的缺点:也就是顺序表的缺点,删除和查找元素,以及设置元素值的时间复杂度是O(n),n是数组中的元素个数。

    (3)稀疏矩阵三元组单链表表示
    这里写图片描述
    注意:这个图没有画出上面那个稀疏矩阵全部的元素。
    缺点:需要存储矩阵的行数和列数,找到某个元素,需要遍历这个元素前面的所有元素。

    //结点
    public class Node<T>{
        private T data;
        private Node<T> next;
    }
    这里的T是上面提到的Triple,三元组
    //单链表
    public class SinglyLinkedList<T>{
       private Node<T> head;
    }
    //稀疏矩阵三元组单链表表示
    public class MatrxiList{
      private int row;
      private int col;
      private SinglyLinkedList<Triple> list;
    }

    (4)稀疏矩阵三元组行的单链表表示
    这里写图片描述
    注意:这图表示的意思就是一个链表里面包含了其他链表(这里是4个)
    缺点:可以很快找到同一行中的其他元素,但是很难找到同一列中的其他元素。

    (5)稀疏矩阵十字链表表示
    这里写图片描述

    public class CrossNode{
        private Triple data;//存储的非零元素
        private CrossNode right;//下一个行元素
        private CrossNode down;//下一个列元素
    }
    public class CrossList{
        private int row;//矩阵的行数
        private int col;//矩阵的列数
        private int[] rowheads[];//存储每行的第一个元素
        private int[] colheads[];//存储每列的第一个元素
    }
    展开全文
  • 稀疏 矩阵的压缩存储

    2014-06-11 20:41:56
    c 语言实现 稀疏矩阵 创建 和 C语言 压缩存储 压缩矩阵转置
  • C++ 实现稀疏矩阵的压缩存储的实例 稀疏矩阵:M*N的矩阵,矩阵中有效值的个数远小于无效值的个数,且这些数据的分布没有规律。  稀疏矩阵的压缩存储:压缩存储值存储极少数的有效数据。使用{row,col,value}三元组...
  • 主要介绍了C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储的相关资料,这里实现稀疏矩阵和对称矩阵的压缩存储的实例,需要的朋友可以参考下
  • 什么是稀疏矩阵:在矩阵中,我们常见的都是稠密矩阵,即非0元素数目占大多数时;...下图1为一个稀疏矩阵的示例稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素,则稀疏因子...

    03b6224c713c80dc4300ad8b9c0735fe.png

    什么是稀疏矩阵:

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

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

    d0449fc537167a0f96e3c7c6c6e314d5.png

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

    稀疏矩阵的存储方式

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

    稀疏矩阵的压缩存储,数据结构提供有 3 种具体实现方式:三元组顺序表;

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

    十字链表;

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

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

    展开全文
  • 本篇文章主要介绍了C++实现稀疏矩阵的压缩存储实例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 756
精华内容 302
关键字:

稀疏矩阵的压缩存储