稀疏矩阵
时间: 1ms 内存:128M
描述:
假设n*n的稀疏矩阵A采用三元组表示,设计一个程序,实现以下功能:
1、生成如下两个稀疏矩阵的三元组a,b;
a1 0 3 00 1 0 00 0 1 00 0 1 1b3 0 0 00 4 0 00 0 1 00 0 0 22、输出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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。