阅读:0       作者:严长生

稀疏矩阵的存储方法(3种)及C语言代码实现

稀疏矩阵,即含有少量非 0 元素的矩阵,如图 1 所示:
 


图 1 稀疏矩阵 
 
该矩阵中非 0 元素的数量比较少,与其使用普通方式将矩阵中的所有数据元素一一存储,不如只存储非 0 元素更节省内存空间,拿图 1 中矩阵来说,只需存储元素 3、4、5 即可(此类存储方式被称为稀疏矩阵的压缩存储)。
 
稀疏矩阵(压缩)存储的方式有 3 种,分别为:三元组顺序表行逻辑链接的顺序表十字链表

三元组顺序表

存储稀疏矩阵,需记录矩阵中每个非 0 元素的 3 个要素:非 0 元素的值、所在行标(用 i 表示)以及所在列标(用 j 表示),每个非 0 元素的 3 要素都可以用一个三元组(行标、列标、元素值)来表示,矩阵中所有非 0 元素的三元组可以通过顺序表来存储。此方法也被称为稀疏矩阵的三元组表示法

因此,每个非 0 元素的三元组需要使用结构体进行自定义:
//三元组结构体
typedef struct {
    int i,j;//行标i,列标j
    int data;//元素值
}triple;
稀疏矩阵的存储,一方面要存储矩阵中所有非 0 元素的三元组,同时还要记录该稀疏矩阵的行数、列数以及矩阵中非 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 的元素,宜采用十字链表法。

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