Search:

Submit Article

# Program to multiply two polynomials maintained as linked lists

Posted By: Waggoner Fischer     Category: C Programming     Views: 37951

## Code for Program to multiply two polynomials maintained as linked lists in C Programming

```#include <stdio.h>
#include <conio.h>
#include <alloc.h>

/* structure representing a node of a linked list. The node can store a term of a polynomial */struct polynode
{
float coeff ;
int exp ;
} ;

void poly_append ( struct polynode **, float, int ) ;
void display_poly ( struct polynode * ) ;
void poly_multiply ( struct polynode *, struct polynode *, struct polynode ** ) ;
void padd ( float, int, struct polynode ** ) ;

void main( )
{
struct polynode *first, *second, *mult ;
int i = 1 ;

first = second = mult = NULL ;  /* empty linked lists */

poly_append ( &first, 3, 5 ) ;
poly_append ( &first, 2, 4 ) ;
poly_append ( &first, 1, 2 ) ;

clrscr( ) ;
display_poly ( first ) ;

poly_append ( &second, 1, 6 ) ;
poly_append ( &second, 2, 5 ) ;
poly_append ( &second, 3, 4 ) ;

printf ( "\n\n" ) ;
display_poly ( second ) ;

printf ( "\n" );
while ( i++ < 79 )
printf ( "-" ) ;

poly_multiply ( first, second, &mult ) ;

printf ( "\n\n" ) ;
display_poly ( mult ) ;
}

/* adds a term to a polynomial */void poly_append ( struct polynode **q, float x, int y )
{
struct polynode *temp ;
temp = *q ;

/* create a new node if the list is empty */if ( *q == NULL )
{
*q = malloc ( sizeof ( struct polynode ) ) ;
temp = *q ;
}
else
{
/* traverse the entire linked list */while ( temp -> link != NULL )
temp = temp -> link ;

/* create new nodes at intermediate stages */
temp -> link = malloc ( sizeof ( struct polynode ) ) ;
temp = temp -> link ;
}

/* assign coefficient and exponent */
temp -> coeff = x ;
temp -> exp = y ;
temp -> link = NULL ;
}

/* displays the contents of linked list representing a polynomial */void display_poly ( struct polynode *q )
{
/* traverse till the end of the linked list */while ( q != NULL )
{
printf ( "%.1f x^%d  :  ", q -> coeff, q -> exp ) ;
q = q -> link ;
}

printf ( "\b\b\b " ) ;  /* erases the last colon(:) */
}

/* multiplies the two polynomials */void poly_multiply ( struct polynode *x, struct polynode *y,
struct polynode **m )
{
struct polynode *y1 ;
float coeff1, exp1 ;

y1 = y ;  /* point to the starting of the second linked list */if ( x == NULL && y == NULL )
return ;

/* if one of the list is empty */if ( x == NULL )
*m = y ;
else
{
if ( y == NULL )
*m = x ;
else/* if both linked lists exist */
{
/* for each term of the first list */while ( x != NULL )
{
/* multiply each term of the second linked list with a                     term of the first linked list */while ( y != NULL )
{
coeff1 = x -> coeff * y -> coeff ;
exp1 = x -> exp + y -> exp ;
y = y -> link ;

/* add the new term to the resultant polynomial */
padd ( coeff1, exp1, m ) ;
}

y = y1 ;  /* reposition the pointer to the starting of                         the second linked list */

x = x -> link ;  /* go to the next node */
}
}
}
}

/* adds a term to the polynomial in the descending order of the exponent */void padd ( float c, int e, struct polynode **s )
{
struct polynode *r, *temp = *s ;

/* if list is empty or if the node is to be inserted before the first node */if ( *s == NULL || e > ( *s ) -> exp )
{
*s = r = malloc ( sizeof ( struct polynode ) ) ;
( *s ) -> coeff = c ;
( *s ) -> exp = e ;
( *s ) -> link = temp ;
}
else
{
/* traverse the entire linked list to search the position to insert a new node */while ( temp != NULL )
{
if ( temp -> exp == e )
{
temp -> coeff += c ;
return ;
}

if ( temp -> exp > e && ( temp -> link -> exp < e ||    temp -> link == NULL ) )
{
r = malloc ( sizeof ( struct polynode ) ) ;
r -> coeff = c;
r -> exp = e ;
temp -> link = r ;
return ;
}

temp = temp -> link ;  /* go to next node */
}

r -> link = NULL ;
temp -> link = r ;
}
}
```
Share:

 Waggoner Fischer author of Program to multiply two polynomials maintained as linked lists is from Frankfurt, Germany. View All Articles

 Please enter your CommentComment should be atleast 30 Characters.Please put code inside [Code] your code [/Code]. No Comment Found, Be the First to post comment!