Monday, July 11, 2011

Write a program to find polynomial multiplication using linked list.


#include<stdio.h>
#include<stdlib.h>
struct node
{
int c;
int exp;
struct node *next;
};
main()
{
struct node *start=NULL,*start1=NULL,*start2=NULL;
int n,m;
void create(struct node **, int);
void show(struct node *);
void mul(struct node *,struct node*,struct node**);
extern void insert(struct node **start3,int c,int exp);
extern struct node* search(struct node *start, int exp);
printf("\nEnter the number of elements you want in your first polynomial :");
scanf("%d",&m);
create(&start,m);
printf("\nEnter the number of elements you want in your second polynomial :");
scanf("%d",&n);
create(&start1,n);
mul(start,start1,&start2);
printf("\n first linked list is :\n");
show(start);
printf("\n second linked list is :\n");
show(start1);
printf("\n added linked list is :\n");
show(start2);
getch();    
}

void create(struct node **q,int n)
{
int i;
struct node *lst;
struct node *p;
lst=NULL;
printf("\nEnter the data only in the correct polynomial form :\n ");
for(i=1;i<=n;i++)
{
 p=(struct node *)malloc(sizeof(struct node));
 printf("\nEnter the %d cofficient :",i);
 scanf("%d",&(p->c));
  printf("\nEnter the %d exponent :",i);
 scanf("%d",&(p->exp));
 p->next=NULL;
 if(*q==NULL)
    *q=p;
 else
   lst->next=p;
  lst=p;
}
}

void show(struct node *start)
{
while(start!=NULL)
{
printf(" %dX%d",start->c,start->exp);
start=start->next;
}
}

void mul(struct node *start,struct node *start1,struct node **start2)
{
    struct node *ptr1,*ptr2,*ptr3=NULL;
    int c,exp;
    for(ptr2=start1;ptr2!=NULL;ptr2=ptr2->next)
    {
     for(ptr1=start;ptr1!=NULL;ptr1=ptr1->next)
     {
       c=ptr2->c*ptr1->c;
       exp=ptr2->exp+ptr1->exp;
       insert(&ptr3,c,exp);
     }
    }
    *start2=ptr3;
}  
               
void insert(struct node **start3,int c,int exp)
{
     struct node *p,*loc;
     if(*start3==NULL)
     {
       p=(struct node*)malloc(sizeof(struct node));
       p->c=c;
       p->exp=exp;
       p->next=NULL;
       *start3=p;
     }
     else
     {
         loc=(struct node*)search(*start3,exp);
         if((loc->next)==NULL)
         {
          p=(struct node*)malloc(sizeof(struct node));
          p->c=c;
          p->exp=exp;
          p->next=NULL;      
          loc->next=p;
         }
         else if((loc->next)->exp==exp)  
         {
          (loc->next)->c=(loc->next)->c+c;
         }
         else if ((loc->next)->exp<exp)
         {
          p=(struct node*)malloc(sizeof(struct node));
          p->c=c;
          p->exp=exp;
          p->next=loc->next;
          loc->next=p;  
         }      
     }
}

 struct node* search(struct node *start, int exp)  
 {
        struct node *ptr,*prev;
        ptr=start;
        prev=NULL;
        while(ptr!=NULL&&ptr->exp>exp)
        {
            prev=ptr;
            ptr=ptr->next;
        }
        return prev;
}
             
       


Previous Next Home
0 Comments
Comments

Leave a Comment

:)) ;)) ;;) :D ;) :p :(( :) :( :X =(( :-o :-/ :-* :| 8-} :)] ~x( :-t b-( :-L x( =))

Twitter Delicious Facebook Favorites More