Given two polynomials in the form of linked list. The task is to find the multiplication of both polynomials.
Examples:
Input: Poly1: 3x^2 + 5x^1 + 6, Poly2: 6x^1 + 8 Output: 18x^3 + 54x^2 + 76x^1 + 48 On multiplying each element of 1st polynomial with elements of 2nd polynomial, we get 18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48 On adding values with same power of x, 18x^3 + 54x^2 + 76x^1 + 48 Input: Poly1: 3x^3 + 6x^1 - 9, Poly2: 9x^3 - 8x^2 + 7x^1 + 2 Output: 27x^6 - 24x^5 + 75x^4 - 123x^3 + 114x^2 - 51x^1 - 18
Approach:
- In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.
- Store the multiplied value in a new linked list.
- Then we will add the coefficients of elements having the same power in resultant polynomial.
Below is the implementation of the above approach:
#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 ; struct polynode *link ; } ; 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 ; r -> link = temp -> link ; temp -> link = r ; return ; } temp = temp -> link ; /* go to next node */ } r -> link = NULL ; temp -> link = r ; } }
0 Comments