Data Structures Using C Practical File

Practical File For Data Structures In C Programming Language.
Arrays
Linked Lists
Stacks
Queues
Trees

1. DATA
STRUCTURES
USING C
(PRACTICAL
FILE)


MADE BY: SUBMITTED TO:
RAHUL CHUGH Ms.RACHNA MINOCHA
40/GDIT/JIMS/2016
BCA 4
th
Semester

2. PROGRAM TO PRINT 1D ARRAY




#include<stdio.h>
#include<conio.h>
void main()
{
int A[8]={1,2,6,4,88,55,43,21};
int i;
clrscr();
printf("The elements in the array Are :");
for(i=0;i<8;i++)
{
printf(" %d ",A[i]);
}
getch();
}

3. PROGRAM TO INSERT AN ELEMENT IN THE ARRAY AT A SPECIFIED POSITION


#include<stdio.h>
#include<conio.h>
void main()
{
int array[100], position, c, n, value;
clrscr();

printf("Enter number of elements in array \n");
scanf("%d", &n);

printf("Enter %d elements \n", n);

for (c = 0; c<n; c++)
scanf("%d", &array[c]);

printf("Enter the location where you wish to insert an element
\n");
scanf("%d", &position);

printf("Enter the value to insert \n");
scanf("%d", &value);

for (c = n - 1; c < position - 1; c--)
array[c+1] = array[c];

array[position-1] = value;

printf("Resultant array is: \n");

for (c = 0; c < n; c++)
printf("%d ", array[c]);


getch();
}

5. PROGRAM TO DELETE AN ELEMENT FROM THE ARRAY


#include <stdio.h>
#include<conio.h>
void main()
{
int array[100], position, c, n;
clrscr();
printf("Enter number of elements in array \n");
scanf("%d", &n);

printf("Enter %d elements \n", n);

for ( c = 0 ; c < n ; c++ )
scanf("%d", &array[c]);

printf("Enter the location where you wish to delete element \n");
scanf("%d", &position);

if ( position >= n+1 )
printf("Deletion not possible. \n");
else
{
for ( c = position - 1 ; c < n - 1 ; c++ )
array[c] = array[c+1];

printf("Resultant array is \n");

for( c = 0 ; c < n - 1 ; c++ )
printf("%d\n", array[c]);
}
getch();

}

7. LINEAR SEARCHING

#include <stdio.h>
#include<conio.h>
void main()
{
int array[100], search, c, n;
clrscr();
printf("Enter the number of elements in array \n");
scanf("%d", &n);

printf("Enter %d integer(s) \n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter a number to search \n");
scanf("%d", &search);

for (c = 0; c < n; c++)
{
if (array[c] == search) /* If required element is found */
{
printf("%d is present at location %d. \n", search, c+1);
break;
}
}
if (c == n)
printf("%d isn't present in the array. \n", search);

getch();
}

9. PROGRAM TO DISPLAY THE NUMBER OF OCCURENCES OF
AN ELEMENT IN AN ARRAY



#include<stdio.h>
#include<conio.h>
void main()
{
int array[100], search, c, n, count = 0;
clrscr();
printf("Enter the number of elements in array \n");
scanf("%d",&n);

printf("Enter %d numbers \n", n);

for ( c = 0 ; c < n ; c++ )
scanf("%d",&array[c]);

printf("Enter the number to search \n");
scanf("%d",&search);

for ( c = 0 ; c < n ; c++ )
{
if ( array[c] == search )
{
printf("%d is present at location %d. \n", search, c+1);
count++;
}
}
if ( count == 0 )
printf("%d is not present in array. \n", search);
else
printf("%d is present %d times in array. \n", search, count);

getch();
}

10. BUBBLE SORT

#include<conio.h>
#include<stdio.h>
void main()
{
int i,j,n,a[100],temp;
clrscr();
printf("Enter the number of digits = ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the number = ");
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
for(j=0;j<(n-i);j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("\tThe sorted Array Is:\n");
for(i=0;i<n;i++)
{
printf( "%d ",a[i]);

}
getch();
}

12. INSERTION SORT


#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],i,j,k,n;
clrscr();
printf("Enter the total numbers you have to enter = ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the number = ");
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
k=a[i];
for(j=i-1;j>=0 && k<a[j];j --)
{
a[j+1]=a[j];
}
a[j+1]=k;
}
printf("Sorted Array: \n");
for(i=0;i<n;i++)
{
printf("%d",a[i]);
printf("\n");
}
getch();
}

