前面学习了如何使用三元组顺序表存储稀疏矩阵,其实现过程就是将矩阵中各个非 0 元素的行标、列标和元素值以三元组的形式存储到一维数组中。通过研究实现代码你会发现,三元组顺序表每次提取指定元素都需要遍历整个数组,运行效率很低。
本节将学习另一种存储矩阵的方法——行逻辑链接的顺序表。它可以看作是三元组顺序表的升级版,在三元组顺序表的基础上提高了查找某一行非 0 数据的效率。
行逻辑链接的顺序表和三元组顺序表的实现过程类似,它们存储矩阵的过程完全相同,都是将矩阵中非 0 元素的三元组(行标、列标和元素值)存储在一维数组中。但为了提高提取查找指定行非 0 元素的效率,前者在存储矩阵时比后者多使用了一个数组,专门记录矩阵中每行第一个非 0 元素在一维数组中的位置。
图 1 稀疏矩阵示意图
图 1 是一个稀疏矩阵,当使用行逻辑链接的顺序表对其进行压缩存储时,需要做以下两个工作:
将矩阵中的非 0 元素采用三元组的形式存储到一维数组 data 中,如图 2 所示(和三元组顺序表一样):
图 2 三元组存储稀疏矩阵
使用数组 rpos 记录矩阵中每行第一个非 0 元素在一维数组中的存储位置。如图 3 所示:
图 3 存储各行首个非 0 元素在数组中的位置
通过以上两步操作,即实现了使用行逻辑链接的顺序表存储稀疏矩阵。
举个简单的例子,查找图 1 矩阵中第 2 行所有的非 0 元素。如果使用三元组顺序表,就必须从头遍历数组中的每个三元组,逐个进行判断;而如果使用行逻辑链接的顺序表,借助 rpos 数组可以直接获得数组第 2 行首个非 0 元素在数组中的位置,还可以获得第 2 行最后一个元素在数组中的位置,查找效率大大提升。
行逻辑链接的顺序表,可以用下面的结构来表示:
//三元组
typedef struct
{
int i,j;//行,列
ElemType e;//元素值
}Triple;
//行逻辑链接的顺序表
typedef struct
{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];//每行第一个非零元素在data数组中的位置
int mu,nu,tu;//行数,列数,元素个数
}RLSMatrix;
例如,使用行逻辑链接的顺序表存储图 1 的稀疏矩阵,C 语言实现代码如下:
#include
#define MAXSIZE 12500
#define MAXRC 100
#define ElemType int
typedef struct
{
int i, j;//行,列
ElemType e;//元素值
}Triple;
typedef struct
{
Triple data[MAXSIZE + 1];
int rpos[MAXRC + 1];//每行第一个非零元素在data数组中的位置
int mu, nu, tu;//行数,列数,元素个数
}RLSMatrix;
//矩阵的输出函数
void display(RLSMatrix M) {
int i, j, k;
for (i = 1; i |