Sparse metrics, Data Structure & Algorithms

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.        

Ans:

A matrix in which number of zero entries is quite higher than the number of non zero entries is called the sparse matrix. The natural method or technoque of expressing matrices in memory as two-dimensional arrays may not be appropriate for sparse matrices. One can save the space by storing only nonzero entries. For example matrix A (3*3 matrix) which is represented below

 

0    2      0

5   0     0

0   6     9

can be written in sparse matrix form as:

3   3     4

0    1      2

1   0   5

2   2   6

2   3   9

In this the first row represent the dimension of matrix and last column tells us about the total number of non zero values; from the second row onwards it is giving the location and value of non zero number.

Representation of a 4*4 matrix using linked list is given below:

#define MAX1 4

#define MAX2 4

struct cheadnode           /* structure for col

headnode */

{

int colno ;

struct node *down ;

struct cheadnode *next ;

} ;

struct rheadnode          /* structure for row

headnode */

{

int rowno ;

struct node * right ;

struct rheadnode *next ;

} ;

struct node                  /* structure for node to

store element */

{

int row ; int col ; int val ;

struct node *right ;

struct node *down ;

} ;

struct spmat                /* structure for special headnode */

{

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 *p )           /*

initializes structure elements */

{

int i ;

for ( i = 0 ; i < MAX1 ; i++ )            /* create row headnodes */

p -> rhead[i] = ( struct rheadnode * ) malloc (

sizeof ( struct rheadnode ) ) ;

for ( i = 0 ; i < MAX1 - 1 ; i++ ) /* initialize and

link row headnodes together */

{

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 ;

for ( i = 0 ; i < MAX1 ; i++ )          /* create col headnodes */

p -> chead[i] = ( struct cheadnode * ) malloc (

sizeof ( struct cheadnode ) ) ;

for ( i = 0 ; i < MAX2 - 1 ; i++ )               /*

initialize and link col headnodes together */

{

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 ;

}

void create_array ( struct sparse *p )    /* creates, dynamically the matrix of size MAX1 x MAX2 */

{

int n, i ;

p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof (

int ) ) ;

for ( i = 0 ; i < MAX1 * MAX2 ; i++ )        /*

get the element and store it */

{

printf ( "Enter element no. %d:", i ) ;

scanf ( "%d", &n ) ;

* ( p -> sp + i ) = n ;

}

}

Posted Date: 7/10/2012 7:12:35 AM | Location : United States







Related Discussions:- Sparse metrics, Assignment Help, Ask Question on Sparse metrics, Get Answer, Expert's Help, Sparse metrics Discussions

Write discussion on Sparse metrics
Your posts are moderated
Related Questions
This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi

perform the following length operation LENGTH("welcome to ICA")=

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o



Step-1: For the current node, verify whether it contain a left child. If it has, then go to step-2 or else go to step-3 Step-2: Repeat step-1 for left child Step-3: Visit (th

lower triangular matrix and upper triangular matrix

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's