前面讲过的稀疏矩阵的三元组顺序表，是用顺序存储结构存放稀疏矩阵，这种存储结构就如同之前学习顺序存储结构的时候所讲，比较适用于不出现元素的增加、减少等操作中。对于稀疏矩阵也如此，如果在稀疏矩阵中，遇到了元素的增加、减少操作，就必须要移动三元组顺序表中的元素。根据以往的经验，这种情况下最好使用链式存储结构。

以之前学过的单链表为例，其类型声明如下：

typedef struct LNode{
    ElemType data;  //结点的数据域
    struct LNode * next; //结点的指针域
}LNode, *LinkList;  //LinkList 为指向结构体 LNode 的指针类型

在这个类型中，声明了单链表中每个结点的结构：数据域、指针域。包含这些域的结点链接起来，就形成了单链表。

如果将稀疏矩阵以链式存储结构表示，也需要声明结点的结构。

以如下稀疏矩阵为例：

如果要存储其中的非零元素，显然必须要说明该元素所在的行、列以及数值，也就是结点结构中应该有行、列和非零元素的值。但是，如果结点仅仅是这样的结构，还无法构成“链”，若要构成链式结构，必须要有“指针”指示当前非零元素的“后继”非零元素。矩阵中每个非零元的“后继”非零元，可能是与它在同一行、也有可能是在同一列。所以，每个结点还必须包括另个域：

• 向右域 right：用以链接同一行中下一个非零元。
• 向下域：down：用以链接同一列中下一个非零元。

如图 1 所示，即为表示稀疏矩阵链式存储结构中的一个结点的结构示意图。

按照这种结点设计，矩阵  中的非零元素就可以表示为图 2 所示的存储方式，同一行的非零元通过 right 域链接成一个线性链表，同一列的非零元通过 down 域链接成一个线性链接，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。

在十字链表中的每个行链表和列链表，可以用之前学过的单链表或循环单链表表示。

在单链表中，单链表可由头指针唯一确定，因此每个链表都有一个头指针。对于十字链表中的行链表和列链表，每个链表也都有一个头指针。可以用两个一维数组，分别存储行链表的头指针和列链表的头指针，最终得到如图 3 所示的存储结构示意图。

按照上述示意图，就可以写出表示稀疏矩阵的十字链表的存储结构：

typedef struct OLNode{
    int i, j; //非零元的行下标、列下标
    ElemType e; //非零元数值
    struct OLNode * right, * down; //非零元所在行表和列表的后继链域
}OLNode; * OLink; //非零元结点

typedef struct{
    OLink * rhead, *chead; //行和列链表头指针向量基址
    int mu, nu, tu; //稀疏矩阵的行数、列数和非零元个数
}CrossList; 

根据图 3 可以知道，十字链表本质上就是以前所学过的链表的综合，因此，如果要将一个稀疏矩阵存储为十字链表的结构，也就是不断地向行链表或者列链表中插入新的非零元素所对应的结点。

Status CreateSMatrixOL(CrossList &M){
    //创建稀疏矩阵 M，采用十字链表存储表示
    if(M) free(M); //判断 M 是否已经存在，如果存在就不再创建
    scanf(&m, &n, &t); //输入 M 的行数、列数和非零元个数
    M.mu = m;
    M.nu = n;
    M.tu = t;
    if (!(M.rhead = (OLink *) malloc((m+1) * sizeof(OLink))))
        exit(OVERFLOW);
    if (!(M.chead = (OLink *) malloc((n+1) * sizeof(OLink))))
        exit(OVERFLOW);
    M.rhead[] = M.chead[] = NULL;//初始化行列头指针向量；各行列链表为空链表
    for (scanf(&i, &j, &e)); i != 0; scanf(&i, &j, &e){//按任意次序输入非零元
        if(!(p = (OLNode *)malloc(sizeof(OLNode))))
            exit(OVERFLOW);
        //生成结点
        p->i = i;
        p->j = j;
        p->e = e;
        
        if(M.rhead[i] == NULL || M.rhead[i]->j > j){
            //i 行链表空 
            //或输入的列号小于行表的首元结点的列下标
            //则该结点做插入到头指针后，即作为新的首元结点
            //此处使用单链表
            p->right = M.rhead[i];//M.rhead[i]为NULL或原首元结点
            M.rhead[i] = p;//头指针指向 p
        } else {//在行链表中适当位置插入
            for(q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right){
                p->right = q->right;
                q->right = p;
            }//完成结点插入
        }
        
        //列链表中插入结点
        if(M.chead[j] == NULL || M.chead[j]->i > i){
            p->down = M.chead[j];
            M.chead[j] = p;
        } else {
            for(q = M.chead[j]; (q->down) && q->down->i < i; q = q->down){
                p->down = q->down;
                q->down = p;
            }
        }
    }
    return OK;
}

【算法分析】

上述算法对非零元输入的先后次序没有任何要求。每建立一个非零元的结点，都要寻査它在行表和列表中的插入位置。若矩阵  为  ，且有  个非零元，则算法的时间复杂度为  。

本文系转载，版权归原作者所有，

转载自公众号 CS创新实验室 ，如若侵权请联系我们进行删除！  

《行业指标体系白皮书》下载地址：https://www.dtstack.com/resources/1057/?src=bbs

《数据治理行业实践白皮书》下载地址：https://www.dtstack.com/resources/1001/?src=bbs

《数栈V6.0产品白皮书》下载地址：https://www.dtstack.com/resources/1004/?src=bbs

想了解或咨询更多有关袋鼠云大数据产品、行业解决方案、客户案例的朋友，浏览袋鼠云官网：https://www.dtstack.com/?src=bbs

同时，欢迎对大数据开源项目有兴趣的同学加入「袋鼠云开源框架钉钉技术群」，交流最新开源技术信息，群号码：30537511，项目地址：https://github.com/DTStack