πŸŽ“ Computer Science & Engineering Portal

Master Engineering Disciplines with Structured Notes

Comprehensive academic lecture notes, exam-oriented unit summaries, laboratory manuals, and previous year question papers designed strictly for university students.

πŸ“‘

University Syllabi

AKTU & AICTE aligned semester guidelines.

πŸ“

Exam Question Papers

Previous 5 years solved university papers.

πŸ’‘

Lab Manuals & Viva

Practical codes with outputs & interview Qs.

Core Subjects & Units Hub

Click on any specific unit to immediately view its lecture notes below

Viewing All Lectures

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 ;
    }
}

Labels: ,

Discussion & Queries (<$I18NNumComments$>):

<$CommentPager$>
<$I18NAtCommentTimeWithPermalink$>, <$I18NCommentAuthorSaid$>

<$BlogCommentBody$>

<$BlogCommentDeleteIcon$>
<$CommentPager$>