/* C PROGRAM TO IMPLEMENT DEQUEUES USING ARRAYS*/

#include<stdio.h>
#include<stdlib.h>
int dque[20],rear=-1,front=-1,size=20,item,i;
main()
{
int ch;
do
{
printf("\n 1.linsert()");
printf("\n 2.rinsert()");
printf("\n 3.ldelete()");
printf("\n 4.rdelete()");
printf("\n 5.display()");
printf("\n 6.exit()\n");
printf("enter the choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
linsert();
break;
case 2:
rinsert();
break;
case 3:
ldelete();
break;
case 4:
rdelete();
break;
case 5:
display();
break;
case 6:
exit(0);
}
}while(ch!=6);
}
linsert()
{
int item;
printf("enter the item");
scanf("%d",&item);
if(rear>=size-1)
{
printf("overflow");
}

43
 else
{
if(front==-1)
{
front=0;
rear=0;
dque[rear]=item;
return;
}
for(i=rear;i>=front;i--)
dque[i+1]=dque[i];
dque[front]=item;
rear++;
}
}
rinsert()
{
printf("enter the item");
scanf("%d",&item);
if(rear>=size-1)
{
printf("overflow");
return;
}
else
{
if(front==-1)
{
front=0;
}
rear++;
dque[rear]=item;
return;
}
}
ldelete()
{
if(rear==-1||front>rear)
{
printf("underflow");
return;
}
item=dque[front];
front++;
printf("%d",item);
}
rdelete()
{
if((rear==-1)||(front>rear))

44
 {

printf("underflow");
return;
}
item=dque[rear];
--rear;
printf("%d",item);
}
display()
{
int i;
for(i=front;i<=rear;i++)
printf("%d",dque[i]);
}

/*OUTPUT*/
1.linsert
2.rinsert
3.ldelete
4.rdelete
5.display
6.exit
enter the choice::1
enter the item::3
1.linsert
2.rinsert
3.ldelete
4.rdelete
5.display
6.exit
enter the choice::2
enter the item::4
1.linsert
2.rinsert
3.ldelete
4.rdelete
5.display
6.exit
enter the choice::5
34
1.linsert
2.rinsert
3.ldelete
4.rdelete
5.display
6.exit
enter the choice::6

45
/* C PROGRAM TO SORT THE ARRAY LIST USING INSERTION SORT*/

