Cover Image

Wednesday, 24 September 2014

Application of Linked List (Addition of polynomials)

#include<iostream>
using namespace std;
typedef struct list node;
struct list
{
int coeff,expo;
node *next;
};
void disp_poly(node*);
int count(node*);
node* create_poly(int);
node* add_poly(node*,node*);
node* copyof(node*);

int main()
{
int num;
node *poly1,*poly2,*sum=NULL;
cout<<"For first polynomial enter the number of terms : ";
cin>>num;
poly1=create_poly(num);
cout<<"Polynomial so formed is : ";
disp_poly(poly1);
cout<<endl<<endl;
cout<<"For second polynomial enter the number of terms : ";
cin>>num;
poly2=create_poly(num);
cout<<"Polynomial so formed is : ";
disp_poly(poly2);
cout<<endl<<endl;
cout<<"After addition :\n";
disp_poly(poly1);
disp_poly(poly2);
cout<<" = ";
sum=add_poly(poly1,poly2);
disp_poly(sum);
return 0;
}
node* create_poly(int num)
{
node *poly=NULL,*temp;
for(int i = 1;i<=num;i++)
{
    if(poly==NULL)
    {
    poly=new node;
    poly->next=NULL;
    cout<<"Enter the coefficient and exponent for term "<<i<<" : ";
    cin>>poly->coeff>>poly->expo;
    temp=poly;
  }
  else
  {
    temp->next=new node;
    temp->next->next=NULL;
    cout<<"Enter the coefficient and exponent for term "<<i<<" : ";
    cin>>temp->next->coeff>>temp->next->expo;
    temp=temp->next;
  }
}
return poly;
}
void disp_poly(node *poly)
{
node *temp=poly;
while(temp)
{
  cout<<"+"<<temp->coeff<<"x^"<<temp->expo;
  temp=temp->next;
}
}
node* copyof(node *poly)
{
node  *sum=NULL,*temp,*temp2=poly;
while(temp2)
{
  if(sum==NULL)
  {
    sum=new node;
    sum->next=NULL;
    sum->coeff=temp2->coeff;
    sum->expo=temp2->expo;
    temp=sum;
  }
  else
   {
    temp->next=new node;
    temp->next->next=NULL;
    temp->next->coeff=temp2->coeff;
    temp->next->expo=temp2->expo;
    temp=temp->next;
  }
  temp2=temp2->next;
}
return sum;
}
int count(node *poly)
{
int c=0;
node *temp=poly;
while(temp)
{
  c++;
  temp=temp->next;
}
return c;
}
node* add_poly(node *poly1,node *poly2)
{
int sizeof_poly1,sizeof_poly2,found;
node *temp,*sum=NULL,*sum_temp;

sizeof_poly1=count(poly1);
sizeof_poly2=count(poly2);

if(sizeof_poly1>sizeof_poly2)
{
  sum=copyof(poly1);
  temp=poly2;
  while(temp)
  {
    found=0;
    sum_temp=sum;
    while(sum_temp)
    {
      if(sum_temp->expo==temp->expo)
      {
          sum_temp->coeff+=temp->coeff;
        found++;
      }
      sum_temp=sum_temp->next;
    }
    if(!found)
    {
      for(sum_temp=sum;sum_temp->next;sum_temp=sum_temp->next);// pointing to last node
      sum_temp->next=new node;
      sum_temp->next->next=NULL;
      sum_temp->next->coeff=temp->coeff;
      sum_temp->next->expo=temp->expo;
    }
    temp=temp->next;
  }
}
else
{
  sum=copyof(poly2);
  temp=poly1;
  while(temp)
  {
    found=0;
    sum_temp=sum;
    while(sum_temp)
    {
      if(sum_temp->expo==temp->expo)
      {
        sum_temp->coeff+=temp->coeff;
        found++;
       }
      sum_temp=sum_temp->next;
    }
    if(!found)
    {
      for(sum_temp=sum;sum_temp->next;sum_temp=sum_temp->next);// pointing to last node
      sum_temp->next=new node;
      sum_temp->next->next=NULL;
      sum_temp->next->coeff=temp->coeff;
      sum_temp->next->expo=temp->expo;
    }
    temp=temp->next;
  }
}
return sum;
}

Output :


No comments:

Post a Comment