NOJ数据结构013——以十字链表为存储结构实现矩阵相加

亦凉 2022-11-17 14:59 248阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210410212650529.png]  
本题是一道十分有挑战性的题目，反正我是被折磨了很久。。。  
思路倒较为简单，直接上代码，注意点基本都写在注释里了。

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        
        int row, col;            //非零元行列下标
        int data;                //非零元数据
        struct Node *right, *down;//非零元行列后继链域
    }Node, *Link;
    
    typedef struct
    {
        
        Link *row_head, *col_head;//行列链表头指针
        int m, n, len;            //矩阵行，列，非零元个数
    }CrossList;
    
    CrossList A, B, C;
    
    CrossList InitLink(int m, int n, int t);//初始化十字链表
    void InsertLink(CrossList *A, Link s);   //插入元素进入矩阵
    void CreateLink(CrossList *A);           //创建十字链表输入数据
    Link CopyNode(Link s);                   //复制节点
    void AddLink(CrossList *A, CrossList *B, CrossList *C);//十字链表相加
    void Print(CrossList *C);  //打印矩阵
    
    int main()
    {
        
        int m, n, t1, t2;
        scanf("%d%d%d%d", &m, &n, &t1, &t2);
        A = InitLink(m, n, t1);
        B = InitLink(m, n, t2);
        C = InitLink(m, n, t1+t2);
        CreateLink(&A);
        CreateLink(&B);
        AddLink(&A, &B, &C);
        Print(&C);
        return 0;
    }
    
    CrossList InitLink(int m, int n, int t)
    {
           //初始化十字链表
        CrossList L;
        L.m = m;
        L.n = n;
        L.len = t;
        int tmp_m = L.m+1, tmp_n = L.n+1;
        L.row_head = (Link*) malloc (sizeof(Link)*tmp_m);
        L.col_head = (Link*) malloc (sizeof(Link)*tmp_n);
        for (int i = 0; i <= L.m; i++) {
        
            L.row_head[i] = NULL; //行置空
        }
        for (int j = 0; j <= L.n; j++) {
        
            L.col_head[j] = NULL; //列置空
        }
        return L;
    }
    
    void InsertLink(CrossList *A, Link s)
    {
           //插入元素进入矩阵
        if (A->row_head[s->row] == NULL) {
        
        	//需要插入的行中没有元素
            A->row_head[s->row] = s;
            s->right = NULL;
        }
        else {
        
            Link t;
            t = A->row_head[s->row];
            while (t->right != NULL && t->right->col < s->col) {
        
            	//查找需要插入的行的位置
                t = t->right;
            }
            s->right = t->right;
            t->right = s;
        }
        if (A->col_head[s->col] == NULL) {
        
        	//需要插入的行中没有元素
            A->col_head[s->col] = s;
            s->down = NULL;
        }
        else {
        
            Link t;
            t = A->col_head[s->col];
            while (t->down != NULL && t->down->row < s->row) {
        
            	//查找需要插入的列的位置
                t = t->down;
            }
            s->down = t->down;
            t->down = s;
        }
    }
    
    void CreateLink(CrossList *A)
    {
           //创建十字链表输入数据
        int tmp_row, tmp_col, tmp_data;
        Link s;
        for (int i = 0; i < A->len; i++) {
        
            s = (Link) malloc (sizeof(Node));
            scanf("%d%d%d", &tmp_row, &tmp_col, &tmp_data);
            s->row = tmp_row;
            s->col = tmp_col;
            s->data = tmp_data;
            s->right = NULL;
            s->down = NULL;
            InsertLink(A, s);
        }
    }
    
    Link CopyNode(Link s)
    {
           //复制节点
    	//为避免指针传递的影响
        Link tmp_s;
        tmp_s = (Link) malloc (sizeof(Node));
        tmp_s->col = s->col;
        tmp_s->row = s->row;
        tmp_s->data = s->data;
        tmp_s->down = NULL;
        tmp_s->right = NULL;
        return tmp_s;
    }
    
    void AddLink(CrossList *A, CrossList *B, CrossList *C)
    {
           //十字链表相加
        C->len = 0;
        for (int i = 1; i <= A->m; i++) {
        
            if (A->row_head[i] != NULL || B->row_head[i] != NULL) {
        
                if (A->row_head[i] != NULL && B->row_head[i] != NULL) {
        
                    Link t, s;
                    t = A->row_head[i];//t为A第i行第一个元素
                    s = B->row_head[i];//s为B第i行第一个元素
                    while (t != NULL && s != NULL) {
        
                    	//两链表在同一行都有元素
                        if (t->col > s->col) {
        //t的列数大于s的列数
                            Link tmp_s;
                            tmp_s = CopyNode(s);
                            //此处是为避免地址传递带来的影响
                            InsertLink(C, tmp_s);
                            s = s->right;
                            C->len++;
                        }
                        else if (t->col < s->col) {
        //t的列数小于s的列数
                            Link tmp_t;
                            tmp_t = CopyNode(t);
                            InsertLink(C, tmp_t);
                            t = t->right;
                            C->len++;
                        }
                        else if (t->col == s->col) {
        //t的列数等于s的列数
                            Link r;
                            r = CopyNode(s);
                            r->data = s->data + t->data;
                            if (r->data != 0) {
         //相加为0的情况
                                InsertLink(C, r);
                                C->len++;
                            }
                            s = s->right;
                            t = t->right;
                        }
                    }
                    while (t != NULL) {
        
                    	//A中第i行剩余元素
                        Link tmp_t;
                        tmp_t = CopyNode(t);
                        InsertLink(C, tmp_t);
                        t = t->right;
                        C->len++;
                    }
                    while (s != NULL) {
        
                    	//B中第i行剩余元素
                        Link tmp_s;
                        tmp_s = CopyNode(s);
                        InsertLink(C, tmp_s);
                        s = s->right;
                        C->len++;
                    }
                }
                if (A->row_head[i] != NULL && B->row_head[i] == NULL) {
        
                	//只有A在第i行有元素
                    Link t;
                    t = A->row_head[i];
                    while (t != NULL) {
        
                        Link tmp_t;
                        tmp_t = CopyNode(t);
                        InsertLink(C, tmp_t);
                        t = t->right;
                        C->len++;
                    }
                }
                if (A->row_head[i] == NULL && B->row_head[i] != NULL) {
        
                	//只有B在第i行有元素
                    Link s;
                    s = B->row_head[i];
                    while (s != NULL) {
        
                        Link tmp_s;
                        tmp_s = CopyNode(s);
                        InsertLink(C, tmp_s);
                        s = s->right;
                        C->len++;
                    }
                }
            }
        }
    }
    
    void Print(CrossList *C)
    {
          //打印矩阵
        Link s;
        for (int i = 1; i <= C->m; i++) {
        
            if (C->row_head[i] != NULL) {
        
                s = C->row_head[i];
                while (s != NULL) {
        
                    printf("%d %d %d\n", s->row, s->col, s->data);
                    s = s->right;
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/9d9fd8c5ec2d4d5383006487b420a731.png
[20210410212650529.png]: /images/20221022/c493b113a41e43a5bb9fdca648d2ba40.png