- it
- 稀疏矩阵
#include<iostream>
using namespace std
;
template<class T>
struct matrixterms
{
T element
;
int mrow
;
int mcol
;
};
template<class T>
class spareMatrix
{
public:
spareMatrix();
~spareMatrix(){};
void replace();
void multiply(spareMatrix
<T
> &Q
);
void add(spareMatrix
<T
>);
void output();
int getrow(){return row
;}
int getcol(){return col
;}
matrixterms
<T
> * gets(){return a
;}
int anum
;
private:
matrixterms
<T
> *a
;
int row
,col
;
};
template<class T>
spareMatrix
<T
>::spareMatrix()
{
a
= NULL;
row
= 0;
col
= 0;
anum
= 0;
}
template<class T>
void spareMatrix
<T
>::replace()
{
int n
,m
,k
=0;
cin
>>n
>>m
;
row
= n
;
col
= m
;
a
= new matrixterms
<T
> [m
*n
];
int num
;
for(int i
=0;i
<n
;i
++)
{
for(int j
=0;j
<m
;j
++)
{
cin
>>num
;
if(num
!=0)
{
a
[k
].element
=num
;
a
[k
].mrow
= i
;
a
[k
].mcol
= j
;
k
++;
}
}
} anum
= k
;
}
template<class T>
void spareMatrix
<T
>::output()
{
int k
= 0;
cout
<<row
<<" "<<col
<<endl
;
for(int i
=0;i
<row
;i
++)
{
for(int j
=0;j
<col
;j
++)
{
if(a
[k
].mrow
==i
&&a
[k
].mcol
==j
)
{ cout
<<a
[k
].element
<<" ";
k
++;}
else
cout
<<0<<" ";
}
cout
<<endl
;
}
}
template<class T>
void spareMatrix
<T
>::add(spareMatrix
<T
> Q
)
{
int qrow
=Q
.getrow();
int qcol
=Q
.getcol();
if(qrow
!=row
||qcol
!=col
)
{
a
= Q
.gets();
row
= Q
.getrow();
col
= Q
.getcol();
anum
= Q
.anum
;
cout
<<-1<<endl
;
return;
}
else{
T
*a1
= new T
[row
*col
];
T
*a2
= new T
[row
*col
];
T
*a3
= new T
[row
*col
];
int k
=0;
for(int i
=0;i
<row
;i
++)
for(int j
=0;j
<col
;j
++)
{
if(a
[k
].mrow
==i
&&a
[k
].mcol
==j
)
{
a1
[i
*col
+j
]=a
[k
].element
;
k
++;
}
else
a1
[i
*col
+j
]=0;
}k
=0;
matrixterms
<T
> *c
= Q
.gets();
for(int i
=0;i
<row
;i
++)
for(int j
=0;j
<col
;j
++)
{
if(c
[k
].mrow
==i
&&c
[k
].mcol
==j
)
{
a2
[i
*col
+j
]=c
[k
].element
;
k
++;
}
else
a2
[i
*col
+j
]=0;
}
for(int i
=0;i
<row
;i
++)
for(int j
=0;j
<col
;j
++)
{
a3
[i
*col
+j
]= a1
[i
*col
+j
]+a2
[i
*col
+j
];
}
k
=0;
for(int i
=0;i
<row
;i
++)
for(int j
=0;j
<col
;j
++)
{
if(a3
[i
*col
+j
]!=0)
{a
[k
].element
=a3
[i
*col
+j
];
a
[k
].mrow
=i
;
a
[k
].mcol
=j
;
k
++;
}
}
anum
= k
;
delete c
;
delete []a1
;
delete []a2
;
delete []a3
;
}
}
struct remenber
{
int k
;
int nn
;
};
template <class T>
void spareMatrix
<T
>::multiply(spareMatrix
<T
> &Q
)
{
if( col
!=Q
.getrow() )
{
a
= Q
.gets();
row
= Q
.getrow();
col
= Q
.getcol();
anum
= Q
.anum
;
cout
<<-1<<endl
;
return;}
else{
matrixterms
<T
> *q
=Q
.gets();
matrixterms
<T
> c
[row
*col
];
int rowEnum
[row
];
for(int i
=0;i
<row
;i
++)
rowEnum
[i
]=0;
for(int i
=0;i
<anum
;i
++)
{
for(int j
=0;j
<row
;j
++)
if(a
[i
].mrow
==j
)
{
rowEnum
[j
]++;
}
}
remenber re
[row
];
for(int i
=0,j
=0;j
<row
;i
+=rowEnum
[j
],j
++)
{
if(rowEnum
[j
]!=0)
{
re
[j
].k
=1;
re
[j
].nn
=i
;
}
else
{re
[j
].k
=0;
re
[j
].nn
=-1;
if(i
==anum
)
break;
}
}
int sum1
=0,sum2
=0;
int jishu
=0,m
=0;
for(int i
=0, N
=rowEnum
[0];i
<row
;i
++,N
+=rowEnum
[i
])
{
if(re
[i
].k
==0)
{
if(i
==row
-1)
break;
else
continue;
}
if(re
[i
].k
!=0) {
for(int l
=0;l
<Q
.getcol();l
++){
for(int j
=re
[i
].nn
;j
<N
;j
++)
{
for(int g
=0;g
<Q
.anum
;g
++){
if(q
[g
].mcol
==l
&&a
[j
].mcol
==q
[g
].mrow
)
{
sum1
+= a
[j
].element
*q
[g
].element
;
jishu
++;
sum2
= sum2
+sum1
;
}
if(g
==Q
.anum
-1&&jishu
==0)
{
sum1
=0;
}
jishu
=0;
sum1
=0;
}
}
if(sum2
!=0)
{
c
[m
].element
=sum2
;
c
[m
].mrow
=i
;
c
[m
].mcol
=l
;
m
++;
}
sum2
=0;
}
}}
for(int i
=0;i
<m
;i
++)
{
a
[i
].element
=c
[i
].element
;
a
[i
].mcol
=c
[i
].mcol
;
a
[i
].mrow
=c
[i
].mrow
;
}
col
= Q
.getcol();
anum
= m
;
}
}
int main()
{
spareMatrix
<int> p
;
int n
;
cin
>>n
;
int cho
;
for(int i
=0;i
<n
;i
++)
{
cin
>>cho
;
switch (cho
){
case 1:{
p
.replace();
break;
}
case 2:{
spareMatrix
<int> g
;
g
.replace();
p
.multiply(g
);
break;
}
case 3:{
spareMatrix
<int> h
;
h
.replace();
p
.add(h
);
break;
}
case 4:{
p
.output();
break;
}
default:{
break;
}
}
}
}
