数组和广义表的基本运算实现（三元组）

本是古典何须时尚 2022-08-22 14:18 199阅读 0赞

问题及代码：

a：![20160530163235725][] b： ![20160530163239698][]

/*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：6-4.cpp
    * 作    者：单昕昕
    * 完成日期：2016年5月30日
    * 版 本 号：v1.0
    * 问题描述：假设n n的稀疏矩阵A采用三元组表示，设计一个程序exp6-4.cpp实现如下功能：
             （1）生成如下两个稀疏矩阵的三元组a和b；
             （2）输出a转置矩阵的三元组；
             （3）输出a+b的三元组；
             （4）输出a b的三元组。
    * 程序输入：无
    * 程序输出：如题。
    */
    
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define M 4//行数
    #define N 4//列数
    #define MaxSize 1010//稀疏矩阵中非零元素最多个数
    
    typedef struct
    {
        int r;//行号
        int c;//列号
        int d;//元素值
    } TupNode;//三元组定义
    
    typedef struct
    {
        int rows;//行数
        int cols;//列数
        int nums;//非零元素个数
        TupNode data[MaxSize];
    } TSMatrix;//三元组顺序表定义
    //以行序方式扫描稀疏矩阵A，将其非零元素插入到三元组t中
    void CreatMat(TSMatrix &t,int A[M][N])
    {
        int i,j;
        t.rows=M,t.cols=N,t.nums=0;
        for(i=0; i<M; ++i)//行主序开始扫描
            for(j=0; j<N; ++j)
                if(A[i][j])//只储存非零元素
                {
                    t.data[t.nums].r=i;
                    t.data[t.nums].c=j;
                    t.data[t.nums].d=A[i][j];
                    ++t.nums;
                }
    }
    //输出三元组
    void DisMat(TSMatrix t)
    {
        if(t.nums<=0) return;
        cout<<'\t'<<t.rows<<'\t'<<t.cols<<'\t'<<t.nums<<endl;
        cout<<'\t'<<"-------------------"<<endl;
        for(int i=0; i<t.nums; ++i)
            cout<<'\t'<<t.data[i].r<<'\t'<<t.data[i].c<<'\t'<<t.data[i].d<<endl;
    }
    //矩阵转置
    void TranTat(TSMatrix t,TSMatrix &tb)
    {
        int p,q=0,v;
        tb.rows=t.cols;
        tb.cols=t.rows;
        tb.nums=t.nums;
        if(t.nums!=0)
            for(v=0; v<t.cols; ++v)
                for(p=0; p<t.nums; ++p)
                    if(t.data[p].c==v)
                    {
                        tb.data[q].r=t.data[p].c;
                        tb.data[q].c=t.data[p].r;
                        tb.data[q].d=t.data[p].d;
                        ++q;
                    }
    }
    //两个稀疏矩阵相加
    bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
    {
        int i=0,j=0,k=0;
        int v;
        if(a.rows!=b.rows||a.cols!=b.cols) return false;
        c.rows=a.rows,c.cols=a.cols;
        while(i<a.nums&&j<b.nums)
        {
            if(a.data[i].r==b.data[j].r)
            {
                if(a.data[i].c<b.data[j].c)
                {
                    c.data[k].r=a.data[i].r;
                    c.data[k].c=a.data[i].c;
                    c.data[k].d=a.data[i].d;
                    ++k,++i;
                }
                else if(a.data[i].c>b.data[j].c)
                {
                    c.data[k].r=b.data[i].r;
                    c.data[k].c=b.data[i].c;
                    c.data[k].d=b.data[i].d;
                    ++k,++j;
                }
                else
                {
                    v=a.data[i].d+b.data[j].d;
                    if(v)
                    {
                        c.data[k].r=a.data[i].r;
                        c.data[k].c=a.data[i].c;
                        c.data[k].d=v;
                        ++k;
                    }
                    ++i,++j;
                }
            }
            else if(a.data[i].r<b.data[j].r)
            {
                c.data[k].r=a.data[i].r;
                c.data[k].c=a.data[i].c;
                c.data[k].d=a.data[i].d;
                ++k,++i;
            }
            else
            {
                c.data[k].r=b.data[i].r;
                c.data[k].c=b.data[i].c;
                c.data[k].d=b.data[i].d;
                ++k,++j;
            }
            c.nums=k;
        }
        return true;
    }
    //两个稀疏矩阵相乘
    void MatMul(int a[M][N],int b[M][N],int z[M][N])
    {
        memset(z,0,sizeof(z));
        int i,j,k;
        for (k=0; k<N; k++)
            for(i=0; i<N; i++)
                for (j=0; j<N; j++)
                    z[i][k]+=a[i][j]*b[j][k];
    }
    
    TSMatrix a,b,c;
    int z[M][N];
    int main()
    {
        int x[M][N]= {1,0,3,0,
                      0,1,0,0,
                      0,0,1,0,
                      0,0,1,1
                     };
        int y[M][N]= {3,0,0,0,
                      0,4,0,0,
                      0,0,1,0,
                      0,0,0,2
                     };
        CreatMat(a,x);
        cout<<"a的三元组："<<endl;
        DisMat(a);
        CreatMat(b,y);
        cout<<"b的三元组："<<endl;
        DisMat(b);
        cout<<"a转置为c"<<endl;
        TranTat(a,c);
        cout<<"c的三元组："<<endl;
        DisMat(c);
        cout<<"c=a+b"<<endl;
        cout<<"c的三元组："<<endl;
        if(MatAdd(a,b,c))  DisMat(c);
        cout<<"c=a×b"<<endl;
        cout<<"c的三元组："<<endl;
        MatMul(x,y,z);
        /*for(int i=0; i<4; ++i)
        {
            for(int j=0; j<4; ++j)
                cout<<z[i][j]<<" ";
            cout<<endl;
        }*/
        CreatMat(c,z);
        DisMat(c);
        return 0;
    }
    /*
    1 0 3 0
    0 1 0 0
    0 0 1 0
    0 0 1 1
    
    3 0 0 0
    0 4 0 0
    0 0 1 0
    0 0 0 2
    */

运行结果：

![Center][]

[20160530163235725]: https://img-blog.csdn.net/20160530163235725
[20160530163239698]: /images/20220722/4d8386466d214124b678274f2e31db85.png
[Center]: /images/20220722/2e852b338283492583ee988c79946c32.png