Polynimial Operation

Wrote by Unknown 01:02 Post Comment


Algorithm : Polynomial Operations

Let us consider a polynomial expression of single variable x stored in a linked list
pointed by header node p. The nodes are arranged in descending order of exponent starting
from the header.The algorithm ‘Evaluate’ calculates the value of the polynomial depending
on the value of the x user gives. 
Evaluate(p,x)
{
  if(p->link=NULL)
	print "There is no expression to solve..!"
  else
	{
	s=0
	trav=p->link
	while(trav≠NULL)
		{
		s=s+trav->coeff*(x^trav->exp)  
		trav=trav->link
		}
	print s
	}
}

Let us consider there are two such polynomial expressions stored in two single linked list
pointed by header p1 and p2 respectively. Now the first algorithm ‘Addition’ adds the above
two polynomials and store the output polynomial in another linked list pointed by p3.
And the second algorithm ‘Multiplication’ multiplies the above two polynomials and store
the output polynomial in another linked list pointed by p3.

Addition(p1,p2,p3)
{
  m1=p1->link
  m2=p2->link
  while(m1≠NULL && m2≠NULL)					 
	{								  
	t=getnode()
	if(m1->exp>m2->exp)
		{
		t->exp=m1->exp
		t->coeff=m1->coeff
		m1=m1->link
		}
	

     else if(m1->expexp)
		{
		t->exp=m2->exp
		t->coeff=m2->coeff
		m2=m2->link
		}
	else
		{
		r=m1->coeff+m2->coeff
		if(r≠0)
			{
			t->exp=m1->exp
			t->coeff=r
			}
		else
			t=NULL
		m1=m1->link
		m2=m2->link
		}
	if(t≠NULL)
		{        	if(p3->link=NULL)
			{
			p3->link=t
			trav=t
			}
		else
			{
			trav->link=t
			trav=trav->link
			}
		}
	}
while(m1≠NULL)							
	{
	t=getnode()
	t->exp=m1->exp
	t->coeff=m1->coeff
	m1=m1->link
	trav->link=t
	trav=trav->link
	}

while(m2≠NULL)
	{
	t=getnode()
	t->exp=m2->exp
	t->coeff=m2->coeff
	m2=m2->link
	trav->link=t
	trav=trav->link
	}
show(p3)
}


Multiplication(p1,p2,p3)
{
  m1=p1->link
  while(m1≠NULL)
	{
	 m2=p2->link
	 while(m2≠NULL)
		{
		c=m1->coeff*m2->coeff
		e=m1->exp+m2->exp
		t=getnode()
		t->exp=e
		t->coeff=c
		if(p3->link=NULL)
			p3->link=t
		else
			{
			trav=p3->link
			while(trav≠NULL && trav->exp>=t->exp)
				{
				save=trav
				trav=trav->link
				}
			if(save->exp=t->exp)
				{
				save->coeff=save->coeff+t->coeff
				}
			else
				{
				save->link=t
				t->link=trav
				}
			}
		 m2=m2->link
		}
	 m1=m1->link
	}
 show(p3)
}

Here we use two functions show(header) and getnode().
The 1st one shows the elements in the linked list pointed by header.
The 2nd one creates a node and return it's address to the pointer variable.


C Program For Polynimial Operation
1.Creation
2.Evaluation
3.Addition
4.Multiplication.
5.Show
6.Exit


Source Code:




#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node
{
 int coef;
 int exp;
 struct node *link;
};


struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=NULL;
 return t;
};

void create(struct node *P)
{
  struct node *trav,*t;
  int i,n,co,ex;

  printf("\nEnter number of terms:");
  scanf("%d",&n);
  for(i=1;i<=n;i++)
   {
     t=getnode();
     printf("\nEnter co-ef of term-%d :",i);
     scanf("%d",&co);
     printf("\nEnter expo of term-%d :",i);
     scanf("%d",&ex);
     t->coef=co;
     t->exp=ex;
     if(P->link==NULL)
      {
	 P->link=t;
	 trav=P->link;
      }
     else
      {
	 trav->link=t;
	 trav=t;
      }
   }
}
void show(struct node *P)
{
  struct node *trav;
  if(P->link==NULL)
   {
     printf("\nPolynomial not created.");
   }
  else
   {
     printf("\nThe polynomial is:\t");
     trav=P->link;
     while(trav!=NULL)
      {
	if(trav->exp==0)
	 {
	   printf("%d",trav->coef);
	 }
	else
	 {
	   printf("%dX^%d+",trav->coef,trav->exp);
	 }
	trav=trav->link;
      }
   }
}



