write an algorithm for addition of two sparse matrix
Answers
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
void printsparse(int b[MAX][3]);
void readsparse(int b[MAX][3]);
void addsparse(int b1[MAX][3],int
b2[MAX][3],int b3[MAX][3]);
void main()
{
int b1[MAX][3],b2[MAX][3],b3[MAX][3];
readsparse(b1);
readsparse(b2);
addsparse(b1,b2,b3);
printsparse(b3);
}
void readsparse(int b[MAX][3])
{
int i,t,m,n;
printf(“nEnter no. of rows and columns:”);
scanf(“%d%d”,&m,&n);
printf(“No. of non-zero triples:”);
scanf(“%d”,&t);
b[0][0]=m;
b[0][1]=n;
b[0][2]=t;
for(i=1;i<=t;i++)
{
printf(“Enter the triples(row,column,value):”);
scanf(“%d%d%d”,&b[i][0],&b[i][1],&b[i][2]);
}
}
void addsparse(int b1[MAX][3],int
b2[MAX][3],int b3[MAX][3])
{
int t1,t2,i,j,k;
if(b1[0][0]!=b2[0][0]||b1[0][1]!=b2[0][1])
{
printf(“nYou have entered invalid matrix!!Size must be
equal”);
exit(0);
}
t1=b1[0][2];
t2=b2[0][2];
i=j=k=0;
b3[0][0]=b1[0][0];
b3[0][1]=b1[0][1];
while(i<=t1&&j<=t2)
{
if(b1[i][0]<b2[j][0])
//row numbers are not equal
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
k++;
i++;
}
else if(b2[j][0]<b1[i][0])
//row numbers are not equal
{
b3[k][0]=b2[j][0];
b3[k][1]=b2[j][1];
b3[k][2]=b2[j][2];
k++;
j++;
}
else if(b1[i][1]<b2[j][1])
//row numbers are equal, compare column
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
k++;
i++;
}
else if(b2[j][1]<b1[i][1])
//row numbers are equal, compare column
{
b3[k][0]=b2[j][0];
b3[k][1]=b2[j][1];
b3[k][2]=b2[j][2];
k++;
j++;
}
else
{
b3[k][0]=b1[i][0]; //row and
column numbers are equal
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2]+b2[j][2];
k++;
i++;
j++;
}
}
while(i<=t1) //copy
remaining terms from b1
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
i++;
k++;
}
while(j<=t2) //copy
remaining terms from b2
{
b3[k][0]=b2[j][0];
b3[k][1]=b1[j][1];
b3[k][2]=b1[j][2];
j++;
k++;
}
b3[0][2]=k-1; //set number
of terms in b3
}
void printsparse(int b[MAX][3])
{
int i,t;
t=b[0][2];
printf(“nrowtcolumntvalue”);
for(i=1;i<=t;i++)
{
printf(“n%dt%dt%d”,b[i][0],b[i][1],b[i][2]);
}
}
Algorithm for addition of two sparse matrix:
Sparse_Matrix_Addition(A, B, AROW, BROW, ACOL, BCOL, m, n)
* m,n are number of rows and columns in the matrix
* A is the array containing non-zero elements of first matrix
* B is the array containing non-zero elements of second matrix
* C is the array containing non-zero elements of resultant matrix
* AROW is the row array of first sparse matrix
* BROW is the row array of second sparse matrix
* CROW is the row array of resultant sparse matrix
* ACOL is the column array of first sparse matrix
* BCOL is the column array of second sparse matrix
* CCOL is the column array of resultant sparse matrix
1. Begin
2. n = 1
3. ia = ib = ic = ja = jb = jc = 1
4. Repeat while (ia <= m)
5. if(AROW[ia] == 0 AND BROW[ib] ==0)
6. CROW[ic++] = 0
7. end if
8. else if(AROW[ia] == 0)
9. BMAX = BROW[ib++] – 1
10. CROW[ic++] = n
11. Repeat while(jb <= BMAX)
12. CCOL[jc] = BCOL[jb]
13. C[jc++] = B[jb++]
14. n++
15. end Repeat
16. end else if
17. else if(BROW[ib] == 0)
18. AMAX = AROW[ia++] – 1
19. CROW[ic++] = n
20. Repeat while(ja <= AMAX)
21. CCOL[jc] = ACOL[jb]
22. C[jc++] = A[ja++]
23. n++
24. end Repeat
25. end else if
26. else
27. AMAX = AROW[ia++] – 1
28. BMAX = BROW[ib++] – 1
29. Repeat while(ja <= AMAX and jb <= BMAX)
30. CROW[ic++] = n
31. if(ACOL[ja] == BCOL[jb])
32. C[jc] = A[ja] + B[jb++]
33. CCOL[jc++] = ACOL[ja++]
34. n++
35. end if
36. else if(ACOL[ja] < BCOL[jb])
37. C[jc] = A[ja]
38. CCOL[jc++] = ACOL[ja++]
39. n++
40. end else if
41. else
42. C[jc] = B[jb]
43. CCOL[jc++] = BCOL[jb++]
44. n++
45. end else if
46. end Repeat
47. Repeat while (ja <=AMAX)
48. C[jc] = A[ja]
49. CCOL[jc++] = ACOL[ja++]
50. n++
51. end Repeat
52. Repeat while (jb <=BMAX)
53. C[jc] = B[jb]
54. CCOL[jc++] =BCOL[jb++]
55. n++
56. end Repeat
57. end else
58. ia++
59. ib++
60. end Repeat
61. end Sparse_Matrix_Addition