数据结构24：矩阵压缩存储(十字链表、三元组顺序表、行逻辑链接的顺序表）

如果矩阵中有很多数值相同的数据元素，在存储时，可以考虑对其进行适当的压缩存储。

有必要压缩存储的矩阵大致分为两大类：

矩阵中含有大量的相同数值，称为特殊矩阵（例如对称矩阵和上下三角矩阵）。
矩阵中只有极少量的元素是非 0 元素，称为稀疏矩阵。

两类矩阵压缩存储的方法：

特殊矩阵中，对于相同的数据元素，只存储一个。
稀疏矩阵中，只需要存储非 0 元素。

对称矩阵

如果n阶矩阵中的元素满足： a_ij = a_ji ( i 为行标， j 为列标)，就称这个矩阵为对称矩阵。

图1 对称矩阵

图1 为 3 阶对称矩阵，图中的虚线为矩阵的 “主对角线” ，主对角线上方区域称为 “上三角” ；主对角线下方称为 “下三角” ，沿主对角线对称的数据元素一一相等，所以对于此矩阵来说，只需要存储 6 个元素即可。

若将对称矩阵压缩存储在一维数组 S[k] 中，矩阵中数据元素在数组中存储的位置和所在的行标（用 i 表示）和列标（用 j 表示）有关。

对称矩阵沿主对角线对称的数据元素相等，任选一边的数据元素进行存储即可：

存储下三角区域的数据元素：

存储上三角区域的数据元素：

上下三角矩阵

上下三角矩阵，和对称矩阵类似，不同在于，上三角矩阵是指主对角线下方的元素（不包括主对角线上的）都是常数C（包括数值 0 ）；同理，下三角矩阵是指主对角线上方的元素都是常数C。

例如：

图2 下三角矩阵

存储时，上（下）三角存储上（下）三角的数据元素，除此之外，额外存储一个下（上）三角含有的常数C（图 2 中，C==0）。

稀疏矩阵

稀疏矩阵，简单的说，就是矩阵中只含有少量的非 0 元素，相比于使用普通方式将矩阵中的所有数据元素一一存储，不如只存储非 0 元素更节省内存空间。

例如：

图 3 稀疏矩阵

矩阵压缩存储的方式

矩阵压缩存储的方式有 3 种，分别为：三元组顺序表、行逻辑链接的顺序表和十字链表。

三元组顺序表

在存储稀疏矩阵时，除了要存储非 0 元素的值之外，还需要存储元素所在矩阵中的行标 i 和列标 j ，三个元素构成三元组（行标，列标，元素值）。

所以，表示三元组结构需要使用结构体进行自定义：

//三元组结构体
typedef struct 
{
　　int i, j;　　//行标i，列标j
　　int data;　　//元素值
}triple;

每个稀疏矩阵的表示，需要存储矩阵中所有非 0 元素的三元组，并且还需要记录矩阵的行数和列数，这样才能唯一确定一个稀疏矩阵。
所以，表示矩阵的结构也需要使用结构体实现：
#define number 100
//矩阵的结构表示
typedef struct {
triple data[number];//存储该矩阵中所有非0元素的三元组
int n,m,num;//n和m分别记录矩阵的行数和列数，num记录矩阵中所有的非0元素的个数
}TSMatrix;
例如，对于图 3 的稀疏矩阵来说，即将（2，2，3）、（2，3，4）、（3，2，5）存储进 data 数组，并且存储稀疏矩阵的行数3和列数3 ，该稀疏矩阵中非 0 元素有 3 个。

行逻辑链接的顺序表

使用三元组顺序表存储矩阵后，当需要提取矩阵某一行的非 0 元素时，需要遍历整个顺序表。
为了提高查找的效率，在三元组顺序表的基础上，增加一个数组用于记录每一行第一个非 0 元素的存储位置，这样的存储结构，称为：行逻辑链接的顺序表。

结构代码：

#define number 100


typedef struct 
{
　　int i, j;
　　int data;
}triple;

typedef struct 
{
　　triple data[number];
　　int rpos[number];　　//存储各行第一个非0元素在三元组表中的位置
　　int n, m, num;
}TSMatrix;

十字链表

以上两种存储稀疏矩阵的方法，说到底，还是操作数组，在进行矩阵运算过程中，如果有插入非 0 元素或者删除某一个元素的操作，可能需要大量的移动数组中的三元组。这时，就要考虑使用链表的存储结构。

例如在进行“将矩阵 B 加到矩阵 A 上”的操作时，矩阵 A 中的数据元素会发生很大的变化，之前的 0 元素可能变成非 0 元素，非 0 元素也可能变成 0 （正负数相加为 0）。在这种情况下，就需要使用链表的存储结构来存储矩阵，这种存储方式称为：十字链表法。

例如，将下列矩阵以十字链表的方式存储起来：

图4 十字链表

采用十字链表法存储矩阵的非 0 元素时，链表中的结点由 5 部分组成：

图5 十字链表中的结点

两个指针域：一个指向所在列的下一个元素，一个指向所在行的下一个元素。

结构代码：

typedef struct OLNode
{
　　int i, j;
　　int data;
　　struct OLNode *right, *down;
}OLNode;

//此结构体表示一个矩阵，其中包含矩阵的行数，列数，非0元素的个数以及用于存储各行以及各列元素头指针的动态数组rhead和chead。
typedef struct 
{
　　OLNode *rhead, *chead;
　　int n, m, num;
}CrossList;

总结

稀疏矩阵的三种不同的存储方法，采用哪种方法要看程序具体要实现的功能：
如果想完成例如矩阵的转置这样的操作，宜采用三元组顺序表；
如果想实现矩阵的乘法这样的功能，宜采用行逻辑链接的顺序表；
如果矩阵运算过程中（例如矩阵的加法），需要不断地插入非 0 元素或删除变为 0 的元素，宜采用十字链表法。

有关三种存储方法的实例：矩阵转置、矩阵的乘法和矩阵的加法各自利用一节来详细介绍。