稀疏矩阵

一、什么是稀疏矩阵?

简单地说,设矩阵Amn中有s个非零元素,若s远远小于矩阵元素的总数(s < m * n),则称A为稀疏矩阵。令e = s / (m * n),称e为矩阵的系数因子。

当用数组存储稀疏矩阵中元素时,仅有少部分空间被利用,造成空间浪费。为了节省存储空间,可以采用一种压缩的存储方法来表示稀疏矩阵的内容。

由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须记下元素所在的行和列的位置(i,j)。

因此,稀疏矩阵A中的一个非零元素可由一个三元组(i, j, aij)唯一确定。

二、三元组表

假设非零元素的三元组以按行优先的原则顺序排列,一个稀疏矩阵可转换成用一个对应的线性顺序表来表示,其中每个元素由一个上述的三元组构成,该线性表称为三元组表,记为(i,j,v)。其类型说明如下:

typedef int DataType;

#define maxsize 1000

Struct Triple {
  int i, j;   // 非零元素的行、列号
  DataType v;   // 非零元素的值
}

class SparseMatrix {
  private:
    int rows, cols, terms;
    Triple data[maxsize];
  
  public:
    SparseMatrix(int Maxrow, int Maxcol);   // 构造函数
    SparseMatrix Transmatrix();   // 转置
}

三、十字链表存储

三元组表是用顺序方法存储稀疏矩阵的非零元素的。当非零元素的位置或个数经常变化时,三元组就不适合做稀疏矩阵的存储结构。

例如,两矩阵做加操作时,会改变非零元素的个数;用三元组表表示矩阵时,元素的插入和删除会导致大量的结点移动。此时,采用链式存储结构更为合适。

一般采用十字链表的链接存储方法。在该方法中,稀疏矩阵的每个非零元素可用一个含5个域的结点表示,结点结构信息如下图所示:

十字链表结点结构

除了表示非零元素所在的行、列和值的三元组(i,j,v)外,还增加了两个链域:指向本行中下一个非零元素的行指针域right和指向本列下一个非零元素的列指针域down。

同一行的非零元素通过right域链接成一个线性表,同一列的非零元素通过down域链接成一个线性表。每个非零元素既是某个行链表中的一个结点,又是某个列链表中的一个结点。整个矩阵构成了一个十字交叉的链表,故称这样的链表为十字链表。

为便于操作,在十字链表的行链表和列链表上设置行头结点、列头结点和十字链表头结点。它们采用和非零元素结点类似的结点结构,具体如上图(b)所示。其中行头结点和列头结点的 i 和 j 域值均为零;行头结点的 right 指针指向该行链表的第一个结点,它的 down 指针为空;列头结点的 down 指针指向该列链表的第一个结点,它的 right 指针为空。所有的行、列链表和它们对应的头结点链接成一个循环链表。十字链表头结点的 i 和 j 域分别存放稀疏矩阵的行数和列数,链表头结点的 next 指针指向行头结点链表中的第一行头结点,down 和 right 指针为 NULL。下图是稀疏矩阵 A 的十字链表:

稀疏矩阵的十字链表

用户头像
登录后发表评论