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

Write a procedure that produces independent stack, Write a procedure (make-...

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Functions and modelling the data flows, Read the scenario (Pickerings Prope...

Read the scenario (Pickerings Properties). (a) List the functions of the system, as perceived by an external user. (b) List the external entities. Note that because we are mo

Create algorithm for similarities between documents, Here is a diagram show...

Here is a diagram showing similarities between documents; this is an actual set of physics lab assignments from a large university. Each node (square) in the graph is a doc

Flow chart, What is tha flow chart of algorithm

What is tha flow chart of algorithm

Algorithm to find maximum and minimum numbers, Give an algorithm to find bo...

Give an algorithm to find both the maximum and minimum of 380 distinct numbers that uses at most 568 comparisons.

Explain optimal binary search trees, Explain Optimal Binary Search Trees ...

Explain Optimal Binary Search Trees One of the principal application of Binary Search Tree is to execute the operation of searching. If probabilities of searching for elements

Algorithm that counts number of nodes in a linked list, Q. Write an algorit...

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

Illustrate an example of algorithm, Illustrate an example of algorithm ...

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

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