1// Aim: Program to perform Linked List operations (Polynomial operations).
2#include<stdio.h>
3#include<stdlib.h>
4struct node
5{
6    int coef;
7    int expo;
8    struct node *link;
9};
10
11struct node *create(int coef, int expo)
12{
13    struct node *newnode = (struct node *)malloc(sizeof(struct node));
14    newnode->coef = coef;
15    newnode->expo = expo;
16    newnode->link = NULL;
17    return newnode;
18}
19
20struct node *insert(struct node *head, int coef, int expo)
21{
22    struct node *newnode = create(coef, expo);
23    if(head == NULL)
24    {
25        return newnode;
26    }
27    if(expo > head->expo)
28    {
29        newnode->link = head;
30        return newnode;
31    }
32    struct node *current = head;
33    while(current->link != NULL && current->link->expo > expo)
34    {
35        current = current->link;
36    }
37    newnode->link = current->link;
38    current->link = newnode;
39    return head;
40}
41
42void display(struct node *head)
43{
44    while(head != NULL)
45    {
46        printf("%dx^%d", head->coef, head->expo);
47        head = head->link;
48        if(head != NULL)
49        {
50            printf(" + ");
51        }
52    }
53    printf("\n");
54}
55
56struct node *readpoly(){
57    struct node *head = NULL;
58    int n, coef, expo;
59    printf("Enter the number of terms: ");
60    scanf("%d", &n);
61    printf("Enter the coefficient and exponent: ");
62    for(int i = 0; i < n; i++)
63    {
64        scanf("%d %d", &coef, &expo);
65        head = insert(head, coef, expo);
66    }
67    return head;
68}
69
70struct node *addpoly(struct node *p1, struct node *p2)
71{
72    struct node *result = NULL;
73    struct node *ptr1 = p1, *ptr2 = p2;
74    while(ptr1 != NULL && ptr2 != NULL)
75    {
76        if(ptr1==NULL)
77        {
78            result = insert(result, ptr2->coef, ptr2->expo);
79            ptr2 = ptr2->link;
80        }
81        else if(ptr2==NULL)
82        {
83            result = insert(result, ptr1->coef, ptr1->expo);
84            ptr1 = ptr1->link;
85        }
86        else if(ptr1->expo == ptr2->expo)
87        {
88            result = insert(result, ptr1->coef + ptr2->coef, ptr1->expo);
89            ptr1 = ptr1->link;
90            ptr2 = ptr2->link;
91        }
92        else if(ptr1->expo > ptr2->expo)
93        {
94            result = insert(result, ptr1->coef, ptr1->expo);
95            ptr1 = ptr1->link;
96        }
97        else
98        {
99            result = insert(result, ptr2->coef, ptr2->expo);
100            ptr2 = ptr2->link;
101        }
102    }
103    return result;
104}
105
106struct node *multipoly(struct node *p1, struct node *p2)
107{
108    struct node *result = NULL;
109    struct node *ptr1 = p1;
110    while(ptr1 != NULL)
111    {
112        struct node *ptr2 = p2;
113        while(ptr2 != NULL)
114        {
115            int res1 = ptr1->coef * ptr2->coef;
116            int res2 = ptr1->expo + ptr2->expo;
117            result = insert(result, res1, res2);
118            ptr2 = ptr2->link;
119        }
120        ptr1 = ptr1->link;
121    }
122    return result;
123}
124
125
126struct node *simplify(struct node *head)
127{
128    struct node *ptr1 = head, *ptr2, *dup;
129    while(ptr1 != NULL && ptr1->link != NULL)
130    {
131        ptr2 = ptr1;
132        while(ptr2->link != NULL)
133        {
134            if(ptr1->expo == ptr2->link->expo)
135            {
136                ptr1->coef = ptr1->coef + ptr2->link->coef;
137                dup = ptr2->link;
138                ptr2->link = ptr2->link->link;
139                free(dup);
140            }
141            else
142            {
143                ptr2 = ptr2->link;
144            }
145        }
146        ptr1 = ptr1->link;
147    }
148    return head;
149}
150
151int main()
152{
153    struct node *poly1 = NULL, *poly2 = NULL;
154    printf("Enter the first polynomial:\n");
155    poly1 = readpoly();
156    printf("Enter the second polynomial:\n");
157    poly2 = readpoly();
158    printf("The first polynomial is: ");
159    display(poly1);
160    printf("The second polynomial is: ");
161    display(poly2);
162    struct node *addition = addpoly(poly1, poly2);
163    printf("The sum of the polynomials is: ");
164    display(addition);
165    struct node *multiplication = multipoly(poly1, poly2);
166    multiplication = simplify(multiplication);
167    printf("The product of the polynomials is: ");
168    display(multiplication);
169    return 0;
170}