13. SELECTION SORT

#include<stdio.h>
#include<conio.h>

void main()
{
int a[100],n,i,j,min,temp;
clrscr();

printf("\n Enter the Number of Elements: ");
scanf("%d", &n);

printf("\n Enter %d Elements: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[min]>a[j])
min=j;
}
if(min!=i)
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}

printf("\n The Sorted array in ascending order: ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

getch();
}

15. MERGE SORT

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define n 10
int ar[n];
int temp[n];
void mergesort(int[],int,int);
void merge( int , int , int , int);
void main()
{
int l,h,i;
clrscr();
l=0;
h=n-1;
for(i=0;i<n;i++)
{
printf("Enter the Number = ");
scanf("%d",&ar[i]);
}
mergesort(ar,l,h);
printf("The sorted Array: \n");
for(i=0;i<n;i++)
{
printf("\t");
printf("%d",ar[i]);
printf("\n");
}
getch();
}
void mergesort(int ar[],int l, int h)
{
int m;
if(l<h)
{
m=(l+h)/2;
mergesort(ar,l,m);
mergesort(ar,m+1,h);
merge(l,m,m+1,h);
}
}
void merge(int p, int q , int r , int s )
{
int i,j,k;
i=p;
j=r;
k=p;
while(i<=q && j<=s)
{
if(ar[i]<ar[j])

16. {
temp[k]=ar[i];
i++;
k++;
}
else
{
temp[k]=ar[j];
j++;
k++;
}
}
while(i<=q)
{
temp[k]=ar[i];
i++;
k++;
}
while(j<=s)
{
temp[k]=ar[j];
k++;
j++;


}
for(i=0;i<=s;i++)
{
ar[i]=temp[i];
}
}

17. QUEUES


#include<stdio.h>
#include<conio.h>

#define MAX 50
int que_arr[MAX];
int rear=-1;
int front=-1;
void main()
{
int choice;
clrscr();
while(1)
{
printf("1.Insert element to queue \n");
printf("2. Delete element from queue \n");
printf("3. Display all elements of queue \n");
printf("4. Quit \n");

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

case 1: insert();
break;
case 2: del();
break;
case 3: display();
break;
case 4: exit(1);
default: printf("Wrong Choice \n");
}
}
}

insert()
{
int add_item;
if(rear == MAX-1)
printf("Queue Overflow \n");
else
{
if(front == -1)
front=0;
printf("insert the element in queue : ");
scanf("%d",&add_item);
rear=rear+1;

18. que_arr[rear]=add_item;
}
}

del()
{
if(front == -1 || front>rear)
{
printf("Queue Underlow \n");
return;
}
else
{
printf("Element deleted from queue is : %d \n",que_arr[front]);
front=front+1;
}
}

display()
{
int i;
if (front == -1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for(i=front; i<=rear; i++)
printf(" %d ",que_arr[i]);
printf("\n");
}
}

20. STACKS


#include<stdio.h>
#include<conio.h>
int s[10];
int top= -1;
void main()
{
int ch,el;
int ans;
void push(int);
int pop();
void display();
clrscr();
do
{
printf("MENU\n");
printf("press 1 for push \n");
printf("press 2 for pop\n");
printf("press 3 for display \n");
printf("enter your choice \n");
scanf("%d",&ch);
switch(ch)
{
case 1: if(top==9)
{
printf("stack overflow");
}
else
{
printf("enter the element to be pushed");
scanf("%d",&el);
push(el);
}
break;
case 2: if(top==-1)
{
printf("stack underflow");
}
else
{
printf("the deleted element is %d \n", pop());
}
break;
case 3: display();
break;
default: printf("wrong choice \n");
}
printf("\n do you want to continue : 5 for yes , 6 for no");
scanf("%d",&ans);

21. }
while(ans!=6);
getch();
}
void push(int x)
{
top=top+1;
s[top]=x;
}
int pop()
{
int y;
y=s[top];
top=top-1;
return y;
}
void display()
{
int i;
printf("elements in the stack are: \n");
for (i=0;i<=top;i++)
{
printf(" %d ",s[i]);
}
}

