|
前面学习了如何使用三元组顺序表存储稀疏矩阵，其实现过程就是将矩阵中各个非 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 |