Linked Lists Polynomial Manipulation

Polynomial Manipulation

• As we know a polynomial has the main fields as coefficient, exponent in linked list, it will have one more field called 'next' field to point to next term in the polynomial. If there are n terms in the polynomial then n such nodes has to be created.

• The typical node will look like this,

• For example : To represent 3x²+5x+7 the link list will be,

• In each node, the exponent field will store exponent corresponding to that term, the coefficient field will store coefficient corresponding to that term and the next field will point to next term in the polynomial. Again for simplifying the algorithms such as addition of two polynomials we will assume that the polynomial terms are stored in descending order of exponents.

The node structure for a singly linked list for representing a term of polynomial can be defined as follows:

typedef struct Pnode

{

   float coef;

   int exp;

   struct node *next;

}P;

Advantages of linked representation over arrays:

1. Only one pointer will be needed to point to first term of the polynomial.

2. No prior estimation on number of terms in the polynomial is required. This results in flexible and more space efficient representation.

3. The insertion and deletion operations can be carried out very easily without movement of data.

 

Disadvantage of linked representation over arrays:

1. We can not access any term randomly or directly we have to go from start node always.

 

Addition of Two Polynomials Represented using Singly Linear Link List

Logic for polynomial addition by linked list :

Step 1 :

First of all we create two linked polynomials.

For example

P₁ = 3x³ +2x²+1x

P₂ = 5x⁵ +3x²+7

Each node in the polynomial will look like this,

The linked list for P₁ will be,

Similarly the P₂ will be,

Step 2 :

For addition of two polynomials if exponents of both the polynomials are same then we add the coefs. For storing the result we will create the third linked list say p3. The processing will be as follows:

Step 3 :

Step 4:

Step 5 :

Step 6 :

Finally

P₃ list is the addition of two polynomials.

 

'C++' Program

/*

**********************************************************

Program To Perform Addition Of Two Polynomials Using Singly Linear Linked List

***********************************************************

*/

#include<iostream>

#include<cstdlib>

using namespace std;

#define TRUE 1

#define FALSE 0

class Lpadd

{

private:

typedef struct pnode

{

   float coef;

   int exp;

   structpnode *next;

}p;

p *head;

public:

Lpadd();

void get_poly(),add(Lpadd,Lpadd);

void display();

p *Attach(int,float,p *);

~Lpadd();

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

Lpadd::Lpadd()

{

   head = NULL;

}

void Lpadd::get_poly()

{

   p *New, *last;

   int Exp,flag;

   float Coef;

   char ans='y';

   flag = TRUE; // flag to indicate whether a new node

   // is created for the first time or not

   cout<<"\nEnter the polynomial in desending order of exponent\n";

   do

   {

      cout<<"\nEnter the Coefficient and Exponent of a term :";

      cin>>Coef>>Exp;

      // allocate new node

      New = new p;

      New‒>next=NULL;

      if ( New = = NULL )

      cout<<"\nMemory can not be allocated";

      New‒˃ coef = Coef;

      //putting coef,exp values in the node

      New ‒> exp = Exp ;

      if (flag= =TRUE) // Executed only for the first time

                             //for creating the first node

      {

         head = New;

         last = head;

         flag = FALSE;

      }

      else

      {

         // last keeps track of the most recently

         // created node

         last ‒>next = New;

         last = New;

      }

      cout<<"\n Do you Want To Add more Terms?(y/n)";

      ans=getch();

      while(ans= ='y');

      return;

}

void Lpadd::display()

{

   p *temp;

   temp=head;

   if ( temp = = NULL)

   {

      cout<<"The polynomial is empty\n";

      getch();

      return;

   }

   cout<<endl;

   while (temp‒>next = NULL)

   {

      cout<<temp‒>coef<<" x^ "<<temp‒>exp<<"+ ";

      temp = temp −> next;

   }

   cout<<temp ‒>coef<<<" x^ "<<temp ‒>exp;

   getch();

}

void Lpadd::add(Lpadd p1,Lpadd p2)

{

   p *temp1, *temp2,*dummy;

   float Coef;

   temp1 =p1.head;

   temp2 =p2.head;

   head = new p;

   if (head = = NULL)

   cout<<"\nMemory can not be allocated";

   dummy = head;//dummy is a start node

   while (temp1 |= NULL && temp2 |= NULL)

   {                                                   

   if(temp1‒>exp= =temp2‒>exp)

   {

      Coef =temp1‒>coef + temp2‒>coef;

      head = Attach(temp1‒>exp,Coef,head);

      temp1 = temp1‒>next;

      temp2 = temp2‒>next;

   }

   else if(temp1‒>exp<temp2‒>exp)

   {

      Coef = temp2 ‒> coef;

      head = Attach(temp2‒>exp, Coef,head);

      temp2 = temp2 ‒> next ;

   }

   else if(temp1‒>exp>temp2‒>exp)

   {

      Coef = temp1‒> coef;

      head = Attach(temp1‒>exp, Coef,head);

      temp1 = temp1‒> next ;

   }

}

//copying the contents from first polynomial to the resultant

//poly

while (temp1 != NULL)

{

   head = Attach(temp1‒>exp,temp1‒>coef,head);

   temp1 = temp1 ‒> next;

}

//copying the contents from second polynomial to the resultant poly.

while (temp2 != NULL )

{

   head =Attach(temp2‒>exp,temp2‒>coef,head);

   temp2 =temp2 ‒> next;

}

head ‒>next = NULL;

head = dummy ‒>next;//Now set temp as starting node

delete dummy;

return;

}

p *Lpadd::Attach( int Exp, float Coef, p *temp)

{

   p *New, *dummy;

   New = new p;

   if (New = = NULL )

      cout<<"\n Memory can not be allocated \n";

   New‒>exp = Exp;

   New‒>coef = Coef;

   New‒>next = NULL;

   dummy = temp;

   dummy‒>next = New;

   dummy = New;

   return(dummy);

}

Lpadd::~Lpadd()

{

   p *temp;

   temp = head;

   while(head!= NULL)

   {

      temp = temp‒>next;

      delete head;

      head=temp;

   }

}

void main()

{

   Lpadd p1,p2,p3;

   clrscr();

   cout<<"\n Enter the first polynomial\n\n";

   p1.get_poly();

   clrscr();

   cout<<"\nEnter the Second polynomial\n\n";

   p2.get_poly();

   clrscr();

   cout<<"\nThe first polynomial is \n";

   p1.display();

   cout<<"\nThe second polynomial is\n";

   p2.display();

   p3.add(p1,p2);

   cout<<"\nThe Addition of the Two polynomials is...\n";

   p3.display();

   exit(0);

}

Output

Enter the first polynomial

Enter the polynomial in desending order of exponent

Enter the Coefficient and Exponent of a term :3 3

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :2 2

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :1 1

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :5 0

Do you Want To Add more Terms?(y/n)n

Enter the Second polynomial

Enter the polynomial in desending order of exponent

Enter the Coefficient and Exponent of a term :5 1

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :7 0

Do you Want To Add more Terms?(y/n)

The first polynomial is

3 x ^3+ 2 x^ 2+ 1 x^ 1+ 5 x^ 0

The second polynomial is

5 x ^1+7 x^ 0

The Addition of the Two polynomials is...

3 x ^3+2 x ^2+ 6 x^ 1+ 12 x^ 0

 

Review Questions

1. Write a C++ code to perform addition of two polynomials using link list form of queue.

2. Discuss about addition of two polynomials using linked list with necessary ADT.