1// Aim: Program to perform Sparse Matrix Addition.
2#include<stdio.h>
3
4void display(int x[10][3]){
5    int i,j;
6    printf("Sparse matrix representation\n");
7    for(i=0;i<=x[0][2];i++){
8        for(j=0;j<3;j++){
9            printf("%d  \t",x[i][j]);
10        }
11        printf("\n");
12    }
13}
14
15void read(int a[10][10], int s[10][3], int m, int n){
16    int i,j,k=1;
17    s[0][0]=m;
18    s[0][1]=n;
19    for(i=0;i<m;i++){
20        for(j=0;j<n;j++){
21            if(a[i][j]!=0){
22                s[k][0]=i;
23                s[k][1]=j;
24                s[k][2]=a[i][j];
25                k++;
26            }
27        }
28    }
29    s[0][2] = k - 1; 
30}
31
32void add(int a[10][3], int b[10][3], int s[10][3]){
33    int i=1,j=1,k=1;
34    if(a[0][0]!=b[0][0] || a[0][1]!=b[0][1]){
35        printf("Matrix size mismatch\n");
36        return;
37    }
38    s[0][0] = a[0][0];
39    s[0][1] = a[0][1];
40    while(i <= a[0][2] && j <= b[0][2]){
41        if(a[i][0] < b[j][0] || (a[i][0] == b[j][0] && a[i][1] < b[j][1])){
42            s[k][0] = a[i][0];
43            s[k][1] = a[i][1];
44            s[k][2] = a[i][2];
45            i++;
46        } else if(a[i][0] > b[j][0] || (a[i][0] == b[j][0] && a[i][1] > b[j][1])){
47            s[k][0] = b[j][0];
48            s[k][1] = b[j][1];
49            s[k][2] = b[j][2];
50            j++;
51        } else {
52            s[k][0] = a[i][0];
53            s[k][1] = a[i][1];
54            s[k][2] = a[i][2] + b[j][2];
55            i++;
56            j++;
57        }
58        k++;
59    }
60    while(i <= a[0][2]){
61        s[k][0] = a[i][0];
62        s[k][1] = a[i][1];
63        s[k][2] = a[i][2];
64        i++;
65        k++;
66    }
67    while(j <= b[0][2]){
68        s[k][0] = b[j][0];
69        s[k][1] = b[j][1];
70        s[k][2] = b[j][2];
71        j++;
72        k++;
73    }
74    s[0][2] = k - 1; // Number of non-zero elements
75}
76
77int main(){
78    int a[10][10], b[10][10], s1[10][3], s2[10][3], sum[10][3];
79    int m, n, i, j;
80
81    printf("Enter the number of rows and columns of the matrices: ");
82    scanf("%d %d", &m, &n);
83
84    printf("Enter the elements of the first matrix:\n");
85    for(i=0; i<m; i++){
86        for(j=0; j<n; j++){
87            scanf("%d", &a[i][j]);
88        }
89    }
90
91    printf("Enter the elements of the second matrix:\n");
92    for(i=0; i<m; i++){
93        for(j=0; j<n; j++){
94            scanf("%d", &b[i][j]);
95        }
96    }
97
98    read(a, s1, m, n);
99    read(b, s2, m, n);
100
101    add(s1, s2, sum);
102
103    printf("First matrix in sparse form:\n");
104    display(s1);
105
106    printf("Second matrix in sparse form:\n");
107    display(s2);
108
109    printf("Sum of matrices in sparse form:\n");
110    display(sum);
111
112    return 0;
113}