# PTA5-1 稀疏矩阵的处理 (25 分)

## PTA5-1 稀疏矩阵的处理 (25 分)

(3) 矩阵乘。如果两个矩阵可以相乘，进行两个矩阵的乘并输出，前面输出标题 “The product matrix is:”； 如果不能相乘，则输出 “Can not multiply!”

``````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
``````

``````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
``````

``````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
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!
``````

``````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
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
{
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;
for(int i=1; i<=m; i++)
{
}
for(int i=1; i<=n; i++)
{
}
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;
{
}
else
{
while(q->right&&q->right->y<j)
{
q=q->right;
}
p->right=q->right;
q->right=p;
}
{
}
else
{
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;
for(int i=1; i<=L1->mx; i++)
{
}
for(int i=1; i<=L1->my; i++)
{
}
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;
{
}
else
{
while(q->right&&q->right->y<j)
{
q=q->right;
}
p->right=q->right;
q->right=p;
}
{
}
else
{
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;
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;
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));
creatCrossNode(L1,1);
Node L2=(Node)malloc(sizeof(struct LNode));
creatCrossNode(L2,0);
Node L4=(Node)malloc(sizeof(struct LNode));
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++)
{
{
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++)
{
while(p)
{
List op=(List)malloc(sizeof(struct CrossNode));
op->x=p->x;
op->y=p->y;
op->value=p->value;
{
L4->mvalue++;
}
{
{
L4->mvalue--;
}
}
{
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;
}
}
if(ch=='L')
{
cout<<"Rows="<<L4->mx<<",Cols="<<L4->my<<",r="<<L4->mvalue<<endl;
for(int i=1; i<=L4->mx; i++)
{
{
while(p)
{
if(p->value!=0)
{
printf("%d %d %dn", p->x, p->y, p->value);
}
p=p->right;
}
}
}
}
else
{
shuchusss(L4);
}

}
else
{
}
if(L1->my==L2->mx)
{
Node L5=(Node)malloc(sizeof(struct LNode));
L5->mx=L1->mx;
L5->my=L2->my;
L5->mvalue=0;
for(int i=1; i<=L5->mx; i++)
{
}
for(int i=1; i<=L5->my; i++)
{
}
for(int i=1; i<=L1->mx; i++)
{
List p,q;
if(p)
{
for(int j=1; j<=L2->my; j++)
{
//cout<<j<<endl;
int sum=0;
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;
{
// cout<<"****"<<endl;
}
else
{
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++)
{
{
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

)">