Write A Program For Polynomial representation With Explanation

Program

# include <stdio.h>
# include <stdlib.h>
struct pnode
   {
      int exp;
      double coeff;
      struct pnode *link;
   };

struct pnode *insert(struct pnode *, int,double);
void printlist ( struct pnode * );
struct pnode *polyadd(struct pnode *, struct pnode *);
struct pnode *sortlist(struct pnode *);

struct pnode *insert(struct pnode *p, int e,double c)
{
   struct pnode *temp;
   if(p==NULL)
   {
      p=(struct pnode *)malloc(sizeof(struct pnode));
      if(p==NULL)
      {
         printf("Error\n");
         exit(0);
      }
      p-> exp = e;
      p->coeff = c;
      p-> link = NULL;
   }
   else
   {
      temp = p;
      while (temp-> link!= NULL)
      temp = temp-> link;
      temp-> link = (struct pnode *)malloc(sizeof(struct pnode));
      if(temp -> link == NULL)
      {
   printf("Error\n");
         exit(0);
      }
    temp = temp-> link;
      temp-> exp = e;
      temp->coeff = c;
      temp-> link = NULL;
   }
   return (p);
}

/* a function to sort a list */
struct pnode *sortlist(struct pnode *p)
{
   struct pnode *temp1,*temp2,*max,*prev,*q;
   q = NULL;
   while(p != NULL)
   {
      prev = NULL;
      max = temp1 = p;
      temp2 = p -> link;
      while ( temp2 != NULL )
      {
         if(max -> exp < temp2 -> exp)
              {
         max = temp2;
                 prev = temp1;
               }
               temp1 = temp2;
               temp2 = temp2-> link;
            }
      if(prev == NULL)
            p = max -> link;
            else
            prev -> link = max -> link;
            max -> link = NULL;
            if( q == NULL)
            q = max; /* moves the node with highest data value in the list
pointed to by p to the list
   pointed to by q as a first node*/
         else
         {
            temp1 = q;
            /* traverses the list pointed to by q to get pointer to its
last node */
         while( temp1 -> link != NULL)
         temp1 = temp1 -> link;
         temp1 -> link = max; /* moves the node with highest data value
in the list pointed to
   by p to the list pointed to by q at the end of list pointed by
   q*/

         }
      }
      return (q);
   }
   /* A function to add two polynomials */
   struct pnode *polyadd(struct pnode *p, struct pnode *q)
   {
      struct pnode *r = NULL;
      int e;
      double c;
      while((p!=NULL) && (q != NULL))
               {
                  if(p->exp > q->exp)
                   {
                        r = insert(r,p->exp,p->coeff);
                        p = p->link;
                   }
                   else
                      if(p->exp < q->exp)
                    {
                        r = insert(r,q->exp,q->coeff);
                        q = q->link;
                     }
                     else
   {
      c = p->coeff + q->coeff;
      e = q->exp;
      r = insert( r, e,c);
      p = p->link;
      q = q->link;
            }
   while(p != NULL)
            {
                  r = insert( r, p->exp,p->coeff);
                  p = p->link;
            }
            while(q!=NULL)
            {
                     r = insert( r, q->exp,q->coeff);
                     q = q->link;
            }
   return(r);
   }

   void printlist ( struct pnode *p )
   {
      printf("The polynomial is\n");
      while (p!= NULL)
           {
      printf("%d %lf\t",p-> exp,p->coeff);
               p = p-> link;
         }
   }
   void main()
   {
         int e;
         int n,i;
         double c;
         struct pnode *poly1 = NULL ;
         struct pnode *poly2=NULL;
         struct pnode *result;
         printf("Enter the terms in the polynomial1 \n");
         scanf("%d",&n);
         i=1;
         while ( n-- > 0 )
         {
      printf( "Enter the exponent and coefficient of the term number
%d\n",i);
               scanf("%d %lf",&e,&c);
               poly1 = insert ( poly1,e,c);
         }
        printf("Enter the terms in the polynomial2 \n");
         scanf("%d",&n);
         i=1;
         while ( n-- > 0 )
         {
      printf( "Enter the exponent and coefficient of the term number
%d\n",i);
               scanf("%d %lf",&e,&c);
               poly2 = insert ( poly2,e,c);
         }
         poly1 = sortlist(poly1);
         poly2 = sortlist(poly2);
         printf("The polynomial 1 is\n");
         printlist ( poly1 );
         printf("The polynomial 2 is\n");
         printlist ( poly2 );
        result = polyadd(poly1,poly2);
         printf("The result of addition is\n");
         printlist ( result );
   }

Explanation

1. If the polynomials to be added have n and m terms, respectively, then the linked list representation of these polynomials contains m and n terms, respectively.
2. Since polyadd traverses each of these lists, sequentially, the maximum number of iterations that polyadd will make will not be more than m + n. So the computation time of polyadd is O(m + n).