BFS AND DFS Algorithm using C Language

Represent a given graph using adjacency list and perform BFS AND DFS Algorithm. Use the map of the area around the college as the graph. Identify the prominent land marks as nodes and perform DFS and BFS on that.

BFS AND DFS Algorithm Code

 
 #include  
 #include  
 #include  
 #define MAX 30  
 typedef struct tree  
 {  
 char data[7];  
 struct tree *lc;  
 struct tree *rc;  
 }tree;  
 typedef struct stack1  
 {  
 int flag;  
 struct tree * addr;  
 struct stack1 *link;  
 }stack1;  
 tree *alloc();  
 tree * create();  
 tree * insert(tree *);  
 void recin(tree *);  
 void recpost(tree *);  
 void recpre(tree *);  
 void itin(tree *);  
 void itpost(tree *);  
 void itpre(tree *);  
 tree *delet(tree *,char[]);  
 tree *parent(tree *,tree *);  
 tree *succ(tree *,tree *);  
 tree *pre(tree *,tree *);  
 void search(tree *,char[]);  
 tree *search1(tree *,char[],int * );  
 void leveldis(tree *);  
 tree *mirror(tree *);  
 tree * freeall(tree *);  
 int depth(tree *,char[]);  
 int height(tree *);  
 void main()  
 {  
 int i=0,ch,ch1,data;  
 char d[7];  
 tree *f=NULL,*f1=NULL;  
 do  
 {  
 clrscr();  
 printf("\n\t\tBST TREE OPERATION\n\t\t1.CREATE\n\t\t2.INSERT\n\t\t3.DELETE");  
 printf("\n\t\t4.SEARCH\n\t\t5.RECURSIVE TRAVERSE\n\t\t6.ITERATIVE TRAVERSE");  
 printf("\n\t\t7.DEPTH OF TREE\n\t\t8.MIRROR IMAGE\n\t\t9.LEVEL WISE DISPLAY MIRROR IMAGE\n\t\t10.HEIGHT OF TREE\n\t\t11.EXIT\n\t\tENTER UR CHOICE");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tCREATE");  
 f=create();  
 break;  
 case 2:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tINSERT");  
 f=insert(f);  
 }  
 break;  
 case 3:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tDELETE\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 f=delet(f,d);  
 }  
 break;  
 case 4:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tSEARCH\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 search(f,d);  
 }  
 break;  
 case 5:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tRECURSIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 recin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 recpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 recpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 getch();  
 }while(ch1!=4);  
 getch();  
 break;  
 case 6:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tITERATIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 itin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 itpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 itpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch1!=4);  
 getch();  
 break;  
 case 7:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tDEPTH OF TREE\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 i=depth(f,d);  
 if(i!=-1)  
 printf("DEPTH OF GIVEN NODE IS %d",i);  
 getch();  
 }  
 break;  
 case 8:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 if(f1!=NULL)  
 f1=freeall(f1);  
 printf("\n\t\tMIRROR OF TREE");  
 f1=mirror(f);  
 recin(f1);  
 getch();  
 }  
 break;  
 case 9:  
 if(f1==NULL)  
  printf("CREATE MIRROR IMAGE FIRST");  
 else  
 {  
 printf("\n\t\tLEVEL WISE MIRROR OF TREE");  
 leveldis(f1);  
 }  
 break;  
 case 10:  
 if(f==NULL)  
  printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\theight OF TREE:");  
 i=height(f);  
 printf("%d",i);  
 }  
 break;  
 case 11:  
 break;  
 }  
 getch();  
 }while(ch!=11);  
 }  
 tree * create()  
 {  
 tree *root=NULL;  
 do  
 {  
 root=insert(root);  
 printf("DO U WANT TO ENTER MORE");  
 }while(getche()=='y'||getche()=='Y');  
 return root;  
 }  
 tree *alloc()  
 {  
 tree *nw;  
 nw=(tree *)malloc(sizeof(tree));  
 nw->lc=nw->rc=NULL;  
 printf("ENTER DATA");  
 flushall();  
 gets(nw->data);  
 return nw;  
 }  
 tree * insert(tree *root)  
 {  
 tree *nw,*t;  
 nw=alloc();  
 if(root==NULL)  
 return nw;  
 t=root;  
 while(1)  
 {  
 if(strcmp(nw->data,t->data)<0)  
 {  
 if(t->lc==NULL)  
 {  
 t->lc=nw;  
 return root;  
 }  
 t=t->lc;  
 }  
 else if(strcmp(nw->data,t->data)>0)  
 {  
 if(t->rc==NULL)  
 {  
 t->rc=nw;  
 return root;  
 }  
 t=t->rc;  
 }  
 else  
 {  
 printf("ALREADY PRESNT");  
 free(nw);  
 break;  
 }  
 }  
 return root;  
 }  
 void recin(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recin(root->lc);  
 puts(root->data);  
 recin(root->rc);  
 }  
 }  
 void recpost(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recpost(root->lc);  
 recpost(root->rc);  
 puts(root->data);  
 }  
 }  
 void recpre(tree *root)  
 {  
 if(root!=NULL)  
 {  
 puts(root->data);  
 recpre(root->lc);  
 recpre(root->rc);  
 }  
 }  
 void itin(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 puts(t->data);  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpre(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 puts(t->data);  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpost(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 t=t->rc;  
 }  
 else  
 {  
 puts(t->data);  
 nw=top;  
 top=top->link;  
 free(nw);  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }  
 tree * freeall(tree *t)  
 {  
 tree * q;  
 q=t;  
 if(t!=NULL)  
 {  
 t=freeall(t->lc);  
 t=freeall(q->rc);  
 free(q);  
 }  
 return NULL;  
 }  
 tree *delet(tree *root,char val[])  
 {  
 tree *d,*s,*c,*p,*node;  
 int i=0;  
 p=root;  
 node=search1(root,val,&i);  
 if(i!=0)  
 {  
 if(node->rc!=NULL&&node->lc!=NULL)  
 {  
 printf("WANT TO DELETE BY SUCCESSOR PRESS 'y' ,PRESS ANY KEY FOR PREDECCESOR");  
 if(getche()=='y')  
 s=succ(root,node);  
 else  
 s=pre(root,node);  
 }  
 else  
 s=node;  
 if(s->lc!=NULL)  
 c=s->lc;  
 else  
 c=s->rc;  
 p=parent(root,s);  
 if(p==NULL)  
 {  
 root=c;  
 free(root);  
 return c;  
 }  
 if(p->lc==s)  
 p->lc=c;  
 else  
 p->rc=c;  
 if(s!=node)  
 strcpy(node->data,s->data);  
 free(s);  
 printf("DELETED");  
 }  
 else  
 printf("NOT FOUND");  
 getch();  
 return root;  
 }  
 tree *parent(tree *root,tree *node)  
 {  
 tree *p;  
 p=root;  
 if(strcmp(p->data,node->data)==0)  
 p=NULL;  
 else  
 while(p!=NULL)  
 {  
 if(strcmp(p->data,node->data)<0)  
 {  
 if(p->rc==node)  
 return p;  
 p=p->rc;  
 }  
 else  
 {  
 if(p->lc==node)  
 break;  
 p=p->lc;  
 }  
 }  
 return p;  
 }  
 tree *succ(tree *root,tree *node)  
 {  
 tree *t,*p;  
 if(node->rc!=NULL)  
 {  
 t=node->rc;  
 while(t->lc!=NULL)  
 t=t->lc;  
 return t;  
 }  
 t=node;  
 p=parent(root,node);  
 while(p->lc!=t&&t!=NULL)  
 {  
 t=p;  
 p=succ(root,t);  
 }  
 return p;  
 }  
 tree *pre(tree *root,tree *node)  
 {  
 tree *t,*p;  
 if(node->lc!=NULL)  
 {  
 t=node->lc;  
 while(t->rc!=NULL)  
 t=t->rc;  
 return t;  
 }  
 t=node;  
 p=parent(root,node);  
 while(p->rc!=t&&t!=NULL)  
 {  
 t=p;  
 p=succ(root,t);  
 }  
 return p;  
 }  
 void search(tree *root,char val[])  
 {  
 tree *t,*q;  
 t=root;  
 if(strcmp(val,root->data)!=0)  
 {  
 if(strcmp(val,t->data)>0)  
 q=t->rc;  
 else if(strcmp(val,t->data)<0)  
 q=t->lc;  
 while(q!=NULL)  
 {  
 if(strcmp(val,q->data)>0)  
 q=q->rc;  
 else if(strcmp(val,q->data)<0)  
 q=q->lc;  
 else  
 break;  
 if(strcmp(q->data,t->data)>0)  
 t=t->rc;  
 else if(strcmp(q->data,t->data)<0)  
 t=t->lc;  
 }  
 }  
 else  
 q=root;  
 if(q==NULL)  
 printf("\nNOT FOUND");  
 else  
 {  
 if(q==root)  
 printf("\nIT IS ROOT NODE");  
 else  
 {  
 printf("\nITS PARENT IS:");  
 puts(t->data);  
 }  
 if(q->lc==NULL&&q->rc==NULL)  
 printf("\nIT IS A LEAF NODE");  
 else  
 {  
 if(q->lc!=NULL)  
 {  
 printf("\nITS LEFT CHILD IS:");  
 puts(q->lc->data);  
 }  
 else  
 printf("\nLEFT CHILD IS NOT PRESENT");  
 if(q->rc!=NULL)  
 {  
 printf("\nITS RIGHT CHILD IS:");  
 puts(q->rc->data);  
 }  
 else  
 printf("\nRIGHT CHILD IS NOT PRESENT");  
 }  
 }  
 getch();  
 }  
 tree *mirror(tree *root)  
 {  
 tree *t,*q,*f=NULL,*nw;  
 tree *st[20][2];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 nw=(tree *)malloc(sizeof(tree));  
 nw->lc=NULL;  
 nw->rc=NULL;  
 if(t==NULL)  
 {  
 t=st[top][0];  
 q=st[top--][1];  
 q->lc=nw;  
 q=q->lc;  
 }  
 else if(t!=root)  
 {  
 q->rc=nw;  
 q=q->rc;  
 }  
 if(f==NULL)  
 {  
 f=nw;  
 q=f;  
 }  
 strcpy(q->data,t->data);  
 if(t->rc!=NULL)  
 {  
 st[++top][0]=t->rc;  
 st[top][1]=q;  
 }  
 t=t->lc;  
 }  
 return f;  
 }  
 void leveldis(tree *f)  
 {  
 tree *queue[MAX],*t;  
 int front=-1,rear=-1,i=-1,pl=0,cl=1;  
 t=f;  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t;  
 while(cl!=0||pl!=0)  
 {  
 if(pl==0)  
 {  
 i++;  
 printf("\nELEMENT IN %d LEVEL:",i);  
 pl=cl;  
 cl=0;  
 }  
 t=queue[front];  
 if(front==rear)  
 front=rear=-1;  
 else  
 front=(front+1)%MAX;  
 puts(t->data);  
 if(t->lc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->lc;  
 cl++;  
 }  
 if(t->rc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->rc;  
 cl++;  
 }  
 pl--;  
 }  
 getch();  
 }  
 int depth(tree *root,char val[])  
 {  
 tree *t,*node;  
 int i=0;  
 t=root;  
 while(t!=NULL)  
 {  
 if(strcmp(val,t->data)==0)  
 return i;  
 else if(strcmp(val,t->data)<0)  
 {  
 i++;  
 t=t->lc;  
 }  
 else  
 {  
 i++;  
 t=t->rc;  
 }  
 }  
 printf("NOT FOUND");  
 getch();  
 return -1;  
 }  
 tree* search1(tree *root,char val[],int *i)  
 {  
 tree *t;  
 t=root;  
 while(t!=NULL)  
 {  
 if(strcmp(val,t->data)>0)  
 t=t->rc;  
 else if(strcmp(val,t->data)<0)  
 t=t->lc;  
 else  
 {  
 *i=1;  
 break;  
 }  
 }  
 return t;  
 }  
 int height(tree *t)  
 {  
 int hl,hr;  
 if(t==NULL)  
 return 0;  
 if(t->lc==NULL&&t->rc==NULL)  
 return 0;  
 hl=height(t->lc);  
 hr=height(t->rc);  
 if(hl>hr)  
 return(hl+1);  
 return(hr+1);  
 }

 

Expression Tree in C

Write a program to implement Expression Tree using C Language with the following features :

• Recursive Traverse
• Iterative Traverse

 
 #include  
 #include  
 #include  
 typedef struct tree  
 {  
 char data;  
 struct tree *lc;  
 struct tree *rc;  
 }tree;  
 typedef struct stack1  
 {  
 int flag;  
 struct tree * addr;  
 struct stack1 *link;  
 }stack1;  
 tree * freeall(tree *);  
 void prefix(char []);  
 void postfix(char []);  
 void display(char []);  
 tree *ptprefix(char [],int *);  
 tree *ptpostfix(char [],int *);  
 tree *alloc(char);  
 void recin(tree *);  
 void recpost(tree *);  
 void recpre(tree *);  
 void itin(tree *);  
 void itpre(tree *);  
 void itpost(tree *);  
 void main()  
 {  
 int ch,ch1,i;  
 char str[50];  
 tree *f=NULL;  
 clrscr();  
 do  
 {  
 clrscr();  
 printf("\n\t\t1.INPUT\n\t\t2.RECURSIVE TRAVERSE\n\t\t3.ITERATIVE TRAVERSE\n\t\t4.EXIT");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 printf("\n\t\tINPUT MENU\n\t\t1.PREFIX EXPRESSION\n\t\t2.POSTFIX EXPRESSION\n\t\t3.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tPREFIX EXPRESSION");  
 prefix(str);  
 i=0;  
 f=ptprefix(str,&i);  
 break;  
 case 2:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tPOSTFIX EXPRESSION");  
 postfix(str);  
 i=strlen(str)-1;  
 f=ptpostfix(str,&i);  
 break;  
 case 3:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 break;  
 case 2:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tRECURSIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 recin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 recpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 recpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 getch();  
 }while(ch1!=4);  
 getch();  
 break;  
 case 3:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tITERATIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 itin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 itpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 itpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch1!=4);  
 getch();  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch!=4);  
 }  
 void prefix(char str[])  
 {  
 int i=0,rank=0;  
 while(1)  
 {  
 str[i++]=getche();  
 if(str[i-1]=='\r'&&i>2&&rank==1)  
 break;  
 else if(rank!=1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/'))  
 rank=rank-1;  
 else if(((str[i-1]>=48&&str[i-1]<=57)||(str[i-1]>=65&&str[i-1]<=90)||(str[i-1]>=97&&str[i-1]<=122)))  
 rank=rank+1;  
 else  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 if(rank>1)  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 }  
 str[i-1]=NULL;  
 }  
 void postfix(char str[])  
 {  
 int i=0,rank=0;  
 while(1)  
 {  
 str[i++]=getche();  
 if(str[i-1]=='\r'&&i>2&&rank==1)  
 break;  
 if(i>1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/'))  
 rank=rank-1;  
 else if((str[i-1]>=48&&str[i-1]<=57)||(str[i-1]>=65&&str[i-1]<=90)||(str[i-1]>=97&&str[i-1]<=122))  
 rank=rank+1;  
 else  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 if(rank<1)  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 }  
 str[i-1]=NULL;  
 }  
 tree *ptprefix(char str[],int *i)  
 {  
 tree *nw;  
 nw=alloc(str[(*i)]);  
 if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/')  
 {  
 ++*i;  
 nw->lc=ptprefix(str,i);  
 ++*i;  
 nw->rc=ptprefix(str,i);  
 }  
 return nw;  
 }  
 tree * alloc(char c)  
 {  
 tree *nw;  
 nw=(tree *)malloc(sizeof(tree));  
 nw->data=c;  
 nw->lc=NULL;  
 nw->rc=NULL;  
 return nw;  
 }  
 tree *ptpostfix(char str[],int *i)  
 {  
 tree *nw;  
 char c;  
 nw=alloc(str[(*i)]);  
 if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/')  
 {  
 --*i;  
 nw->rc=ptpostfix(str,i);  
 --*i;  
 nw->lc=ptpostfix(str,i);  
 }  
 return nw;  
 }  
 void recin(tree *root)  
 {  
 if(root!=NULL)  
 {  
 if(root->lc!=NULL)  
 printf("(");  
 recin(root->lc);  
 printf("%c",root->data);  
 recin(root->rc);  
 if(root->rc!=NULL)  
 printf(")");  
 }  
 }  
 void recpost(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recpost(root->lc);  
 recpost(root->rc);  
 printf("%c",root->data);  
 }  
 }  
 void recpre(tree *root)  
 {  
 if(root!=NULL)  
 {  
 printf("%c",root->data);  
 recpre(root->lc);  
 recpre(root->rc);  
 }  
 }  
 void itpre(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 printf("%c",t->data);  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpost(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 t=t->rc;  
 }  
 else  
 {  
 printf("%c",t->data);  
 nw=top;  
 top=top->link;  
 free(nw);  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }  
 tree * freeall(tree *t)  
 {  
 tree * q;  
 q=t;  
 if(t!=NULL)  
 {  
 t=freeall(t->lc);  
 t=freeall(q->rc);  
 free(q);  
 }  
 return NULL;  
 }  
 void itin(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 if(t->lc!=NULL)  
 printf("(");  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 printf("%c",t->data);  
 t=t->rc;  
 }  
 else  
 {  
 nw=top;  
 top=top->link;  
 t=nw->addr;  
 free(nw);  
 if(t->rc!=NULL)  
 printf(")");  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }

 

Queue Operations using C Language

 

Write a program to Queue Operations using C Language to implement the following functions :

• Create Queue
• Delete Queue
• Display Queue
• Delete Queue

Queue Operations using C Language Code

#include  
 #include  
 #include  
 typedef struct queue  
 {  
 char name[20];  
 char diesease[50];  
 struct add  
 {  
 int hno;  
 int sno;  
 char city[20];  
 }add;  
 struct queue * link;  
 }queue;  
 typedef struct prior  
 {  
 queue * front;  
 queue * rear;  
 int priority;  
 struct prior * next;  
 }prior;  
 prior *create();  
 prior *delet(prior *);  
 void display(queue *,int *);  
 void alloc(queue *);  
 prior *freeall(prior *);  
 void main()  
 {  
 int ch,ch1,temp;  
 prior *t,*f=NULL;  
 do  
 {  
 clrscr();  
 printf("\n\t1.CREATE\n\t2.DELETE\n\t3.DISPLAY\n\t4.EXIT\n\tENTER UR CHOICE:");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1: if(f!=NULL)  
 f=freeall(f);  
 printf("\nCREATE");  
 f=create();  
 break;  
 case 2:  
 if(f==NULL)  
 printf("FIRST CREATE !!!!!");  
 else  
 {  
 printf("\nDELETE");  
 f=delet(f);  
 }  
 getch();  
 break;  
 case 3:  
 if(f==NULL)  
 printf("FIRST CREATE !!!!!");  
 else  
 {  
 do  
 {  
 clrscr();  
 printf("\n\tDISPLAY\n\t1.BY CATEGORY\n\t2.ALL\n\t3.EXIT\n\tENTER UR CHOICE");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\nENTER THE CATEGORY:\n1.SERIOUS\n2.NON-SERIOUS\n3.GENERAL");  
 scanf("%d",&ch);  
 temp=1;  
 t=f;  
 clrscr();  
 while(t!=NULL)  
 {  
 if(t->priority==ch)  
 break;  
 t=t->next;  
 }  
 if(t!=NULL)  
 display(t->front,&temp);  
 else  
 printf("NOT FOUND");  
 getch();  
 break;  
 case 2:  
 t=f;  
 temp=1;  
 clrscr();  
 while(t!=NULL)  
 {  
 display(t->front,&temp);  
 t=t->next;  
 }  
 getch();  
 break;  
 case 3:  
 break;  
 default:printf("\nINVALID CHOICE");  
 }  
 }while(ch1!=3);  
 }  
 getch();  
 break;  
 case 4:  
 break;  
 default:printf("\nINVALID CHOICE");  
 }  
 }while(ch!=4);  
 getch();  
 }  
 prior * create()  
 {  
 int p;  
 prior *f=NULL,*nw1,*t;  
 queue *nw;  
 do  
 {  
 nw=(queue *)malloc(sizeof(queue));  
 nw->link=NULL;  
 alloc(nw);  
 printf("\nGIVE THE PRIORITY TO THIS PATIENT:");  
 while(1)  
 {  
 scanf("%d",&p);  
 if(p>0&&p<4)  
 break;  
 else  
 printf("INVALID PRIORITY");  
 }  
 if(f==NULL)  
 {  
 nw1=(prior *)malloc(sizeof(prior));  
 nw1->next=NULL;  
 nw1->priority=p;  
 nw1->front=nw;  
 nw1->rear=nw;  
 f=nw1;  
 }  
 else  
 {  
 if(f->priority>p)  
 {  
 nw1=(prior *)malloc(sizeof(prior));  
 nw1->next=NULL;  
 nw1->priority=p;  
 nw1->front=nw;  
 nw1->rear=nw;  
 nw1->next=f;  
 f=nw1;  
 }  
 t=f;  
 while(p>=t->next->priority&&t->next!=NULL)  
 t=t->next;  
 if(p==t->priority)  
 {  
 t->rear->link=nw;  
 t->rear=nw;  
 }  
 else  
 {  
 nw1=(prior *)malloc(sizeof(prior));  
 nw1->next=NULL;  
 nw1->priority=p;  
 nw1->front=nw;  
 nw1->rear=nw;  
 nw1->next=t->next;  
 t->next=nw1;  
 }  
 }  
 printf("DO U WANT TO ENTER MORE:");  
 }while(getche()=='y'||getche()=='Y');  
 return f;  
 }  
 void alloc(queue *nw)  
 {  
 printf("\nENTER NAME:");  
 flushall();  
 gets(nw->name);  
 printf("\nENTER DIESEASE:");  
 flushall();  
 gets(nw->diesease);  
 printf("\nENTER H.NO:");  
 scanf("%d",&(nw->add.hno));  
 printf("\nENTER S.NO:");  
 scanf("%d",&(nw->add.sno));  
 printf("\nENTER CITY:");  
 flushall();  
 gets(nw->add.city);  
 }  
 void display(queue *t,int *temp)  
 {  
 while(t!=NULL)  
 {  
 printf("\n\nNAME:");  
 printf("%s",t->name);  
 printf("\nDIESEASE:");  
 printf("%s",t->diesease);  
 printf("\nADDRESS");  
 printf("\nHOUSE.NO:");  
 printf("%d",(t->add.hno));  
 printf("\nSTREET.NO:");  
 printf("%d",(t->add.sno));  
 printf("\nCITY:");  
 printf("%s",(t->add.city));  
 t=t->link;  
 getch();  
 }  
 }  
 prior *delet(prior *f)  
 {  
 prior *nw;  
 queue *q,*q1;  
 q=f->front;  
 if(q->link==NULL)  
 {  
 nw=f;  
 f=f->next;  
 free(nw);  
 }  
 else  
 f->front=q->link;  
 free(q);  
 printf("\nDATA is DELETED!!!!!!");  
 getch();  
 return f;  
 }  
 prior *freeall(prior *f)  
 {  
 prior *t;  
 queue *s,*r;  
 while(f!=NULL)  
 {  
 r=f->front;  
 while(r!=NULL)  
 {  
 s=r;  
 r=r->link;  
 free(s);  
 }  
 t=f;  
 f=f->next;  
 free(t);  
 }  
 return f;  
 }

 