void evaluate(struct node *P,int x)
{
  float s;

  struct node *trav,*t;
  if(P->link==NULL)
   {
     printf("\nList empty.");
   }
  else
   {
     s=0;
     trav=P->link;
     while(trav!=NULL)
      {
	 s=s+(trav->coef)*pow(x,trav->exp);
	 trav=trav->link;
      }
     printf("\nValue of the polynomial(for x=%d) =%g",x,s);
   }
}


void add(struct node *p1,struct node *p2)
{
  int r;
  struct node *m1,*m2,*t,*trav,*p3;
  p3->link=NULL;
  m1=p1->link;
  m2=p2->link;
  while(m1!=NULL && m2!=NULL)
   {
     if(m1->exp>m2->exp)
      {
	t=getnode();
	t->exp=m1->exp;
	t->coef=m1->coef;
	m1=m1->link;
      }
     else if(m1->expexp)
      {
	t=getnode();
	t->exp=m2->exp;
	t->coef=m2->coef;
	m2=m2->link;
      }
     else if(m1->exp==m2->exp)
      {
	r=m1->coef+m2->coef;
	if(r!=0)
	 {
	   t=getnode();
	   t->coef=r;
	   t->exp=m1->exp;
	 }
	else
	 {
	   t=NULL;
	 }
	m1=m1->link;
	m2=m2->link;
      }
     if(t!=NULL)
      {
	if(p3->link==NULL)
	 {
	   p3->link=t;
	   trav=t;
	 }
	else
	 {
	   trav->link=t;
	   trav=trav->link;
	 }
      }
   }
  while(m1!=NULL)
   {
     t=getnode();
     t->exp=m1->exp;
     t->coef=m1->coef;
     m1=m1->link;
     trav->link=t;
     trav=trav->link;
   }
  while(m2!=NULL)
   {
     t=getnode();
     t->exp=m2->exp;
     t->coef=m2->coef;
     m2=m2->link;
     trav->link=t;
     trav=trav->link;
   }
  show(p3);
}


void polymult(struct node *p1,struct node *p2)
{
  int c,e;
  struct node *m1,*m2,*trav,*save,*t,*p3;
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
     {
	c=m1->coef*m2->coef;
	e=m1->exp+m2->exp;
	t=getnode();
	t->exp=e;
	t->coef=c;
	if(p3->link==NULL)
	 {
	   p3->link=t;
	 }
	else
	 {
	   trav=p3->link;
	   while(trav!=NULL && trav->exp>=t->exp)
	   {
	     save=trav;
	     trav=trav->link;
	   }
	   if(save->exp==t->exp)
	    {
	      save->coef=save->coef+t->coef;
	    }
	    else
	     {
	       save->link=t;
	       t->link=trav;
	     }
	  }
	 m2=m2->link;
     }
    m1=m1->link;
  }
  show(p3);
}



