Write a algorithm in c to add two sparse matrices?

Answer 1

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#define MAX1 3

#define MAX2 3

#define MAXSIZE 9

#define BIGNUM 100

struct sparse

{

int *sp ;

int row ;

int *result ;

} ;

void initsparse ( struct sparse * ) ;

void create_array ( struct sparse * ) ;

int count ( struct sparse ) ;

void display ( struct sparse ) ;

void create_tuple ( struct sparse *, struct sparse ) ;

void display_tuple ( struct sparse ) ;

void addmat ( struct sparse *, struct sparse, struct sparse ) ;

void display_result ( struct sparse ) ;

void delsparse ( struct sparse * ) ;

void main( )

{

struct sparse s[5] ;

int i ;

clrscr( ) ;

for ( i = 0 ; i <= 4 ; i++ )

initsparse ( &s[i] ) ;

create_array ( &s[0] ) ;

create_tuple ( &s[1], s[0] ) ;

display_tuple ( s[1] ) ;

create_array ( &s[2] ) ;

create_tuple ( &s[3], s[2] ) ;

display_tuple ( s[3] ) ;

addmat ( &s[4], s[1], s[3] ) ;

printf ( "\nResult of addition of two matrices: " ) ;

display_result ( s[4] ) ;

for ( i = 0 ; i <= 4 ; i++ )

delsparse ( &s[i] ) ;

getch( ) ;

}

/* initialises structure elements */

void initsparse ( struct sparse *p )

{

p -> sp = NULL ;

p -> result = NULL ;

}

/* dynamically creates the matrix */

void create_array ( struct sparse *p )

{

int n, i ;

/* allocate memory */

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

/* add elements to the array */

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.result + i ) ) ;

}

}

/* deallocates memory */

void delsparse ( struct sparse *p )

{

if ( p -> sp != NULL )

free ( p -> sp ) ;

if ( p -> result != NULL )

free ( p -> result ) ;

}

Answer 2

1. Initialize

l=1

T=0

2. Scan each row

Repeat thru step 9 while l<=M

3. Obtain row indices and starting positions of next rows

J=AROW[l]

K=BROW[l]

CROW[l]=T+1

AMAX=BMAX=0

If l<M

then Repeat for P=l+1, l+2, ......M while AMAX=0

If AROW[P]/=0

then AMAX=AROW[P]

Repeat for P=l+1, l+2,.......M while BMAX=0

If BROW[P]/=0

then BMAX=BROW[P]

If AMAX=0

then AMAX=R+1

If BMAX=0

then BMAX=S+1

4. Scan columns of this row

Repeat thru step 7 while J/=0 and K/=0

5. Elements in same column?

If ACOL[J]=BCOL[K]

then SUM=A[J]+B[K]

COLUMN=ACOL[J]

J=J+1

K=K+1

else If ACOL[J]<BCOL[K]

then SUM=A[J]

COLUMN=ACOL[J]

J=J+1

else SUM=B[K]

COLUMN=BCOL[K]

K=K+1

6. Add new elements to sum of matrices

If SUM/=0

then T=T+1

C[T]=SUM

CCOL[T]=COLUMN

7. End of either row?

If J=AMAX

then J=0

If K=BMAX

then K=0

8. Add remaining elements of a row

If J=0 and K/=0

then repeat while K<BMAX

T=T+1

C[T]=B[K]

CCOL[T]=BCOL[K]

K=K+1

else if K=0 and J/=0

then repeat while J<AMAX

T=T+1

C[T]=A[J]

CCOL[T]=ACOL[J]

J=J+1

9. Adjust index to matrix C and increment row index

If T<CROW[l]

then CROW[l]=0

l=l+1

10. Finished

Exit