TMA 2002

Sparse Matrix

#include <iostream.h>
#include <process.h>
#include <conio.h>
//This program implements the linked list representation of Sparse matrix
// for multiplying two Sparse Matrices
class Sparse
{
int i,j,k;
public:
Sparse *next;
Sparse()
{
i=j=k=0;
}
Sparse(int i,int j)
{
this->i=i;
this->j=j;
}
void SetNonZeroElements(Sparse *head,int k)
{
head->k=k;
}
void accept(int i,int j,int k)
{
this->i=i;
this->j=j;
this->k=k;
}
void display()
{
cout<<i<<" "<<j<<" "<<k<<endl;
}
int validateSparseMultiplication(Sparse *head1,Sparse *head2)
{
if (head1->j!=head2->i)
return 0;
else
return 1;
}
int MaxRow(Sparse *head)
{
if (head!=NULL)
return head->i;
else
return 0;
}
int MaxCol(Sparse *head)
{
if (head!=NULL)
return head->j;
else
return 0;
}
int RCValueExists(int ,int ,Sparse *);
void AddToElementIJ(int,int,int,Sparse *);
};
int Sparse::RCValueExists(int i,int j,Sparse *head)
{ Sparse *ptr=head->next;
for(;ptr!=NULL;ptr=ptr->next)
{
if ((ptr->i==i) && (ptr->j==j))
return ptr->k;
}
return 0;
}
void Sparse::AddToElementIJ(int i,int j,int k,Sparse *head)
{
Sparse *ptr=head->next;
for(;ptr!=NULL;ptr=ptr->next)
{
if ((ptr->i==i) && (ptr->j==j))
ptr->k=ptr->k+k;
return;
}
return;
}
void main()
{
int r,c,i,j,k,ctr;
Sparse *A,*B,*C,*start1,*start2,*start3,*ptr1,*ptr2;
clrscr();
//Accept Details Regarding First Matrix & Its Elements
cout<<endl<<"Enter no of rows in first sparse matrix : ";
cin>>r;
cout<<endl<<"Enter no of columns in first sparse matrix : ";
cin>>c;
cout<<endl<<"\t"<<"Enter elements of matrix A"<<endl<<endl;
ctr=0;
A=new Sparse(r,c);
start1=A;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
cout<<"Enter element of "<<i<<"th row and "<<j<<"th column : ";
cin>>k;
if (k!=0)
{
A->next=new Sparse();
A=A->next;
A->accept(i,j,k);
ctr++;
}
}
A->next=NULL;
A->SetNonZeroElements(start1,ctr);

//Accept Details Regarding Second Matrix B & Its Elements
cout<<endl<<"Enter no of rows in second sparse matrix : ";
cin>>r;
cout<<endl<<"Enter no of columns in second sparse matrix : ";
cin>>c;
cout<<endl<<"\t"<<"Enter elements of matrix B"<<endl<<endl;
ctr=0;
B=new Sparse(r,c);
start2=B;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
cout<<"Enter element of "<<i<<"th row and "<<j<<"th column : ";
cin>>k;
if (k!=0)
{
B->next=new Sparse();
B=B->next;
B->accept(i,j,k);
ctr++;
}
}
B->next=NULL;
B->SetNonZeroElements(start2,ctr);
clrscr();
cout<<endl<<"\t"<<"Sparse Matrix A"<<endl;
//Display stored elements of Matrix A
for(ptr1=start1;ptr1!=NULL;ptr1=ptr1->next)
ptr1->display();
cout<<endl<<"\t"<<"Sparse Matrix B"<<endl;
//Display stored elements of Matrix B
for(ptr1=start2;ptr1!=NULL;ptr1=ptr1->next)
ptr1->display();
//Validate Matrix Multiplication
if (A->validateSparseMultiplication(start1,start2)==0)
{
cout<<"Number of columns in Matrix A should be equal to"<<endl;
cout<<"Number of rows in Matrix B"<<endl;
exit(1);
}
C=new Sparse(r,B->MaxCol(start2));
start3=C;
ctr=0;
for(i=1;i<=A->MaxRow(start1);i++)
for(j=1;j<=A->MaxCol(start1);j++)
for(k=1;k<=B->MaxCol(start2);k++)
{
if (A->RCValueExists(i,j,start1)!=0 && B->RCValueExists(j,k,start2)!=0)
{
if (C->RCValueExists(i,k,start3)==0)
{
C->next=new Sparse(i,k);
C=C->next;
C->accept(i,k,A->RCValueExists(i,j,start1)*B->RCValueExists(j,k,start2));
}
else
{
C->AddToElementIJ(i,k,A->RCValueExists(i,j,start1)*B->RCValueExists(j,k,start2),start3);
}
ctr++;
}
}
C->next=NULL;
C->SetNonZeroElements(start3,ctr);
cout<<endl<<"\t"<<"Resultant Matrix"<<endl;
for(ptr2=start3;ptr2!=NULL;ptr2=ptr2->next)
ptr2->display();
}