已知稀疏矩阵用三元组表示,编写c=a*b的算法。
时间: 2023-06-05 15:47:46 浏览: 133
已知稀疏矩阵用三元组表示编写C=A*B的算法。
4星 · 用户满意度95%
算法步骤如下:
1. 首先判断矩阵a和矩阵b是否可以相乘,即a的列数是否等于b的行数,如果不相等则无法相乘,返回错误信息。
2. 创建一个新的稀疏矩阵c,用三元组表示。
3. 遍历矩阵a的每一行,对于每一行中的非零元素,遍历矩阵b的对应列,对于每一列中的非零元素,将它们的乘积累加到c的对应位置上。
4. 返回稀疏矩阵c。
代码实现如下:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int row;
int col;
int value;
} Triple;
typedef struct {
Triple data[MAX_SIZE];
int rows;
int cols;
int nums;
} SparseMatrix;
SparseMatrix matrix_multiply(SparseMatrix a, SparseMatrix b) {
SparseMatrix c;
int i, j, k, sum;
if (a.cols != b.rows) {
printf("Error: cannot multiply matrices.\n");
exit(1);
}
c.rows = a.rows;
c.cols = b.cols;
c.nums = 0;
for (i = 1; i <= a.rows; i++) {
for (j = 1; j <= b.cols; j++) {
sum = 0;
for (k = 1; k <= a.nums; k++) {
if (a.data[k].row == i) {
int p;
for (p = 1; p <= b.nums; p++) {
if (b.data[p].col == j && a.data[k].col == b.data[p].row) {
sum += a.data[k].value * b.data[p].value;
break;
}
}
}
}
if (sum != 0) {
c.nums++;
c.data[c.nums].row = i;
c.data[c.nums].col = j;
c.data[c.nums].value = sum;
}
}
}
return c;
}
int main() {
SparseMatrix a = {
.data = {
{1, 1, 2},
{1, 3, 1},
{2, 2, 3},
{3, 1, 4},
{3, 3, 5}
},
.rows = 3,
.cols = 3,
.nums = 5
};
SparseMatrix b = {
.data = {
{1, 2, 1},
{2, 1, 2},
{2, 3, 3},
{3, 2, 4}
},
.rows = 3,
.cols = 3,
.nums = 4
};
SparseMatrix c = matrix_multiply(a, b);
int i;
for (i = 1; i <= c.nums; i++) {
printf("(%d, %d, %d) ", c.data[i].row, c.data[i].col, c.data[i].value);
}
printf("\n");
return 0;
}
```
阅读全文