数据结构例程——稀疏矩阵的十字链表表示

我会带着你远行 2022-03-26 07:43 445阅读 0赞

本文针对[数据结构基础系列网络课程(5)：数组与广义表][5]中第4课时[稀疏矩阵的十字链表表示][Link 1]。

![这里写图片描述][20151007211229227]

下面的程序中，实现了创建并显示十字链表的算法。

#include <stdio.h>#include <malloc.h>#define M 3                     //矩阵行#define N 3                     //矩阵列#define Max ((M)>(N)?(M):(N))   //矩阵行列较大者typedef int ElemType;typedef struct mtxn{    int row;                    //行号    int col;                    //列号    struct mtxn *right,*down;   //向右和向下的指针    union    {        ElemType value;        struct mtxn *link;    } tag;} MatNode;          //十字链表类型定义void CreatMat(MatNode *&mh,ElemType a[][N]){    int i,j;    MatNode *h[Max],*p,*q,*r;    mh=(MatNode *)malloc(sizeof(MatNode));//创建十字链表的头节点    mh->row=M;    mh->col=N;    r=mh;                   //r指向尾节点    for (i=0; i<Max; i++)       //采用尾插法创建头节点h1,h2,…循环链表    {        h[i]=(MatNode *)malloc(sizeof(MatNode));        h[i]->down=h[i]->right=h[i];        //将down和right方向置为循环的        r->tag.link=h[i];                   //将h[i]加到链表中        r=h[i];    }    r->tag.link=mh;                         //置为循环链表    for (i=0; i<M; i++)                     //处理每一行    {        for (j=0; j<N; j++)                 //处理每一列        {            if (a[i][j]!=0)                 //处理非零元素            {                p=(MatNode *)malloc(sizeof(MatNode));   //创建一个新节点                p->row=i;                p->col=j;                p->tag.value=a[i][j];                q=h[i];                         //查找在行表中的插入位置                while (q->right!=h[i] && q->right->col<j)                    q=q->right;                p->right=q->right;                q->right=p; //完成行表的插入                q=h[j];                         //查找在列表中的插入位置                while (q->down!=h[j] && q->down->row<i)                    q=q->down;                p->down=q->down;                q->down=p;      //完成列表的插入            }        }    }}void DispMat(MatNode *mh){    MatNode *p,*q;    printf("行=%d  列=%d\n", mh->row,mh->col);    p=mh->tag.link;    while (p!=mh)    {        q=p->right;        while (p!=q)        //输出一行非零元素        {            printf("%d\t%d\t%d\n", q->row,q->col,q->tag.value);            q=q->right;        }        p=p->tag.link;    }}//本主程序用于调试int main(){    ElemType a[M][N]= {
        {
        1,0,3},{
        0,2,0},{
        0,0,5}};    ElemType b[M][N]= {
        {-1,0,2},{
        0,-2,0},{
        1,0,-5}};    MatNode *mx,*my;    CreatMat(mx,a);    CreatMat(my,b);    printf("a的十字链表:\n");    DispMat(mx);    printf("b的十字链表:\n");    DispMat(my);    return 0;}
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7 
        8 
        9 
        10 
        11 
        12 
        13 
        14 
        15 
        16 
        17 
        18 
        19 
        20 
        21 
        22 
        23 
        24 
        25 
        26 
        27 
        28 
        29 
        30 
        31 
        32 
        33 
        34 
        35 
        36 
        37 
        38 
        39 
        40 
        41 
        42 
        43 
        44 
        45 
        46 
        47 
        48 
        49 
        50 
        51 
        52 
        53 
        54 
        55 
        56 
        57 
        58 
        59 
        60 
        61 
        62 
        63 
        64 
        65 
        66 
        67 
        68 
        69 
        70 
        71 
        72 
        73 
        74 
        75 
        76 
        77 
        78 
        79 
        80 
        81 
        82 
        83 
        84 
        85 
        86 
        87 
        88 
        89

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[5]: http://edu.csdn.net/course/detail/1512
[Link 1]: http://edu.csdn.net/course/detail/1512/23605
[20151007211229227]: /images/20220326/909b875d819144119cf5d723e6cfbce0.png
[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485