行逻辑链接的顺序表（压缩存储稀疏矩阵）详解

2021年1月12日   |   by tgcode

前面学习了如何使用三元组顺序表存储稀疏矩阵，其实现过程就是将矩阵中各个非 0 元素的行标、列标和元素值以三元组的形式存储到一维数组中。通过研究实现代码你会发现，三元组顺序表每次提取指定元素都需要遍历整个数组，运行效率很低。

本节将学习另一种存储矩阵的方法——行逻辑链接的顺序表。它可以看作是三元组顺序表的升级版，即在三元组顺序表的基础上改善了提取数据的效率。

行逻辑链接的顺序表和三元组顺序表的实现过程类似，它们存储矩阵的过程完全相同，都是将矩阵中非 0 元素的三元组（行标、列标和元素值）存储在一维数组中。但为了提高提取数据的效率，前者在存储矩阵时比后者多使用了一个数组，专门记录矩阵中每行第一个非 0 元素在一维数组中的位置。

图 1 稀疏矩阵示意图

图 1 是一个稀疏矩阵，当使用行逻辑链接的顺序表对其进行压缩存储时，需要做以下两个工作：

1. 将矩阵中的非 0 元素采用三元组的形式存储到一维数组 data 中，如图 2 所示（和三元组顺序表一样）：
   
   
   图 2 三元组存储稀疏矩阵
    
2. 使用数组 rpos 记录矩阵中每行第一个非 0 元素在一维数组中的存储位置。如图 3 所示:
   
   
   图 3 存储各行首个非 0 元素在数组中的位置

通过以上两步操作，即实现了使用行逻辑链接的顺序表存储稀疏矩阵。

此时，如果想从行逻辑链接的顺序表中提取元素，则可以借助 rpos 数组提高遍历数组的效率。

例如，提取图 1 稀疏矩阵中的元素 2 的过程如下：

• 由 rpos 数组可知，第一行首个非 0 元素位于data[1]，因此在遍历此行时，可以直接从第 data[1] 的位置开始，一直遍历到下一行首个非 0 元素所在的位置（data[3]）之前；
• 同样遍历第二行时，由 rpos 数组可知，此行首个非 0 元素位于 data[3]，因此可以直接从第 data[3] 开始，一直遍历到下一行首个非 0 元素所在的位置（data[4]）之前；
• 遍历第三行时，由 rpos 数组可知，此行首个非 0 元素位于 data[4]，由于这是矩阵的最后一行，因此一直遍历到 rpos 数组结束即可（也就是 data[tu]，tu 指的是矩阵非 0 元素的总个数）。

以上操作的完整 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){
    for(int i=1;i
运行结果：

	0 3 0 5

	0 0 1 0

	2 0 0 0

	总结
通过系统地学习使用行逻辑链接的顺序表压缩存储稀疏矩阵，可以发现，它仅比三元组顺序表多使用了一个 rpos 数组，从而提高了提取数据时遍历数组的效率。

相关推荐: 顺序表和链表的优缺点（区别、特点）详解

 相关推荐: 好的架构是进化来的，不是设计来的　　好的架构不是设计出来的而是演进出来的 　　对很多创业公司而言，在初期的时候，我们很难在初期就预估到流量十倍以后、百倍以后、一千倍以后网站的架构会变成什么样。当然，如果在最初的时期，就设计一个千万级并发的流量架构…