void main()
{
  int ch,ch1,x,ch4,ch3;
  struct node *p1,*p2,*p3;
  
  while(1)
  {
    printf("\n@ Polynomial operations:");
    printf("\n\t1.Creation.\n\t2.Evaluation\n\t3.Addition\n\t4.Multiplication.\n\t5.Show\n\t6.Exit");  
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
     {
       case 1:printf("\nCreate=>1.poly-1 2.poly-2");
              printf("\nEnter your choice:");
              scanf("%d",&ch4);
              switch(ch4)
              {
                case 1:
                       p1=getnode();
                       create(p1);
                       break;
                case 2:
                       p2=getnode();
                       create(p2); 
                       break;
              }
              break;
       case 2:
              printf("\nEvaluate=>1.poly-1 2.poly-2");
              printf("\nEnter your choice:");
              scanf("%d",&ch4);
              switch(ch4)
              {
                case 1:
                       printf("\nEnter the value of x :");
                       scanf("%d",&x);
                       evaluate(p1,x);
                       break;
                case 2:
                       printf("\nEnter the value of x :");
                       scanf("%d",&x);
                       evaluate(p2,x); 
                       break;
              }
              break;
              
       case 3:
	      add(p1,p2);

	      break;
       case 4:
	      polymult(p1,p2);

	      break;
       case 5:
	      printf("\nshow=>1.poly-1 2.poly-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch3);
	      switch(ch3)
	      {
		case 1:

		       show(p1);
		       break;
		case 2:

		       show(p2);
		       break;
	      }
	      break;
       case 6:
	      exit(0);
     }
  }
}



 OUTPUT :
  
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:1

Create=>1.poly-1 2.poly-2
Enter your choice:1

Enter number of terms:3

Enter co-ef of term-1 :3

Enter expo of term-1 :2

Enter co-ef of term-2 :4

Enter expo of term-2 :1

Enter co-ef of term-3 :1

Enter expo of term-3 :0

@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:1

Create=>1.poly-1 2.poly-2
Enter your choice:2

Enter number of terms:2

Enter co-ef of term-1 :2

Enter expo of term-1 :1

Enter co-ef of term-2 :3

Enter expo of term-2 :0

@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:5

show=>1.poly-1 2.poly-2
Enter your choice:1

The polynomial is:      3X^2+4X^1+1
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:5

show=>1.poly-1 2.poly-2
Enter your choice:2

The polynomial is:      2X^1+3
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:2

Evaluate=>1.poly-1 2.poly-2
Enter your choice:1

Enter the value of x :2

Value of the polynomial(for x=2) =21
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:3

The polynomial is:      3X^2+6X^1+4
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:4

The polynomial is:      6X^3+17X^2+14X^1+3



*************************Another Method Of Polynimial Operation*******************************

Source Code:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

struct node
{
    int coef;
    int expo;
    struct node *link;
};

struct node *create(struct node *);
struct node *insert_s(struct node *,float,int);
struct node *insert(struct node *,float,int);
void display(struct node *ptr);
void poly_add(struct node *,struct node *);
void poly_mult(struct node *,struct node *);
int main()
{
    struct node *start1=NULL,*start2=NULL;
    int c,ch;
    printf("Enter polynomial 1 :\n\n");
    start1=create(start1);

    printf("Enter polynomial 2 :\n\n");
    start2=create(start2);

    printf("Polynomial 1 is :  ");
    display(start1);
    printf("Polynomial 2 is :  ");
    display(start2);
    do
    {
	printf("****MENU****");
	printf("\n1. Addition");
	printf("\n2. multiplication");
	printf("\n3. Exit");
	printf("\nenter your choice(1-3):");
	scanf("%d",&c);
	switch(c)
	{
		case 1:  poly_add(start1, start2);
			 break;
		case 2:  poly_mult(start1, start2);
			  break;
		case 3:	exit(0);

		default:printf("wrong choice");
			break;
	}

	printf("do you wish to continue?(0/1):");
	scanf("%d",&ch);
    }while(ch==1);
    getch();
    return 0;
}//End of main()

struct node *create(struct node *start)
{
    int i,n,ex;
    float co;
    printf("Enter the number of terms : ");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
	printf("Enter coeficient for term %d : ",i);
	scanf("%f",&co);
	printf("Enter exponent for term %d : ",i);
	scanf("%d",&ex);
	start=insert_s(start,co,ex);
    }
    return start;
}//End of create()
struct node *insert_s(struct node *start,float co,int ex)
{
    struct node *ptr,*tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->coef=co;
    tmp->expo=ex;
    //list empty or exp greater than first one 
    if(start==NULL || ex > start->expo)
    {
	tmp->link=start;
	start=tmp;
    }
    else
    {
	ptr=start;
	while(ptr->link!=NULL && ptr->link->expo >= ex)
	    ptr=ptr->link;
	tmp->link=ptr->link;
	ptr->link=tmp;
    }
    return start;
}//End of insert()

