由于稀疏矩阵中存在大量零元素,从而占用大量空间,如何对它进行压缩存储?所谓压缩存储是指只存储非零元的信息节省不必要的空间浪费。常用的压缩存储方法有:【三元组法】【十字链表法】
2.1三元组法
所谓三元组法是指用一块相同大小的连续的内存空间(顺序表)或者结点形式(链表),并以按矩阵的行顺序存储矩阵中的每个非零元信息。为确保非零元唯一确定,三元组保存信息时需要保存非零元的所在矩阵中的行号和列号以及元素本身,即一个三元组表示为:(i,j,aij),i是行号,j是列号。一个矩阵的所有非零元的三元组作为结构类型的元素存储在连续的内存空间中或链表形成一个集合称为三元组表。(注:按矩阵的行顺序存储是指矩阵的第一行的第一个非零元存储在三元组表的第一个位置,第二个非零元存储在三元组表的第二个位置)
有了三元组表可以唯一确定矩阵中的非零元位置,但却不能唯一确定矩阵,因为矩阵的行数和列数没有指明,因此需要用额外的空间存储矩阵的列数和行数,为了方便再加一个空间来存储矩阵中非零元的总数,其存储方式如下:
//这里以顺序表存储为例,以三元组的方式存储稀疏矩阵
#define MAXSIZE 100
typedef int ElemType;//类型重命名【鉴名知意】
typedef struct {
int i,j;//非零元的行和列
ElemType e;//非零元
}Triple;
typedef struct{
Triple data[MAXSIZE];
int m,n,nonzeroNums;//矩阵的行m,矩阵的列n,非零元数量nonzeroNums
}TSMatrix