Polynomial Addition and Multiplication using Linked List

Polynomial Addition and Multiplication using Linked List

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int coef;
 int exp;
 struct node *link;
};
void insert_term(struct node **,int,int);
void traverse(struct node *);
void poly_add(struct node **,struct node **,struct node **);
void poly_pdt(struct node **,struct node **,struct node **);
void main()
{
 struct node *start_p=NULL,*start_q=NULL,*start_r=NULL;
 int i,n,c,e;
 printf("Enter first polynomial?\n");
 printf("Enter no of terms?\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  printf("Enter %d term\n",i+1);
  printf("Enter coefficient\n");
  scanf("%d",&c);
  printf("Enter exponent\n");
  scanf("%d",&e);
  insert_term(&start_p,c,e);
 }
 printf("Enter second polynomial\n");
 printf("Enter no of terms?\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  printf("Enter %d term",i+1);
  printf("Enter coefficient\n");
  scanf("%d",&c);
  printf("Enter exponent\n");
  scanf("%d",&e);
  insert_term(&start_q,c,e);
 }
 printf("First polynomial:\n");
 traverse(start_p);
 printf("second polynomial:\n");
 traverse(start_q);
 poly_add(&start_p,&start_q,&start_r);
 printf("sum of two polynomial:\n");
 traverse(start_r);
 start_r=NULL;
 poly_pdt(&start_p,&start_q,&start_r);
 printf("Product of the two polynomial:\n");
 traverse(start_r);
 
}
void insert_term(struct node **start,int c,int e)
{ 
 struct node *temp,*temp1,*prev;
 if (*start==NULL)
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if (temp==NULL)
   printf("Node is not created.Term cannot be inserted\n");
  else
  {
   temp->coef=c;
   temp->exp=e;
   temp->link=NULL;
   *start=temp;
  }
 }
 else
 {
  temp1=*start;
  while (temp1!=NULL && temp1->exp>e)
  {
   prev=temp1;
   temp1=temp1->link;
  }
  if(temp1==NULL)
  {
   temp=(struct node *)malloc(sizeof(struct node));
   if (temp==NULL)
    printf("Node is not created\n");
    
   else
   {
    temp->coef=c;
    temp->exp=e;
    temp->link=NULL;
    prev->link=temp; 
   }
  }
  else
  {
   if(temp1->exp==e)
    temp1->coef=temp1->coef+c;
   else
   {
    if(temp1==*start)
    {
     temp=(struct node *)malloc (sizeof (struct node));
     if(temp==NULL)
      printf("Node is not created\n");
     else
     {
      temp->coef=c;
      temp->exp=e;
      temp->link=*start;
      *start=temp;
     }
    }
    else
    {
     temp=(struct node *)malloc(sizeof(struct node));
     if (temp==NULL)
      printf("node is not created\n");
     else
     {
      temp->coef=c;
      temp->exp=e;
      temp->link=temp1;
      prev->link=temp;
     }
    }
   } 
  }
 }

}
void traverse(struct node *start)
{
 struct node *temp;
 temp=start;
 if (temp==NULL)
  printf("Empty polynomial\n");
 else
 {
  while(temp!=NULL)
  {
   printf("+  %d X ^%d ",temp->coef,temp->exp);
   temp=temp->link;
  }
  printf("\n");
 }
 

}
void poly_add(struct node** start_p,struct node **start_q,struct node** start_r)
{
 int c,e;
 struct node *pptr,*qptr;
 *start_r=NULL;
 pptr=*start_p;
 qptr=*start_q;
 while(pptr!=NULL && qptr!=NULL)
 {
  if (pptr->exp==qptr->exp)
  {
   c=pptr->coef+qptr->coef;
   e=pptr->exp;
   insert_term(start_r,c,e);
   pptr=pptr->link;
   qptr=qptr->link;
  }
  else
  {
   if (pptr->exp>qptr->exp)
   {
    c=pptr->coef;
    e=pptr->exp;
    insert_term(start_r,c,e);
    pptr=pptr->link;
   }
   else
   {
    c=qptr->coef;
    e=qptr->exp;
    insert_term(start_r,c,e);
    qptr=qptr->link;
   }
  }
 }
 while(pptr!=NULL)
 {
  c=pptr->coef;
  e=pptr->exp;
  insert_term(start_r,c,e);
  pptr=pptr->link;
 }
 while (qptr!=NULL)
 {
  c=qptr->coef;
  e=qptr->exp;
  insert_term(start_r,c,e);
  qptr=qptr->link;
 }
 
}
void poly_pdt(struct node ** start_p,struct node **start_q,struct node** start_r)
{
 int c,e;
 struct node *pptr,*qptr;
 *start_r=NULL;
 pptr=*start_p;
 qptr=*start_q;
 if (*start_p==NULL && *start_q==NULL)
  printf("\n Multiplication of polynomial is not possible\n");
 else
 {
  while(pptr!=NULL)
  {
   qptr=*start_q;
   while(qptr!=NULL)
   {
    c=pptr->coef*qptr->coef;
    e=pptr->exp+qptr->exp;
    insert_term(start_r,c,e);
    qptr=qptr->link;
   }
   pptr=pptr->link;
  }
 }
}

Output

C Program for Linked List Implementation

