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 %d\n", 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 %d\n", 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 %d\n", p->x, p->y, p->value);
}
p=p->right;
}
}
}
}
else
{
shuchusss(L5);
}
}
else
{
cout<<"Can not multiply!";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/380866.html
標籤：AI
上一篇：機器學習（一）：回歸