PTA5-1 稀疏矩阵的处理 (25 分)
PTA5-1 稀疏矩阵的处理 (25 分)
现要求编程实现稀疏矩阵在“压缩”存储时的矩阵的常用操作，如输出、转置、求和、乘等。 即输入两个矩阵，完成如下操作： (1) 转置。对第一个矩阵进行转置并输出，前面输出标题 “The transformed matrix is:”
(2) 矩阵加。如两个矩阵可以相加，进行两个矩阵的加运算并输出，前面输出标题 “The added matrix is:”；如果不能相加，则输出 “Can not add!”；
(3) 矩阵乘。如果两个矩阵可以相乘，进行两个矩阵的乘并输出，前面输出标题 “The product matrix is:”； 如果不能相乘，则输出 “Can not multiply!”
输入格式:
输入有多行，第1行包括三个整数，分别是矩阵的大小m,n及非零元素的个数r。后面r行分别输入各个非零元素的 行、列、值。
输出格式:
输出有两种形式，操作时分别用符号“L”、“H”指出输出形式。 L: 以三元组的形式输出，即先输出矩阵的行数、列数和非零元素个数，再按行主序依次输出各个非零元素的行、列和值。各输出项之间空格分隔。 H: 按人们习惯的矩阵格式输出，即输出一个mn的矩阵，是零元素的输出0，非零元素输出元素值。设定每个元素占位宽度为4。（要输出矩阵的行号和列号，并对齐）
输入样例1：
10 8 4
1 8 1
3 3 2
3 7 3
10 1 4
10 8 2
2 6 1
3 7 -3
H
输入样例2：
100 90 5
1 10 100
50 60 200
50 80 100
60 60 200
99 89 10
100 90 4
1 1 10
50 60 -200
50 80 100
70 70 10
L
输出样例1：
The transformed matrix is:
1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 0 0 0 4
2 0 0 0 0 0 0 0 0 0 0
3 0 0 2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0
7 0 0 3 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0
The added matrix is:
1 2 3 4 5 6 7 8
1 0 0 0 0 0 0 0 1
2 0 0 0 0 0 1 0 0
3 0 0 2 0 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0
10 4 0 0 0 0 0 0 0
Can not multiply!
输出样例2：
The transformed matrix is:
Rows=90,Cols=100,r=5
10 1 100
60 50 200
60 60 200
80 50 100
89 99 10
The added matrix is:
Rows=100,Cols=90,r=6
1 1 10
1 10 100
50 80 200
60 60 200
70 70 10
99 89 10
Can not multiply!
代码
可以自行优化一下，用函数包装会简洁很多。
#include<bits/stdc++.h>
using namespace std;
typedef struct CrossNode* List;
int a[10000000][3];
struct CrossNode
{
int x,y,value;
List right,down;
};
struct LNode
{
List* rhead;
List* chead;
int mx,my,mvalue;
};
typedef struct LNode* Node;
void creatCrossNode(Node L1,int c)
{
int m,n,p;
cin>>m>>n>>p;
L1->mx=m;
L1->my=n;
L1->mvalue=p;
L1->rhead=(List*)malloc(sizeof(List)*(m+1));
L1->chead=(List*)malloc(sizeof(List)*(n+1));
for(int i=1; i<=m; i++)
{
L1->rhead[i]=NULL;
}
for(int i=1; i<=n; i++)
{
L1->chead[i]=NULL;
}
int cnt=0;
while(p--)
{
int i,j,k;
cin>>i>>j>>k;
if(c==1)
{
a[cnt][0]=i;
a[cnt][1]=j;
a[cnt++][2]=k;
}
List p=(List)malloc(sizeof(struct CrossNode));
p->x=i;
p->y=j;
p->value=k;
List q;
if(L1->rhead[i]==NULL||L1->rhead[i]->y>j)
{
p->right=L1->rhead[i];
L1->rhead[i]=p;
}
else
{
q=L1->rhead[i];
while(q->right&&q->right->y<j)
{
q=q->right;
}
p->right=q->right;
q->right=p;
}
if(L1->chead[j]==NULL||L1->chead[j]->x>i)
{
p->down=L1->chead[j];
L1->chead[j]=p;
}
else
{
q=L1->chead[j];
while(q->down&&q->down->x<i)
{
q=q->down;
}
p->down=q->down;
q->down=p;
}
}
}
void createss(Node L1,Node L2)
{
L1->mx=L2->mx;
L1->my=L2->my;
L1->mvalue=L2->mvalue;
L1->rhead=(List*)malloc(sizeof(List)*(L1->mx+1));
L1->chead=(List*)malloc(sizeof(List)*(L1->my+1));
for(int i=1; i<=L1->mx; i++)
{
L1->rhead[i]=NULL;
}
for(int i=1; i<=L1->my; i++)
{
L1->chead[i]=NULL;
}
int p=L1->mvalue;
int cnt=0;
while(p--)
{
int i,j,k;
i=a[cnt][0];
j=a[cnt][1];
k=a[cnt++][2];
List p=(List)malloc(sizeof(struct CrossNode));
p->x=i;
p->y=j;
p->value=k;
List q;
if(L1->rhead[i]==NULL||L1->rhead[i]->y>j)
{
p->right=L1->rhead[i];
L1->rhead[i]=p;
}
else
{
q=L1->rhead[i];
while(q->right&&q->right->y<j)
{
q=q->right;
}
p->right=q->right;
q->right=p;
}
if(L1->chead[j]==NULL||L1->chead[j]->x>i)
{
p->down=L1->chead[j];
L1->chead[j]=p;
}
else
{
q=L1->chead[j];
while(q->down&&q->down->x<i)
{
q=q->down;
}
p->down=q->down;
q->down=p;
}
}
}
void shuchu(Node L1)
{
printf(" ");
for(int i=1; i<=L1->mx; i++)
{
printf("%4d",i);
}
cout<<endl;
int cnt=0;
for(int i=1; i<=L1->my; i++)
{
cnt=0;
List p=L1->chead[i];
printf("%4d",i);
while(p)
{
for(int x=cnt+1; x<p->x; x++)
{
printf(" 0");
}
cnt=p->x;
printf("%4d",p->value);
p=p->down;
}
for(int x=cnt+1; x<=L1->mx; x++)
{
printf(" 0");
}
cout<<endl;
}
}
void shuchusss(Node L1)
{
printf(" ");
for(int i=1; i<=L1->my; i++)
{
printf("%4d",i);
}
cout<<endl;
int cnt=0;
for(int i=1; i<=L1->mx; i++)
{
cnt=0;
List p=L1->rhead[i];
printf("%4d",i);
while(p)
{
for(int x=cnt+1; x<p->y; x++)
{
printf(" 0");
}
cnt=p->y;
printf("%4d",p->value);
p=p->right;
}
for(int x=cnt+1; x<=L1->my; x++)
{
printf(" 0");
}
cout<<endl;
}
}
int main()
{
Node L1=(Node)malloc(sizeof(struct LNode));
L1->chead=NULL;
L1->rhead=NULL;
creatCrossNode(L1,1);
Node L2=(Node)malloc(sizeof(struct LNode));
L2->chead=NULL;
L2->rhead=NULL;
creatCrossNode(L2,0);
Node L4=(Node)malloc(sizeof(struct LNode));
L4->rhead=NULL;
L4->chead=NULL;
createss(L4,L1);
char ch;
cin>>ch;
cout<<"The transformed matrix is:"<<endl;
//shuchusss(L1);
//shuchusss(L2);
if(ch=='L')
{
cout<<"Rows="<<L1->my<<",Cols="<<L1->mx<<",r="<<L1->mvalue<<endl;
for (int i = 1; i <= L1->my; i++)
{
if (L1->chead[i])
{
List p = L1->chead[i];
while (p)
{
printf("%d %d %dn", p->y, p->x, p->value);
p = p->down;
}
}
}
}
else
{
shuchu(L1);
}
if(L1->mx==L2->mx&&L1->my==L2->my)
{
for(int i=1; i<=L2->mx; i++)
{
List p=L2->rhead[i];
while(p)
{
List op=(List)malloc(sizeof(struct CrossNode));
op->x=p->x;
op->y=p->y;
op->value=p->value;
if(L4->rhead[i]==NULL||L4->rhead[i]->y>p->y)
{
L4->mvalue++;
op->right=L4->rhead[i];
L4->rhead[i]=op;
}
else if(L4->rhead[i]->y==p->y)
{
L4->rhead[i]->value=L4->rhead[i]->value+p->value;
if(L4->rhead[i]->value==0)
{
L4->mvalue--;
}
}
else if(L4->rhead[i]->y<p->y)
{
List q=L4->rhead[i];
while(q->right&&q->right->y<p->y)
{
q=q->right;
}
if(q->right&&p&&p->y==q->right->y)
{
q->right->value=q->right->value+p->value;
if(q->right->value==0)
{
L4->mvalue--;
}
}
else
{
L4->mvalue++;
op->right=q->right;
q->right=op;
}
}
p=p->right;
}
}
cout<<"The added matrix is:"<<endl;
if(ch=='L')
{
cout<<"Rows="<<L4->mx<<",Cols="<<L4->my<<",r="<<L4->mvalue<<endl;
for(int i=1; i<=L4->mx; i++)
{
if(L4->rhead[i])
{
List p=L4->rhead[i];
while(p)
{
if(p->value!=0)
{
printf("%d %d %dn", p->x, p->y, p->value);
}
p=p->right;
}
}
}
}
else
{
shuchusss(L4);
}
}
else
{
cout<<"Can not add!"<<endl;
}
if(L1->my==L2->mx)
{
Node L5=(Node)malloc(sizeof(struct LNode));
L5->chead=NULL;
L5->rhead=NULL;
L5->mx=L1->mx;
L5->my=L2->my;
L5->mvalue=0;
L5->rhead=(List*)malloc(sizeof(List)*(L5->mx+1));
L5->chead=(List*)malloc(sizeof(List)*(L5->my+1));
for(int i=1; i<=L5->mx; i++)
{
L5->rhead[i]=NULL;
}
for(int i=1; i<=L5->my; i++)
{
L5->chead[i]=NULL;
}
for(int i=1; i<=L1->mx; i++)
{
List p,q;
p=L1->rhead[i];
if(p)
{
for(int j=1; j<=L2->my; j++)
{
//cout<<j<<endl;
int sum=0;
q=L2->chead[j];
p=L1->rhead[i];
while(q&&p)
{
if(q->x==p->y)
{
sum=sum+q->value*p->value;
p=p->right;
q=q->down;
}else if(q->x>p->y)
{
p=p->right;
}else
{
q=q->down;
}
}
//cout<<"sum="<<sum<<endl;
if(sum!=0)
{
L5->mvalue++;
List op=(List)malloc(sizeof(struct CrossNode));
op->x=i;
op->y=j;
op->value=sum;
if(L5->rhead[i]==NULL||L5->rhead[i]->y>j)
{
op->right=L5->rhead[i];
L5->rhead[i]=op;
// cout<<"****"<<endl;
}
else
{
List oq=L5->rhead[i];
while(oq->right&&oq->right->y<j)
{
oq=oq->right;
}
op->right=oq->right;
oq->right=op;
}
}
}
}
}
cout<<"The product matrix is:"<<endl;
if(ch=='L')
{
cout<<"Rows="<<L5->my<<",Cols="<<L5->mx<<",r="<<L5->mvalue<<endl;
for(int i=1; i<=L5->mx; i++)
{
if(L5->rhead[i])
{
List p=L5->rhead[i];
while(p)
{
if(p->value!=0)
{
printf("%d %d %dn", p->x, p->y, p->value);
}
p=p->right;
}
}
}
}
else
{
shuchusss(L5);
}
}
else
{
cout<<"Can not multiply!";
}
return 0;
}
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码