Stack Operations using C Language

Implement stack as an abstract data type (ADT) using linked list.

Use this ADT for

•  infix to prefix conversion
• infix to post fix conversion
• evaluation of post fix expression

 #include  
 #include  
 #include  
 #include  
 #include  
 typedef struct stack  
 {  
 char data;  
 struct stack * link;  
 }stack;  
 typedef struct eval  
 {  
 float data;  
 struct eval * link;  
 }eval;  
 typedef struct val  
 {  
 char data;  
 float value;  
 struct val * link;  
 }val;  
 int pinppost(char);  
 int pstppost(char);  
 int pinppre(char);  
 int pstppre(char);  
 float posteval(char []);  
 float preeval(char []);  
 void create(char []);  
 void postfix(char [],char []);  
 void prefix(char [],char []);  
 void display(char []);  
 void main()  
 {  
 int ch;  
 float j;  
 char str[50],str1[50],str2[50];  
 float dummy;  
 &dummy;  
 str[0]=NULL;  
 str1[0]=NULL;  
 str2[0]=NULL;  
 clrscr();  
 do  
 {  
 clrscr();  
 printf("\n\t\tOPERATION ON STACK\n\t\t1.INFIX EXPRESSION\n\t\t2.INFIX TO PREFIX\n\t\t3.INFIX TO POSTFIX\n\t\t4.EVALUATION FOR PREFIX\n\t\t5.EVALUATION FOR POSTFIX\n\t\t6.EXIT");  
 printf("\n\t\tENTER UR CHOICE");  
 flushall();  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 printf("\n\t\tINFIX EXPRESSION:");  
 create(str);  
 display(str);  
 break;  
 case 2:  
 if(str[0]==NULL)  
 printf("enter input first");  
 else  
 {  
 printf("\n\t\tINFIX TO PREFIX :");  
 prefix(str,str2);  
 printf("\nINFIX EXPRESSION IS:");  
 display(str);  
 printf("\nPREFIX EXPRESSION IS:");  
 display(str2);  
 }  
 getch();  
 break;  
 case 3: if(str[0]==NULL)  
 printf("enter input first");  
 else  
 {  
 printf("\n\t\tINFIX TO POSTFIX EXPRESSION");  
 postfix(str,str1);  
 printf("\nINFIX EXPRESSION IS:");  
 display(str);  
 printf("\nPOSTFIX EXPRESSION IS:");  
 display(str1);  
 }  
 getch();  
 break;  
 case 4: if(str[0]==NULL||str2[0]==NULL)  
 printf("either you havnt given input or you havnt done conversion,first do that part ");  
 else  
 {  
 printf("\n\t\tEVALUATION ON PREFIX EXPRESSION");  
 j=preeval(str2);  
 printf("\nVALUE EVALUATED IS:%f",j);  
 }  
 getch();  
 break;  
 case 5: if(str[0]==NULL||str1[0]==NULL)  
 printf("either you havnt given input or you havnt done conversion,first do that part ");  
 else  
 {  
 printf("\n\t\tEVALUATION ON POSTFIX EXPRESSION");  
 j=posteval(str1);  
 printf("\nVALUE EVALUATED IS:%f",j);  
 }  
 getch();  
 break;  
 case 6:  
 printf("\n\t\tEXIT");  
 break;  
 }  
 }while(ch!=6);  
 }  
 void create(char str[])  
 {  
 int rank=0,i=0,j=0,k,m,l;  
 while(1)  
 {  
 str[i]=getche();  
 i++;  
 if(str[i-1]=='\r')  
 {  
 if(rank!=1||j!=0||i<=2)  
 {  
 printf("\ninvalid exprexion,enter from starting");  
 j=0;  
 rank=0;  
 i=0;  
 }  
 else  
 break;  
 }  
 else if(str[i-1]=='(')  
 if(rank==1)  
 {  
 printf("\ninvalid exprexion,enter from starting");  
 i=0;  
 j=0;  
 rank=0;  
 }  
 else  
 j++;  
 else if(str[i-1]==')')  
 if(rank==0)  
 {  
 printf("\ninvalid exprexion,enter from starting");  
 i=0;  
 j=0;  
 rank=0;  
 }  
 else  
 j--;  
 else if(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/')  
 rank=rank-1;  
 else if((str[i-1]>=48&&str[i-1]<=57)||(str[i-1]>=65&&str[i-1]<=90)||(str[i-1]>=97&&str[i-1]<=122))  
 rank=rank+1;  
 else if(str[i-1]!=')'&&str[i-1]!='(')  
 {  
 printf("\ninvalid entry,enter from starting");  
 i=0;  
 j=0;  
 rank=0;  
 }  
 if((rank!=1&&rank!=0)||j<0)  
 {  
 printf("\ninvalid exprexion,enter from starting");  
 i=0;  
 j=0;  
 rank=0;  
 }  
 }  
 str[i]=NULL;  
 }  
 void display(char str[])  
 {  
 int i=0;  
 while(str[i]!=NULL)  
 {  
 printf("%c",str[i]);  
 i++;  
 }  
 getch();  
 }  
 void prefix(char str[],char str2[])  
 {  
 int i,l,j;  
 stack *nw,*top,*top1=NULL;  
 l=strlen(str);  
 i=l-1;  
 for(j=l;j>0;j--)  
 str[j]=str[j-1];  
 str[j]='#';  
 nw=(stack *)malloc(sizeof(stack));  
 nw->data='#';  
 top=nw;  
 while(1)  
 {  
 while(pinppre(str[i])<pstppre(top->data))  
 {  
 nw=(stack *)malloc(sizeof(stack));  
 nw->data=top->data;  
 nw->link=top1;  
 top1=nw;  
 nw=top;  
 top=top->link;  
 free(nw);  
 }  
 if(pinppre(str[i])==pstppre(top->data))  
 {  
 if(top->data=='#')  
 break;  
 nw=top;  
 top=top->link;  
 free(nw);  
 i--;  
 }  
 else  
 {  
 nw=(stack *)malloc(sizeof(stack));  
 nw->data=str[i--];  
 nw->link=top;  
 top=nw;  
 }  
 }  
 for(j=0;j<l;j++) <br=""> {  
 str[j]=str[j+1];  
 }  
 str[l]=NULL;  
 j=0;  
 while(top1!=NULL)  
 {  
 str2[j]=top1->data;  
 nw=top1;  
 top1=top1->link;  
 free(nw);  
 j++;  
 }  
 str2[j]=NULL;  
 }  
 void postfix(char str[],char str1[])  
 {  
 int l,i,j;  
 stack *nw,*top;  
 i=j=0;  
 l=strlen(str);  
 str[l-1]='#';  
 nw=(stack *)malloc(sizeof(stack));  
 nw->data='#';  
 top=nw;  
 while(1)  
 {  
 while(pinppost(str[i])<pstppost(top->data))  
 {  
 str1[j++]=top->data;  
 nw=top;  
 top=top->link;  
 free(nw);  
 }  
 if(pinppost(str[i])==pstppost(top->data))  
 {  
 if(top->data=='#')  
 break;  
 nw=top;  
 top=top->link;  
 free(nw);  
 i++;  
 }  
 else  
 {  
 nw=(stack *)malloc(sizeof(stack));  
 nw->data=str[i++];  
 nw->link=top;  
 top=nw;  
 }  
 }  
 str[l-1]=NULL;  
 str1[j]=NULL;  
 }  
 int pinppost(char c)  
 {  
 switch(c)  
 {  
 case '#': return(-1);  
 case '*':  
 case '/': return(3);  
 case '+':  
 case '-': return(1);  
 case '^': return(6);  
 case '(': return(8);  
 case ')': return(0);  
 }  
 return(7);  
 }  
 int pstppost(char c)  
 {  
 switch(c)  
 {  
 case '#': return(-1);  
 case '*':  
 case '/': return(4);  
 case '+':  
 case '-': return(2);  
 case '^': return(5);  
 case '(': return(0);  
 }  
 return(7);  
 }  
 int pinppre(char c)  
 {  
 switch(c)  
 {  
 case '#': return(-1);  
 case '*':  
 case '/': return(4);  
 case '+':  
 case '-': return(2);  
 case '^': return(5);  
 case '(': return(0);  
 case ')': return(8);  
 }  
 return(7);  
 }  
 int pstppre(char c)  
 {  
 switch(c)  
 {  
 case '#': return(-1);  
 case '*':  
 case '/': return(3);  
 case '+':  
 case '-': return(1);  
 case '^': return(6);  
 case ')': return(0);  
 }  
 return(7);  
 }  
 float posteval(char str1[])  
 {  
 val *nw,*t,*top=NULL;  
 eval *nw1,*top1=NULL;  
 int i;  
 float opr1;  
 char op;  
 i=0;  
 for(i=0;str1[i]!=NULL;i++)  
 {  
 if(str1[i]!='+'&&str1[i]!='-'&&str1[i]!='*'&& str1[i]!='^'&&str1[i]!='/')  
 {  
 nw=top;  
 while(nw!=NULL)  
 {  
 if(str1[i]==nw->data)  
 break;  
 nw=nw->link;  
 }  
 if(nw==NULL)  
 {  
 nw=(val *)malloc(sizeof(val));  
 nw->data=str1[i];  
 printf("ENTER THE VALUE OF %c:",str1[i]);  
 scanf("%f",&(nw->value));  
 nw->link=top;  
 top=nw;  
 }  
 nw1=(eval *)malloc(sizeof(eval));  
 nw1->data=nw->value;  
 nw1->link=top1;  
 top1=nw1;  
 }  
 else  
 {  
 op=str1[i];  
 opr1=top1->data;  
 nw1=top1;  
 top1=top1->link;  
 free(nw1);  
 switch(op)  
 {  
 case '*':opr1=top1->data*opr1;  
 break;  
 case '/':opr1=top1->data/opr1;  
 break;  
 case '+':opr1=top1->data+opr1;  
 break;  
 case '-':opr1=top1->data-opr1;  
 break;  
 case '^':opr1=pow(top1->data,opr1);  
 break;  
 }  
 top1->data=opr1;  
 }  
 }  
 opr1=top1->data;  
 free(top1);  
 return(opr1);  
 }  
 float preeval(char str[])  
 {  
 val *nw,*t,*top=NULL;  
 eval *nw1,*top1=NULL;  
 int i,n;  
 float opr1,opr2;  
 char op;  
 i=0;  
 for(i=0;str[i]!=NULL;i++)  
 {  
 if(str[i]!='+'&&str[i]!='-'&&str[i]!='*'&& str[i]!='^'&&str[i]!='/')  
 {  
 nw=top;  
 while(nw!=NULL)  
 {  
 if(str[i]==nw->data)  
 break;  
 nw=nw->link;  
 }  
 if(nw==NULL)  
 {  
 nw=(val *)malloc(sizeof(val));  
 nw->data=str[i];  
 printf("ENTER THE VALUE OF %c:",str[i]);  
 scanf("%f",&(nw->value));  
 nw->link=top;  
 top=nw;  
 }  
 opr1=nw->value;  
 while(1)  
 {  
 if(top1==NULL||top1->data=='+'||top1->data=='-'||top1->data=='*'||top1->data=='/'||top1->data=='^')  
 break;  
 opr2=top1->data;  
 nw1=top1;  
 top1=top1->link;  
 free(nw1);  
 op=(char)top1->data;  
 nw1=top1;  
 top1=top1->link;  
 free(nw1);  
 switch(op)  
 {  
 case '*':opr1=opr2*opr1;  
 break;  
 case '/':opr1=opr2/opr1;  
 break;  
 case '+':opr1=opr2+opr1;  
 break;  
 case '-':opr1=opr2-opr1;  
 break;  
 case '^':opr1=pow(opr2,opr1);  
 break;  
 }  
 }  
 nw1=(eval*)malloc(sizeof(eval));  
 nw1->data=opr1;  
 nw1->link=top1;  
 top1=nw1;  
 }  
 else  
 {  
 nw1=(eval*)malloc(sizeof(eval));  
 nw1->data=(float)str[i];  
 nw1->link=top1;  
 top1=nw1;  
 }  
 }  
 opr1=top1->data;  
 free(top1);  
 return(opr1);  
 }

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;  
 }