实验五（数据结构与算法实验） 稀疏矩阵
稀疏矩阵ADT的实现：
在现实应用中，一些规模很大的特殊矩阵具有重要的地位。特殊矩阵可以采用二维数组存储，简单直接（顺序存储方式保持了矩阵中元素之间的二维线性关系），矩阵操作的算法都很简单，但是其空间的利用率很低（因为重复元素或零元素比较多）。 稀疏矩阵就是一种应用很广泛的特殊的矩阵，在实现稀疏矩阵ADT时通常采用“压缩”存储方案，即把只存储稀疏矩阵的非零元素，把稀疏矩阵抽象成为一个以三元组（行，列，值）为数据元素的线性表来处理，而我们知道：线性表可以采用顺序存储，也可以采用链式存储（通常用十字链表）。
现要求编程实现稀疏矩阵在“压缩”存储时的常用操作，如输出、转置、求和、乘等。（注：在代码注释中说明你采用的存储结构）
需要输入两个矩阵，完成：
(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: 按人们习惯的矩阵格式输出，即输出一个m*n的矩阵，是零元素的输出0，非零元素输出元素值。设定每个元素占位宽度为4。（要输出行号和列号，并对齐）
例如：输入如下：
10 8 4 //第1个矩阵 10行，8列，4个非零元素
1 8 1 //第1行第8列元素值为1
3 3 2 //第3行第3列元素值为2
3 7 3 //第3行第7列元素值为3
10 1 4 //第10行第1列元素值为4
10 8 2 //第2个矩阵 10行，8列，2个非零元素
2 6 1 //第2行第6列元素值为1
3 7 -3 //第3行第7列元素值为-3
H //输出格式类别
输出如下：
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!
再如，输入矩阵如下：
100 90 5 //矩阵的行数为100，列数为90，共5个非零元素。
1 10 100 //a(1,10)=100
50 60 200 //a(50,60)=200
50 80 100 //a(50,80)=100
60 60 200 //a(60,60)=200
99 89 10 //a(99,89)=10
100 90 4 //矩阵b的行数为100，列数为90，共4个非零元素。
1 1 10 //b(1,1)=10
50 60 -200 //b(50,60)=-200
50 80 100 //b(50,80)=100
70 70 10 //b(70,70)=10
L
输出如下：
The transformed matrix is:
Rows=100,Cols=90,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!
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define per(i , a , b) for(register int i=(a);i>=(b);i--)
#define ms(s) memset(s, 0, sizeof(s))
#define squ(x) (x)*(x)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int , int> pi;
const int maxn = 1e6+10;
struct mat{
int x,y;
int z;
}a[maxn],b[maxn],c[maxn];
map<pi ,int>mp;
map<pi ,int>::iterator it;
bool vis[maxn];
int r1,c1,r2,c2,cnt1,cnt2;
int r3,c3,cnt3;
char op[4];
bool cmp(mat A,mat B) {
if(A.x!=B.x) return A.x<B.x;
if(A.y!=B.y) return A.y<B.y;
return A.z<B.z;
}
template<class T>
inline void read (T &x) {
x = 0;
int sign = 1;
char c = getchar ();
while (c < '0' || c > '9') {
if ( c == '-' ) sign = - 1;
c = getchar ();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar ();
}
x = x * sign;
}
void print1() {
printf ("Rows=%d,Cols=%d,r=%d\n",r3,c3,cnt3);
rep(i,1,cnt3) {
printf ("%d %d %d\n",c[i].x,c[i].y,c[i].z);
}
}
void print2() {
printf (" ");
rep(i,1,c3) {
printf ("%4d",i);
}
printf ("\n");
rep(i,1,r3) {
rep(j,0,c3) {
if(j==0) {
printf ("%4d",i);
continue;
}
int tmp=0;
if(!mp.count ({i,j})) printf ("%4d",tmp);
else {
tmp = mp[{i,j}];
printf ("%4d",tmp);
}
}
printf ("\n");
}
}
void add() {
ms (vis);
mp.clear ();
r3=r1;c3=c1;cnt3=0;
rep(i,1,cnt1) {
int x = a[i].x,y = a[i].y,z = a[i].z;
rep(j,1,cnt2) {
if(x==b[j].x&&y==b[j].y) {
z+=b[j].z;
vis[j]=1;
}
}
if(z==0) continue;
else {
c[++cnt3].z=z;
c[cnt3].x=x;
c[cnt3].y=y;
mp[{x,y}]=z;
}
}
rep(i,1,cnt2) {
if(vis[i]) continue;
if(b[i].z==0) continue;
c[++cnt3].z=b[i].z;
c[cnt3].x=b[i].x;
c[cnt3].y=b[i].y;
mp[{c[cnt3].x,c[cnt3].y}]=c[cnt3].z;
}
sort(c+1,c+1+cnt3,cmp);
printf ("The added matrix is:\n");
if(op[0]=='L') {
print1();
} else {
print2();
}
}
void mul() {
ms(vis);mp.clear ();
r3=r1;c3=c2;cnt3=0;
rep(i,1,cnt1) {
int x = a[i].x,y=a[i].y,z=a[i].z;
rep(j,1,cnt2) {
if(y==b[j].x) {
int tmp=z*b[j].z;
mp[{x,b[j].y}]+=tmp;
}
}
}
for(it=mp.begin ();it!=mp.end ();it++) {
pi p = (*it).first;
int z = (*it).second;
if(z==0) continue;
c[++cnt3].z=z;
c[cnt3].x=p.first;
c[cnt3].y=p.second;
}
sort (c+1,c+1+cnt3,cmp);
printf ("The product matrix is:\n");
if(op[0]=='L') {
print1 ();
}
else print2 ();
}
void tr() {
r3=c1;c3=r1;cnt3=0;
ms(vis);
rep(i,1,cnt1) {
if(a[i].z==0) {
continue;
}
c[++cnt3].x=a[i].y;
c[cnt3].y=a[i].x;
c[cnt3].z=a[i].z;
mp[{c[cnt3].x,c[cnt3].y}]=c[cnt3].z;
}
sort (c+1,c+1+cnt3,cmp);
printf ("The transformed matrix is:\n");
if(op[0]=='L') {
print1 ();
}
else print2 ();
mp.clear ();
}
int main(int argc, char * argv[])
{
read (r1);read (c1);read (cnt1);
rep(i,1,cnt1) {
read(a[i].x);read(a[i].y);read (a[i].z);
}
read (r2);read (c2);read (cnt2);
rep(i,1,cnt2) {
read(b[i].x);read(b[i].y);read(b[i].z);
}
scanf("%s",op);
sort(a+1,a+1+cnt1,cmp);
sort(b+1,b+1+cnt2,cmp);
tr();
if(r1==r2&&c1==c2) {
add();
}
else {
printf ("Can not add!\n");
}
if(c1==r2) {
mul();
}
else {
printf ("Can not multiply!\n");
}
return 0;
}