//PROGRAM TO CREATE A REPRESENTATION OF SPARSE MATRIX AND 
PERFORM OPERATIONS

#include<stdio.h>
#include<conio.h>
void implement(int[][10],int,int,int[][10]);
void add(int[][10],int,int,int[][10],int[][10]);
void sub(int[][10],int,int,int[][10],int[][10]);
void transpose(int[][10],int,int[][10]);
void main()
{
int a[10][10];
int b[10][10];
int c[10][10];
int d[10][10];
int e[50][10];
int row,col,k,l,ch;
char che;
clrscr();
printf("enter the no. of rows\t:");
scanf("%d",&row);
printf("\n enter the no. of coloms\t:");
scanf("%d",&col);
printf("\n enter the elements of sparse matrix \t:");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("\n element at [%d][%d]\t",k,l);
scanf("%d",&a[k][l]);
}
}
printf("sparse matrix is \n");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("%d\t",a[k][l]);
}
printf("\n");
}
do
{
printf("\n      CYNET MENU\n");
printf("1:REPRESENTATION\n");
printf("2:ADDITION\n");
printf("3:SUBTRACTION\n");
printf("4:TRANSPOSE\n");
printf("5:EXIT\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
       implement(a,row,col,b);
       break;
case 2:

printf("\n enter the elements of second sparse matrix \t:");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("\n element at [%d][%d]\t",k,l);
scanf("%d",&c[k][l]);
}
}
printf("sparse matrix is \n");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("%d\t",c[k][l]);
}
printf("\n");
}
implement(a,row,col,b);
implement(c,row,col,d);
add(b,row,col,d,e);
       break;
case 3:
printf("\n enter the elements of second sparse matrix \t:");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("\n element at [%d][%d]\t",k,l);
scanf("%d",&c[k][l]);
}
}
printf("sparse matrix is \n");
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
printf("%d\t",c[k][l]);
}
printf("\n");
}
implement(a,row,col,b);
implement(c,row,col,d);
sub(b,row,col,d,e);
       break;
case 4:
       implement(a,row,col,b);
       transpose(b,col,c);
       break;

case 5:
       exit();
default:
	printf("you entered wrong choice\n");
}
printf("do you want to continue(y\Y):");
che=getche();
//clrscr();
}while(che=='y'||che=='Y');
getch();
}
void implement(int a[][10],int row,int col,int b[][10])
{
int g=1,nz=0,k,l;
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
if(a[k][l]!=0)
{
nz=nz+1;
}
}
}
b[0][0]=row;
b[0][1]=col;
b[0][2]=nz;
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
if(a[k][l]!=0)
{
b[g][0]=k;
b[g][1]=l;
b[g][2]=a[k][l];
g++;
}
}
}
printf("implementation of sparse matrix is\n");
for(k=0;k<g;k++)
{
for(l=0;l<3;l++)
{
printf("%d\t",b[k][l]);
}
printf("\n");
}
}
void add(int b[][10],int row,int col,int d[][10],int e[]
[10])
{
int p1=1,p2=1,i=1;
int k,l;
if(b[0][0]!=d[0][0])
{
printf("addition is not possible\n");
}
else
{
while(p1<=b[0][2]&&p2<=d[0][2])
{
if(b[p1][0]==d[p2][0])
{
 if(b[p1][1]<d[p2][1])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
else if(b[p1][1]>d[p2][1])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  else if(b[p1][1]==d[p2][1])
  {
  e[i][0]=d[p1][0];
  e[i][1]=d[p1][1];
  e[i][2]=b[p1][2]+d[p2][2];
  if(e[i][2]!=0)
  {
   i++;
    }
    p1++;
    p2++;
  }

  }
  else if(b[p1][0]<d[p2][0])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
  else if(b[p1][0]>d[p2][0])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  }
  if(p1!=b[0][2])
  {
  while(p1<=b[0][2])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
  }
  else if(p2!=d[0][2])
  {
  while(p2<=d[0][2])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  }
  e[0][0]=row;
  e[0][1]=col;
  e[0][2]=i-1;


  printf("matrix after addition\n");
  for(k=0;k<i;k++)
  {
  for(l=0;l<3;l++)
  {
  printf("%d\t",e[k][l]);
  }
  printf("\n");
  } }
   }

 void sub(int b[][10],int row,int col,int d[][10],int e[]
[10])

{
int p1=1,p2=1,i=1;
int k,l;
if(b[0][0]!=d[0][0])
{
printf("subtraction is not possible\n");
}
else
{
while(p1<=b[0][2]&&p2<=d[0][2])
{
if(b[p1][0]==d[p2][0])
{


 if(b[p1][1]<d[p2][1])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
 else if(b[p1][1]>d[p2][1])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  else if(b[p1][1]==d[p2][1])
  {
  e[i][0]=d[p1][0];
  e[i][1]=d[p1][1];
  e[i][2]=b[p1][2]-d[p2][2];
  if(e[i][2]!=0)
  {
   i++;
    }
    p1++;
    p2++;
  }

  }
  else if(b[p1][0]<d[p2][0])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
  else if(b[p1][0]>d[p2][0])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  }
  if(p1!=b[0][2])
  {
  while(p1<=b[0][2])
  {
  e[i][0]=b[p1][0];
  e[i][1]=b[p1][1];
  e[i][2]=b[p1][2];
  i++;
  p1++;
  }
  }
  else if(p2!=d[0][2])
  {
  while(p2<=d[0][2])
  {
  e[i][0]=d[p2][0];
  e[i][1]=d[p2][1];
  e[i][2]=d[p2][2];
  i++;
  p2++;
  }
  }

  e[0][0]=row;
  e[0][1]=col;
  e[0][2]=i-1;


  printf("matrix after subtraction\n");
  for(k=0;k<=i;k++)
  {
  for(l=0;l<3;l++)
  {
  printf("%d\t",e[k][l]);
  }
  printf("\n");
  } }
  }

  void transpose(int b[][10],int col,int c[][10])
  {
  int i,j,k,temp;

  for(i=0;i<=b[0][2];i++)
  {
  c[i][0]=b[i][1];
  c[i][1]=b[i][0];
  c[i][2]=b[i][2];
  }
  for(i=1;i<=b[0][2];i++)
  {
  for(j=i+1;j<=b[0][2];j++)
  {
   if(c[i][0]>c[j][0])
   {
    for(k=0;k<3;k++)
    {
     temp=c[i][k];
     c[i][k]=c[j][k];
     c[j][k]=temp;
     }
     }

     }
     }
     printf("transpose of matrix is\n");
     for(i=0;i<=c[0][2];i++)
     {
     for(j=0;j<3;j++)
     {
     printf("%d\t",c[i][j]);
     }
     printf("\n");
     }
     }