A polynomial expression can be represented as a linked list where each node contains coefficients and exponents and a link to the next element. For example: Polynomial: ax^2 + bx + c , can be represented in terms of this node:
struct node
{ int coeff;
int exp;
struct node *next;
};
And ax^2 can be stored as node having a and 2 and link to the node, in turn, which has elements b and 1 and link to next node having values c and 0. You are supposed to create list for expressing polynomials and write function to add these two polynomials. For addition function, you may use the following information:
a) Start with pointers to both the polynomials say p and q. If you find that exponents of the visited node are equal, then add their coefficients and store the result in a new node pointed by the result of sum (a new polynomial), say r.
b)If exponents are different, then first add the node of the polynomial whose exponent is higher. Let node of p has higher exponent than add current term of p to r. Keep comparing the exponents in this manner and append the new nodes or nodes from p and q to r.
Ex.
Code:
# include <stdio.h>
# include <malloc.h>
struct node
{
int coeff;
int exp;
struct node *next;
};
struct node *addition(struct node *,struct node *);
struct node *list(struct node *);
struct node *insert(struct node *,int,int);
void display(struct node *);
void main( )
{
struct node *p_start,*q_start,*r_start;
p_start=NULL;
q_start=NULL;
r_start=NULL;
printf("Polynomial 1 :\n");
p_start=list(p_start);
printf("Polynomial 2 :\n");
q_start=list(q_start);
r_start=addition(p_start,q_start);
printf("Polynomial 1 is : ");
display(p_start);
printf("Polynomial 2 is : ");
display(q_start);
printf("Resultant polynomial is : ");
display(r_start);
}
struct node *list(struct node *start)
{
int i,n,ex;
int co;
printf("How many terms u want to enter : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Enter coefficient for term %d : ",i);
scanf("%d",&co);
printf("Enter exponent for term %d : ",i);
scanf("%d",&ex);
start=insert(start,co,ex);
}
return start;
}
struct node *insert(struct node *start,int co,int ex)
{
struct node *ptr,*tmp;
tmp= (struct node*)malloc(sizeof(struct node));
tmp->coeff=co;
tmp->exp=ex;
if(start==NULL || ex>start->exp)
{
tmp->next=start;
start=tmp;
}
else
{
ptr=start;
while(ptr->next!=NULL && ptr->next->exp>ex)
{
ptr=ptr->next;
}
tmp->next=ptr->next;
ptr->next=tmp;
}
return start;
}
struct node *addition(struct node *p_start,struct node *q_start)
{
struct node *r_start,*tmp,*p;
r_start=NULL;
if(p_start==NULL && q_start==NULL)
return r_start;
else if(p_start!=NULL && q_start==NULL)
{
while(p_start!=NULL)
{
tmp=(struct node *)malloc(sizeof(struct node));
tmp->coeff=p_start->coeff;
tmp->exp=p_start->exp;
if (r_start==NULL)
{
r_start=tmp;
p=tmp;
}
else
{
p->next=tmp;
p=tmp;
}
p_start=p_start->next;
}
}
else if(p_start==NULL && q_start!=NULL)
{
while(q_start!=NULL)
{
tmp=(struct node *)malloc(sizeof(struct node));
tmp->coeff=q_start->coeff;
tmp->exp=q_start->exp;
if (r_start==NULL)
{
r_start=tmp;
p=tmp;
}
else
{
p->next=tmp;
p=tmp;
}
q_start=q_start->next;
}
}
else
{
while(p_start!=NULL && q_start!=NULL )
{
tmp=(struct node*)malloc(sizeof(struct node));
if(r_start==NULL)
{
r_start=tmp;
p=tmp;
}
else
{
p->next=tmp;
p=tmp;
}
if(p_start->exp > q_start->exp)
{
tmp->coeff=p_start->coeff;
tmp->exp=p_start->exp;
p_start=p_start->next;
}
else if(q_start->exp > p_start->exp)
{
tmp->coeff=q_start->coeff;
tmp->exp=q_start->exp;
q_start=q_start->next;
}
else if(p_start->exp == q_start->exp)
{
tmp->coeff=p_start->coeff + q_start->coeff;
tmp->exp=p_start->exp;
p_start=p_start->next;
q_start=q_start->next;
}
}
}
p->next=NULL;
return r_start;
}
void display(struct node *ptr)
{
if(ptr==NULL)
{
printf("Empty\n");
}
while(ptr!=NULL)
{
printf("(%dx^%d) + ", ptr->coeff,ptr->exp);
ptr=ptr->next;
}
printf("\b\b \n");
}
Output:
Polynomial 1 :
How many terms u want to enter : 3
Enter coefficient for term 1 : 5
Enter exponent for term 1 : 3
Enter coefficient for term 2 : 2
Enter exponent for term 2 : 2
Enter coefficient for term 3 : 4
Enter exponent for term 3 : 0
Polynomial 2 :
How many terms u want to enter : 3
Enter coefficient for term 1 : 8
Enter exponent for term 1 : 2
Enter coefficient for term 2 : 10
Enter exponent for term 2 : 1
Enter coefficient for term 3 : 3
Enter exponent for term 3 : 0
Polynomial 1 is : (5x^3) + (2x^2) + (4x^0)
Polynomial 2 is : (8x^2) + (10x^1) + (3x^0)
Resultant polynomial is : (5x^3) + (10x^2) + (10x^1) + (7x^0)
nice post
ReplyDelete