Circular Link List using C Language
Represent single variable polynomial as a circular link list. Accept the terms in the polynomial in any order, i.e. not necessarily in the decreasing order of exponent. Sort while creating polynomial in the decreasing order of exponent and write a menu driven program to perform Circular Link List display, addition, multiplication and evaluation.
Concept of Circular Link List organization, singly linked list, doubly linked list, circular linked list.Linked list as ADT. Representation and manipulations of polynomials using linked lists,comparison of sequential linked organization with linked organization, concept Generalized Linked List.
Circular Link List using C Language Code
#include
#include
#include
#include
typedef struct poly1
{
int pow;
float coeff;
struct poly1 *link;
}poly1;
poly1 *create();
void display(poly1 *);
poly1 *mul(poly1 *,poly1 *);
poly1 *add(poly1 *,poly1 *);
float evaluate(poly1 *,float);
poly1 *alloc();
int valid();
float validf();
poly1 *freeall(poly1 *);
void main()
{
poly1 *p1=NULL,*p2=NULL,*p3;
int ch,ch1;
float m;
float dummy;
&dummy;
clrscr();
do
{
clrscr();
printf("\n\t\tOPERATION ON POLYNOMIALS");
printf("\n\t\t1.CREATE\n\t\t2.DISPLAY\n\t\t3.ADDITION\n\t\t4.MULTPLICATION\n\t\t5.EVALUATION\n\t\t6.EXIT");
printf("\n\t\tENTER UR CHOICE:");
ch=valid();
switch(ch)
{
case 1: do
{
clrscr();
printf("\nCREATING POLYNOMIAL");
printf("\n\t\t1.FIRST POLY\n\t\t2.SECOMND POLY\n\t\t3.EXIT");
printf("\n\t\tENTER UR CHOICE:");
ch1=valid();
switch(ch1)
{
case 1: if(p1!=NULL)
freeall(p1);
printf("\n\t\tFIRST POLY");
p1=create();
break;
case 2: if(p2!=NULL)
freeall(p2);
printf("\n\t\tSECOND POLY");
p2=create();
break;
case 3:break;
default:printf("INVALID CHOICE");
}
}while(ch1!=3);
break;
case 2: do
{
clrscr();
printf("\nDISPLAYING POLYNOMIAL");
printf("\n\t\t1.FIRST POLY\n\t\t2.SECOMND POLY\n\t\t3.EXIT");
printf("\n\t\tENTER UR CHOICE:");
ch1=valid();
switch(ch1)
{
case 1: if(p1==NULL)
printf("\nEMPTY POLY");
else
{
printf("\n\t\tFIRST POLY");
display(p1);
}
getch();
break;
case 2: if(p2==NULL)
printf("\nEMPTY POLY");
else
{
printf("\n\t\tSECOND POLY");
display(p2);
}
getch();
break;
case 3:break;
default:printf("INVALID CHOICE");
getch();
}
}while(ch1!=3);
break;
case 3: if(p1==NULL&&p2==NULL)
printf("\nADDITION NOT POSSIBLE");
else
{
printf("\n\t\tADDITION");
p3=add(p1,p2);
if(p3==NULL)
printf("p3 is empty");
else
display(p3);
}
getch();
break;
case 4: if(p1==NULL&&p2==NULL)
printf("\nMULTIPLICATION NOT POSSIBLE");
else
{
printf("\n\t\tFIRST POLY*SECOND POLY");
p3=mul(p1,p2);
display(p3);
}
getch();
break;
case 5: do
{
clrscr();
printf("\n\t\tEVALUATION");
printf("\n\t\tENTER THE VALUE OF x:");
m=validf();
printf("\n\t\tEVALUATION ON");
printf("\n\t\t1.FIRST POLY\n\t\t2.SECOMND POLY\n\t\t3.EXIT");
printf("\n\t\tENTER UR CHOICE:");
ch1=valid();
switch(ch1)
{
case 1: if(p1==NULL)
printf("\nEVALUATION CANT BE DONE ON EMPTY POLY");
else
{
printf("\n\t\tFIRST POLY");
m=evaluate(p1,m);
printf("\n\tevaluation\t%f",m);
}
getch();
break;
case 2: if(p2==NULL)
printf("\nEVALUATION CANT BE DONE ON EMPTY POLY");
else
{
printf("\n\t\tSECOND POLY");
m=evaluate(p2,m);
printf("\n\tevaluation\t%f",m);
}
getch();
break;
case 3:break;
default:printf("INVALID CHOICE");
getch();
}
}while(ch1!=3);
break;
case 6: break;
default:printf("\n\t\tINVALID CHOICE");
getch();
}
}while(ch!=6);
}
/*poly1 *create()
{
poly1 *nw,*p,*t;
p=NULL;
do
{
nw=alloc(p);
if(nw!=NULL)
{
t=p;
if(p==NULL)
{
p=nw;
nw->link=p;
}
else
{
do
{
if(nw==t)
{
if(nw==p)
p=0;
else
p=nw;
break;
}
t=t->link;
}while(t!=p);
if(p!=0&&p!=nw)
{
if(nw->pow>p->pow)
{
while(t->link!=p)
t=t->link;
nw->link=p;
p=nw;
t->link=p;
}
else
{
while(t->link!=p && nw->powlink->pow)
t=t->link;
nw->link=t->link;
t->link=nw;
}
}
}
}
printf("\nDO U WANT ENTER MORE:y/n");
}while(getche()=='y');
return p;
}
poly1 *alloc(poly1* p)
{
poly1 *nw,*t,*n,*t1;
t=p;
nw=(poly1 *)malloc(sizeof(poly1));
while(1)
{
printf("\nENTER COEFF:");
nw->coeff=validf();
if(nw->coeff!=0)
break;
}
printf("\nENTER POWER:");
nw->pow=valid();
if(p!=NULL)
do
{
if(nw->pow==t->link->pow)
{
printf("\nthis power already exits");
printf("DO U WANT TO ADD IT IN PREVEIOUS:y/n");
if(getche()=='y')
{
t->link->coeff=t->link->coeff+nw->coeff;
if(t->link->coeff==0)
{
n=t->link;
t->link=t->link->link;
if(p->coeff==0)
{
p=p->link;
free(n);
free(nw);
return p;
}
free(n);
}
}
free(nw);
return(NULL);
}
t=t->link;
}while(t!=p);
return nw;
} */
void display( poly1 *p)
{
poly1 *t;
t=p;
do
{
if(t->coeff==1)
{
if(t->pow==0)
printf("%f",t->coeff);
}
else
printf("%f",t->coeff);
if(t->pow!=0)
printf("x");
if(t->pow>1)
printf("^%d",t->pow);
t=t->link;
if(t!=p)
if(t->coeff>0)
printf("+");
}while(t!=p);
getch();
}
float evaluate(poly1 *p,float x)
{
float result=0;
poly1 *t;
t=p;
do
{
result+=(t->coeff * pow(x,t->pow) );
t=t->link;
} while(t!=p);
return result;
}
poly1 *add(poly1 *p1,poly1 *p2)
{
poly1 *p3,*t,*s,*r,*last;
int flag=0,flag1=0;
t=p1;
s=p2;
p3=NULL;
last=p3;
if(p1==NULL)
return p2;
if(p2==NULL)
return p1;
do
{
r=(poly1 *)malloc(sizeof(poly1));
if(t->powpow)
{
r->pow=s->pow;
r->coeff=s->coeff;
s=s->link;
flag1=1;
}
else if(t->pow>s->pow)
{
r->pow=t->pow;
r->coeff=t->coeff;
t=t->link;
flag=1;
}
else
{
r->pow=t->pow;
r->coeff=t->coeff+s->coeff;
s=s->link;
t=t->link;
flag=1;
flag1=1;
}
if(r->coeff!=0)
{
if(p3==NULL)
{
p3=r;
}
else
{
last->link=r;
}
last=r;
}
else
free(r);
}while((t!=p1||flag==0)&&(s!=p2||flag1==0));
while(t!=p1||flag==0)
{
if(p3==NULL)
{
p3=r=(poly1 *)malloc(sizeof(poly1));
}
else
{
r->link=(poly1 *)malloc(sizeof(poly1));
r=r->link;
}
r->pow=t->pow;
r->coeff=t->coeff;
t=t->link;
flag=1;
last=r;
}
while(s!=p2||flag1==0)
{
if(p3==NULL)
{
p3=r=(poly1 *)malloc(sizeof(poly1));
}
else
{
r->link=(poly1 *)malloc(sizeof(poly1));
r=r->link;
}
r->pow=s->pow;
r->coeff=s->coeff;
s=s->link;
flag1=1;
last=r;
}
last->link=p3;
return p3;
}
poly1 *mul(poly1 *p1,poly1 * p2)
{
poly1 *p,*t,*r,*s,*n;
t=p1;
s=p2;
p=NULL;
r=NULL;
do
{
do
{
r=(poly1 *)malloc(sizeof(poly1));
r->coeff=t->coeff*s->coeff;
r->pow=t->pow+s->pow;
n=p;
if(p==NULL)
{
p=r;
r->link=p;
}
else
{
while(n->link!=p && r->powlink->pow)
n=n->link;
if(r->pow==n->link->pow)
{
n->link->coeff=r->coeff+n->link->coeff;
free(r);
if(n->link->coeff==0)
{
r=n->link;
n->link=p;
free(r);
}
}
else
{
r->link=n->link;
n->link=r;
}
}
t=t->link;
}while(t!=p1);
s=s->link;
}while(s!=p2);
return p;
}
poly1 *freeall(poly1 *p)
{
poly1 *t,*r;
r=p;
do
{
t=r;
r=r->link;
free(t);
}while(r!=p);
return p;
}
int valid()
{
int k,p;
char str[25];
k=-1;
do
{
k++;
str[k]=getche();
if(k>0)
if(str[k]=='\r')
{
str[k]='\0';
return(atoi(str));
}
if(str[k]<48 || str[k]>57)
{
printf("\ninvalid choice");
k--;
}
}while(str[k]!='\r');
return(0);
}
float validf()
{
int k,p,count=0;
char str[25];
k=-1;
do
{
k++;
str[k]=getche();
if(k>0)
if(str[k]=='\r')
{
str[k]='\0';
return(atof(str));
}
if(str[k]==46||str[k]==45)
count++;
if(((str[k]<48||str[k]>57)&& (str[k]!=46&&str[k]!=45)) || count>1)
{
printf("\ninvalid choice");
count=0;
k--; }
}while(str[k]!='\r');
return(0);
}
poly1 *create()
{
poly1 *nw,*p,*t,*r,*s;
p=NULL;
do
{
nw=alloc();
if(nw!=NULL)
{
t=p;
if(p==NULL)
{
p=nw;
nw->link=p;
}
else
{
if(nw->pow>p->pow)
{
while(t->link!=p)
t=t->link;
nw->link=p;
p=nw;
t->link=p;
}
else
{
while(t->link!=p && nw->pow<=t->link->pow)
t=t->link;
if(nw->pow==t->pow)
{
printf("\nthis power already exits");
printf("DO U WANT TO ADD IT IN PREVEIOUS:y/n");
if(getche()=='y')
{
t->coeff+=nw->coeff;
if(t->coeff==0)
{
if(p==p->link)
{
free(p);
p=NULL;
}
else
{
r=p;
while(r->link!=t)
r=r->link;
s=t;
if(p==t)
{
p=t->link;
}
r->link=t->link;
free(s);
}
}
}
free(nw);
}
else
{
nw->link=t->link;
t->link=nw;
}
}
}
}
printf("\nDO U WANT ENTER MORE:y/n");
}while(getche()=='y');
return p;
}
poly1 *alloc()
{
poly1 *nw;
nw=(poly1 *)malloc(sizeof(poly1));
while(1)
{
printf("\nENTER COEFF:");
nw->coeff=validf();
if(nw->coeff!=0)
break;
}
printf("\nENTER POWER:");
nw->pow=valid();
return nw;
}
