NOJ数据结构实验006——稀疏矩阵的乘法

叁歲伎倆 2023-01-14 01:53 174阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]  
本题并未想到更好的方法，只好依次遍历将矩阵a每一行与矩阵b相乘放到矩阵c中。  
上代码：

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100
    typedef struct
    {
        
        int row,col;   /*非零元行下标、列下标*/
        int data;      /*非零元数据*/
    }Triple;
    
    typedef struct
    {
        
        Triple elem[MAXSIZE];   /*非零元的三元组表*/
        int row, col, len;        /*非零元个数*/
    }TSMatrix;
    
    TSMatrix a, b, c;
    
    TSMatrix InitMatrix(int m, int n);             //初始化三元矩阵
    void CreateMatrix(TSMatrix *mat);              //输入矩阵数据
    void MulMatrix(TSMatrix *a, TSMatrix *b, TSMatrix *c);  //矩阵相乘
    void PrintMatrix(TSMatrix *c);                 //打印矩阵
    
    int main()
    {
        
        int m1, m2, n1, n2;
        scanf("%d%d", &m1, &n1);
        a = InitMatrix(m1, n1);
        CreateMatrix(&a);
        scanf("%d%d", &m2, &n2);
        b = InitMatrix(m2, n2);
        CreateMatrix(&b);
        c = InitMatrix(m1, n2);
        MulMatrix(&a, &b, &c);
        PrintMatrix(&c);
        return 0;
    }
    
    TSMatrix InitMatrix(int m, int n)
    {
            //初始化三元矩阵
        TSMatrix Mat;
        Mat.row = m;
        Mat.col = n;
        Mat.len = 0;
        return Mat;
    }
    
    void CreateMatrix(TSMatrix *mat)
    {
           //输入矩阵数据
        int tmp_row, tmp_col, tmp_data;
        int i = 0;
        while(1) {
        
            scanf("%d%d%d", &tmp_row, &tmp_col, &tmp_data);
            if (tmp_row == 0 && tmp_col == 0 && tmp_data == 0) {
        
                break;
            }
            mat->elem[i].row = tmp_row;
            mat->elem[i].col = tmp_col;
            mat->elem[i].data = tmp_data;
            mat->len++;
            i++;
        }
    }
    
    
    void MulMatrix(TSMatrix *a, TSMatrix *b, TSMatrix *c)
    {
           //矩阵相乘
        int cnt = -1, sum = 0, tmp_a = 0, tmp_b = 0;
        c->len = 0;
        for (int i = 1; i <= a->row; i++) {
        
            //按行遍历矩阵a
            for (int j = 1; j <= b->col; j++) {
        
                //按列遍历矩阵b
                sum = 0;
                for (int k = 1; k <= a->col; k++) {
        
                    //在矩阵a中某行、矩阵b中某列依次选取元素
                    for (int m = 0; m < a->len; m++) {
        
                        //选取a中元素
                        if (a->elem[m].row == i
                              && a->elem[m].col == k) {
        
                            tmp_a = a->elem[m].data;
                        }
                    }
                    for (int n = 0; n < b->len; n++) {
        
                        //选取b中元素
                        if (b->elem[n].row == k
                              && b->elem[n].col == j) {
        
                            tmp_b = b->elem[n].data;
                        }
                    }
                    sum += tmp_a * tmp_b;//累加
                    tmp_a = 0, tmp_b = 0;
                }
                if (sum != 0) {
        
                    cnt++;
                    c->elem[cnt].data = sum;
                    c->elem[cnt].row = i;
                    c->elem[cnt].col = j;
                    c->len++;
                }
            }
        }
    }
    
    
    void PrintMatrix(TSMatrix *c)
    {
          //打印矩阵
        for (int i = 0; i < c->len; i++) {
        
            printf("%d %d %d\n", c->elem[i].row, c->elem[i].col, c->elem[i].data);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/aab70c282c4a45f39b1fd1d21e3f17bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/56394648cac3444e9156dfbbad38d27a.png