作者：解学武

稀疏矩阵的压缩存储方式共有 3 种，分别是：三元组顺序表、行逻辑链接的顺序表和十字链表法。

前两种两种存储稀疏矩阵的方法，都是将稀疏矩阵存储到顺序表中，也就是数组中，这会产生一个问题，即在进行矩阵运算过程中，如果要插入非 0 元素或者删除非 0 元素的操作，需要大量的移动数组中的三元组，效率很低。

因此想到了用链表存储稀疏矩阵，就是十字链表法的由来。

例如，将下列矩阵以十字链表的方式存储起来：


采用十字链表法存储矩阵的非 0 元素时，链表中的结点由 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;

采用十字链表法存储稀疏矩阵，在操作此矩阵时，由 rhead 数组存储的矩阵各行的头指针，即可找到指定行的元素链表，由 chead 数组存储的矩阵各列的头指针，可找到指定列的元素链表。通过链表即可实现对矩阵中各元素的操作。
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。