23. SINGLY LINKED LIST
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<process.h>
//Structure declaration for the node
struct node
{
int info;
struct node *link;
}*start;
//This function will create a new linked list
void Create_List(int data)
{
struct node *q,*tmp;
//Dynamic memory is been allocated for a node
tmp= (struct node*)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;
if(start==NULL) /*If list is empty*/
start=tmp;
else
{ /*Element inserted at the end*/
q=start;
while(q->link!=NULL)
q=q->link;

24. q->link=tmp;
}
}/*End of create_list()*/
//This function will add new element at the beginning of the linked
list
void AddAtBeg(int data)
{
struct node *tmp;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=start;
start=tmp;
}/*End of addatbeg()*/
//Following function will add new element at any position
void AddAfter(int data,int pos)
{
struct node *tmp,*q;
int i;
q=start;
//Finding the position to add new element to the linked list
for(i=0;i<pos-1;i++)
{
q=q->link;
if(q==NULL)
{
printf ("\n\n There are less than %d elements",pos);
getch();

25. return;
}
}/*End of for*/
tmp=(struct node*)malloc(sizeof (struct node));
tmp->link=q->link;
tmp->info=data;
q->link=tmp;
}/*End of addafter()*/
//Delete any element from the linked list
void Del(int data)
{
struct node *tmp,*q;
if (start->info == data)
{
tmp=start;
start=start->link; /*First element deleted*/
free(tmp);
return;
}
q=start;
while(q->link->link != NULL)
{
if(q->link->info == data) /*Element deleted in be tween*/
{
tmp=q->link;
q->link=tmp->link;
free(tmp);

26. return;
}
q=q->link;
}/*End of while */
if(q->link->info==data) /*Last element deleted*/
{
tmp=q->link;
free(tmp);
q->link=NULL;
return;
}
printf ("\n\nElement %d not found",data);
getch();
}/*End of del()*/
//This function will display all the element(s) in the linked list
void Display()
{
struct node *q;
if(start == NULL)
{
printf ("\n\nList is empty");
return;
}
q=start;
printf("\n\nList is : ");
while(q!=NULL)
{

27. printf ("%d ", q->info);
q=q->link;
}
printf ("\n");
getch();
}/*End of display() */
//Function to count the number of nodes in the linked list
void Count()
{
struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->link;
cnt++;
}
printf ("Number of elements are %d \n",cnt);
getch();
}/*End of count()*/

//Function to search an element from the linked list
void Search(int data)
{
struct node *ptr = start;
int pos = 1;
//searching for an element in the linked list
while(ptr!=NULL)

28. {
if (ptr->info==data)
{
printf ("\n\nItem %d found at position %d ", data, pos);
getch();
return;
}
ptr = ptr->link;
pos++;
}
if (ptr == NULL)
printf ("\n\nItem %d not found in list",data);
getch();
}
void main()
{
int choice,n,m,position,i;
start=NULL;
while(1)
{
clrscr();
printf ("1.Create List \n");
printf ("2.Add at beginning\n");
printf ("3.Add after \n");
printf ("4.Delete\n");
printf ("5.Display\n");
printf ("6.Count\n");

29. printf ("7.Search\n");
printf ("8.Quit\n");
printf ("\nEnter your choice:");
scanf ("%d",&choice);
switch (choice)
{
case 1:
printf ("\n\nHow many nodes you want:");
scanf ("%d",&n);
for(i = 0;i<n;i++)
{
printf ("\nEnter the element:");
scanf ("%d",&m);
Create_List(m);
}
break;
case 2:
printf ("\n\nEnter the element : ");
scanf ("%d",&m);
AddAtBeg(m);
break;
case 3:
printf ("\n\nEnter the element:");
scanf ("%d",&m);
printf ("\nEnter the position after which this element is inserted:");
scanf ("%d",&position);
AddAfter(m,position);

30. break;
case 4:
if (start == NULL)
{
printf("\n\nList is empty");
continue;
}
printf ("\n\nEnter the element for deletion:");
scanf ("%d",&m);
Del(m);
break;
case 5:
Display();
break;
case 6:
Count();
break;

case 7:
printf("\n\nEnter the element to be searched:");
scanf ("%d",&m);
Search(m);
break;
case 8:
exit(0);
default:
printf ("\n\nWrong choice");

31. }/*End of switch*/
}/*End of while*/
}/*End of main()*/

34. STACK IMPLEMENTATION USING LINKED LIST

