/******************************************************
-> This C++ program is to perform sparse matrix
addition.
THE FOLLOWING ASSUMPTIONS ARE MADE IN ORDER TO
SIMPLIFY THE PROGRAM
_______________________________________________
1) The row numbers and column numbers are supposed
to be start from 1.
2) There are no duplicates in the input
-> Data structures used
Matrix : multi linked list
-> This program works in microsoft vc++ in windows xp
*******************************************************/
#include<iostream.h>
#include<stdlib.h>
class sparse
{
private:
int r; // row number
int c; // column number
sparse *rptr; // row pointer
sparse *cptr; // column header
int data; // actual data
public:
sparse * create(sparse*);
void display(sparse*);
void add(sparse*,sparse*);
};
sparse * sparse::create(sparse*h)
{
cout<<“\nEnter the no. of rows ::”;
cin>>r;
cout<<“Enter the no. of columns ::”;
cin>>c;
// create the head node
h=new sparse;
h->r=r;
h->c=c;
h->rptr=h;
h->cptr=h;
h->data=0;
// create column headers
sparse *ptr;
int i,j,d;
ptr=h;
for(i=1;i<=c;i++)
{
sparse *node;
node=new sparse;
node->r=0;
node->c=i;
node->data=0;
node->rptr=h;
node->cptr=node;
ptr->rptr=node;
ptr=node;
}
// create row headers
ptr=h;
for(i=1;i<=r;i++)
{
sparse *node;
node=new sparse;
node->r=i;
node->c=0;
node->data=0;
node->rptr=node;
node->cptr=h;
ptr->cptr=node;
ptr=node;
}
cout<<“\n now enter the non zero elements ”
<<“one by one\n”;
cout<<“\nEnter row number,column number,data\n”;
cout<<“Enter (0 0 0) to stop ::”;
cin>>i>>j>>d;
if(i>r || j>c ||i<1 ||j<1)
{
cout<<” error input”;
exit(1);
}
while(i&&j&&d)
{
sparse * row_header=h->cptr;
sparse * column_header=h->rptr;
// find the correct row header and column header
while(row_header->r<i)
row_header=row_header->cptr;
while(column_header->c<j)
column_header=column_header->rptr;
sparse *ptr1;
sparse *ptr2;
// find the correct position to insert
sparse*row_ptr=row_header;
while(row_ptr->c<j)
{
ptr1=row_ptr;
row_ptr=row_ptr->rptr;
if(row_ptr==row_header)
break;
}
sparse*column_ptr=column_header;
while(column_ptr->r<i)
{
ptr2=column_ptr;
column_ptr=column_ptr->cptr;
if(column_ptr==column_header)
break;
}
sparse *node;
node=new sparse;
node->r=i;
node->c=j;
node->data=d;
ptr1->rptr=node;
ptr2->cptr=node;
node->rptr=row_ptr;
node->cptr=column_ptr;
cout<<“\nEnter row number,column number,data\n”;
cout<<“Enter (0 0 0) to stop ::”;
cin>>i>>j>>d;
if(i>r || j>c )
{
cout<<” error input”;
exit(1);
}
}
return h;
}
void sparse::display(sparse*h)
{
sparse *right;
right=h->cptr;
while(right!=h)
{
sparse *r=right;
right=right->rptr;
while(right!=r)
{
cout<<right->r
<<‘\t'<<right->c
<<‘\t'<<right->data<<endl;
right=right->rptr;
}
right=right->cptr;
}
}
void sparse::add(sparse*h1,sparse*h2)
{
if(h1->r==h2->r && h1->c==h2->c)
cout<<“The addition of the two given ”
<<“sparse matrices is ::\n”;
else
{
cout<<“addition is not possible”;
exit(1);
}
sparse *r1;
r1=h1->cptr;
sparse *r2;
r2=h2->cptr;
while(r1!=h1)
{
sparse * p1=r1;
r1=r1->rptr;
sparse * p2=r2;
r2=r2->rptr;
while(r1!= p1 && r2!=p2)
{
if(r1->c==r2->c)
{
cout<<r1->r<<‘\t'<<r1->c<<‘\t’
<<(r1->data+r2->data)<<endl;
r1=r1->rptr;
r2=r2->rptr;
}
else if(r1->c>r2->c)
{
cout<<r2->r<<‘\t'<<r2->c<<‘\t’
<<r2->data<<endl;
r2=r2->rptr;
}
else
{
cout<<r1->r<<‘\t'<<r1->c<<‘\t’
<<r1->data<<endl;
r1=r1->rptr;
}
}
while(r1!=p1)
{
cout<<r1->r<<‘\t'<<r1->c<<‘\t’
<<r1->data<<endl;
r1=r1->rptr;
}
while(r2!=p2)
{
cout<<r2->r<<‘\t'<<r2->c<<‘\t’
<<r2->data<<endl;
r2=r2->rptr;
}
r1=r1->cptr;
r2=r2->cptr;
}
}
void main()
{
cout<<“******************************************”;
cout<<“\nThis program is to perform addition of \n”;
cout<<” two sparse matrices \n”;
cout<<“*******************************************\n”;
sparse s;
sparse *h1=NULL,*h2=NULL;
cout<<“Enter the values for sparse matrix 1 ::\n”;
cout<<“****************************************\n”;
h1=s.create(h1);
s.display(h1);
cout<<“Enter the values for sparse matrix 2 ::\n”;
cout<<“****************************************\n”;
h2=s.create(h2);
s.display(h2);
s.add(h1,h2);
}
well the programme is great bt can u make this programme without using pointer concept
Here is a program for sparse matrix addition without using pointers, also we don’t have to make any assumptions:
http://www.programminghelp.in/c-program-for-adding-to-sparse-matrices-using-class/
For different approach of the same program without using pointer
http://goo.gl/EiebK
thanks
yaa…
we have done this too
check the following link to see that
https://ds4beginners.wordpress.com/tag/linear-lists/
how can we print that
11111111111111 ———|
1111111111 11 |—— |
11 11 | | |
11111111111111 |——–|
Saprse Matrix in a fprmat
I want code in list form
how can we print that
start ———|
|—— |
| | |
|——–|
Saprse Matrix in a fprmat
I want code in list form
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
Start with 1 then 2 3 4 —–16
Hi ASHish
This is vara prasad of ds4beginners…
Thanks for Ur comment……..
Your Question is not clear I think……….?
this is really very good site as if i will learn alot from that but can u e-mail me the pdf file for data structure on my e-mail.thanks
Good, but it can be more easy according to new user. If any other sit also avlable for a beginner please reply.
Thanks a lot….
Good, but it can be more easy according to new user. If any other sit also avlable for a beginner please reply.
0 1 2
3 0 4
5 6 0
above structure is called sparse matrix ??? reply me
The short answer is- Above matrix is not sparse.
The long answer is- Above matrix is not sparse because in this matrix
No. of non zero elements> No. of zero elements.
and the definition of sparse matrix says that a matrix is called sparse if
No. of non zero elements< No. of zero elements.
its not sparse mat
condition is that: [ no of non zero ele < (total no of ele in mat/3)]
yes the avobe matrix is a sparce matrix…
wawawe
hi buddy could u tell me how can i show resultant matrix in normal matrix format instead of
row col data
sir please send me a sparse matrix coding in data structure using c++.please sir
can u sent me the code for sparse matrix addition in C.
Hi THere ! I Want To know if we + or * 2 sparse the result will be onther sparse or not? plzzzzzzzzzzzz tell me ! Thank YOu !
i want to knw addition n multiplication of sparse matrix using C programming, give me solution
hi, i want to subtract and multiply and transpose program ,help me, thanks.
Write a program to represent sparse integer matrices (that is, most entries are zero) using linked
lists. For an m n matrix Amn, let A(i; j), where 0 i m and 0 j n, denote the entry at
ith row and jth column. Your program should store only non-zero entries of A using linked lists as
described in the following.
Matrix representation
Corresponding to each non-zero entry A(i; j), your program should create a record containing
the following seven elds:
1. i
2. j
3. A(i; j) value
4. `Up’ pointer pointing to A(k; j), where k i and A(k; j) 6= 0, which is the next element
in column j. That is, A(l; j) = 0 for all l 2 fi + 1; : : : ; k 1g.
6. `Left’ pointer pointing to A(i; k), where k j and A(i; k) 6= 0, which is the next element in
row j. That is, A(i; l) = 0 for all l 2 fj + 1; : : : ; k 1g.
For each input matrix Amn, in addition to its non-zero entries, your program should also store
two pointer arrays R and C of size m and n respectively, where R[i] and C[j] store pointer to the
rst non-zero element in row i and column j respectively.
Matrix input format
To read a matrix A as input, your program should read m and n followed by each row of A.
Consecutive row elements are tab (`nt’) separated.
Matrix operations::
Implement the following ve operations on matrices stored in the above fashion.
1. Matrix transpose: For a matrix Amn, output AT . Your implementation should not make a
copy of the matrix elements in memory.
2. Matrix addition: For two matrices Amn and Bmn, output A + B.
3. Matrix multiplication: For two matrices Amn and Bnk, output A B.
4. Row permutation: The input to your program is a matrix Amn and a permutation of its row
numbers given by the ordered sequence fp0; : : : ; pm1g, where pi denotes the new position of
row i. Your program should output Bmn such that B(pi; j) = A(i; j) for all i 2 f0; : : : ;m1g
and j 2 f0; : : : ; n 1g. Your implementation should not make a copy of the matrix elements
in memory.
5. Column permutation: The input to your program is a matrix Amn and a permutation of
its column numbers given by the ordered sequence fp0; : : : ; pn1g, where pj denotes the new
position of column j. Your program should output Bmn such that B(i; pj) = A(i; j) for all
i 2 f0; : : : ;m 1g and j 2 f0; : : : ; n 1g. Your implementation should not make a copy of
the matrix elements in memory.
Ensure that the output of addition and multiplication follows the same representation scheme
where only the non-zero elements are stored in memory.
Output format::
Implement a print method to print a matrix and use the same procedure to print the output
for the above operations. The print method should print the number of rows and columns of the
matrix in separate lines followed by all its elements (including the zeroes) in row-wise manner.
Each row should be printed in a separate line and the row elements should be tab separated. Your
program should not print anything to the output except the output matrix.
0 0 1
2 0 0
6 7 0
is this sparce matrix?
Write a program in C to read a sparse matrix of integer values and to search the sparse matrix for an element specified by the user. Print the result of the search appropriately. Use the triple to represent an element in the sparse matrix.
An Alternative method:
http://www.programminghelp.in/2011/10/19/c-program-for-adding-to-sparse-matrices-using-class/
hi
i tried to implement the code using a matrix for row headers and column headers but i have a problem some where please help me out..
#include
using namespace std;
class sparse{
int row;
int column;
int data;
sparse *row_link;
sparse *column_link;
public:
sparse * create(sparse*);
void display(sparse*);
};
sparse * sparse::create(sparse*h)
{
cout<>row;
cout<>column;
// create the head node
sparse *columnheader[column];
sparse *rowheader[row];
//create head node
h=new sparse;
h->row=row;
h->column=column;
h->data=0;
h->row_link=columnheader[column];
h->column_link=rowheader[row];
//create rowheader
sparse *ptr;
int i,j,d;
ptr=h;
for (i=0;irow=i;
rowheader[i]->column=0;
rowheader[i]->row_link=h;
rowheader[i]->column_link=rowheader[i];
ptr->column_link=rowheader[i];
ptr=rowheader[i];
}
//create columnheader
ptr=h;
for (i=0;irow=0;
columnheader[i]->column=i;
columnheader[i]->row_link=columnheader[i];
columnheader[i]->column_link=h;
ptr->row_link=columnheader[i];
ptr=columnheader[i];
}
cout<<"\n now enter the non zero elements "
<<"one by one\n";
cout<<"\nEnter row number,column number,data\n";
cout<>i>>j>>d;
if(i>row || j>column ||i<1 ||j<1)
{
cout<column_link;
sparse * column_header=h->row_link;
// find the correct row header and column header
while(row_header->rowcolumn_link;
while(column_header->columnrow_link;
sparse *ptr1;
sparse *ptr2;
// find the correct position to insert
sparse*row_ptr=row_header;
while(row_ptr->columnrow_link;
if(row_ptr==row_header)
break;
}
sparse*column_ptr=column_header;
while(column_ptr->rowcolumn_link;
if(column_ptr==column_header)
break;
}
sparse *node;
node=new sparse;
node->row=i;
node->column=j;
node->data=d;
ptr1->row_link=node;
ptr2->column_link=node;
node->row_link=row_ptr;
node->column_link=column_ptr;
cout<<"\nEnter row number,column number,data\n";
cout<>i>>j>>d;
if(i>row || j>column )
{
cout<column_link;
while(right!=h)
{
sparse *r=right;
right=right->row_link;
while(right!=r)
{
cout<row
<<'\t'<column
<<'\t'<data<row_link;
}
right=right->column_link;
}
}
int main()
{
sparse s;
sparse *h1=NULL;
cout<<"Enter the values for sparse matrix \n";
h1=s.create(h1);
s.display(h1);
}
Hi!. I am trying to trasnpose the matrix the matrix before adding the I ma having issues with that, can you help. I can only scwith the cols to rows, but not the rows to coulms, ezample given:
1,1,3
3,1,5
the result should be
1,1,3
1,3,5
I thoguth of creating a new matrix and switching the los and rows, and return it. here is my code:
template
sparse * sparse::traspose(sparse*h)
{
sparse *right;
sparse *left;
right=h->cptr;
left=h->cptr;
while(right!=h)
{
sparse *r=right;
sparse *l=left;
left=right->rptr;
right=right->rptr;
while(right!=r)
{
left->c= right->r;
left->r=right->c;
left->data=right->data;
left=right->rptr;
right=right->rptr;
}
left=right->cptr;
right=right->cptr;
}
right=h->rptr;
left=h->rptr;
while(right!=h)
{
sparse *r=right;
sparse *l=left;
left=right->cptr;
right=right->cptr;
int x=0;
while(right!=r)
//while(x c= right->r;
left->r=right->c;
left->data=right->data;
left=right->cptr;
right=right->cptr;
}
left=right->rptr;
right=right->rptr;
}
return left;
}
thnkx, i want to simple logic of programming in data structure using c.
what is sparse matrix applications in data structure please reply me
no.of non zero elements =no.of zero elements then what it is called?
Can I have a Program for Sparse Matrix Multiplication
What i do not realize is if truth be told how you are now not actually much more neatly-liked than you might be right now.
You’re very intelligent. You already know therefore significantly when it comes to this matter, produced me personally imagine it from a lot of varied angles. Its like men and women aren’t
involved except it’s one thing to accomplish with Woman gaga! Your personal stuffs excellent. Always take care of it up!
I think this is one of the most significant information for me.
And i am glad reading your article. But should remark on few general things, The site style is wonderful, the articles is really great : D.
Good job, cheers
Hello There. I found your blog the usage of msn. That is a very neatly written
article. I’ll be sure to bookmark it and return to read extra of your useful info. Thank you for the post. I’ll definitely comeback.
can you send me the code for sparse matrix multiplication in c++
can you pls send me the code for sparse matrix multiplication in c++….