C program to add two polynomials using linked list

In this article, we will learn c program to add two polynomials using linked list. The program takes an input of coefficient and power separately of 2 different polynomials and add them up to a new polynomial. The time complexity of it is O(m+n), where m & n are the number of nodes in first and second equations respectively.

Algorithm:
1. Read no. of terms in first Polynomial 'p'
2. Read Coefficient and exponent(power) of the first polynomial
3. Read no. of terms in first Polnomial 'q'
4. Read Coefficient and exponent(power) of the second polynomial
5. Traverse both Polynomial 'p' and 'q' respectively
6. Compare the exponent(power) of both polynomials starting from the first node, if the values of both node’s exponent are the same add the coefficients and then copy the added value with node to the result.

To write a c program to add two polynomials using linked list, There are 3 terms we need to understand. Which are "Coefficients", "Power" & "Address of Next Node".
Node structure of Link List - Add two polynomials
Before we look into the logic of a program, Lets first understand the algorithm to add two polynomials. For that consider mentioned two equations p(x) and q(x).

Input:
p(x) = 3x^2 + 4x^1 + 2
q(x) = 3x^1 + 5

Adding two polynomials using linked list
Adding two polynomials using linked list
The above image showcases the way to implement the equation to the linked list representation. Also, observe coefficient and power value. Next, we will check for the coefficients of the exponents that have the same value of exponents and add them, which returns the final polynomial.

Output:
Result = 3x^2 + 7x + 7

Program Source Code:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int coef;
    int pow;
    struct node *next;
}poly;
menu()
{
    int ch;
    system("clear");
    printf("\n\t1)Create 1'st Polynomial ");
    printf("\n\t2)Create 2'nd Polynomial ");
    printf("\n\t3)Display");
    printf("\n\t4)Add Polynomials");
    printf("\n\tEnter your choice:");
    scanf("%d",&ch);
    return ch;
}
void b_sort(poly *head)
{
    poly *t1,*temp;
    int i,flag=1,scan;
    t1=(poly *)malloc(sizeof(poly));
    temp=(poly *)malloc(sizeof(poly));
    for(scan=1;flag==1;scan++)
    {
        temp=head->next;
        flag=0;
        for(i=0;i<head->coef-scan;i++)
        {
            if(temp->pow<temp->next->pow)
            {
                t1->coef=temp->coef;
                t1->pow=temp->pow;
                temp->coef=temp->next->coef;
                temp->pow=temp->next->pow;
                temp->next->coef=t1->coef;
                temp->next->pow=t1->pow;
                flag=1;
            }
            temp=temp->next;
        }
    }
}
void create(poly **head)
{
    int coef,pow;
    *head=(poly *)malloc(sizeof(poly));
    printf("\n\tEnter number of terms: ");
    scanf("%d",&(*head)->coef);
    (*head)->next=NULL;
    int i;
    poly *newnode;
    poly  *curr=*head;
    for(i=0;i<(*head)->coef;i++)
    {
        newnode=(poly *)malloc(sizeof(poly));
        system("clear");
        printf("\n\tEnter %d term: ",i+1);
        scanf("%d",&coef);
        printf("\n\tEnter power of %d term: ",i+1);
        scanf("%d",&pow);
        newnode->coef=coef;
        newnode->pow=pow;
        while(curr->next)
            curr=curr->next;
        curr->next=newnode;
        curr=newnode;
    }
    curr->next=NULL;
}
void display(poly *head)
{
    if(head==NULL)
        printf("\n\tEmpty\n");
    else
    {
        poly *temp=head->next;
        while(temp)
        {
            if(temp->next==NULL)
            {
                if(temp->pow==0)
                {
                    printf("%d",temp->coef);
                    return;
                }
                if(temp->pow==1)
                {
                    printf("%dx",temp->coef);
                    return;
                }
                else
                {
                    printf("%dx^%d",temp->coef,temp->pow);
                    return;
                }
            }
            else
            if(temp->pow==1)
                printf("%dx+",temp->coef);
            else
            if(temp->pow==0)
                printf("%d+",temp->coef);
            else
                printf("%dx^%d+",temp->coef,temp->pow);
            temp=temp->next;
        }
    }
}
void adddisplay(poly *head)
{
    if(head==NULL)
        printf("\n\tEmpty\n");
    else
    {
        poly *temp=head->next->next;
        while(temp)
        {
            if(temp->next==NULL)
            {
                if(temp->pow==0)
                {
                    printf("%d",temp->coef);
                    return;
                }
                if(temp->pow==1)
                {
                    printf("%dx",temp->coef);
                    return;
                }
                else
                {
                    printf("%dx^%d",temp->coef,temp->pow);
                    return;
                }
            }
            else
            if(temp->pow==1)
                printf("%dx+",temp->coef);
            else
            if(temp->pow==0)
                printf("%d+",temp->coef);
            else
                printf("%dx^%d+",temp->coef,temp->pow);
            temp=temp->next;
        }
    }
}
poly *add(poly *head1,poly *head2)
{
    poly *head3=NULL;
    poly *curr1,*curr2,*curr3;
    curr1=head1; curr2=head2; curr3=head3;
    poly *newnode;
    head3=(poly *)malloc(sizeof(poly));
    curr3=head3;
    while(curr1||curr2)
    {
        newnode=(poly *)malloc(sizeof(poly));
        newnode->next=NULL;
        if(curr1->pow>curr2->pow)
        {
            newnode->coef=curr1->coef;
            newnode->pow=curr1->pow;
            curr1=curr1->next;
        }
        else
        if(curr1->pow<curr2->pow)
        {
            newnode->coef=curr2->coef;
            newnode->pow=curr2->pow;
            curr2=curr2->next;
        }
        else
        {
            newnode->coef=curr1->coef+curr2->coef;
            newnode->pow=curr2->pow;
            curr1=curr1->next;
            curr2=curr2->next;
        }
        if(curr1==NULL&&curr2!=NULL)
        {
            newnode->coef=curr2->coef;
            newnode->pow=curr2->pow;
            curr2=curr2->next;   
        }
        if(curr2==NULL&&curr1!=NULL)
        {
            newnode->coef=curr1->coef;
            newnode->pow=curr1->pow;
            curr1=curr1->next;
        }
        curr3->next=newnode;
        curr3=newnode;
        curr3->next=NULL;
    }
    return head3; 
}
main()
{
    int ch;
    poly *head1=NULL;
    poly *head2=NULL;
    while((ch=menu())!=0)
    {
        if(ch==1)
            create(&head1);
        else
        if(ch==2)
            create(&head2);
        else
        if(ch==3)
        {
            printf("\n\t1'st Polynomial\t\t");   
            display(head1);
            printf("\n");
            printf("\n\t2'nd Polynomial\t\t");
            display(head2);
            getchar();getchar();
        }
        else
        if(ch==4)
        {
            poly *head3=NULL;
            b_sort(head1);
            b_sort(head2);
            head3=add(head1,head2);
            printf("\n\tResult\t\t");
            adddisplay(head3);
            getchar();getchar();
        }
    }
}

Output:
add two polynomials using linked list with output
add two polynomials using linked list with output

Post a Comment

0 Comments