稀疏矩阵的乘法运算

题目信息

数据压缩是提高传输、存储效率一种技术。

本实验要求实现两个稀疏矩阵相乘积的算法。其中稀疏矩阵非零元素数量小于100.

输入

第1个稀疏矩阵的行数,列数,非零元个数(三个数都大于0),三元组

第2个稀疏矩阵的行数,列数,非零元个数(三个数都大于0),三元组

以行为主序输入稀疏矩阵三元组表

输出

乘积矩阵的行数

列数

非零元个数(三个数都大于0)

三元组

测试样例

3441 1 31 4 52 2 -13 1 24241 2 22 1 13 1 -23 2 4

3231,2,62,1,-13,2,4

解答

#include<stdio.h>typedef struct{int i, j;int e;} Node;typedef struct{Node nodes[105];int rpos[105];//各行第一个非零元的位置表int m, n, t;} Matrix;int main(){//freopen("/Users/zhj/Downloads/test.txt", "r", stdin);Matrix A, B;scanf("%d%d%d", &A.m, &A.n, &A.t);for (int i = 1; i <= A.t; i++){scanf("%d%d%d", &A.nodes[i].i, &A.nodes[i].j, &A.nodes[i].e);}int num[1000];for (int col = 1; col <= A.m; col++){num[col] = 0;}for (int i = 1; i <= A.t; i++){num[A.nodes[i].i]++;}A.rpos[1] = 1;for (int col = 2; col <= A.m; col++){A.rpos[col] = A.rpos[col - 1] + num[col - 1];}scanf("%d%d%d", &B.m, &B.n, &B.t);for (int i = 1; i <= B.t; i++){scanf("%d%d%d", &B.nodes[i].i, &B.nodes[i].j, &B.nodes[i].e);}for (int col = 1; col <= B.m; col++){num[col] = 0;}for (int i = 1; i <= B.t; i++){num[B.nodes[i].i]++;}B.rpos[1] = 1;for (int col = 2; col <= B.m; col++){B.rpos[col] = B.rpos[col - 1] + num[col - 1];}Matrix Q;Q.m = A.m;Q.n = B.n;Q.t = 0;//创建答案矩阵if (A.t * B.t != 0){//Q是非零矩阵for (int arow = 1; arow <= A.m; arow++){//处理A的每一行int ctemp[105] = {0};Q.rpos[arow] = Q.t + 1;int tp;//tp是下一行元素在nodes表中位置if (arow < A.m){tp = A.rpos[arow + 1];}else{tp = A.t + 1;}for (int p = A.rpos[arow]; p < tp; p++){//对当前行中每一个非零元，既从当前在nodes表中位置找到下一行元素在nodes表的位置int brow = A.nodes[p].j;//此为A表中的纵向位置值，在B表中找相应的行号即可int t;//t仍然为下一行的位置if (brow < B.m){t = B.rpos[brow + 1];}else{t = B.t + 1;}for (int q = B.rpos[brow]; q < t; q++){int ccol = B.nodes[q].j;//Q中的纵坐标是以B元素中的j来说话的ctemp[ccol] += A.nodes[p].e * B.nodes[q].e;}}for (int ccol = 1; ccol <= Q.n; ccol++){//压缩存储该行的非零元if (ctemp[ccol]){//如果此处有值的话Q.t++;//Q的非零元素多了一个Q.nodes[Q.t].i = arow;//行号为此时遍历的A的行号Q.nodes[Q.t].j = ccol;//列号为此时正在进行压缩所遍历到有值的地方Q.nodes[Q.t].e = ctemp[ccol];//累计的和拷贝过来}}}}printf("%d\n", Q.m);printf("%d\n", Q.n);printf("%d\n", Q.t);for (int i = 1; i <= Q.t; i++){printf("%d,%d,%d\n", Q.nodes[i].i, Q.nodes[i].j, Q.nodes[i].e);}return 0;}

想法

对于A中每个元素A.nodes[p](p=1,2,...,A.t),找到N中所有满足条件A.nodes[p].j = B.nodes.i的元素B.nodes[q],求得A.nodes[p].v和B.nodes[q].v的乘积.

乘积矩阵Q中每个元素的值是个累积和,这个乘积A.nodes[p].v * B.nodes[q],v只是Q[i][j]中的一部分.为便于操作,应对每个元素设一累计和的变量,其初值为零,然后扫面数组A,求得相应元素的乘积并累加到适当的求累计和的变量上