稀疏矩阵

时间: 1ms        内存:128M

描述:

假设n*n的稀疏矩阵A采用三元组表示,设计一个程序,实现以下功能:

1、生成如下两个稀疏矩阵的三元组a,b;

a
1 0 3 0
0 1 0 0
0 0 1 0
0 0 1 1
b
3 0 0 0
0 4 0 0
0 0 1 0
0 0 0 2

2、输出a转置矩阵的三元组。

3、输出a+b的三元组。

4、输出a*b的三元组。

输入:

输出:

输出有三项

1、a转置矩阵的三元组

2、a+b的三元组

3、a*b的三元组

每两项之间有一个空行!

示例输入:

示例输出:

0 0 1
1 1 1
...

0 0 4
...

...
...

提示:

参考答案(内存最优[0]):

#include <iostream>
#include<cstdio>
using namespace std;
#define M 4
#define N 4
typedef struct
{
    int r;
    int c;
    int d;
} TupNode;
typedef struct
{
    int rows;
    int cols;
    int nums;
    TupNode data[1000];
} TSMatrix;
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]!=0)
            {
                t.data[t.nums].r=i;
                t.data[t.nums].c=j;
                t.data[t.nums].d=A[i][j];
                t.nums++;
            }
        }
}
void DispMat(TSMatrix t)
{
    int i;
    if(t.nums<=0)
        return ;
    printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
    printf("\t--------------------\n");
    for(i=0; i<t.nums; i++)
        printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
}
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++)
            {
                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++;
            }
    }
}
int main()
{
    TSMatrix t,t1,tb;
    int c[4][4];
    int a[M][N]= {{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};
    CreatMat(t,a);
    TranTat(t,tb);
    printf("a的三元组:\n");
    DispMat(t);
    printf("a的转置三元组:\n");
    DispMat(tb);
    int b[M][N]= {{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};
    CreatMat(t1,b);
    printf("b的三元组:\n");
    DispMat(t1);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            c[i][j] = a[i][j] + b[i][j];
    CreatMat(t,c);
    printf("a+b的和:\n");
    DispMat(t);
    int sum;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            sum = 0;
            for (int k = 0; k < N; k++)
            {
                sum += a[i][k] * b[k][j];
            }
            c[i][j]=sum;
        }
    }
    CreatMat(t,c);
    printf("a*b的三元组:\n");
    DispMat(t);
    return 0;
    
}

参考答案(时间最优[0]):

#include <iostream>
#include<stdio.h>
using namespace std;
typedef struct
{
    int r,c,d;
} Node;
typedef struct
{
    int rows,cols,nums;
    Node data[11];
} shunxu;
int main()
{
    shunxu a,b,c,d;
    int i,j,p,k;
    a.rows=b.rows=a.cols=b.cols=4;
    a.nums=6;
    b.nums=4;
    a.data[1].r=0;
    a.data[1].c=0;
    a.data[1].d=1;
    a.data[2].r=0;
    a.data[2].c=2;
    a.data[2].d=3;
    a.data[3].r=1;
    a.data[3].c=1;
    a.data[3].d=1;
    a.data[4].r=2;
    a.data[4].c=2;
    a.data[4].d=1;
    a.data[5].r=3;
    a.data[5].c=2;
    a.data[5].d=1;
    a.data[6].r=3;
    a.data[6].c=3;
    a.data[6].d=1;
    b.data[1].r=0;
    b.data[1].c=0;
    b.data[1].d=3;
    b.data[2].r=1;
    b.data[2].c=1;
    b.data[2].d=4;
    b.data[3].r=2;
    b.data[3].c=2;
    b.data[3].d=1;
    b.data[4].r=3;
    b.data[4].c=3;
    b.data[4].d=2;
    p=1;
    for(i=0; i<4; i++)
    {
        for(j=1; j<=6; j++)
        {
            if(a.data[j].c==i)
            {
                c.data[p].r=i;
                c.data[p].c=a.data[j].r;
                c.data[p].d=a.data[j].d;
                p++;
            }
        }
    }
    for(i=1; i<=6; i++)
        printf("%d %d %d\n",c.data[i].r,c.data[i].c,c.data[i].d);
    printf("\n");
    i=j=1;
    k=1;
    d.cols=d.rows=4;
    while(i<=6&&j<=4)
    {
        if(a.data[i].r==b.data[j].r)
        {
            if(a.data[i].c==b.data[j].c)
            {
                d.data[k].c=a.data[i].c;
                d.data[k].r=a.data[i].r;
                d.data[k].d=a.data[i].d+b.data[j].d;
                k++;
                i++;
                j++;
            }
            else if(a.data[i].c<b.data[j].c)
            {
                d.data[k].c=a.data[i].c;
                d.data[k].r=a.data[i].r;
                d.data[k].d=a.data[i].d;
                k++;
                i++;
            }
            else
            {
                d.data[k].c=b.data[j].c;
                d.data[k].r=b.data[j].r;
                d.data[k].d=b.data[j].d;
                k++;
                j++;
            }
        }
        else if(a.data[i].r<b.data[j].r)
        {
            d.data[k].r=a.data[i].r;
            d.data[k].c=a.data[i].c;
            d.data[k].d=a.data[i].d;
            k++;
            i++;
        }
        else
        {
            d.data[k].c=a.data[j].c;
            d.data[k].c=a.data[j].c;
            d.data[k].d=a.data[j].d;
            k++;
            j++;
        }
        d.nums=k;
    }
    for(i=1; i<d.nums; i++)
        printf("%d %d %d\n",d.data[i].r,d.data[i].c,d.data[i].d);
    printf("\n");
  printf("0 0 3\n");
   printf("0 2 3\n");
    printf("1 1 4\n");
     printf("2 2 1\n"); 
     printf("3 2 1\n"); 
     printf("3 3 2\n");
    printf("\n");
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。