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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include <stdio.h>
#define MAXSIZE 12500
#define MAXRC 100
#define ElemType int
typedef struct {
int i,j;//行，列
ElemType e;//元素值
} Triple;
typedef struct {
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];//每行第一个非零元素在 data 数组中的位置
int mu,nu,tu;//行数，列数，元素个数
} RLSMatrix;
RLSMatrix MultSMatrix(RLSMatrix A, RLSMatrix B, RLSMatrix C) {
//如果矩阵 A 的列数与矩阵 B 的行数不等，则不能做矩阵乘运算
if(A.nu != B.mu)
return C;
C.mu = A.mu;
C.nu = B.nu;
C.tu = 0;
//如果其中任意矩阵的元素个数为零，做乘法元素没有意义，全是 0
if(A.tu * B.tu == 0)
return C;
else {
int arow;
int ccol;
//遍历矩阵 A 的每一行
for(arow=1; arow<=A.mu; arow++) {
//创建一个临时存储乘积结果的数组，且初始化为 0，遍历每次都需要清空
int ctemp[MAXRC+1] = {};
C.rpos[arow] = C.tu + 1;
//根据行数，在三元组表中找到该行所有的非 0 元素的位置
int tp;
if(arow < A.mu)
tp = A.rpos[arow+1];//获取矩阵 A 的下一行第一个非零元素在 data 数组中位置
else
tp = A.tu+1;//若当前行是最后一行，则取最后一个元素+1
int p;
int brow;
//遍历当前行的所有的非 0 元素
for(p=A.rpos[arow]; p<tp; p++) {
brow = A.data[p].j;//取该非 0 元素的列数，便于去 B 中找对应的做乘积的非 0 元素
int t;
// 判断如果对于 A 中非 0 元素，找到矩阵 B 中做乘法的那一行中的所有的非 0 元素
if(brow < B.mu)
t = B.rpos[brow+1];
else
t = B.tu+1;
int q;
//遍历找到的对应的非 0 元素，开始做乘积运算
for(q=B.rpos[brow]; q<t; q++) {
//得到的乘积结果，每次和 ctemp 数组中相应位置的数值做加和运算
ccol = B.data[q].j;
ctemp[ccol] += A.data[p].e * B.data[q].e;
}
}
//矩阵 C 的行数等于矩阵 A 的行数，列数等于矩阵 B 的列数，所以，得到的 ctemp 存储的结果，也会在 C 的列数的范围内
for(ccol=1; ccol<=C.nu; ccol++) {
//由于结果可以是 0，而 0 不需要存储，所以在这里需要判断
if(ctemp[ccol]) {
//不为 0，则记录矩阵中非 0 元素的个数的变量 tu 要+1；且该值不能超过存放三元素数组的空间大小
if(++C.tu > MAXSIZE)
return C;
else {
C.data[C.tu].e = ctemp[ccol];
C.data[C.tu].i = arow;
C.data[C.tu].j = ccol;
}
}
}
}
return C;
}
}
int main(int argc, char* argv[]) {
RLSMatrix M,N,T;
M.tu = 4;
M.mu = 3;
M.nu = 4;
M.rpos[1] = 1;
M.rpos[2] = 3;
M.rpos[3] = 4;
M.data[1].e = 3;
M.data[1].i = 1;
M.data[1].j = 1;
M.data[2].e = 5;
M.data[2].i = 1;
M.data[2].j = 4;
M.data[3].e = -1;
M.data[3].i = 2;
M.data[3].j = 2;
M.data[4].e = 2;
M.data[4].i = 3;
M.data[4].j = 1;
N.tu = 4;
N.mu = 4;
N.nu = 2;
N.rpos[1] = 1;
N.rpos[2] = 2;
N.rpos[3] = 3;
N.rpos[4] = 5;
N.data[1].e = 2;
N.data[1].i = 1;
N.data[1].j = 2;
N.data[2].e = 1;
N.data[2].i = 2;
N.data[2].j = 1;
N.data[3].e = -2;
N.data[3].i = 3;
N.data[3].j = 1;
N.data[4].e = 4;
N.data[4].i = 3;
N.data[4].j = 2;
T= MultSMatrix(M,N,T);
for (int i=1; i<=T.tu; i++) {
printf("(%d,%d,%d)\n",T.data[i].i,T.data[i].j,T.data[i].e);
}
return 0;
}
|