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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| #include<stdio.h>
#include<stdlib.h>
typedef struct OLNode {
int i,j,e; //矩阵三元组 i 代表行 j 代表列 e 代表当前位置的数据
struct OLNode *right,*down; //指针域 右指针 下指针
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead; //行和列链表头指针
int mu,nu,tu; //矩阵的行数,列数和非零元的个数
} CrossList;
CrossList CreateMatrix_OL(CrossList M);
CrossList AddSMatrix(CrossList M,CrossList N);
void display(CrossList M);
void main() {
CrossList M,N;
printf("输入测试矩阵 M:\n");
M=CreateMatrix_OL(M);
printf("输入测试矩阵 N:\n");
N=CreateMatrix_OL(N);
M=AddSMatrix(M,N);
printf("矩阵相加的结果为:\n");
display(M);
}
CrossList CreateMatrix_OL(CrossList M) {
int m,n,t;
int i,j,e;
OLNode *p,*q;
scanf("%d%d%d",&m,&n,&t);
M.mu=m;
M.nu=n;
M.tu=t;
if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink)))||!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink)))) {
printf("初始化矩阵失败");
exit(0);
}
for(i=1; i<=m; i++) {
M.rhead[i]=NULL;
}
for(j=1; j<=n; j++) {
M.chead[j]=NULL;
}
for(scanf("%d%d%d",&i,&j,&e); 0!=i; scanf("%d%d%d",&i,&j,&e)) {
if(!(p=(OLNode*)malloc(sizeof(OLNode)))) {
printf("初始化三元组失败");
exit(0);
}
p->i=i;
p->j=j;
p->e=e;
if(NULL==M.rhead[i]||M.rhead[i]->j>j) {
p->right=M.rhead[i];
M.rhead[i]=p;
} else {
for(q=M.rhead[i]; (q->right)&&q->right->j<j; q=q->right);
p->right=q->right;
q->right=p;
}
if(NULL==M.chead[j]||M.chead[j]->i>i) {
p->down=M.chead[j];
M.chead[j]=p;
} else {
for (q=M.chead[j]; (q->down)&& q->down->i<i; q=q->down);
p->down=q->down;
q->down=p;
}
}
return M;
}
CrossList AddSMatrix(CrossList M,CrossList N) {
OLNode * pa,*pb;
OLink * hl=(OLink*)malloc(M.nu*sizeof(OLink));
OLNode * pre=NULL;
for (int j=1; j<=M.nu; j++) {
hl[j]=M.chead[j];
}
for (int i=1; i<=M.mu; i++) {
pa=M.rhead[i];
pb=N.rhead[i];
while (pb!=NULL) {
OLNode * p=(OLNode*)malloc(sizeof(OLNode));
p->i=pb->i;
p->j=pb->j;
p->e=pb->e;
p->down=NULL;
p->right=NULL;
if (pa==NULL||pa->j>pb->j) {
if (pre==NULL) {
M.rhead[p->i]=p;
} else {
pre->right=p;
}
p->right=pa;
pre=p;
if (!M.chead[p->j]||M.chead[p->j]->i>p->i) {
p->down=M.chead[p->j];
M.chead[p->j]=p;
} else {
p->down=hl[p->j]->down;
hl[p->j]->down=p;
}
hl[p->j]=p;
} else {
if (pa->j<pb->j) {
pre=pa;
pa=pa->right;
continue;
}
if (pa->j==pb->j) {
pa->e+=pb->e;
if (pa->e==0) {
if (pre==NULL) {
M.rhead[pa->i]=pa->right;
} else {
pre->right=pa->right;
}
p=pa;
pa=pa->right;
if (M.chead[p->j]==p) {
M.chead[p->j]=hl[p->j]=p->down;
} else {
hl[p->j]->down=p->down;
}
free(p);
}
}
}
pb=pb->right;
}
}
display(M);
return M;
}
void display(CrossList M) {
printf("输出测试矩阵:\n");
printf("M:\n---------------------\ni\tj\te\n---------------------\n");
for (int i=1; i<=M.nu; i++) {
if (NULL!=M.chead[i]) {
OLink p=M.chead[i];
while (NULL!=p) {
printf("%d\t%d\t%d\n",p->i,p->j,p->e);
p=p->down;
}
}
}
}
|