“The computer was born to solve problems that did not exist before.”

Random Posts

Sunday, November 14, 2021

Multiplication of two polynomials using Linked list

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: 

  1. In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.
  2. Store the multiplied value in a new linked list.
  3. 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 ;
    }
}

No comments:

Post a Comment

Post Top Ad

Your Ad Spot

Pages

SoraTemplates

Best Free and Premium Blogger Templates Provider.

Buy This Template