struct node *insert(struct node *start,float co,int ex)
{
    struct node *ptr,*tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->coef=co;
    tmp->expo=ex;
    //if list is empty
    if(start==NULL)
    {
	tmp->link=start;
	start=tmp;
    }
    else    //Insert at the end of the list
    {
	ptr=start;
	while(ptr->link!=NULL)
	    ptr=ptr->link;
	tmp->link=ptr->link;
	ptr->link=tmp;
    }
    return start;
}//End of insert()

void display(struct node *ptr)
{
    if(ptr==NULL)
    {
	printf("Zero polynomial\n");
	return;
    }
    while(ptr!=NULL)
    {
	printf("(%dx^%d)", ptr->coef,ptr->expo);
	ptr=ptr->link;
	if(ptr!=NULL)
	    printf(" + ");
	else
	    printf("\n");
    }
}//End of display()
void poly_add(struct node *p1,struct node *p2)
{
    struct node *start3;
    start3=NULL;

    while(p1!=NULL && p2!=NULL)
    {
	if(p1->expo > p2->expo)
	{
	    start3=insert(start3,p1->coef,p1->expo);
	    p1=p1->link;
	}
	else if(p2->expo > p1->expo)
	{
	    start3=insert(start3,p2->coef,p2->expo);
	    p2=p2->link;
	}
	else if(p1->expo==p2->expo)
	{
	    start3=insert(start3,p1->coef+p2->coef,p1->expo);
	    p1=p1->link;
	    p2=p2->link;
	}
    }
    //if poly2 has finished and elements left in poly1
    while(p1!=NULL)
    {
	start3=insert(start3,p1->coef,p1->expo);
	p1=p1->link;
    }
    //if poly1 has finished and elements left in poly2
    while(p2!=NULL)
    {
	start3=insert(start3,p2->coef,p2->expo);
	p2=p2->link;
    }
    printf("Added polynomial is : ");
    display(start3);
}//End of poly_add()

void poly_mult(struct node *p1, struct node *p2)
{
    struct node *start3;
    struct node *p2_beg = p2;
    start3=NULL;
    if(p1==NULL || p2==NULL)
    {
	printf("Multiplied polynomial is zero polynomial\n");
	return;
    }
    while(p1!=NULL)
    {
	p2=p2_beg;
	while(p2!=NULL)
	{
	    start3=insert_s(start3,p1->coef*p2->coef,p1->expo+p2->expo);
	    p2=p2->link;
	}
	p1=p1->link;
    }

    printf("Multiplied polynomial is : ");
    display(start3);
}//End of poly_mult()


input-output:
Enter polynomial 1 :

Enter the number of terms : 3
Enter coeficient for term 1 : 4
Enter exponent for term 1 : 2
Enter coeficient for term 2 : 3
Enter exponent for term 2 : 1
Enter coeficient for term 3 : 6
Enter exponent for term 3 : 0
Enter polynomial 2 :

Enter the number of terms : 3
Enter coeficient for term 1 : 4
Enter exponent for term 1 : 3
Enter coeficient for term 2 : 6
Enter exponent for term 2 : 2
Enter coeficient for term 3 : 4
Enter exponent for term 3 : 1
Polynomial 1 is :  (4x^2) + (3x^1) + (6x^0)
Polynomial 2 is :  (4x^3) + (6x^2) + (4x^1)
****MENU****
1. Addition
2. multiplication
3. Exit
enter your choice(1-3):1
Added polynomial is : (4x^3) + (10x^2) + (7x^1) + (6x^0)
do you wish to continue?(0/1):1
****MENU****
1. Addition
2. multiplication
3. Exit
enter your choice(1-3):2
Multiplied polynomial is : (16x^5) + (24x^4) + (12x^4) + (16x^3) + (18x^3) + (24
x^3) + (12x^2) + (36x^2) + (24x^1)
do you wish to continue?(0/1):0

Tags: Linked List

Share:

0 comments