Addition Of Polynomials Using Linked List
Given two polynomials, represented by a linked list, write a function to add these polynomials and set the result to new polynomial represented by a linked list.
Adding polynomials means adding the coefficients of polynomial terms having equal power and appending the remaining terms of both polynomials.
Addition Of Polynomials Using C++ | Linked List Implementation
#include<iostream>
using namespace std;
class Node{
private:
int coeff;
int power;
char sign;
Node* next;
friend class Polynomial;
};
class Polynomial{
private:
Node* head = NULL;
void sort(){
if(this->head == NULL) return;
Node* tmp = head;
bool sorted = true;
while(sorted){
sorted = false;
Node* inner = head;
while(inner->next != NULL){
if(inner->power < inner->next->power){
int tmpCoeff = inner->coeff;
int tmpPower = inner->power;
char tmpSign = inner->sign;
inner->coeff = inner->next->coeff;
inner->power = inner->next->power;
inner->sign = inner->next->sign;
inner->next->coeff = tmpCoeff;
inner->next->power = tmpPower;
inner->next->sign = tmpSign;
sorted = true;
}
inner = inner->next;
}
}
}
public:
Polynomial(){
this->head = NULL;
}
void create(){
this->head = NULL;
int coeff, power;
char again = 'n';
do{
cout<<"enter coefficient"<<endl;
cin>>coeff;
cout<<"enter power"<<endl;
cin>>power;
Node* node = new Node[1];
node->coeff = coeff;
node->power = power;
node->sign = coeff < 0 ? '-' : '+';
if(this->head == NULL){
this->head = node;
}else{
Node* tmp = this->head;
while(tmp->next != NULL){
tmp = tmp->next;
}
tmp->next = node;
}
sort();
do{
cout<<"enter another node ? y/n"<<endl;
cin>>again;
}while(again != 'n' && again != 'y');
}while(again != 'n');
}
Polynomial add(Polynomial& p){
Node* a = this->head;
Node* b = p.head;
Polynomial* result = new Polynomial[0];
bool compared = false;
while(a != NULL){
compared = false;
b = p.head;
while(b != NULL){
if(b->power == a->power){
Node* addedNode = new Node[1];
addedNode->power = b->power;
addedNode->next = NULL;
addedNode->coeff = a->coeff + b->coeff;
addedNode->sign = addedNode->coeff < 0 ? '-': '+';
if(result->head == NULL){
result->head = addedNode;
} else{
Node* shifted = result->head;
while(shifted->next != NULL){
shifted = shifted->next;
}
shifted->next = addedNode;
}
compared = true;
}
b = b->next;
}
if(!compared){
Node* addedNode = new Node[1];
addedNode->power = a->power;
addedNode->coeff = a->coeff;
addedNode->sign = a->sign;
addedNode->next = NULL;
if(result->head == NULL){
result->head = addedNode;
} else{
Node* shifted = result->head;
while(shifted->next != NULL){
shifted = shifted->next;
}
shifted->next = addedNode;
}
}
a = a->next;
}
//remaining from b
b = p.head;
bool exists = false;
while(b != NULL){
a = result->head;
while(a != NULL){
if(b->power == a->power){
exists = true;
}
a = a->next;
}
if(!exists){
Node* toAdd = new Node[1];
toAdd->power = b->power;
toAdd->coeff = b->coeff;
toAdd->sign = b->sign;
toAdd->next = NULL;
if(result->head == NULL){
result->head = toAdd;
} else{
Node* shifted = result->head;
while(shifted->next != NULL){
shifted = shifted->next;
}
shifted->next = toAdd;
}
}
b = b->next;
}
sort();
return *result;
}
void display(){
if(this->head == NULL){
cout<<"Polynomial Not Set !"<<endl;
return;
}else{
Node* tmp = head;
char sign;
while(tmp != NULL){
if(tmp == head){
cout<<tmp->coeff<<"x^"<<tmp->power<<" ";
}else{
cout<<tmp->sign<<abs(tmp->coeff)<<"x^"<<tmp->power<<" ";
}
tmp = tmp->next;
}
cout<<endl;
}
}
// ~Polynomial(){
// delete head;
// cout<<"head destroyed !"<<endl;
// }
};
int main(){
Polynomial p1, p2;
bool exit = false;
do{
cout<<"===================================="<<endl;
cout<<"select option :"<<endl;
cout<<"1: set first polynomial"<<endl;
cout<<"2: set second polynomial"<<endl;
cout<<"3: display two polynomials"<<endl;
cout<<"4: add two polynomials"<<endl;
cout<<"5: for exit"<<endl;
int ch;
cin>>ch;
cout<<"===================================="<<endl;
switch(ch){
case 1:
p1.create();
break;
case 2:
p2.create();
break;
case 3:
p1.display();
p2.display();
break;
case 4:
cout<<"result of addition is:"<<endl;
p1.add(p2).display();
break;
case 5:
exit = true;
cout<<"exiting..."<<endl;
break;
default:
cout<<"invalid selection !"<<endl;
break;
}
}while(!exit);
return 0;
}
Feel free to modify the code as you like.
