/* Program of polynomial addition using linked list */
# include <stdio.h>
# include <malloc.h>
# include <conio.h>
struct node
{
float coef;
int expo;
struct node *link;
};
struct node *poly_add(struct node *,struct node *);
struct node *enter(struct node *);
struct node *insert(struct node *,float,int);
main( )
{
struct node *p1_start,*p2_start,*p3_start;
p1_start=NULL;
p2_start=NULL;
p3_start=NULL;
clrscr();
printf("Polynomial 1 :\n");
p1_start=enter(p1_start);
printf("Polynomial 2 :\n");
p2_start=enter(p2_start);
p3_start=poly_add(p1_start,p2_start);
printf("Polynomial 1 is : ");
display(p1_start);
printf("Polynomial 2 is : ");
display(p2_start);
printf("Added polynomial is : ");
display(p3_start);
}/*End of main()*/
struct node *enter(struct node *start)
{
int i,n,ex;
float co;
printf("How many terms u want to enter : ");
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(start,co,ex);
}
return start;
}/*End of enter()*/
struct node *insert(struct node *start,float co,int ex)
{
struct node *ptr,*tmp;
tmp= 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;
if(ptr->link==NULL) /*item to be added in the end */
tmp->link=NULL;
}
return start;
}/*End of insert()*/
struct node *poly_add(struct node *p1,struct node *p2)
{
struct node *p3_start,*p3,*tmp;
p3_start=NULL;
if(p1==NULL && p2==NULL)
return p3_start;
while(p1!=NULL && p2!=NULL )
{
tmp=malloc(sizeof(struct node));
if(p3_start==NULL)
{
p3_start=tmp;
p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
if(p1->expo > p2->expo)
{
tmp->coef=p1->coef;
tmp->expo=p1->expo;
p1=p1->link;
}
else
if(p2->expo > p1->expo)
{
tmp->coef=p2->coef;
tmp->expo=p2->expo;
p2=p2->link;
}
else
if(p1->expo == p2->expo)
{
tmp->coef=p1->coef + p2->coef;
tmp->expo=p1->expo;
p1=p1->link;
p2=p2->link;
}
}/*End of while*/
while(p1!=NULL)
{
tmp=malloc(sizeof(struct node));
tmp->coef=p1->coef;
tmp->expo=p1->expo;
if (p3_start==NULL) /*poly 2 is empty*/
{
p3_start=tmp;
p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
p1=p1->link;
}/*End of while */
while(p2!=NULL)
{
tmp=malloc(sizeof(struct node));
tmp->coef=p2->coef;
tmp->expo=p2->expo;
if (p3_start==NULL) /*poly 1 is empty*/
{
p3_start=tmp;
p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
p2=p2->link;
}/*End of while*/
p3->link=NULL;
return p3_start;
}/*End of poly_add() */
display(struct node *ptr)
{
if(ptr==NULL)
{
printf("Empty\n");
return;
}
while(ptr!=NULL)
{
printf("(%.1fx^%d) + ", ptr->coef,ptr->expo);
ptr=ptr->link;
}
printf("\b\b \n"); /* \b\b to erase the last + sign */
}/*End of display()*/