Tim的资源站

一、什么是稀疏矩阵？

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

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

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

因此，稀疏矩阵A中的一个非零元素可由一个三元组（i, j, a_ij）唯一确定。

二、三元组表

假设非零元素的三元组以按行优先的原则顺序排列，一个稀疏矩阵可转换成用一个对应的线性顺序表来表示，其中每个元素由一个上述的三元组构成，该线性表称为三元组表，记为（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 的十字链表：