#include<stdio.h>
main()
{
int a[20],i,n;
printf("enter the n");
scanf("%d",&n);
printf("enter the list");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insert(a,n);
}
insert(int a[],int n)
{
int i,j=0,key;
for(i=0;i<n;i++)
{
key=a[i];
j=i-1;
while((key<a[j])&&(j>=0))
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
printf("enter the sorted list:");
for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
}

/*OUTPUT*/

enter the n:: 5

enter the list:: 11 15 2 13 3

enter the sorted list:2 3 11 13 15

46
/* C PROGRAM TO SORT THE ARRAY LIST USING SELECTION SORT*/

#include<stdio.h>
main()
{
int a[20];
int i,j,large,n,pos;
printf("enter the n:");
scanf("%d",&n);
printf("enter the list:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=n-1;i>=0;i--)
{
large=a[0];
pos=0;
for(j=0;j<=i;j++)
{
if(a[j]>large)
{
large=a[j];
pos=j;
}
}
a[pos]=a[i];
a[i]=large;
}
printf("enter the sorted list");
for(i=0;i<n;i++)
printf(" %d",a[i]);
}

/*OUTPUT*/

enter the n:: 5

enter the list:: 7 2 9 5 1

enter the sorted list:1 2 5 7 9

47
/* C PROGRAM TO SORT THE ARRAY LIST USING QUICK SORT*/

#include<stdio.h>
int a[50];

main()
{
int n,i;
printf("enter the n");
scanf("%d",&n);
printf("enter the list:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,0,n-1);
printf("enter the sorted list:");
for(i=0;i<n;i++)
printf(" %d",a[i]);
}
qsort(int a[],int lb,int ub)
{
int i,j,t,key;
if(lb<ub)
{
i=lb;
j=ub;
key=a[lb];
while(i<j)
{
while((key>=a[i])&&(i<ub))
{
i++;
while(key<a[j])
j--;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[lb]=a[j];
a[j]=key;
qsort(a,lb,j-1);
qsort(a,j+1,ub);
}

48
 else
{

return;
}
}

/*OUTPUT*/

enter the n:: 5

enter the list:: 11 15 2 13 3

enter the sorted list:2 3 11 13 15

49
/* C PROGRAM TO SORT THE ARRAY LIST USING BUBBLE SORT*/

#include<stdio.h>
main()
{
int a[10],n,i,j,temp;
system("clear");
printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter %d elements into the array\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<(n-i)-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("after sorting the elements are\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}

/*OUTPUT*/

enter the n:: 5

enter the list:: 11 15 2 13 3

enter the sorted list:2 3 11 13 15

50
/* C PROGRAM TO SORT THE ARRAY LIST USING HEAP SORT*/

#include<stdio.h>
main()
{
int a[25],n,i;
system("clear");
printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter %d elements into the array\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
heap(a,i,a[i]);
}
printf("after constructing heap the elements are\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
heapsort(a,n);
printf("sorted elements are\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}

heap(int a[],int pos,int k)

{
int f;
f=(pos-1)/2;
while(pos>0 && k>a[f])
{
a[pos]=a[f];
pos=f;
f=(pos-1)/2;
}
a[pos]=k;
}
heapsort(int a[],int n)
{
int k,key,i,j;
for(i=n-1;i>0;i--)
{
key=a[0];
a[0]=a[i];

51
 a[i]=key;
for(j=0;j<i;j++)
{
heap(a,j,a[j]);
}
}
}

/*OUTPUT*/

enter the n:: 7

enter the list:: 11 15 2 13 3 8 18

enter the sorted list:2 3 8 11 13 15 18

52
/*C PROGRAM TO SEARCH A GIVEN ELEMENT IN THE LIST USING LINEAR
SEARCH*/
#include<stdio.h>
main()
{
int i,j,k,n,a[100],flag=1;
printf("number of elements in the array\n");
scanf("%d",&n);
printf("enter array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("the entered array elements are\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\nenter the element to search\n");
scanf("%d",&k);
for(i=0;i<n;i++)
{
if(a[i]==k)
{
printf("search is successful\n");
printf("element %d is found at location %d\n",k,i+1);
flag=0;
break;
}
}
if(flag)
{
printf("search is unsuccessful\n");
}
}

/*OUTPUT*/

number of elements in the array:5

enter array elements:2 1 3 4 5
the entered array elements are:2 1 3 4 5
enter the element to search:4
search is successful
element 4 is found at location 4

53
/*C PROGRAM TO SEARCH A GIVEN ELEMENT IN THE LIST USING BINARY
SEARCH*/

#include<stdio.h>
main()
{
int a[100],i,n,low,high,mid,key,flag=1;
system("clear");
printf("number of elements in the array\n");
scanf("%d",&n);
printf("enter elements in ascending order\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("the elements in ascending order are\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("enter the element to be search\n");
scanf("%d",&key);
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(key<a[mid])
high=mid-1;
else if(key>a[mid])
low=mid+1;
else if(key==a[mid])
{
printf("search is successful\n");
printf("%d found at location %d\n",key,mid+1);
flag=0;
break;
}
}
if(flag)
printf("search is unsuccessful\n");
}
/*OUTPUT*/
Number of elements in the array:5
Enter elements in ascending order:1 2 3 4 5
The elements in ascending order are:1 2 3 4 5
Enter the element to be search:3
Search is successful 3 found at location 3

54
/*C PROGRAM TO SEARCH A GIVEN ELEMENT IN THE LIST USING RECURSIVE
BINARY SEARCH*/

#include<stdio.h>
int key;
main()
{
int a[50],i,n,loc;

printf("enter the size of the array\n");

scanf("%d",&n);
printf("enter array elements in assending order\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("the ewntered elements are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("enter the element to search\n");
scanf("%d",&key);
loc=bin(a,0,n-1);

if(loc==0)
printf("unsuccessful search,%d not found\n",key);
else
{
printf("successful search\n");
printf("%d found at position %d\n",key,loc);
}
}
int bin(int b[],int low,int high)

int mid,p;

if(low<=high)
{
mid=(low+high)/2;
printf("%d ", mid);
if(key<b[mid])
{
high=mid-1;
p=bin(b,low,mid-1);
return p;
}
else if(key>b[mid])
{
low=mid+1;

55
 p=bin(b,mid+1,high);
return p;
}
else if(key==b[mid])
{
printf("%d",b[mid]);
return(mid + 1);
} }

else

return(0);

/*OUTPUT*/
Number of elements in the array:5
Enter elements in ascending order:1 2 3 4 5
The elements in ascending order are:1 2 3 4 5
Enter the element to be search:3
Search is successful 3 found at location 3

56
/*C PROGRAM FOR PERFORMING THE LINKED LIST OPERATIONS ON A SINGLY
LINEAR LINKED LIST*/

#include<stdio.h>
#include<stdlib.h>
void insertbeg();
void insertend();
void insertpos();
void delbeg();
void delend();
void delpos();
void display();
struct node
{
int info;
struct node *link;
};
struct node *create(),*first=NULL;
int item,key;
main()
{
int choice;
while(1)
{
printf("\n1.Insertbeg\n2.Insertend\n3.Insertpos\n4.delbeg\n5.delend\n6.delpos\n7.display\
n8.exit\n");
printf("Enter U'r choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
insertbeg();
break;
case 2:
insertend();
break;
case 3: insertpos();
break;

case 4: delbeg();
break;
case 5:
delend();
break;

case 6:
delpos();
break;

57
 case 7:
display();
break;

case 8:
exit(1);
default:
printf("INVALID CHOICE TRY AGAIN\n");
}
}
}

struct node *create()

{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
return(new);
}

void insertbeg()
{
struct node *new;

new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
if(first==NULL)
{
new->info=item;
new->link=NULL;
first=new;
}
else
{
new->info=item;
new->link=first;
first=new;
}
}

void insertend()
{
struct node *new,*temp;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
if(first==NULL)
{

58
 new->info=item;
new->link=NULL;
first=new;
}

else
{
temp=first;
while(temp->link!=NULL)
temp=temp->link;
new->info=item;
new->link=NULL;
temp->link=new;
}
}

void insertpos()
{
struct node *new,*prev,*temp;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
printf("ENter key position\n");
scanf("%d",&key);
temp=first;
while(temp->info!=key&&temp->link!=NULL)

{
prev=temp;
temp=temp->link;
}
if(temp->info==first->info&&temp->info==key)
{
new->info=item;
new->link=temp;
first=new;
}
else
{
new->info=item;
new->link=temp;
prev->link=new;
}
}

void delbeg()
{
struct node *temp;
if(first==NULL)
{

59
 printf("LIST IS EMPTY\n");
return;
}

else
{
temp=first;
first=temp->link;
free(temp);
}
}

void delend()
{
struct node *temp,*prev;
if(first==NULL)
{
printf("LIST IS EMPTY\n");
return;
}
else
{
temp=first;
while(temp->link!=NULL)
{
prev=temp;
temp=temp->link;
}
prev->link=NULL;
free(temp);
}
}

void delpos()
{
int key;
struct node *temp,*prev;
if(first==NULL)
{
printf("LIST IS EMPTY\n");
return;
}
else
{
temp=first;
printf("Enter the KEY element which is to be deleted\n");
scanf("%d",&key);
while(temp->info!=key&&temp->link!=NULL)
{
prev=temp;

60
 temp=temp->link;
}
if(temp->info==first->info && temp->info==key)
{ first=temp->link;
free(temp);
}

else if(temp->info==key&&temp->link!=NULL)
{
prev->link=temp->link;
free(temp);
}
else if(temp->link==NULL && temp->info==key)
{
delend();
}
else
printf("key element not found in the list\n");
}
}

void display()
{
struct node *temp;
temp=first;
if(temp==NULL)
{
printf("LIST IS EMPTY\n");
return;
}
else
{
while(temp!=NULL)
{
printf("%d->",temp->info);
temp=temp->link;
}

}
}

61
 /*OUTPUT*/

1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
1
Enter element to be inserted
2
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
3
Enter element to be inserted
3
ENter key position
2
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
7
2->3->
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice 8

62
/*C PROGRAM FOR PERFORMING THE LINKED LIST OPERATIONS ON A DOUBLY
LINKED LIST*/

#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *lptr;
struct node *rptr;
}*first=NULL;

struct node *create();

void insertbeg();
void insertend();
void insertSpos();
void delbeg();
void delend();
void delpos();
void display();
int item,key;
main()
{
int choice;
while(1)
{

printf("\n 1.Insertbeg\n 2.Insertend\n 3.Insertpos\n 4.delbeg\n 5.delend \n 6.delpos\n

7.display\n 8.exit\n");

printf("Enter U'r choice\n");

scanf("%d",&choice);
switch(choice)
{

case 1:
insertbeg();
break;
case 2:
insertend();
break;
case 3:
insertSpos();
break;

case 4:
delbeg();
break;

63
 case 5:
delend();
break;
case 6:
delpos();
break;
case 7:
display();
break;
case 8:
exit(1);
default: printf("INVALID CHOICE TRY AGAIN\n");
}
}
}

struct node *create()

{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
return(new);
}

void insertbeg()
{
struct node *new;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
if(first==NULL)
{
new->info=item;
new->rptr=NULL;
new->lptr=NULL;
first=new;
}
else
{
new->info=item;
new->rptr=first;
new->lptr=NULL;
first->lptr=new;
first=new;
}
}

void insertend()
{
struct node *new,*temp;
new=create();
printf("Enter element to be inserted\n");

64
 scanf("%d",&item);
if(first==NULL)
{
new->info=item;
new->rptr=NULL;
new->lptr=NULL;
first=new;
}
else
{
temp=first;
while(temp->rptr!=NULL)
temp=temp->rptr;
new->info=item;
new->rptr=NULL;
new->lptr=temp;
temp->rptr=new;
}
}

void insertSpos()
{
struct node *new,*temp;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
printf("ENter key position\n");
scanf("%d",&key);
if(first==NULL)
{
new->info=item;
new->rptr=NULL;
new->lptr=NULL;
first=new;
}
else
{
temp=first;
while(temp->info!=key&&temp->rptr!=NULL)
{
temp=temp->rptr;
}
if(temp->info==first->info&&temp->info==key)
insertbeg();
else if(temp->rptr!=NULL)
{
new->info=item;
new->lptr=temp->lptr;
new->rptr=temp;
temp->lptr->rptr=new;

65
 temp->lptr=new;
}
else
{
printf("KEY NOT FOUND IN THE DOUBLY LINKED LIST\n");
return;
}
}
}

void delbeg()
{
struct node *temp;
if(first==NULL)
{
printf("DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else
{
temp=first;
first=temp->rptr;
free(temp);
}
}

void delend()
{
struct node *temp;
if(first==NULL)
{
printf("DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else
{
temp=first;
while(temp->rptr!=NULL)
{
temp=temp->rptr;
}
if(temp->rptr==temp->lptr)
{
first=temp->rptr;
free(temp);
}
else
{
temp->lptr->rptr=temp->rptr;

66
 free(temp);
}
}
}
void delpos()
{
int key;
struct node *temp;
if(first==NULL)
{
printf("DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else
{
temp=first;
printf("Enter the KEY element which is to be deleted\n");
scanf("%d",&key);
while(temp->info!=key&&temp->rptr!=NULL)
{
temp=temp->rptr;
}
if(temp->info==first->info&&temp->info==key)
delbeg();
else if(temp->info==key&&temp->rptr==NULL)
delend();
else if(temp->info==key&&temp->rptr!=NULL)
{
temp->lptr->rptr=temp->rptr;
temp->rptr->lptr=temp->lptr;
free(temp);
}
else
printf("KEY NOT FOUND IN THE DOUBLY LINKED LIST\n");
}
}

void display()
{
struct node *temp;
temp=first;
if(temp==NULL)
{
printf("LIST IS EMPTY\n");
return;
}

while(temp!=NULL)
{
printf("%d->",temp->info);

67
 temp=temp->rptr;
}
}

/*OUTPUT*/

1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
1
Enter element to be inserted
3
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
4
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
7
LIST IS EMPTY
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
8

68
/*C PROGRAM FOR PERFORMING THE LINKED LIST OPERATIONS ON A DOUBLY
CIRCULARLY LINKED LIST*/

#include<stdio.h>
#include<stdlib.h>
void insertbeg();
void insertend();
void insertpos();
void delbeg();
void delend();
void delpos();
void display();
struct node
{
int info;
struct node *lptr;
struct node *rptr;
}*first=NULL;
struct node *create();

int item,key;
main()
{
int choice;
while(1)
{
printf("\n1.Insertbeg\n2.Insertend\n3.Insertpos\n4.delbeg\n5.delend\n6.delpos\n7.dis-
play\n8.exit\n");
printf("Enter U'r choice\n");
scanf("%d",&choice);
switch(choice)
{

case 1:
insertbeg();
break;
case 2:
insertend();
break;
case 3:
insertpos();
break;
case 4:
delbeg();
break;
case 5:
delend();
break;
case 6:
delpos();
break;

69
 case 7:
display();
break;
case 8:
exit(1);
default:
printf("INVALID CHOICE TRY AGAIN\n");
}
}
}
struct node *create()
{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
return(new);
}

void insertbeg()
{
struct node *new,*last;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
if(first==NULL)
{
first=new;
new->info=item;
new->lptr=new;
new->rptr=new;
}
else
{
last=first;
while(last->rptr!=first)
last=last->rptr;
last->rptr=new;
new->info=item;
new->rptr=first;
new->lptr=last;
first->lptr=last;
first=new;
}
}
void insertend()
{
struct node *new,*temp,*prev;
new=create();
printf("Enter element to be inserted\n");
scanf("%d",&item);
if(first==NULL)
{

70
 first=new;
new->info=item;
new->lptr=first;
new->rptr=new;
}
else
{
temp=first;
while(temp->rptr!=first)
{
prev=temp;
temp=temp->rptr;
}
new->info=item;
new->rptr=first;
temp->rptr=new;
new->lptr=temp;
first->lptr=new;
}
}
void insertpos()
{
struct node *new,*temp,*prev;
new=create();
if(first==NULL)
{
first=new;
new->info=item;
new->lptr=first;
new->rptr=new;
}
else
{
printf("Enter key position\n");
scanf("%d",&key);
temp=first;
while(temp->info!=key&&temp->rptr!=first)
{
prev=temp;

temp=temp->rptr;
}
if(temp->info==first->info&&temp->info==key)
insertbeg();
else if(temp->info==key&&temp->rptr==first)
{
printf("enter the element to be inserted\n");
scanf("%d",&item);
new->info=item;
new->lptr=prev;

71
 new->rptr=temp;
prev->rptr=new;
temp->lptr=new;
}
else if(temp->info==key&&temp->rptr!=first)
{
printf("Enter element to be inserted\n");
scanf("%d",&item);
new->info=item;
new->rptr=temp;
new->lptr=prev;
prev->rptr=new;
temp->lptr=new;
}
else
{
printf("KEY NOT FOUND IN THE LIST\n");
return;
}
}
}

void delbeg()
{
struct node *temp,*last;
temp=first;
if(first==NULL)
{
printf("CIRCULARLY DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else if(temp->rptr!=first)
{
last=first;
while(last->rptr!=first)
last=last->rptr;
first=temp->rptr;
last->rptr=first;
first->lptr=last;
free(temp);
}
else
{
free(temp);
first=NULL;
}
}

72
void delend()
{
struct node *temp,*prev;
temp=first;
if(first==NULL)
{
printf("CIRCULARLY DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else if(temp->rptr!=first)
{
while(temp->rptr!=first)
{
prev=temp;
temp=temp->rptr;
}

prev->rptr=first;
first->lptr=prev;
free(temp);
}
else
{
free(temp);
first=NULL;
}
}
void delpos()
{
struct node *temp,*prev;
if(first==NULL)
{
printf("CIRCULARLY DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else
{
temp=first;
printf("Enter the KEY element which is to be deleted\n");
scanf("%d",&key);
while(temp->info!=key&&temp->rptr!=first)
{
prev=temp;
temp=temp->rptr;
}
if(temp->info==key&&temp->info==first->info)
delbeg();
else if(temp->info==key&&temp->rptr==first)
delend();

73
 else if(temp->info==key&&temp->rptr!=first)
{
prev->rptr=temp->rptr;
temp->rptr->lptr=prev;
free(temp);
}
else
{
printf("KEY ELEMENT NOT FOUND IN THE LIST\n");
return;
}
}
}
void display()
{
struct node *temp;
if(first==NULL)
{
printf("CIRCULARLY DOUBLY LINKED LIST IS EMPTY\n");
return;
}
else
{
temp=first;
do
{
printf("%d->",temp->info);
temp=temp->rptr;
}while(temp!=first);
}
}

/*OUTPUT*/

1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
1
Enter element to be inserted
3
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg

74
 5.delend
6.delpos
7.display
8.exit
Enter U'r choice
4
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
7
LIST IS EMPTY
1.Insertbeg
2.Insertend
3.Insertpos
4.delbeg
5.delend
6.delpos
7.display
8.exit
Enter U'r choice
8

75
/*C PROGRAM FOR IMPLEMENT ING THE STACK OPERATIONS ON A LINKED
LIST*/

#include<stdio.h>
#include<stdlib.h>
void push();
void pop();
void display();
int item;
struct node
{
int info;
struct node *link;
};
struct node* create(),*top=NULL,*first;
main()
{
int choice;
while(1)
{
printf("\n1.push operation\n");
printf("2.pop operation\n");
printf("3.display\n");
printf("4.exit\n");
printf("enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("invalid choice\n");
}
}
}
struct node *create()
{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
return new;
}

76
void push()
{
struct node *new,*temp;
new=create();
printf("enter element\n");
scanf("%d",&item);
if(top==NULL)
{
new->info=item;
new->link=NULL;
top=new;
first=new;
}
else
{
temp=first;
while(temp!=top)
{
temp=temp->link;
}
new->info=item;
new->link=NULL;
temp->link=new;
top=new;
}
}
void pop()
{
struct node *temp;
if(top==NULL)
{
printf("stack is empty\n");
return;
}
else
{
temp=first;
if(temp->link!=NULL)
{
while(temp->link!=top)
{
temp=temp->link;
}
temp->link=NULL;
free(top);
top=temp;
}
else
{
free(temp);

top=NULL;

77
 }
}
}

void display()
{
struct node *temp;
if(top==NULL)
{
printf("stack is empty\n");
return;
}
else
{
temp=first;
do
{
printf("%d->",temp->info);
temp=temp->link;
}while(temp!=NULL);
}
}

/*OUTPUT*/

1.push operation
2.pop operation
3.display
4.exit
enter the choice
1
enter element
55

1.push operation
2.pop operation
3.display
4.exit
enter the choice
1
enter element
56

1.push operation
2.pop operation
3.display
4.exit
enter the choice
3

78
55->56->
1.push operation
2.pop operation
3.display
4.exit
enter the choice
2

1.push operation
2.pop operation
3.display
4.exit
enter the choice
3
55->
1.push operation
2.pop operation
3.display
4.exit
enter the choice
4

79
/*C PROGRAM FOR IMPLEMENT ING THE QUEUE OPERATIONS ON A LINKED
LIST*/

#include<stdio.h>
#include<stdlib.h>
void insert();
void delete();
void display();
int item;
struct node
{
int info;
struct node *link;
};
struct node *create(),*top=NULL,*front,*rear;
main()
{
int choice;
while(1)
{
printf("\n1.insert operation\n");
printf("2.delete operation\n");
printf("3.display\n");
printf("4.exit\n");
printf("enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("invalid choice\n");
}
}
}
struct node *create()
{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
return new;
}

80
void insert()
{
struct node *new;
new=create();
printf("enter element\n");
scanf("%d",&item);
if(rear==NULL)
{
new->info=item;
new->link=NULL;
front=new;
rear=new;
}
else
{
new->info=item;
new->link=NULL;
rear->link=new;
rear=new;
}
}

void delete()
{
struct node *temp;
if(front==NULL)
{
printf("queue is empty\n");
return;
}
else
{
temp=front;
front=front->link;
free(temp);

}
}

void display()
{
struct node *temp;
if(front==NULL)
{
printf("stack is empty\n");
return;
}
else
{
temp=front;
do
{

81
 printf("%d->",temp->info);
temp=temp->link;
}while(temp!=NULL);
}
}

/*OUTPUT*/

1.insert operation
2.delete operation
3.display
4.exit
enter the choice
1
enter element
55
1.insert operation
2.delete operation
3.display
4.exit
enter the choice
1
enter element
56
1.insert operation
2.delete operation
3.display
4.exit
enter the choice
3
55->56->
1.insert operation
2.delete operation
3.display
4.exit
enter the choice
2
1.insert operation
2.delete operation
3.display
4.exit
enter the choice
3
56->
1.insert operation
2.delete operation
3.display
4.exit
enter the choice
4

82
/* C PROGRAM TO IMPLEMENT BINARY SEARCH TREE AND TREE TRVERSALS*/

#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int info;
struct tree *rchild,*lchild;
}node;
node *new1=NULL,*root=NULL;
node *create(node *);
node *insert(node *,int);
node *delete1(node *);
void traverse(node *);
void preorder(node *);
void postorder(node *);
void inorder(node *);
void main()
{
int ch,item;
system("clear");
while(1)
{
printf("\n1.CREATE TREE \n 2. INSERT \n 3. DELETE \n 4. TRAVERSE");
printf("\nenter your choice:");
scanf("%d", &ch);
switch(ch)
{
case 1:
root=create(root);
break;
case 2:
printf("Enter element :");
scanf("%d", &item);
root=insert(root,item);
break;
case 3:
root=delete1(root);
break;
case 4:
traverse(root);
break;
case 5:
exit(0);
break;
default:
printf("\n Enter correct choice:");
continue;
}
}
}
node *create(node *t)

83
{
int item;
while (1)
{
printf("Enter a element, enter -1 to exit:");
scanf("%d", &item);
if (item==-1)
{
return t;
break;
}
if (t==NULL)
{
new1=(node *) malloc(sizeof(node));
new1->info=item;
new1->lchild=NULL;
new1->rchild=NULL;
t=new1;
}
else
insert(t,item);
}
}

node *insert(node *t,int item)

{
node *temp=NULL,*ftemp=NULL;
new1=(node *)malloc(sizeof(node));
new1->lchild=NULL;
new1->rchild=NULL;
new1->info=item;
if (t==NULL)
{
t=new1;
return t;
}
temp=t;
while (temp!=NULL)
{
ftemp=temp;
if (temp->info > item)
temp=temp->lchild;
else
temp=temp->rchild;
}
if (ftemp->info >item)
ftemp->lchild=new1;
else
ftemp->rchild=new1;
return t;
}
void traverse(node *t)

84
{
int ch;
printf("\n1.PREORDER\n2.INORDER\n3.POSTORDER\n");
printf("Enter your choice:");
scanf("%d", &ch);
switch(ch)
{
case 1:
preorder(t);
break;
case 2:
inorder(t);
break;
case 3:
postorder(t);
break;
}
}
void preorder(node *t)
{
if (t!=NULL)
{
printf("%5d", t->info);
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(node *t)
{
if (t!=NULL)
{
inorder(t->lchild);
printf("%5d", t->info);
inorder(t->rchild);
}
}
void postorder(node *t)
{
if (t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%5d", t->info);

node *delete1(node *t)

{
node *p,*fp,*rp,*frp;
int item;

85
 p=fp=rp=frp=NULL;
printf("Enter element to delete;");
scanf("%d", &item);
p=t;
while (p->info != item && p!= NULL)
{
fp=p;
if (p->info > item)
p= p->lchild;
else
p=p->rchild;
}
if (p==NULL)
{
printf("\n Eleemtn doesnot exit\n");
return 0;
}
if (p->lchild==NULL)
frp=p->rchild;
else if (p->rchild==NULL)
frp=p->lchild;
else
{
rp=p->rchild;
while (rp->lchild!=NULL)
{
rp=rp->lchild;
}
rp->lchild=p->lchild;
frp=p->rchild;
}
if (fp==NULL)
{
return frp;
}
if (fp->lchild==p)
fp->lchild=frp;
else
fp->rchild=frp;
return t;
}

86
 /*OUTPUT*/

1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:1
Enter a element, enter -1 to exit:9
Enter a element, enter -1 to exit:6
Enter a element, enter -1 to exit:5
Enter a element, enter -1 to exit:3
Enter a element, enter -1 to exit:4
Enter a element, enter -1 to exit:1
Enter a element, enter -1 to exit:-1

1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:4

1.PREORDER
2.INORDER
3.POSTORDER
Enter your choice:1
9 6 5 3 1 4
1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:4

1.PREORDER
2.INORDER
3.POSTORDER
Enter your choice:2
1 3 4 5 6 9

1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:4

1.PREORDER
2.INORDER
3.POSTORDER

87
Enter your choice:3
1 4 3 5 6 9
1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:3
Enter element to delete;9

1.CREATE TREE
2. INSERT
3. DELETE
4. TRAVERSE
enter your choice:5

88