#include<conio.h>
#include<stdio.h>
#include<malloc.h>
#include<process.h>
//Structure is created a node
struct node
{
int info;
struct node *link;//A link to the next node
};
//A variable named NODE is been defined for the structure
typedef struct node *NODE;
//This function is to perform the push operation
NODE push(NODE top)
{
NODE NewNode;
int pushed_item;
//A new node is created dynamically

NewNode = (NODE)malloc(sizeof(struct node));
printf("\nInput the new value to be pushed on the stack:");
scanf("%d",&pushed_item);
NewNode->info=pushed_item;//Data is pushed to the stack
NewNode->link=top;//Link pointer is set to the n ext node

35. top=NewNode;//Top pointer is set
return(top);
}/*End of push()*/
//Following function will implement the pop operation
NODE pop(NODE top)
{
NODE tmp;
if(top == NULL)//checking whether the stack is empty or not
printf ("\nStack is empty\n");
else
{
tmp=top;//popping the element
printf("\nPopped item is %d \n",tmp->info);
top=top->link;//resetting the top pointer
tmp->link=NULL;
free(tmp);//freeing the popped node
}
return(top);
}/*End of pop()*/
//This is to display the entire element in the stack
void display(NODE top)
{
if(top==NULL)
printf("\nStack is empty\n");
else
{
printf("\nStack elements:\n");

36. while(top != NULL)
{
printf("%d\n",top->info);
top = top->link;
}/*End of while */
}/*End of else*/
}/*End of display()*/
void main()
{
char opt;
int choice;
NODE Top=NULL;
do
{
clrscr();
printf("\n1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY\n");
printf("4.EXIT\n");
printf("\nEnter your choice:");
scanf("%d", &choice);
switch(choice)
{
case 1:
Top=push(Top);
break;
case 2:

37. Top=pop(Top);
break;
case 3:
display(Top);
break;
case 4:
exit(1);
default:
printf("\nWrong choice\n");
}/*End of switch*/
printf ("\n\nDo you want to continue (Y/y) = ");
fflush(stdin);
scanf("%c",&opt);
}while((opt == 'Y') || (opt == 'y'));
}/*End of main() */

39. QUEUE IMPLEMENTATION USING LINKED LIST

//THIS PROGRAM WILL IMPLEMENT ALL THE OPERATIONS
//OF THE QUEUE, IMPLEMENTED USING LINKED LIST

//CODED AND COMPILED IN TURBO C
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
//A structure is created for the node i n queue
struct queu
{
int info;
struct queu *next;//Next node address
};
typedef struct queu *NODE;
//This function will push an element into the queue
NODE push(NODE rear)
{
NODE NewNode;
//New node is created to push the data
NewNode=(NODE)malloc(sizeof( struct queu));
printf ("\nEnter the no to be pushed = ");
scanf ("%d",&NewNode->info);
NewNode->next=NULL;
//setting the rear pointer

40. if (rear != NULL)
rear->next=NewNode;
rear=NewNode;
return(rear);
}
//This function will pop the element from the queue
NODE pop(NODE f,NODE r)
{
//The Queue is empty when the front pointer is NULL
if(f==NULL)
printf ("\nThe Queue is empty");
else
{
printf ("\nThe poped element is = %d",f ->info);
if(f != r)
f=f->next;

else
f=NULL;
}
return(f);
}
//Function to display the e lement of the queue
void traverse(NODE fr,NODE re)
{
//The queue is empty when the front pointer is NULL
if (fr==NULL)

41. printf ("\nThe Queue is empty");
else
{
printf ("\nThe element(s) is/are = ");
while(fr != re)
{
printf("%d ",fr->info);
fr=fr->next;
};
printf ("%d ",fr->info);
}
}
void main()
{
int choice;
char option;
//declaring the front and rear pointer
NODE front, rear;
//Initializing the front and rear pointer to NULL
front = rear = NULL;
do
{
clrscr();
printf ("1. Push\n");
printf ("2. Pop\n");
printf ("3. Traverse\n");
printf ("\n\nEnter your choice = ");

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

case 1:
//calling the push function
rear = push(rear);
if (front==NULL)
{
front=rear;
}
break;
case 2:
//calling the pop function by passing
//front and rear pointers
front = pop(front,rear);
if (front == NULL)
rear = NULL;
break;
case 3:
traverse(front,rear);
break;
}
printf ("\n\nPress (Y/y) to continue = ");
fflush(stdin);
scanf ("%c",&option);
}while(option == 'Y' || option == 'y'); }

45. DOUBLY LINKED LIST