C Program for Linked List Implementation

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node*link;

};
void insert_begin_sll(struct node**,int);
void traverse_sll(struct node*);
void insert_end_sll(struct node **,int);
void insert_position_sll(struct node**,int,int);
void delete_begin_sll(struct node **);
void delete_end_sll(struct node **);
void delete_position_sll(struct node **,int);
void search_sll(struct node**,int);
int main()

{
 int ch,position,key;
 struct node *start=NULL;
 while(1)
 {
  printf("Select from the menu\n");
  printf("1.Insert node at beginning\n2.Traversing\n3.Insert node at end\n4.Insert node at specific position\n5.Delete node from beginning\n6.Delete node from end\n7.Delete node from specified position\n8.searching\n9.exit\n");
 printf("Enter a choice\n");
 scanf("%d",&ch);

 switch (ch)
 {
  case 1:
   printf("Enter key\n");
   scanf("%d",&key);
   insert_begin_sll(&start,key);
   break;
  case 2:
   traverse_sll(start);
   break;
  case 3:
   printf("Enter key\n");
   scanf("%d",&key);
   insert_end_sll(&start,key);
   break;
  case 4:
   printf("Enter key\n");
   scanf("%d",&key);
   printf("Enter position\n");
   scanf("%d",&position);
   insert_position_sll(&start,key,position);
   break;
  case 5:
   delete_begin_sll(&start);
   break;
  case 6:
   delete_end_sll(&start);
   break;
  case 7:
   printf("Enter position\n");
   scanf("%d",&position);
   delete_position_sll(&start,position);
   break;
  case 8:
   printf("Enter the key to be searched\n");
   scanf("%d",&key);
   search_sll(&start,key);
   break;
  case 9:
   exit(0);
 }
 }
}
void insert_begin_sll(struct node **start,int key)
{
 struct node *temp;
 temp=(struct node*)malloc(sizeof(struct node));
 if (temp==NULL)
  printf("Node is not created \n Insertion is not possible\n");
 else
 { 
  temp->data=key;
  temp->link=NULL;
  temp->link=*start;
  *start=temp;
 }
} 
void traverse_sll(struct node *start)
{
 struct node *temp;
 if (start==NULL)
  printf("Linked list is empty\n");
 else
 {
  temp=start;
  while(temp!=NULL)
  {
   printf("%d->",temp->data);
   temp=temp->link;
  }
  printf("NULL\n");
 }
}
void insert_end_sll(struct node**start,int key)
{
 struct node *temp,*temp1;
 temp=(struct node *)malloc(sizeof(struct node));
 if (temp==NULL)
  printf("node is not created\nInsertion is not possible\n");
 else
 {
  temp->data=key;
  temp->link=NULL;
  if(*start==NULL)
   *start=temp;
  else
  {
   temp1=*start;
   while(temp1->link!=NULL)
    temp1=temp1->link;
   temp1->link=temp;
  }
 }
}
void insert_position_sll(struct node **start,int key,int position)
{
 struct node *temp1,*temp;
 int count;
 if (position<=0)
  printf("position is invalid\n");
 else
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if (temp==NULL)
   printf("Node is not created\nInsertion is not possible\n");
  else
  {
   temp->data=key;
   temp->link=NULL;
   if (position==1)
   {
    temp->link=*start;
    *start=temp;
   }
   else
   {
    temp1=*start;
    count=1;
    while (count<position-1 && temp1!=NULL)
    {
     temp1=temp1->link;
     count++;
    }
    if(temp1==NULL)
     printf("Linked list is out of range\n");
    else
    {
     temp->link=temp1->link;
     temp1->link=temp;
    }
   }
  }
 }
}
void delete_begin_sll(struct node **start)
{
 struct node *temp;
 if(*start==NULL)
  printf("Linked list is empty\n Deletion is not possible\n");
 else
 {
  temp=*start;
  *start=(*start)->link;
  free(temp);
 }
}  
void delete_end_sll(struct node **start)
{
 struct node *prev,*temp;
 if(*start==NULL)
  printf("Linked list is empty \nDeletion is not possible\n");
 else
 {
  temp=*start;
  prev=*start;
  while(temp->link!=NULL)
  {
   prev=temp;
   temp=temp->link;
  }
  if(temp==prev)
   *start=NULL;
  else
   prev->link=NULL;
  free(temp);
 }
}
void delete_position_sll(struct node **start,int position)
{
 struct node *temp,*prev;
 int count;
 if (position<=0)
  printf("position is invalid\n");
 else
 {
  if (position==1)
  {
   temp=*start;
   *start=(*start)->link;
  }
  else
  {
   temp=*start;
   prev=*start;
   count=1;
  }
  while (count<position && temp!=NULL)
  {
   prev=temp;
   temp=temp->link;
   count++;
  }
  if(temp==NULL)
   printf("Linked list is out of range\n");
  else
   prev->link=temp->link;
  free(temp);
 }
}
void search_sll(struct node **start,int key)
{
 struct node *temp;
 int flag=0;
 if(start==NULL)
  printf("Linked list is empty.\nSearching is not possible\n");
 else
 {
  temp=*start;
  while (temp!=NULL && flag==0)
  {
   if (key==temp->data)
    flag=1;
   temp=temp->link;
  }
  if (flag==0)
   printf("key is not found\n");
  else
   printf("Key is found\n");
 }
}

Output