cpp/multiply_two_polynomials_using_linkedlist.cpp at master · anujjain5699/cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int coeff,pow;
    Node* next;
};

Node* addNode(Node* head,int coeff,int pow)
{
    Node* new_node=new Node;
    new_node->coeff=coeff;
    new_node->pow=pow;
    new_node->next=NULL;

    if(head==NULL)
    return new_node;

    Node* ptr=head;
    while(ptr->next!=NULL)
    ptr=ptr->next;
    ptr->next=new_node;
    return head;
}

void print(Node* head)
{
    while(head->next)
    {
        cout<<head->coeff<<"x^"<<head->pow<<" + ";
        head=head->next;
    }
    cout<<head->coeff<<"\n";
}

void removeDuplicate(Node* head)
{
    Node *ptr1,*ptr2,*dup;
    ptr1=head;
    while(ptr1 && ptr1->next)
    {
        ptr2=ptr1;
        while(ptr2->next)
        {
            if(ptr1->pow==ptr2->next->pow)
            {
                ptr1->coeff=ptr1->coeff+ptr2->next->coeff;
                dup=ptr2->next;
                ptr2->next=ptr2->next->next;
                delete(dup);
            }
            else
            ptr2=ptr2->next;
        }
        ptr1=ptr1->next;
    }
}

Node* multiply(Node* poly1,Node* poly2,Node* poly3)
{
    Node *ptr1,*ptr2;
    ptr1=poly1;
    ptr2=poly2;
    while(ptr1)
    {
        while(ptr2)
        {
            int coeff,pow;
            coeff=ptr1->coeff*ptr2->coeff;
            pow=ptr1->pow+ptr2->pow;
            poly3=addNode(poly3,coeff,pow);
            ptr2=ptr2->next;
        }
        ptr2=poly2;
        ptr1=ptr1->next;
    }
    removeDuplicate(poly3);
    return poly3;
}

int main()
{
    Node *poly1=NULL,*poly2=NULL,*poly3=NULL;
    poly1=addNode(poly1,3,2);
    poly1=addNode(poly1,5,1);
    poly1=addNode(poly1,6,0);
    poly1=addNode(poly1,6,0);
    //removing duplicate from polynomial also necessary
    removeDuplicate(poly1);
    poly2=addNode(poly2,6,1);
    poly2=addNode(poly2,12,1);
    poly2=addNode(poly2,8,0);
    removeDuplicate(poly2);
    cout<<"polynomial 1: ";
    print(poly1);
    cout<<"polynomial 2: ";
    print(poly2);
    poly3=multiply(poly1,poly2,poly3);
    cout<<"Resultant polynomial: ";
    print(poly3);
    return 0;
}