一、什么是稀疏矩阵?
简单地说,设矩阵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 的十字链表: