3.Write a C program to implement Polynomial addition and Polynomial multiplication using Linked List.
a. Program:(addition)
#include <stdio.h>
#include <stdlib.h>
struct Term
{
int coefficient;
int exponent;
};
struct Polynomial
{
int numTerms;
struct Term *terms;
};
void createPolynomial(struct Polynomial *poly)
{
int i;
printf("Enter the number of terms: ");
scanf("%d", &poly->numTerms);
poly->terms = (struct Term *)malloc(poly->numTerms * sizeof(struct Term));
printf("Enter the terms:\n");
for (i = 0; i< poly->numTerms; i++)
scanf("%d%d", &poly->terms[i].coefficient, &poly->terms[i].exponent);
printf("\n");
}
void displayPolynomial(struct Polynomial poly)
{
int i;
for (i = 0; i<poly.numTerms; i++)
{
printf("%dx^%d", poly.terms[i].coefficient, poly.terms[i].exponent);
if (i + 1 <poly.numTerms)
printf(" + ");
}
printf("\n");
}
struct Polynomial *addPolynomials(struct Polynomial *poly1, struct Polynomial *poly2)
{
int i, j, k;
struct Polynomial *sum;
sum = (struct Polynomial *)malloc(sizeof(struct Polynomial));
sum->terms = (struct Term *)malloc((poly1->numTerms + poly2->numTerms) * sizeof(struct Term));
i = j = k = 0;
while (i< poly1->numTerms&& j < poly2->numTerms)
{
if (poly1->terms[i].exponent> poly2->terms[j].exponent)
sum->terms[k++] = poly1->terms[i++];
else if (poly1->terms[i].exponent< poly2->terms[j].exponent)
sum->terms[k++] = poly2->terms[j++];
else
{
sum->terms[k].exponent = poly1->terms[i].exponent;
sum->terms[k++].coefficient = poly1->terms[i++].coefficient + poly2->terms[j++].coefficient;
}
}
for (; i< poly1->numTerms; i++)
sum->terms[k++] = poly1->terms[i];
for (; j < poly2->numTerms; j++)
sum->terms[k++] = poly2->terms[j];
sum->numTerms = k;
return sum;
}
int main()
{
struct Polynomial poly1, poly2, *polySum;
printf("Enter Polynomial 1:\n");
createPolynomial(&poly1);
printf("Enter Polynomial 2:\n");
createPolynomial(&poly2);
polySum = addPolynomials(&poly1, &poly2);
printf("\n");
printf("Polynomial 1 is: ");
displayPolynomial(poly1);
printf("\n");
printf("Polynomial 2 is: ");
displayPolynomial(poly2);
printf("\n");
printf("Sum of the polynomials is: ");
displayPolynomial(*polySum);
free(poly1.terms);
free(poly2.terms);
free(polySum->terms);
free(polySum);
return 0;
}
Output:
Enter the number of terms: 3
Enter the terms:
32
31
13
Enter Polynomial 2:
Enter the number of terms: 3
Enter the terms:
12
21
32
Polynomial 1 is: 3x^2 + 3x^1 + 1x^3
Polynomial 2 is: 1x^2 + 2x^1 + 3x^2
Sum of the polynomials is: 4x^2 + 5x^1 + 1x^3 + 3x^2
b. Program:(multiplication)
#include <bits/stdc++.h>
using namespace std;
// Node structure containing powerer
// and coefficient of variable
struct Node {
int coeff, power;
Node* next;
};
// Function add a new node at the end of list
Node* addnode(Node* start, int coeff, int power)
{
// Create a new node
Node* newnode = new Node;
newnode->coeff = coeff;
newnode->power = power;
newnode->next = NULL;
// If linked list is empty
if (start == NULL)
return newnode;
// If linked list has nodes
Node* ptr = start;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = newnode;
return start;
}
// Function To Display The Linked list
void printList(struct Node* ptr)
{
while (ptr->next != NULL) {
cout << ptr->coeff << "x^" << ptr->power ;
if( ptr->next!=NULL && ptr->next->coeff >=0)
cout << "+";
ptr = ptr->next;
}
cout << ptr->coeff << "\n";
}
// Function to add coefficients of
// two elements having same powerer
void removeDuplicates(Node* start)
{
Node *ptr1, *ptr2, *dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
// Compare the picked element
// with rest of the elements
while (ptr2->next != NULL) {
// If powerer of two elements are same
if (ptr1->power == ptr2->next->power) {
// Add their coefficients and put it in 1st element
ptr1->coeff = ptr1->coeff + ptr2->next->coeff;
dup = ptr2->next;
ptr2->next = ptr2->next->next;
// remove the 2nd element
delete (dup);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
// Function two Multiply two polynomial Numbers
Node* multiply(Node* poly1, Node* poly2,
Node* poly3)
{
// Create two pointer and store the
// address of 1st and 2nd polynomials
Node *ptr1, *ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != NULL) {
while (ptr2 != NULL) {
int coeff, power;
// Multiply the coefficient of both
// polynomials and store it in coeff
coeff = ptr1->coeff * ptr2->coeff;
// Add the powerer of both polynomials
// and store it in power
power = ptr1->power + ptr2->power;
// Invoke addnode function to create
// a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
// move the pointer of 2nd polynomial
// two get its next term
ptr2 = ptr2->next;
}
// Move the 2nd pointer to the
// starting point of 2nd polynomial
ptr2 = poly2;
// move the pointer of 1st polynomial
ptr1 = ptr1->next;
}
// this function will be invoke to add
// the coefficient of the elements
// having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
}
// Driver Code
int main()
{
Node *poly1 = NULL, *poly2 = NULL, *poly3 = NULL;
// Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 3);
poly1 = addnode(poly1, 6, 1);
poly1 = addnode(poly1, -9, 0);
// Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 9, 3);
poly2 = addnode(poly2, -8, 2);
poly2 = addnode(poly2, 7, 1);
poly2 = addnode(poly2, 2, 0);
// Displaying 1st polynomial
cout << "1st Polynomial:- ";
printList(poly1);
// Displaying 2nd polynomial
cout << "2nd Polynomial:- ";
printList(poly2);
// calling multiply function
poly3 = multiply(poly1, poly2, poly3);
// Displaying Resultant Polynomial
cout << "Resultant Polynomial:- ";
printList(poly3);
return 0;
}
Output:
1st Polynomial:- 3x^3+6x^1-9
2nd Polynomial:- 9x^3-8x^2+7x^1+2
Resultant Polynomial:- 27x^6-24x^5+75x^4-123x^3+114x^2-51x^1-18
