USING STRUCTURE CONVERT CONVENTIONAL(SIMPLE) MATRIX INTO SPARSE MATRIX AND ADDITION OF SPARSE MATRIX IN C USING SWITCHCASE.

                              SPARSE MATRIX

What is Sparse Matrix?

In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm' columns and 'n' rows represent a m X n matrix. There may be a situation in which a matrix contains more number of ZERO values than NON-ZERO values. Such matrix is known as sparse matrix.

When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to represent that matrix. For example, consider a matrix of size 100 X 100 containing only 10 non-zero elements. In this matrix, only 10 spaces are filled with non-zero values and remaining spaces of the matrix are filled with zero. That means, totally we allocate 100 X 100 X 2 = 20000 bytes of space to store this integer matrix. And to access these 10 non-zero elements we have to make scanning for 10000 times. To make it simple we use the following sparse matrix representation.

Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations,

1. Triplet Representation 
2. Linked Representation

Triplet Representation

In this representation, we consider only non-zero values along with their row and column index values. In this representation, the 0th row stores the total number of rows, total number of columns and the total number of non-zero values in the sparse matrix.

SPARSE MATRIX PROGRAM Accept conventional matrix and convert it into sparse matrix using structure and perform addition.

#include<stdio.h>
#include<conio.h>
 struct spa
{
 int row;
 int col;
 int val;
};
void accept(int A[10][10],int r,int c);
void convert(int A[10][10],struct spa s[100],int r,int c);
void add(struct spa s[],struct spa s1[],struct spa s2[]);

void accept(int A[10][10],int r,int c)
{
   int i,j;
 printf("\nEnter matrix element\n");
 for(i=0;i<r;i++)
  {
    for(j=0;j<c;j++)
      {
 scanf("%d",&A[i][j]);
      }
  }
}

void convert(int A[10][10],struct spa s[100],int r,int c)
 {
   int i,j,k=1,count=0;
   for(i=0;i<r;i++)
    {
      for(j=0;j<c;j++)
 {
   if(A[i][j]!=0)
     {
       s[k].row=i;
       s[k].col=j;
       s[k].val=A[i][j];
       k++;
       count++;
     }
 }
    }
s[0].row=r;
s[0].col=c;
s[0].val=count;
count=count+1;
printf("\nMatrix elements are\n");
 for(i=0;i<count;i++)
   {
     printf("%2d",s[i].row);
     printf("%2d",s[i].col);
     printf("%2d\n",s[i].val);
   }
}

void add(struct spa s[],struct spa s1[],struct spa s2[])
  {
   int t1,t2,i,j,k;
   t1=s[0].val;
   t2=s1[0].val;
   i=j=k=1;
   s2[0].row=s[0].row;
   s2[0].col=s[0].col;
  while(i<=t1&&j<=t2)
    {
      if(s[i].row<s1[j].row)
       {
 s2[k].row=s[i].row;
 s2[k].col=s[i].col;
 s2[k].val=s[i].val;
 k++;
 i++;
 continue;
       }
      if(s1[j].row<s[i].row)
       {
 s2[k].row=s1[j].row;
 s2[k].col=s1[j].col;
 s2[k].val=s1[j].val;
 k++;
 j++;
 continue;
       }
      if(s[i].col<s1[j].col)
       {
 s2[k].row=s[i].row;
 s2[k].col=s[i].col;
 s2[k].val=s[i].val;
 k++;
 i++;
 continue;
       }
      if(s1[i].col<s[j].col)
       {
 s2[k].row=s1[j].row;
 s2[k].col=s1[j].col;
 s2[k].val=s1[j].val;
 k++;
 j++;
 continue;
       }
       s2[k].row=s1[i].row;
       s2[k].col=s1[i].col;
       s2[k].val=s[i].val+s1[i].val;
       k++;
       i++;
       j++;

     }
   while(i<=t1)
    {
 s2[k].row=s[i].row;
 s2[k].col=s[i].col;
 s2[k].val=s[i].val;
 i++;
 k++;
    }
    while(j<=t2)
      {
 s2[k].row=s1[i].row;
 s2[k].col=s1[i].col;
 s2[k].val=s1[i].val;
 j++;
 k++;
      }
s2[0].val=k-1;
printf("Matric addition is\n");
 for(i=0;i<=s2[0].val;i++)
  {
    printf("%2d",s2[i].row);
    printf("%2d",s2[i].col);
    printf("%2d\n",s2[i].val);
  }
}

void transpose(struct spa s[],struct spa s2[])
{
 int i,j,k,n;
 s2[0].row=s[0].col;
 s2[0].col=s[0].row;
 s2[0].val= s[0].val;
 k=1;
 n=s[0].val;


}

int main()
{
 int A[10][10],B[10][10],r,c,r1,c1,n;
 struct spa s[100],s1[100],s2[100];
 clrscr();
 printf("Enter no of rows and cols for 1st matrix\n" );
 scanf("%d%d",&r,&c);
 accept(A,r,c);
 printf("Enter no of rows and cols for 2nd matrix\n" );
 scanf("%d%d",&r1,&c1);
 accept(B,r1,c1);
 do
 {
 printf("\nEnter 1 to convert simple matrix into sparse.");
 printf("\nEnter 2 to add two spase matrix.");
 printf("\nEnter 3 for simple transpose.");
 printf("\nEnter 4 for fast transpose.");
 printf("\nEnter 5 to Exit.");
 printf("\nEnter your choice\n");
 scanf("%d",&n);
 switch(n)
 {
   case 1: convert(A,s,r,c);
    convert(B,s,r1,c1);
    break;
   case 2: add(s,s1,s2);
    break;
   case 3: transpose(s,s2);
 }
 }while(n!=5);
getch();
return 0;
}