矩阵相加的算法（存储结构为三元组表）

109 阅读 0 评论 72 点赞

我是靠谱客的博主受伤裙子，这篇文章主要介绍矩阵相加的算法（存储结构为三元组表），现在分享给大家，希望可以做个参考。

假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

稀疏矩阵的三元组顺序表类型TSMatrix的定义：

复制代码

1
2
3
4
5
6
7
8
9
10
11
#define MAXSIZE 20 // 非零元个数的最大值
typedef struct {
int
i,j; // 行下标,列下标
ElemType e; // 非零元素值
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;

实现函数如下：

复制代码

Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵加法: C=A+B */
{
int ai,bi,ci,aj,bj,cj,ap,bp,cp;
ap = bp = cp = 1;
if(A.mu != B.mu || A.nu != B.nu){
return ERROR;
}
C.mu = A.mu;
C.nu = A.nu;
while(ap <= A.tu && bp <= B.tu){
ai = A.data[ap].i;
bi = B.data[bp].i;
if(ai > bi){
ci = bi;
while(ci == B.data[bp].i){
C.data[cp].i = ci;
C.data[cp].j = B.data[bp].j;
C.data[cp].e = B.data[bp].e;
++bp;
++cp;
}
}else if(ai < bi){
ci = ai;
while(ci == A.data[ap].i){
C.data[cp].i = ci;
C.data[cp].j = A.data[ap].j;
C.data[cp].e = A.data[ap].e;
++ap;
++cp;
}
}else if(ai == bi){
ci = ai;
aj = A.data[ap].j;
bj = B.data[bp].j;
if(aj > bj){
C.data[cp].i = ci;
C.data[cp].j = bj;
C.data[cp].e = B.data[bp].e;
++cp;
++bp;
}else if(aj < bj){
C.data[cp].i = ci;
C.data[cp].j = aj;
C.data[cp].e = A.data[ap].e;
++cp;
++ap;
}else if(aj == bj){
if(A.data[ap].e + B.data[bp].e != 0){
C.data[cp].i = ci;
C.data[cp].j = aj;
C.data[cp].e = A.data[ap].e + B.data[bp].e;
++cp;
}
++ap;
++bp;
}
}
}
//以上为稀疏矩阵A或B中的元素完全加完的情况
//以下为稀疏矩阵A或B中的元素部分剩余的情况
while(ap <= A.tu){
C.data[cp].i = A.data[ap].i;
C.data[cp].j = A.data[ap].j;
C.data[cp].e = A.data[ap].e;
++cp;
++ap;
}
while(bp <= B.tu){
C.data[cp].i = B.data[bp].i;
C.data[cp].j = B.data[bp].j;
C.data[cp].e = B.data[bp].e;
++cp;
++bp;
}
C.tu = --cp;
return OK;
}

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
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵加法: C=A+B */
{
int ai,bi,ci,aj,bj,cj,ap,bp,cp;
ap = bp = cp = 1;
if(A.mu != B.mu || A.nu != B.nu){
return ERROR;
}
C.mu = A.mu;
C.nu = A.nu;
while(ap <= A.tu && bp <= B.tu){
ai = A.data[ap].i;
bi = B.data[bp].i;
if(ai > bi){
ci = bi;
while(ci == B.data[bp].i){
C.data[cp].i = ci;
C.data[cp].j = B.data[bp].j;
C.data[cp].e = B.data[bp].e;
++bp;
++cp;
}
}else if(ai < bi){
ci = ai;
while(ci == A.data[ap].i){
C.data[cp].i = ci;
C.data[cp].j = A.data[ap].j;
C.data[cp].e = A.data[ap].e;
++ap;
++cp;
}
}else if(ai == bi){
ci = ai;
aj = A.data[ap].j;
bj = B.data[bp].j;
if(aj > bj){
C.data[cp].i = ci;
C.data[cp].j = bj;
C.data[cp].e = B.data[bp].e;
++cp;
++bp;
}else if(aj < bj){
C.data[cp].i = ci;
C.data[cp].j = aj;
C.data[cp].e = A.data[ap].e;
++cp;
++ap;
}else if(aj == bj){
if(A.data[ap].e + B.data[bp].e != 0){
C.data[cp].i = ci;
C.data[cp].j = aj;
C.data[cp].e = A.data[ap].e + B.data[bp].e;
++cp;
}
++ap;
++bp;
}
}
}
//以上为稀疏矩阵A或B中的元素完全加完的情况
//以下为稀疏矩阵A或B中的元素部分剩余的情况
while(ap <= A.tu){
C.data[cp].i = A.data[ap].i;
C.data[cp].j = A.data[ap].j;
C.data[cp].e = A.data[ap].e;
++cp;
++ap;
}
while(bp <= B.tu){
C.data[cp].i = B.data[bp].i;
C.data[cp].j = B.data[bp].j;
C.data[cp].e = B.data[bp].e;
++cp;
++bp;
}
C.tu = --cp;
return OK;
}