#include<conio.h>
#include<stdio.h>
#include<malloc.h>
#include<process.h>

//Structure is created for the node
struct node
{
struct node *prev;
int info;
struct node *next;
}*start;
typedef struct node *NODE;
//fucntion to create a doubly linked list
void create_list(int num)
{
NODE q,tmp;
//a new node is created
tmp=(NODE)malloc(sizeof(struct node));
tmp->info=num;//assigning the data to the new node
tmp->next=NULL;
if(start==NULL)
{
tmp->prev=NULL;

46. start->prev=tmp;
start=tmp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}/*End of create_list()*/
//Function to add new node at the beginning
void addatbeg(int num)
{
NODE tmp;
//a new node is created for inserting the data
tmp=(NODE)malloc(sizeof(struc t node));
tmp->prev=NULL;
tmp->info=num;
tmp->next=start;
start->prev=tmp;
start=tmp;
}/*End of addatbeg()*/
//This fucntion will insert a node in any specific position
void addafter(int num,int pos)
{

47. NODE tmp,q;
int i;
q=start;
//Finding the position to be inserted
for(i=0;i<pos-1;i++)
{
q=q->next;
if(q==NULL)
{
printf ("\nThere are less than %d elements \n",pos);
return;
}
}
//a new node is created
tmp=(NODE)malloc(sizeof(struct node) );
tmp->info=num;
q->next->prev=tmp;
tmp->next=q->next;
tmp->prev=q;
q->next=tmp;
}/*End of addafter() */
//Function to delete a node
void del(int num)
{
NODE tmp,q;
if(start->info==num)
{

48. tmp=start;
start=start->next; /*first element deleted*/
start->prev = NULL;
free(tmp);//Freeing the deleted node
return;
}
q=start;
while(q->next->next!=NULL)
{
if(q->next->info==num) /*Element deleted in between*/
{
tmp=q->next;
q->next=tmp->next;
tmp->next->prev=q;
free(tmp);
return;
}
q=q->next;
}
if (q->next->info==num) /*last element deleted*/
{ tmp=q->next;
free(tmp);
q->next=NULL;
return;
}
printf("\nElement %d not found\n",num);
}/*End of del()*/

49. //Displaying all data(s) in the node
void display()
{
NODE q;
if(start==NULL)
{
printf("\nList is empty\n");
return;
}
q=start;
printf("\nList is :\n");
while(q!=NULL)
{
printf("%d ", q->info);
q=q->next;
}
printf("\n");
}/*End of display() */
//Function to count the number of nodes in the linked list

void count()
{
NODE q=start;
int cnt=0;
while(q!=NULL)
{
q=q->next;

50. cnt++;
}
printf("\nNumber of elements are %d \n",cnt);
}/*End of count()*/
//Reversing the linked list

void main()
{
int choice,n,m,po,i;
start=NULL;
while(1)
{
//Menu options for the doubly linked list operation
clrscr();
printf("\n1.Create List\n");
printf("2.Add at begining \n");
printf("3.Add after\n");
printf("4.Delete\n");

printf("5.Display\n");
printf("6.Count\n");
printf("7.Exit\n");
printf("\nEnter your choice:");
scanf("%d",&choice);
//switch instruction is called to execute
//correspoding function
switch(choice)

51. {
case 1:
printf("\nHow many nodes you want:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter the element:");
scanf("%d",&m);
//create linked list function is called
create_list(m);
}
break;
case 2:
printf("\nEnter the element:");
scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("\nEnter the element:");
scanf("%d",&m);
printf("\nEnter the position after which this element is inserted:");
scanf("%d",&po);
addafter(m,po);
break;
case 4:
printf("\nEnter the element for deletion:");
scanf("%d",&m);

52. //Delete a node fucntion is called
del(m);
break;
case 5:
display();
getch();
break;
case 6:
count();
getch();
break;
case 7:
exit(0);
break;

default:
printf("\nWrong choice\n");
getch();
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

54. CIRCULAR LINKED LIST
#include<stdio.h>
#include<stdlib.h>

typedef struct Node

{
int info;
struct Node *next;
}node;

node *front=NULL,*rear=NULL,*temp;

void create();
void del();
void display();

int main()
{
int chc;
do
{
printf("\nMenu\n\t 1 to create the element : ");
printf("\n\t 2 to delete the element : ");
printf("\n\t 3 to display the queue : ");

55. printf("\n\t 4 to exit from main : ");
printf("\nEnter your choice : ");
scanf("%d",&chc);

switch(chc)
{
case 1:
create();
break;

case 2:
del();
break;

case 3:
display();
break;

case 4:
return 1;

default:
printf("\nInvalid choice :");
}
}while(1);

return 0;

56. }

void create()
{
node *newnode;
newnode=(node*)malloc(sizeof(node));
printf("\nEnter the node value : ");
scanf("%d",&newnode->info);
newnode->next=NULL;
if(rear==NULL)
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}

rear->next=front;
}

void del()
{
temp=front;
if(front==NULL)
printf("\nUnderflow :");
else
{

57. if(front==rear)
{
printf("\n%d",front->info);
front=rear=NULL;
}
else
{
printf("\n%d",front->info);
front=front->next;
rear->next=front;
}

temp->next=NULL;
free(temp);
}
}

void display()
{
temp=front;
if(front==NULL)
printf("\nEmpty");
else
{
printf("\n");
for(;temp!=rear;temp=temp ->next)

58. printf("\n%d address=%u next=%u\t",temp->info,temp,temp-
>next);
printf("\n%d address=%u next=%u\t",temp->info,temp,temp-
>next);
}
}

60. INFIX TO POSTFIX CONVERSION

#include<stdio.h>
#include<conio.h>
#include<string.h>
//Defining the maximum size of the stack
#define MAXSIZE 100
//Declaring the stack array and top variables in a structure
struct stack
{
char stack[MAXSIZE];
int Top;
};
//type definition allows the user to define an identifier that would
//represent an existing data type. The user -defined data type
identifier
//can later be used to declare variables.
typedef struct stack NODE;
//This function will add/insert an element to Top of the stack
void push(NODE *pu,char item)
{
//if the top pointer already reached the maximum allowed size then
//we can say that the stack is full or overflow
if (pu->Top == MAXSIZE-1)
{
printf("\nThe Stack Is Full");
getch();

61. }
//Otherwise an element can be added or inserted by
//incrementing the stack pointer Top as follows
else
pu->stack[++pu->Top]=item;
}
//This function will delete an element from the Top of the stack
char pop(NODE *po)
{
char item='#';
//If the Top pointer points to NULL, then the stack is empty
//That is NO element is there to delete or pop
if(po->Top == -1)
printf(" \nThe Stack Is Empty. Invalid Infix expression ");
//Otherwise the top most element in the stack is poped or
//deleted by decrementing the Top pointer
else
item=po->stack[po->Top--];
return(item);
}
//This function returns the precedence of the opera tor
int prec(char symbol)
{
switch(symbol)
{
case '(':
return(1);

62. case ')':
return(2);
case '+':
case '-':
return(3);
case '*':
case '/':
case '%':
return(4);
case '^':
return(5);
default:
return(0);
}
}
//This function will return the postfix expression of an infix
void Infix_Postfix(char infix[])
{
int i,j;
int len,priority;
char postfix[MAXSIZE],ch;
//Declaring an pointer variable to the structure
NODE *ps;
//Initializing the Top pointer to NULL
ps->Top=-1;
//Finding length of the string
len=strlen(infix);

63. //At the end of the string inputting a parenthesis ')'
infix[len++]=')';
push(ps,'(');//Parenthesis is pushed to the stack
for( i=0,j=0;i<len;i++)
{
switch(prec(infix[i]))
{
//Scanned char is '(' push to the stack
case 1:
push(ps,infix[i]);
break;
//Scanned char is ')' pop the operator(s) and add to //the postfix
expression
case 2:
ch=pop(ps);
while(ch != '(')
{
postfix[j++]=ch;
ch=pop(ps);
}
break;
//Scanned operator is +, - then pop the higher or same
//precedence operator to add postfi x before pushing
//the scanned operator to the stack
case 3:
ch=pop(ps);
while(prec(ch) >= 3)

64. {
postfix[j++]=ch;
ch=pop(ps);
}
push(ps,ch);
push(ps,infix[i]);
break;
//Scanned operator is *,/,% then pop the higher or
//same precedence operator to add postfix before
//pushing the scanned operator to the stack
case 4:
ch=pop(ps);
while(prec(ch) >= 4)
{
postfix[j++]=ch;
ch=pop(ps);
}
push(ps,ch);
push(ps,infix[i]);
break;
//Scanned operator is ^ then pop the same
//precedence operator to add to postfix be fore pushing
//the scanned operator to the stack
case 5:
ch=pop(ps);
while(prec(ch) == 5)
{

65. postfix[j++]=ch;
ch=pop(ps);
}
push(ps,ch);
push(ps,infix[i]);
break;
//Scanned char is a operand simply add to the postfix
//expression
default:
postfix[j++]=infix[i];
break;
}
}
//Printing the postfix notation to the screen
printf ("\nThe Postfix expression is = ");
for(i=0;i<j;i++)
printf ("%c",postfix[i]);
}
void main()
{
char choice,infix[MAXSIZE];
do
{
clrscr();
printf("\n\nEnter the infix expression = ");
fflush(stdin);
gets(infix);//Inputting the infix notation

66. Infix_Postfix(infix);//Calling the infix to postfix function
printf("\n\nDo you want to continue (Y/y) =");
fflush(stdin);
scanf("%c",&choice);
}while(choice == 'Y' || choice == 'y');
}

67. EVALUATION OF POSTFIX EXPRESSION
#include<stdio.h> //standard input output functions
#include<conio.h> //console functions
#include<string.h> //string functions
#define MAX 50 //max size defined
int stack[MAX]; //a global stack
char post[MAX]; //a global postfix stack
int top=-1; //initializing top to -1
void pushstack(int tmp); //push function
void evaluate(char c); //calculate function
void main()
{
int i,l;
//clrscr();
printf("Insert a postfix notation :: ");
gets(post); //getting a postfix expression
l=strlen(post); //string length
for(i=0;i<l;i++)
{
if(post[i]>='0' && post[i]<='9')
{
pushstack(i); //if the element is a number push
it
}
if(post[i]=='+' || post[i]==' -' || post[i]=='*' ||
post[i]=='/' || post[i]=='^') //if element is an operator
{

68. evaluate(post[i]); //pass it to the evaluate
}
} //print the result from the top
printf("\n\nResult :: %d",stack[top]);
getch();
}

void pushstack(int tmp) //definiton for push
{
top++; //increment ing top
stack[top]=(int)(post[tmp] -48); //type casting the string to its
integer value
}

void evaluate(char c) //evaluate function
{
int a,b,ans; //variables used
a=stack[top]; //a takes the value stored in the top
stack[top]='\0'; //make the stack top NULL as its a string
top--; //decrement top's value
b=stack[top]; //put the value at new top to b
stack[top]='\0'; //make it NULL
top--; //decrement top
switch(c) //check operator been passed to evaluate
{
case '+': //addition
ans=b+a;

69. break;
case '-': //subtraction
ans=b-a;
break;
case '*': //multiplication
ans=b*a;
break;
case '/': //division
ans=b/a;
break;
case '^': //power
ans=b^a;
break;
default:
ans=0; //else 0
}
top++; //incremen t top
stack[top]=ans; //store the answer at top
}

71. BINARY SEARCH TREE
/*
* C Program to Construct a Binary Search Tree and perform deletion,
inorder traversal on it
*/
#include <stdio.h>
#include <stdlib.h>

struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;

void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct bt node *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);

72. int flag = 1;

void main()
{
int ch;

printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");
printf("2 - Delete an element from the tree \n");
printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);

73. break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}

/* To insert a node in the tree */
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}

/* To create a node */

74. void create()
{
int data;

printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}

/* Function to search the appropriate position to insert the new node
*/
void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more
than root node value insert at right */
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value
less than root node value insert at left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}

/* recursive function to perform inorder traversal of tree */

75. void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}

/* To check for the deleted node */
void delete()
{
int data;

if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;

76. t2 = root;
search1(root, data);
}

/* To find the preorder traversal */
void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
printf("%d -> ", t->value);
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}

/* To find the postorder traversal */
void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}

77. if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
printf("%d -> ", t->value);
}

/* Search for the appropriate position to insert the new node */
void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}

/* To delete a node */

78. void delete1(struct btnode *t)
{
int k;

/* To delete leaf node */
if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}

/* To delete node having one left hand child */
else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;

79. }
else if (t1->l == t)
{
t1->l = t->l;

}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}

/* To delete node having right hand child */
else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;

80. t = NULL;
free(t);
return;
}

/* To delete node having two child */
else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}

}

/* To find the smallest element in the right sub tree */
int smallest(struct btnode *t)

81. {
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}

/* To find the largest element in the left sub tree */
int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}