阅读:0       作者:严长生

矩阵压缩存储(十字链表、三元组顺序表、行逻辑链接的顺序表)

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

有必要压缩存储的矩阵大致分为两大类:
  • 矩阵中含有大量的相同数值,称为特殊矩阵(例如对称矩阵和上下三角矩阵)。
  • 矩阵中只有极少量的元素是非 0 元素,称为稀疏矩阵

两类矩阵压缩存储的方法:
  1. 特殊矩阵中,对于相同的数据元素,只存储一个。
  2. 稀疏矩阵中,只需要存储非 0 元素。

对称矩阵

如果n阶矩阵中的元素满足: aij = aji ( 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;

总结

稀疏矩阵的三种不同的存储方法,采用哪种方法要看程序具体要实现的功能:

  1. 如果想完成例如矩阵的转置这样的操作,宜采用三元组顺序表;
  2. 如果想实现矩阵的乘法这样的功能,宜采用行逻辑链接的顺序表;
  3. 如果矩阵运算过程中(例如矩阵的加法),需要不断地插入非 0 元素或删除变为 0 的元素,宜采用十字链表法。

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