#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define MAX1 3
#define MAX2 3
/* structure for col headnode */
struct cheadnode
{
int colno ;
struct node *down ;
struct cheadnode *next ;
} ;
/* structure for row headnode */
struct rheadnode
{
int rowno ;
struct node * right ;
struct rheadnode *next ;
} ;
/* structure for node to store element */
struct node
{
int row ;
int col ;
int val ;
struct node *right ;
struct node *down ;
} ;
/* structure for special headnode */
struct spmat
{
struct rheadnode *firstrow ;
struct cheadnode *firstcol ;
int noofrows ;
int noofcols ;
} ;
struct sparse
{
int *sp ;
int row ;
struct spmat *smat ;
struct cheadnode *chead[MAX2] ;
struct rheadnode *rhead[MAX1] ;
struct node *nd ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
void display ( struct sparse ) ;
int count ( struct sparse ) ;
void create_triplet ( struct sparse *, struct sparse ) ;
void create_llist ( struct sparse * ) ;
void insert ( struct sparse *, struct spmat *, int, int, int ) ;
void show_llist ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s1, s2 ;
clrscr( ) ;
initsparse ( &s1 ) ;
initsparse ( &s2 ) ;
create_array ( &s1 ) ;
printf ( "\nElements in sparse matrix: " ) ;
display ( s1 ) ;
create_triplet ( &s2, s1 ) ;
create_llist ( &s2 ) ;
printf ( "\n\nInformation stored in linked list : " ) ;
show_llist ( s2 ) ;
delsparse ( &s1 ) ;
delsparse ( &s2 ) ;
getch( ) ;
}
/* initializes structure elements */
void initsparse ( struct sparse *p )
{
int i ;
/* create row headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> rhead[i] = ( struct rheadnode * ) malloc ( sizeof ( struct rheadnode ) ) ;
/* initialize and link row headnodes together */
for ( i = 0 ; i < MAX1 - 1 ; i++ )
{
p -> rhead[i] -> next = p -> rhead[i + 1] ;
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> rowno = i ;
}
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> next = NULL ;
/* create col headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> chead[i] = ( struct cheadnode * ) malloc ( sizeof ( struct cheadnode ) ) ;
/* initialize and link col headnodes together */
for ( i = 0 ; i < MAX2 - 1 ; i++ )
{
p -> chead[i] -> next = p -> chead[i + 1] ;
p -> chead[i] -> down = NULL ;
p -> chead[i] -> colno = i ;
}
p -> chead[i] -> down = NULL ;
p -> chead[i] -> next = NULL ;
/* create and initialize special headnode */
p -> smat = ( struct spmat * ) malloc ( sizeof ( struct spmat ) ) ;
p -> smat -> firstcol = p -> chead[0] ;
p -> smat -> firstrow = p -> rhead[0] ;
p -> smat -> noofcols = MAX2 ;
p -> smat -> noofrows = MAX1 ;
}
/* creates, dynamically the matrix of size MAX1 x MAX2 */
void create_array ( struct sparse *p )
{
int n, i ;
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;
/* get the element and store it */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d:", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % MAX2 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array of triplet containing info. about non-zero elements */
void create_triplet ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;
p -> row = count ( s ) ;
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element. Row, column and non-zero element value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* stores information of triplet in a linked list form */
void create_llist ( struct sparse *p )
{
int j = 0, i ;
for ( i = 0 ; i < p -> row ; i++, j+= 3 )
insert ( p, p -> smat, * ( p -> sp + j ), * ( p -> sp + j + 1 ), * ( p -> sp + j + 2) ) ; }
/* inserts element to the list */
void insert ( struct sparse *p, struct spmat *smat , int r, int c, int v )
{
struct node *temp1, *temp2 ;
struct rheadnode *rh ;
struct cheadnode *ch ;
int i, j ;
/* allocate and initialize memory for the node */
p -> nd = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
p -> nd -> col = c ;
p -> nd -> row = r ;
p -> nd -> val = v ;
/* get the first row headnode */
rh = smat -> firstrow ;
/* get the proper row headnode */
for ( i = 0 ; i < r ; i++ )
rh = rh -> next ;
temp1 = rh -> right ;
/* if no element added in a row */
if ( temp1 == NULL )
{
rh -> right = p -> nd ;
p -> nd -> right = NULL ;
}
else
{
/* add element at proper position */
while ( ( temp1 != NULL ) && ( temp1 -> col < c ) )
{
temp2 = temp1 ;
temp1 = temp1 -> right ;
}
temp2 -> right = p -> nd ;
p -> nd -> right = NULL ;
}
/* link proper col headnode with the node */
ch = p -> smat -> firstcol ;
for ( j = 0 ; j < c ; j++ )
ch = ch -> next ;
temp1 = ch -> down ;
/* if col not pointing to any node */
if ( temp1 == NULL )
{
ch -> down = p -> nd ;
p -> nd -> down = NULL ;
}
else
{
/* link previous node in column with next node in same column */
while ( ( temp1 != NULL ) && ( temp1 -> row < r ) )
{
temp2 = temp1 ;
temp1 = temp1 -> down ;
}
temp2 -> down = p -> nd ;
p -> nd -> down = NULL ;
}
}
void show_llist ( struct sparse s )
{
struct node *temp ;
/* get the first row headnode */
int r = s.smat -> noofrows ;
int i ;
printf ( "\n" ) ;
for ( i = 0 ; i < r ; i++ )
{
temp = s.rhead[i] -> right ;
if ( temp != NULL )
{ while ( temp -> right != NULL )
{
printf ( "Row: %d
temp = temp -> right ;
}
if ( temp -> row == i )
printf ( "Row: %d
}
}
/* deallocates memory */
void delsparse ( struct sparse *p )
{
int r = p -> smat -> noofrows ;
struct rheadnode *rh ;
struct node *temp1, *temp2 ;
int i, c ;
/* deallocate memeory of nodes by traversing rowwise */
for ( i = r - 1 ; i >= 0 ; i-- )
{
rh = p -> rhead[i] ;
temp1 = rh -> right ;
while ( temp1 != NULL )
{
temp2 = temp1 -> right ;
free ( temp1 ) ;
temp1 = temp2 ;
}
}
/* deallocate memory of row headnodes */
for ( i = r - 1 ; i >= 0 ; i-- )
free ( p -> rhead[i] ) ;
/* deallocate memory of col headnodes */
c = p -> smat -> noofcols ;
for ( i = c - 1 ; i >= 0 ; i-- )
free ( p -> chead[i] ) ;
}
DataStructure Program to store sparse matrix as a linked list
