REC-Data-Structures-Digital-Cafe/polynomial_addition.c at main · CrypticFate5/REC-Data-Structures-Digital-Cafe · 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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// Find the sum of two polynomial numbers. Represent the polynomial number using single linked List

// Input Format :

// First line contains the degree of the 1st polynomial

// Second line contains the Coefficient of 1st polynomial

// Third line contains the degree of the 2nd polynomial

// Fourth line contains the Coefficient of 2nd polynomial

// Sample Input :

// 3

// 5 2 0 1

// 2

// 4 3 1

// Sample Output:

// 5x^3 + 6x^2 + 3x^1 + 2

// Explanation:

// 5x^3 + 2x^2 + 1   +   4x^2 + 3x^1 + 1 =  5x^3 + 6x^2 + 3x^1 + 2


#include <stdio.h>
#include <stdlib.h>
struct node
{
    int coeff;
    struct node *next;
    int pow;
};
typedef struct node node;
void insert(node *poly, int c, int x)
{
    node *newnode = malloc(sizeof(node));
    newnode->coeff = c;
    newnode->pow = x;
    newnode->next = NULL;
    node *pos = poly;
    while (pos->next != NULL)
    {
        pos = pos->next;
    }
    pos->next = newnode;
}
void sum(node *poly1, node *poly2, node *result)
{
    node *pos1 = poly1->next;
    node *pos2 = poly2->next;
    while (pos1 != NULL && pos2 != NULL)
    {
        if (pos1->pow == pos2->pow)
        {
            int x;
            x = pos1->coeff + pos2->coeff;
            insert(result, x, pos1->pow);
            pos1 = pos1->next;
            pos2 = pos2->next;
        }
        else if (pos1->pow > pos2->pow)
        {
            insert(result, pos1->coeff, pos1->pow);
            pos1 = pos1->next;
        }
        else if (pos1->pow < pos2->pow)
        {
            insert(result, pos2->coeff, pos2->pow);
            pos2 = pos2->next;
        }
    }
}
void traverse(node *poly)
{
    node *pos = poly;
    while (pos->next->next != NULL)
    {
        pos = pos->next;
        printf("%dx^%d", pos->coeff, pos->pow);
        if (pos->next->coeff >= 0)
            printf("+");
    }
    printf("%d", pos->next->coeff);
}
int main()
{
    node *poly1 = malloc(sizeof(node));
    node *poly2 = malloc(sizeof(node));
    node *result = malloc(sizeof(node));
    poly1->next = NULL;
    poly2->next = NULL;
    result->next = NULL;
    int n1, n;
    scanf("%d", &n1);
    n = n1;
    for (int i = 0; i < n1 + 1; i++)
    {
        int j;
        scanf("%d", &j);
        insert(poly1, j, n);
        n--;
    }
    int n2;
    scanf("%d", &n2);
    n = n2;
    for (int i = 0; i < n2 + 1; i++)
    {
        int j;
        scanf("%d", &j);
        insert(poly2, j, n);
        n--;
    }
    sum(poly1, poly2, result);
    traverse(result);
    return 0;
}