稀疏矩阵的乘法运算 | C++ | 稀疏矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h> 
using namespace std;
const int N = 10010;

typedef struct {
	int row, col, data;
} elem;
typedef struct {
	elem *element = (elem*) malloc ( N*sizeof(elem) ) ;
	int ROW, COL, NZRO=0;
} Triplet;

//输出
void printC(Triplet C) {
	printf("%dn%dn%dn",C.ROW,C.COL,C.NZRO);
	for (int i=0; i<C.ROW*C.COL; i++) {
		if (C.element[i].data!=0) {
			printf("%d,%d,%dn",C.element[i].row+1,C.element[i].col+1,C.element[i].data);
		}
	}
}


int main(){
	
	void printC(Triplet);
	Triplet A,B,C;

	//第一个稀疏矩阵A
	scanf("%d %d %d",&A.ROW,&A.COL,&A.NZRO);
	for (int i=0; i<A.NZRO; i++) {
		scanf("%d %d %d",&A.element[i].row,&A.element[i].col,&A.element[i].data);
		A.element[i].row--; A.element[i].col--;
	}
    //补充说明：题目读入的矩阵下标从1开始，而我是从0开始，所以这里对row和col都进行-1的操作。下面的B同理。

	//第二个稀疏矩阵B
	scanf("%d %d %d",&B.ROW,&B.COL,&B.NZRO);
	for (int i=0; i<B.NZRO; i++) {
		scanf("%d %d %d",&B.element[i].row,&B.element[i].col,&B.element[i].data);
		B.element[i].row--; B.element[i].col--;
	}

	//第三个矩阵C
	C.ROW = A.ROW;	C.COL = B.COL;  
	
    //初始化第三个矩阵 
	for (int i=0; i<C.ROW; i++) {
		for (int j=0; j<C.COL; j++) {
			C.element[ i*C.COL+j ].data = 0;
			C.element[ i*C.COL+j ].row  = i; 
			C.element[ i*C.COL+j ].col  = j;
		}
	}

    //计算过程在这里
	for (int i=0; i<A.NZRO; i++) {
		for (int j=0; j<B.NZRO; j++) {
			int d = 0;
			if (A.element[i].col==B.element[j].row) 
				d = A.element[i].data * B.element[j].data; //d是乘法计算的结果
			
			//如果d不为0，则将其加到相应的位置上
			if (d!=0) {
				C.element[ A.element[i].row*C.COL+B.element[j].col ].data += d; 
				if ( C.element[A.element[i].row*C.COL+B.element[j].col].data==0 ) C.NZRO--;
				else if ( C.element[A.element[i].row*C.COL+B.element[j].col].data==d ) C.NZRO++;
			}
		}
	}
	
	printC(C);
	
	return 0;
}