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 an algorithm of value in tax using pseudocode, A town contains a tota...

A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

Define min-heap, Define min-heap A min-heap is a complete binary tree i...

Define min-heap A min-heap is a complete binary tree in which each element is less than or equal to its children. All the principal properties of heaps remain valid for min-hea

Progrrame, how to write a code for for a company , for calculate the salary...

how to write a code for for a company , for calculate the salary pay

Define techniques of dry running of flowcharts, Explain the term- Dry runni...

Explain the term- Dry running of flowcharts  Dry running of flowcharts is essentially a technique to: Determine output for a known set of data to check it carries out th

Siso-4bit register, explain working of siso-register to store 1011 and show...

explain working of siso-register to store 1011 and show timing diagram &table

State about the pseudocode, State the Introduction to pseudocode No spe...

State the Introduction to pseudocode No specific programming language is referred to; development of algorithms by using pseudocode uses generic descriptions of branching, loop

Creation of Heap, Q. Create a heap with the given list of keys: ...

Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation

Linked list implementation of any circular queue, Link list representation ...

Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link

What is solid modeling, What is Solid modeling Solid modeling is the mo...

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

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