6.
APPLICATION OF LIN KED LIST- POLYNOMIAL MANIPULAT ION
• Polynomial is an ordered list.
• A polynomial is the sum of terms where each term consists of variable, coefficient and exponent
• Various operations performed on polynomial are
▪ Addition -- Multiplication --- Differentiation
ADDITION OF POLYNOMIALS – EXAMPLE:
First Polynomial : 3x3+2x2+ x+1
Second Polynomial: 5x3+0x2+7x+0 +
8x3+2x2+8x+1
The resultant Polynomial is 8x3+2x2+8x+1
MULTIP LICATION OF PO LYNOMIALS – EXAMP LE:
First Polynomial :3x3+2x2+ x+1
Second Polynomial: 5x3+7x X
21x4+14x3+7x2+7x
15x6+10x5+5x4+5x3
15x6+10x5+26x4+19x3 +7x2+7x
The resultant Polynomial is 15x6+10x5+26x4+19x3 +7x2+7x
Linked list Implementation of Polynomial ADT: Polynomial ADT
can be implemented using linked list. Linked list consists of three
parts.
1. Coefficient part
2. Power part
3. Pointer to next node containing next element of the polynomial.
EXAMPLE OF A POLYNOM IAL:
The above polynomial is represented in linked list as follows:
TYPE DECLARATION FOR POLYNOMIAL
struct link
{
int coeff; int
pow;
struct link *next;
};
struct link *poly1=NULL,*poly2=NULL,*poly=NULL;
CREATION OF THE POLY NOMIAL
void create(struct link *node)
{
char ch;
do
{
printf("\n enter coeff:");
scanf("%d",&node->coeff);
printf("\n enter power:");
scanf("%d",&node->pow);
node->next=(struct link*)malloc(sizeof(struct link));
node=node->next;
node->next=NULL;
printf("\ncontinue(y/n):");
scanf("%c",&ch);
}
while(ch=='y' || ch=='Y');
}
DISP LAYING THE POLYN OMIAL
void show(struct link *p)
{
while(p!=NULL)
{
printf("%dx^%d",p->coeff,p->pow);
p=p->next;
if(p->next!=NULL)
printf("+");
}
}
ADDITION OF TWO POLY NOMIAL
void polyadd(struct link *poly1, struct link *poly2, struct link *poly)
{
while(poly1->next && poly2->next)
{
if(poly1->pow > poly2->pow)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1=poly1->next;
}
else if(poly1->pow < poly2->pow)
{
poly->pow = poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
else
{
poly->pow=poly1->pow;
poly->coeff = poly1->coeff + poly2->coeff;
poly1=poly1->next;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
while(poly1->next || poly2->next)
{
if(poly1->next)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
if(poly2->next)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
}
POLYNOMIAL DIFFERENTIATION:
void diff(struct link* p1,struct link* p2)
{
while(p1!=NULL)
{
p2->coeff=p1->coeff*p1->pow;
p2->pow=p1->pow-1;
p2->next=NULL;
p2->next=(struct link *)malloc(sizeof(struct link));
p2=p2->next;
p1=p1->next;
}
}
POLYNOMIAL MULTIP LIC ATION:
void polymul(struct link *n1, struct link *n2, struct link *n)
{
struct link * n2beg=n2;
while (n1)
{
struct link * temp=(struct link *)malloc(sizeof(struct link));
temp->next=NULL;
n2=n2beg;
while (n2)
{
temp->coeff = n1->coeff * n2->coeff;
temp->pow = n1->pow + n2->pow;
n2 = n2->next;
temp->next=(struct link *)malloc(sizeof(struct link));
temp=temp->next;
temp->next=NULL;
}
polyadd(temp,n,n);
n1 = n1->next;
}
}
7. MERGING OF LINKED LIST W ITH SORTED DATA
typedef struct node
{
int data;
struct node *next;
}node;
node *merge(node *l1,node *l2)
{
node *l,*p;
l=NULL;
while(l1!=NULL && l2!=NULL)
{
if(l1->data < l2->data)
{
if(l==NULL)
{
l=p=l1;
l1=l1->next;
}
else
{
p->next=l1;
l1=l1->next;
p=p->next;
}
}
else
{
if(l==NULL)
{
l=p=l2;
l2=l2->next;
}
else
{
p->next=l2;
l2=l2->next;
p=p->next;
}
}
}
if(l1!=NULL)
{
if(l==NULL)
l=l1;
else
p->next=l1;
}
if(l2!=NULL)
{
if(l==NULL)
l=l2;
else
p->next=l2;
}
return(l);
}
node *create_sorted( )
{
node *head=NULL,*p,*q;
int n,x,i;
printf("\nNumber of nodes:");
scanf("%d",&n);
printf("\nEnter data:");
for(i=1;i<=n;i++)
{
scanf("%d",&x);
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(head==NULL || x<head->data)
{
p->next=head;
head=p;
}
else
{
q=head;
while(q->next !=NULL && x>q->next->data)
q=q->next;
p->next=q->next;
q->next=p;
}
}
return(head);
}
void print(node *head)
{
printf("\n");
while(head != NULL)
{
printf("%d",head->data);
head=head->next;
}
}
