Sparse metrics, Data Structure & Algorithms

Assignment Help:

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 ;

}

}


Related Discussions:- Sparse metrics

Stack, implement multiple stacks ina single dimensional array. write algori...

implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

Primitive data structure, Primitive Data Structure These are the basic ...

Primitive Data Structure These are the basic structure and are directly operated upon by the machine instructions. These in general have dissimilar representations on different

#, if two relations R and S are joined, then the non matching tuples of bot...

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Structured programming, What do you understand by term structured programmi...

What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

Data structures, 1.  You are required to hand in both a hard copy and an el...

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

#binary search, Ask question #Minima binary search tree is used to locate t...

Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#

Explain b tree (binary tree), B Tree Unlike a binary-tree, every node o...

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Pseudocodes, how to write a pseudo code using Kramer''s rule

how to write a pseudo code using Kramer''s rule

What do you mean by hash clash, What do you mean by hash clash? Hashing...

What do you mean by hash clash? Hashing is not perfect. Occasionally, a collision occurs when two different keys hash into the same hash value and are assigned to the same arra

Objectives of lists, After going through this unit, you will be able to: ...

After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd