阅读:0       作者:解学武

十字链表法详解

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

前两种两种存储稀疏矩阵的方法,都是将稀疏矩阵存储到顺序表中,也就是数组中,这会产生一个问题,即在进行矩阵运算过程中,如果要插入非 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;
采用十字链表法存储稀疏矩阵,在操作此矩阵时,由 rhead 数组存储的矩阵各行的头指针,即可找到指定行的元素链表,由 chead 数组存储的矩阵各列的头指针,可找到指定列的元素链表。通过链表即可实现对矩阵中各元素的操作。