rendered paste body#include<malloc.h>
#include<stdio.h>
#define MAX 9
int getCnt(int p[][3],int r,int c);
int** getSparse(int cnt);
int** consSparse(int mat[][3],int r,int c);
void fillSparse(int mat[][3],int r,int c,int **sp,int cnt);
void print(int mat[][3],int r,int c);
void printSparse(int **sp,int cnt);
int** ConsAddSparse(int mat1[][3],int mat2[][3],int r,int c,int *num);
int** ConsProdSparse(int mat1[][3],int mat2[][3],int r,int c,int *num);
int main()
{
int a[3][3] = {{1,0,7},{0,0,8},{9,0,0}};
int b[3][3] = {{0,0,8},{1,0,3},{0,4,5}};
int **aS,**bS,**sum,**prod,cnt=0;
//Print A and its Sparse
print(a,3,3);
printf("\n------ \n");
print(b,3,3);
//sum = ConsAddSparse(a,b,3,3,&cnt);
prod = ConsProdSparse(a,b,3,3,&cnt);
getchar();
return 0;
}
int getCnt(int p[][3],int r,int c)
{
int cnt = 0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
if(p[i][j] != 0 )
cnt++;
}
return cnt;
}
int** getSparse(int cnt)
{
int **sp,i=0,j=0;
sp = (int**) malloc(sizeof(int) * cnt);
for(i=0;i<cnt;i++)
sp[i] = (int*)malloc(sizeof(int) * 3);
for(i=0;i<cnt;i++)
{
for(j=0;j<3;j++)
sp[i][j] = 0;
}
printf("\n\t Init Sparse Filled..\n");
return sp;
}
void fillSparse(int mat[][3],int r,int c,int** sp,int cnt)
{
int flag=0,ind =0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(mat[i][j] != 0 )
{
sp[ind][0] = i;
sp[ind][1] = j;
sp[ind][2] = mat[i][j];
ind++;
}
if(ind >= cnt)
{
flag = 1;
break;
}
}
if(flag == 1)
break;
}
printf("\n\t Sparse Filled..\n");
return;
}
int** consSparse(int mat[][3],int r,int c)
{
int cnt = getCnt(mat,r,c);
int **sp;
sp = getSparse(cnt);
printf(" \n Cnt = %d \n",cnt);
fillSparse(mat,r,c,sp,cnt);
printSparse(sp,cnt);
}
void printSparse(int **sp,int cnt)
{
printf("\n-------------------\n");
for(int i=0;i<cnt;i++)
{
for(int j=0;j<3;j++)
printf("%d ",sp[i][j]);
printf("\n");
}
}
void print(int mat[][3],int r,int c)
{
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
printf("%d ",mat[i][j]);
printf("\n");
}
}
int** ConsAddSparse(int mat1[][3],int mat2[][3],int r,int c,int *num)
{
int cnt1 = getCnt(mat1,r,c);
int cnt2 = getCnt(mat2,r,c);
int **asp,**bsp,**sum,k=0,ind1=0,ind2=0;
printf(" \n Cnt1 = %d \n",cnt1);
printf(" \n Cnt2 = %d \n",cnt2);
asp = getSparse(cnt1);
bsp = getSparse(cnt2);
fillSparse(mat1,r,c,asp,cnt1);
fillSparse(mat2,r,c,bsp,cnt2);
printSparse(asp,cnt1);
printSparse(bsp,cnt2);
sum = getSparse(cnt1+cnt2);
//Check for Common i and j
ind1 = 0;
ind2 = 0;
k = 0;
while(1)
{
printf("\n\t\tSt : Ind1 : %d Ind2 : %d \n",ind1,ind2);
if((ind1 == cnt1) & (ind2 == cnt2))
break;
else if ((ind1 >= cnt1) && (ind2 < cnt2) )
{
printf("\n\t\t >> Mat 2 %d ",cnt2);
for(;ind2 != cnt2;ind2++)
{
sum[k][0] = bsp[ind2][0];
sum[k][1] = bsp[ind2][1];
sum[k][2] = bsp[ind2][2];
k++;
}
break;
}
else if ((ind2 >= cnt2) && (ind1 < cnt1) )
{
printf("\n\t\t >> Mat 1 %d ",cnt1);
for(;ind1<cnt1;ind1++)
{
sum[k][0] = asp[ind1][0];
sum[k][1] = asp[ind1][1];
sum[k][2] = asp[ind1][2];
k++;
}
break;
}
else
{
if((asp[ind1][0] == bsp[ind2][0]) && (asp[ind1][1] == bsp[ind2][1]))
{
sum[k][0] = asp[ind1][0];
sum[k][1] = asp[ind1][1];
sum[k][2] = asp[ind1][2] + bsp[ind2][2];
ind1++;
ind2++;
k++;
}
else if( (asp[ind1][0] < bsp[ind2][0]) || ( (asp[ind1][0] == bsp[ind2][0]) && (asp[ind1][1] < bsp[ind2][1]) ) )
{
sum[k][0] = asp[ind1][0];
sum[k][1] = asp[ind1][1];
sum[k][2] = asp[ind1][2];
ind1++;
k++;
}
else if( (asp[ind1][0] > bsp[ind2][0]) || ( (asp[ind1][0] == bsp[ind2][0]) && (asp[ind1][1] > bsp[ind2][1]) ) )
{
sum[k][0] = bsp[ind2][0];
sum[k][1] = bsp[ind2][1];
sum[k][2] = bsp[ind2][2];
ind2++;
k++;
}
}
printf("\n\t\t\tEnd : Ind1 : %d Ind2 : %d \n",ind1,ind2);
}
printSparse(sum,k);
return sum;
}
int** ConsProdSparse(int mat1[][3],int mat2[][3],int r,int c,int *num)
{
int cnt1 = getCnt(mat1,r,c);
int cnt2 = getCnt(mat2,r,c);
int **asp,**bsp,**prod,flag =0,k=0,i=0,j=0,l;
printf(" \n Cnt1 = %d \n",cnt1);
printf(" \n Cnt2 = %d \n",cnt2);
asp = getSparse(cnt1);
bsp = getSparse(cnt2);
fillSparse(mat1,r,c,asp,cnt1);
fillSparse(mat2,r,c,bsp,cnt2);
printSparse(asp,cnt1);
printSparse(bsp,cnt2);
prod = getSparse(MAX);
for(i=0;i<cnt1;i++)
{
for(j=0;j<cnt2;j++)
{
if (asp[i][1] == bsp[j][0])
{
flag = 0;
for(l=0;l<k;l++)
{
if((prod[l][0] == asp[i][0]) && (prod[l][1] == bsp[j][1]))
{
flag = 1;
break;
}
}
if(!flag)
{
prod[k][0] = asp[i][0];
prod[k][1] = bsp[j][1];
prod[k][2] = (asp[i][2] * bsp[j][5]);
k++;
}
else
prod[l][2] += (asp[i][2] * bsp[j][2]);
}
}
}
printSparse(prod,k);
return prod;
}