C/C++利用三元组实现稀疏矩阵运算

快来打我* 2022-04-03 16:05 114阅读 0赞

**三元组（（x，y），z）其中（x，y）表示非零元位置，z表示该坐标的值**

**由于实际操作时，我们所用的矩阵0非常多，所以一个一个输入值很浪费时间，也浪费空间，所以用一些三元组表示非零元即能表示一个矩阵**

**三元组稀疏矩阵表示一些图也是很不错的选择**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]  
这样就很浪费空间，三元组直接

((0,1),1)
    ((1,2),1)
    ((3,4),1)
    ((5,6),1)
    ((7,8),1)

## 下面是稀疏矩阵代码： ##

#include <iostream>
    #include<malloc.h>
    #include<stdio.h>
    #define SMAX 1000
    
    using namespace std;
    
    typedef struct
    {
        int i,j;          //储存非零元素的行和列信息
        int  v;            //非零元素的值
    } SPNode;       //定义三元组类型
    
    typedef struct
    {
        int row,col,notZero; //矩阵的行、列和非零元素的个数
        SPNode data[SMAX]; //三元组表
    } SPMatrix;
    
    void printMatrix(SPMatrix m);
    
    SPMatrix createMatrix()
    {
        cout<<"enter row and col and notZero"<<endl;
        int row,col, notZero;
        cin>>row >>col >>notZero;
        SPMatrix matrix;
        matrix.row = row;
        matrix.col = col;
        matrix.notZero = notZero;
    
    
        for(int k = 1; k <= notZero; k++)
        {
            cout <<"enter each row and col and value"<<endl;
            cin >> matrix.data[k].i >>matrix.data[k].j>>matrix.data[k].v;
        }
    
        cout <<"三元组："<<endl;
        for(int k = 1; k <= notZero; k++)
        {
            cout <<"(("<<matrix.data[k].i<<"," << matrix.data[k].j<<")"<<matrix.data[k].v<<"))"<<endl;
        }
    //    printMatrix(matrix);
        return matrix;
    }
    
    void printMatrix(SPMatrix m)
    {
    
        int row = m.row;
        int col = m.col;
        int show[row][col]= {0};
    
        //初始化矩阵
        for(int i=0; i<row; i++)
        {
            for(int j=0; j<col; j++)
            {
                show[i][j]=0;
            }
        }
    
        for(int k=1; k<=m.notZero; k++)
        {
            show[m.data[k].i-1][m.data[k].j-1] = m.data[k].v;
        }
        for(int i=0; i<row; i++)
        {
            for(int j=0; j<col; j++)
            {
                cout<<show[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    SPMatrix add(SPMatrix m1,SPMatrix m2)
    {
    
        if(m1.row!=m2.row || m1.col!=m2.col)
        {
            cout<<"wrong"<<endl;
            return m1;
        }
    
        int flag = 0;
        int num = m1.notZero;
        int m;
        for(int k = 1; k <= num; k++)
        {
            for(m = 1; m <= m2.notZero; m++)
            {
                if(m1.data[k].i == m2.data[m].i && m1.data[k].j == m2.data[m].j)
                {
                    m2.data[k].v += m1.data[m].v;
                    flag = 1;
                    break;
                }
    
            }
            if(flag ==0) //当前位置m2和m1未重合
            {
                m2.notZero++;
                m2.data[m2.notZero] = m1.data[k];
            }
            flag = 0;
        }
    
        return m2;
    }
    SPMatrix sub(SPMatrix m1,SPMatrix m2)
    {
    
        if(m1.row!=m2.row || m1.col!=m2.col)
        {
            cout<<"wrong"<<endl;
            return m1;
        }
    
        int flag = 0;
        int num = m1.notZero;
        int m;
        for(int k = 1; k <= num; k++)
        {
            for(m = 1; m <= m2.notZero; m++)
            {
                if(m1.data[k].i == m2.data[m].i && m1.data[k].j == m2.data[m].j)
                {
                    m2.data[k].v -= m1.data[m].v;
                    flag = 1;
                    break;
                }
    
            }
            if(flag ==0) //当前位置m2和m1未重合
            {
                m2.notZero++;
                m2.data[m2.notZero] = m1.data[k];
                m2.data[m2.notZero].v = -m1.data[k].v;
            }
            flag = 0;
        }
    
        return m2;
    }
    SPMatrix numMul(SPMatrix m)
    {
        int num ;
        cout <<"输入数乘的数："<<endl;
        cin >> num;
        for(int k = 1; k <= num; k++)
        {
            m.data[k].v *= num;
        }
    
        return m;
    }
    
    int isExist(SPMatrix m,SPNode a){
        for(int i=1;i<=m.notZero;i++)
            if(m.data[i].i == a.i &&m.data[i].j == a.j)
                return i;
        return 0;
    }
    SPMatrix Mul(SPMatrix m1,SPMatrix m2)
    {
        if(m1.col != m2.row)
        {
            cout<<"wrong"<<endl;
            return m1;
        }
        SPMatrix result;
        result.row = m1.row;
        result.col = m2.col;
        result.notZero = 0;//初始化
        SPNode data[m1.notZero+m2.notZero];
        int n = 0;
    
        for(int k = 1; k <= m1.notZero; k++)
        {
            for(int m = 1; m <= m2.notZero; m++)
            {
                if(m1.data[k].j == m2.data[m].i)
                {
                    data[n].v = m1.data[k].v*m2.data[m].v;
                    data[n].i = m1.data[k].i;
                    data[n].j = m2.data[m].j;
                    n++;
                    continue;
                }
    
            }
        }
        int flag = 0;
        for(int k =0;k<n;k++){
    
            flag = isExist(result,data[k]);
            if(flag>0){
                result.data[flag].v+=data[k].v;
            }
            else{
                result.notZero++;
                result.data[result.notZero] = data[k];
            }
        }
        return result;
    }
    
    
    int main()
    {
        int num = 0;
        do
        {
            cout<<"***********************************\n";
            cout<<"*              菜单                *\n";
            cout<<"*          1.矩阵相加               *\n";
            cout<<"*          2.矩阵相减               *\n";
            cout<<"*          3.矩阵相乘               *\n";
            cout<<"*          4.矩阵数乘               *\n";
            cout<<"*          6.退出                  *\n";
            cout<<"***********************************\n";
            cin>>num;
            if(1 == num|| 2 == num || 3 == num)
            {
                SPMatrix m1 = createMatrix();
                SPMatrix m2 = createMatrix();
                cout<<"两矩阵为"<<endl;
                printMatrix(m1);
                cout<<endl;
                printMatrix(m2);
                switch(num)
                {
                case 1:
                {
                    if(m1.col!=m2.col || m1.row!=m2.row)
                    {
                        cout<<"行列不同"<<endl;
                    }
                    else{
                        cout<<"结果为："<<endl;
                        printMatrix(add(m1,m2));
                    }
                    break;
                }
                case 2:
                {
    
                    if(m1.col!=m2.col || m1.row!=m2.row)
                    {
                        cout<<"参数错误"<<endl;
                    }
                    else{
                        cout<<"结果为："<<endl;
                        printMatrix(sub(m1,m2));
                    }
                    break;
    
                }
                case 3:
                {
                    if(m1.col!=m2.row)
                    {
                        cout<<"参数错误"<<endl;
                    }
                    else{
                        cout<<"结果为："<<endl;
                        printMatrix(Mul(m1,m2));
                    }
                    break;
                }
                default:
                    break;
                }
            }
            else if(4 == num)
            {
                int number = 1;
                cout<<"请输入矩阵"<<endl;
                SPMatrix m  = createMatrix();
                cout<<"请输入数值"<<endl;
                cin>>number;
                cout<<"矩阵为："<<endl;
                printMatrix(m);
                printMatrix(numMul(m));
            }
            cout<<"按回车继续....";
            getchar();
            getchar();
            system("cls");
        }
        while(1 == num|| 2 == num || 3 == num ||4 == num);
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]: /images/20220403/6455ca5d01e242678247d82fe99d6da2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]: /images/20220403/8a9460b818344e6da37aa10c929d9add.png