COMM-IT CAREER academy

(Affiliated GGSIP University)

FC-1 Sheikh Sarai,
Chirag Delhi – 110017.

Practical file
on
Data structure & algorithm
(BCA 174)

SUBMITTED BY submitted to
LAgneshwar.s ms. juveria mam Enroll no.
112002021 (ASSISTANT PROFESSOR )
 INDEX
1. Write a program to calculate factorial of a number
using functions.
2. Write a program to input an array of ten elements &
prints that array.
3. Write a program to read two matrices and then print
a matrix which is addition of these two matrices.
4. Write a program which reads two matrices and
multiply them.
5. Write a program to display a square matrix.
6. Write a program to find transpose of a matrix.
7. Write a program to read and write array elements
and find the sum of even and odd elements.
8. Write a program to insert an element in array.
9. Write a program to delete an element in an array.
10. Write a program to traverse an array.
11. Write a program to initialize and display array
elements using pointers.
12. Write a program to display the contents of a 2 D
array using pointer.
13. Write a program to accept a matrix from user and
find out matrix is sparse or not.
14. Write a program to sort elements of an array using
bubble sort.
15. Write a program to sort elements of an array using
selection sort.
16. Write a program to sort elements of an array using
insertion sort.
17. Write a program to sort elements of an array using
merge sort.
18. Write a program to search an element using linear
search.
19. Write a program to search an element using binary
search.
20. Write a program to implement singly linked list.
21. Write a program to implement doubly linked list.
22. Write a program to implement header linked list.
23. Write a program to demonstrate the operations
performed on stack.
24. Write a program to demonstrate the linked list
implementation of stack.
25. Write a program to convert infix expression to
postfix form.
26. Write a program to implement queue using array.
27. Write a program to illustrate the working of a
queue when implemented using pointers.
28. Write a program n to implement circular queue
using array.
29. Write a program to implement binary tree
traversals: Inorder, Preorder, Postorder.
30. Write a program to perform insertion, deletion and
traversal in Binary Search tree.
 Answers of questions

Q1. Write a program to calculate factorial of a number

using functions?
#include<stdio.h>
#include<math.h>
int main()

{
    printf("Enter a Number to Find Factorial: ");
    printf("\nFactorial of a Given Number is: %d ",fact());
    return 0;
}
int fact()
{
    int i,fact=1,n;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        fact=fact*i;
    }
    return fact;
}

Q2. Write a program to input an array of ten elements &

prints that array?
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
 for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}

Q3. Write a program to read two matrices and then print

a matrix which is addition of these two matrices?
#include <stdio.h>
int main()
{
int m, n, c, d, first[10][10], second[10][10], sum[10][10];
printf("Enter the number of rows and columns of matrix\n");
scanf("%d%d", &m, &n);
printf("Enter the elements of first matrix\n");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++)
scanf("%d", &first[c][d]);
printf("Enter the elements of second matrix\n");
for (c = 0; c < m; c++)
for (d = 0 ; d < n; d++)
scanf("%d", &second[c][d]);
printf("Sum of entered matrices:-\n");
for (c = 0; c < m; c++) {
for (d = 0 ; d < n; d++) {
sum[c][d] = first[c][d] + second[c][d];
printf("%d\t", sum[c][d]);
}
printf("\n");
}
return 0;
}

Q4. Write a program which reads two matrices and

multiply them?
#include <stdio.h>
int main()
{
int m, n, p, q, c, d, k, sum = 0;
int first[10][10], second[10][10], multiply[10][10];

printf("Enter the number of rows and columns of first matrix\n");

scanf("%d%d", &m, &n);
printf("Enter the elements of first matrix\n");

for ( c = 0 ; c < m ; c++ )

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

printf("Enter the number of rows and columns of second matrix\n");

scanf("%d%d", &p, &q);

if ( n != p )
printf("Matrices with entered orders can't be multiplied with each
other.\n");
else
{
printf("Enter the elements of second matrix\n");

for ( c = 0 ; c < p ; c++ )

for ( d = 0 ; d < q ; d++ )
scanf("%d", &second[c][d]);
 for ( c = 0 ; c < m ; c++ )
{
for ( d = 0 ; d < q ; d++ )
{
for ( k = 0 ; k < p ; k++ )
{
sum = sum + first[c][k]*second[k][d];
}

multiply[c][d] = sum;
sum = 0;
}
}

printf("Product of entered matrices:-\n");

for ( c = 0 ; c < m ; c++ )

{
for ( d = 0 ; d < q ; d++ )
printf("%d\t", multiply[c][d]);

printf("\n");
}
}

return 0;
}

Q5. Write a program to display a square matrix?

#include<stdio.h>
Void main()
{
Int a[10][10];
Clrscr();
Int n,I,j;
Printf(“Enter order of matrix”);
Scanf(“%d”,&n);
Printf(“Enter matrix elements”);
For (i=0;i<n;i++)
For (j=0;j<n;j++)
Scanf(“%d”,&a[i][j]);
Printf(“Matrix A is :\n”);
For (i=0;i<n;i++)
{
For (j=0;j<n;j++)
Printf(“%d”,a[i][j]);
}
}

Q6. Write a program to find transpose of a matrix?

#include <stdio.h>
int main() {
int a[10][10], transpose[10][10], r, c;
printf("Enter rows and columns: ");
scanf("%d %d", &r, &c);
// asssigning elements to the matrix
printf("\nEnter matrix elements:\n");
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
printf("Enter element a%d%d: ", i + 1, j + 1);
scanf("%d", &a[i][j]);
}
// printing the matrix a[][]
printf("\nEntered matrix: \n");
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
printf("%d ", a[i][j]);
if (j == c - 1)
printf("\n");
}
// computing the transpose
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
transpose[j][i] = a[i][j];
}
// printing the transpose
printf("\nTranspose of the matrix:\n");
for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j) {
printf("%d ", transpose[i][j]);
if (j == r - 1)
printf("\n");
}
 return 0;
}

Q7. Write a program to read and write array elements

and find the sum of even and odd elements?
int main()
{
int Size, i, a[10];
int Even_Sum = 0, Odd_Sum = 0;
printf("\n Please Enter the Size of an Array : ");
scanf("%d", &Size);
printf("\nPlease Enter the Array Elements\n");
for(i = 0; i < Size; i++)
{
scanf("%d", &a[i]);
}
for(i = 0; i < Size; i ++)
{
if(a[i] % 2 == 0)
{
Even_Sum = Even_Sum + a[i];
}
else
{
Odd_Sum = Odd_Sum + a[i];
}
}
printf("\n The Sum of Even Numbers in this Array = %d ",
Even_Sum);
printf("\n The Sum of Odd Numbers in this Array = %d ",
Odd_Sum);
return 0;
}
Q8. Write a program to insert an element in array?
include <stdio.h>
int main()
{
int arr[100] = { 0 };
int i, x, pos, n = 10;
// initial array of size 10
for (i = 0; i < 10; i++)
arr[i] = i + 1;
// print the original array
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// element to be inserted
x = 50;
// position at which element
// is to be inserted
pos = 5;
 // increase the size by 1
n++;
// shift elements forward
for (i = n-1; i >= pos; i--)
arr[i] = arr[i - 1];
// insert x at pos
arr[pos - 1] = x;
// print the updated array
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}

Q9. Write a program to delete an element in an array?

#include<stdio.h>
#include<conio.h>
Int i, len, pos, num;
Main();
{
Int a[100]; void insert(int a[],int,int,int);
Clrscr();
Printf(“Enter integers to be read”);
Scanf(“%d”,&len);
Printf(“Enter integers”);
For(i=0;i<=len-1;i++)
{
Scanf(“%d”,&a[i]);
}
Printf(“Enter integer to be inserted”);
Scanf(“%d”,&num);
Printf(“Enter position in the array for insertion”);
Scanf(“%d”,&pos);
--pos;
Insert(a,len,pos,num);
}
Void insert(int a[],. Int len, int pos, int num)
{
For(i=len; i>=pos;i--)
{
a[i+1]=a[i];
}
a[pos]=num;
if(pos>len)
{
Printf(“insertion outside the array”);
}
Len++;
Printf(“New array”)
;
For(i=0;i<len;i++)
{
Printf(“%d\n”, a[i]);
}
}
Q10. Write a program to traverse an array?
#include <stdio.h>
// Function to traverse and print the array
void printArray(int* arr, int n)
{
int i;
printf("Array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program
int main()
{
int arr[] = { 2, -1, 5, 6, 0, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
printArray(arr, n);
return 0;
}

Q11. Write a program to initialize and display array

elements using pointers?
#include<stdio.h>
main()
{
int a[5]={5,4,6,8,9};
printf("Array elements with pointers\n");
int *p=&a[0];
int i;
for(i=0;i<5;i++)
printf("%d\n",*(p+i));
}
Q12. Write a program to display the contents of a 2 D
array using pointer?

#include <stdio.h>
void main(){
int a[3][4]={{1, 2, 3, 4},{5,6,7,8},{9,10,11,12}};
int *ptr=&a[0][0];
int rows=3;
int col=4;
int total_cells= rows*col,i;

for(i = 0; i < total_cells; i++){

printf("%d\t",*(ptr+i));
}
}

Q13. Write a program to accept a matrix from user and

find out matrix is sparse or not?
#include <stdio.h>
int main()
{
int a[100], n, i, j, position, swap;
printf("Enter number of elements");
scanf("%d", &n);
printf("Enter %d Numbers", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for(i = 0; i < n - 1; i++)
{
position=i;
for(j = i + 1; j < n; j++)
{
if(a[position] > a[j])
position=j;
}
if(position != i)
{
swap=a[i];
a[i]=a[position];
a[position]=swap;
}
}
printf("Sorted Array:");
for(i = 0; i < n; i++)
printf("%d", a[i]);
return 0;
}

Q14. Write a program to sort elements of an array using

bubble sort?
#include<stdio.h>
void main()
{
Int a[100], n, i;
Printf(“How many elements in array”);
Scanf(“%d”,&n);
For(i=0; i<=n; i++);
{
Scanf(“%d”,& a[i]);
}
Bubble-sort(a,n);
Printf(“sorted line is as follows”);
For(i=0; i<n; i++)
Printf(“%d”, a[i]);
}
Void bubble-sort (int a[], int n)
{
Int temp, i,j;
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;
}
}
}
}
Q15. Write a program to sort elements of an array using
selection sort?
#include<stdio.h>
Void main()
{
Int a[], n,i:
Printf(“how many elements”);
Scanf(“%d”,&n);
For (i=0; i<n;i++)
{
Scanf(“%d”,&a[i]);
}
Selection-sort(a,n);
For (i=0; i<n;i++)
Printf(“sorted array in :”);
For (i=0; i<=n;i++)
{
printf(“%d”,a[i]);
}
}
Void selection-sort(int a[ ], int n)
{
Int min , temp, loc, I, j;
Min=a[0];
Loc=I;
For (j=i+1; j<=n-1;j++)
{
If (a[j]<min)
{
Min a[j];
Loc=j;
}
}
If(loc !=i)
{
temp= a[i];
a[i]=a[loc];
a[loc]=temp;
}
}
}

Q16. Write a program to sort elements of an array using

insertion sort?
#included <stdio.h>
void main()
{
int a[100],n,k,I,j,temp;
clrscr();
printf(“how many elements ”);
scanf(“%d”,&n);
printf(“Enter the element of array”);
for(i=0;i<=n-1;i++)
{
scanf(“%d”,&a[i]);
}
for(k=1;k<=n-1;k++)
{
temp=a[k];
J=k-1;
while ((temp<a[j]) &&(j>=0))
{
a[j+1]=temp;
}
printf(“Elements of array after sorting are :\n”);
for(i=0;i<n;i++)
{
printf(“%d”,a[i]);
}
getch();
}

Q17. Write a program to sort elements of an array using

merge sort?
#include<stdio.h>
#include<conio.h>
#define MAX 10
void merge(int *arr, int *temp, int low, int mid, int high);
void m_sort(int *arr, int *temp, int low, int high)
{
int mid;
if(high>low)
{
mid=(low+high)/2;
m_sort(arr, temp, low, mid);
m_sort(arr, temp, mid+1, high);
merger(arr, temp, low, mid+1, high);
}
}
void merge(int *arr, int *temp, int low, int mid, int high)
{
int I, end, num, pos;
end=mid-1;
pos=low;
num=high-low+1;
while((low<=end)&&(mid<=high))
{
if(arr[low]<=arr[mid])
{
temp[pos]=arr[low];
pos=pos+1;
mid=mid+1;
}
}
while(low<=end)
{
temp[pos]=arr[low];
low=low+1;
pos=pos+1;
}
while(mid<=high)
{
temp[pos]=arr[mid];
mid=mid+1;
pos=pos+1;
}
for(i=0;i<num;i++)
{
arr[high]=temp[high];
high=high-1;
}
}
void main()
{
int num, arr[MAX],temp[MAX],i;
clrscr();
printf(“\nEnter the number of elements :”);
scanf(“%d”,&num);
if(num>MAX)
printf(“\nArray out of bound!”);
else
{
for(i=0;i<num;i++)
scanf(“%d”,&arr[i]);
m_sort(arr, temp,0,num);
printf(“\nThe list after sorting is:”);
for(i=0;i<num;i++)
printf(“%d”,arr[i]);
}
getch();
}

Q18. Write a program to search an element using linear

search?
#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,item,loc=-1;
clrscr();
printf(“\nEnter the number of element :”);
scanf(“%d”,&n);
printf(“Enter the numbers:\n”);
for(i=0;i<=n-1;i++)
{
scanf(“%d”,&a[i]);
}
printf(“\nEnter the no. to be searched:”);
scanf(“%d”,&item);
for(i=0;i<=n-1;i++)
{
if(item==a[i])
{
loc=i;
break;
}
}
if(loc>=0)
printf(“\n%d is found in position %d”, item,loc+1);
else
printf(“\nItem does not exist”);
getch();
}

Q19. Write a program to search an element using binary

search?
#include<stdio.h>
#include<conio.h>
void main()
{
int a[100], i, loc, mid, beg, end, n, flag=0, item;
clrscr();
printf(“How many elements”);
scanf(“%d”,&n);
printf(“Enter the element of the array\n”);
for(i=0;i<=n-1;i++)
{
scanf(“%d”, &a[i]);
}
printf(“Enter the element to be search\n”);
scanf(“%d”,&item);
loc=0;
beg=0;
end=n-1;
while((beg<=end)&&(item!=a[mid]))
{
mid=((beg+end)/2);
if(item==a[mid])
{
printf(“search is successful\n”);
loc=mid;
printf(“Position of the item %d\n”, loc+1);
flag=flag+1;
}
else if(item<a[mid])
end=mid-1;
else
beg=mid+1;
}
if(flag==0)
{
printf(“search is not successful\n”);
}
getch();
}
Q20. Write a program to implement singly linked list?
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
Struct node
{
Int info;
Struct node *next;
};
Typedef struct node NODE;
NODE *start;
Void createemptylist(NODE *start)
{
*start NULL;
}
Void traverse (NODE*P)
{
While(P!=NULL)
{
Printf(“%d\n”, P->num);
P=P->next;
}
}
Void insertatbegin (int item)
{
NODE *P, *loc;
P=(NODE*)malloc (sizeof(NODE));
F= num=item;
P->next=NULL;
If (start==NULL)
Start=p;
Else
{
loc = start;
while (loc-> next !=NULL)
loc =loc ->next;
loc->next=ptr;
}
}
Void dele_beg(void)
{
NODE *P;
If(start==NULL)
Printf(“list is empty”);
Else
{
P=start;
Start=start-> next;
Printf(“no deleted is=%d”,P->num);
Free(P);
}
}
Void dele_end()
{
NODE *P, *loc;
If (start==NULL)
{
Printf(“list is empty”);
}
Else
If ((start)->next==NULL)
{
P=start;
Start = NULL;
Printf(“no deleted is ‘%d”,p->num);
Free(P);
}
Else{
Loc =start;
P=start->next;
While(P->next=NULL)
{ _loc=p;
P=P->next;
}
Loc->next=NULL;
Printf(“no deleted is =%d”,P->num);
Free(P);
}
}
Void insert_spe (NODE *start, int item)
{
NODE *P, *loc;
Int item , k;
For(k=o;loc=start;k<temp;k++)
{
Loc =loc->next;
If (loc==NULL)
{
Printf(“node in the list at less than one\n”);
Return;
}
}
P=(NODE*)malloc(sizeof(NODE));
P->num=item;
P->next=loc->next;
Loc->next=P;
}
dele_spe()
{
Node *P, *temp;
Int I,loc;
Printf(“enter the position to delete\n”);
Scanf(“%d”,&loc);
If (start==NULL)
{
Printf(“empty list”);
}
Else
{
Ptr=start;
for(i=1;i<=loc;i++)
{
Temp=ptr;
Ptr=ptr-> next;
}
Printf(“no deleted is=%d”,ptr->num);
Temp-> next=ptr->next;
Free(ptr);
}
}
Void main()
{
Int choice, item, after;
Char ch;
Clrscr();
Createemptylist(start);
Do
{
Printf(“1.Insert element at begin\n”);
Printf(“2.Insert element at end position\n”);
Printf(“3.Insert specific the position\n”);
Printf(“4.traverse the list in order \n”);
Printf(“5.Delete from the begin\n”);
Printf(“6.Delete from the last \n”);
Printf(“7. Delete the element from the specific\n”);
Printf(“8. Exit\n”);

Printf(“1.Enter your choice \n”);

Scanf(“%d”,&choice);
Switch(choice)
{
Case 1: printf(“Enter the item\n”);
Scanf(“%d”,&item);
Break;

Case 2: printf(“Enter the item\n”);

Scanf(“%d”,&item);
Insert_at_end(item);
Break;

Case 3: printf(“Enter the item\n”);

Scanf(“%d”,&item);
Insert_spe (start, item)
Break;

Case 4: printf(“inverse the list\n”);

Traverse(start);
Break;

Case 5: printf(“delete the item\n”);

Dele_beg();
Break;

Case 6: printf(“Delete the item\n”);

Dele_end(start);
Break;

Case 7: printf(“delete the item\n”);

Dele_spe(start);
Break;

Case 8: exit(0);
}
}
While (choice!=8);
Getch();
}
Q21. Write a program to implement doubly linked list?

Q22. Write a program to implement header linked list?

#include<stdio.h>
#include<stdlib.h>

int count=0;

struct node
{
int data;
struct node* next;
}*start,*header;

void print()
{
struct node *p=start;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}

void insert_at_front(int node_data)

{
struct node *p;
p=(struct node *)malloc(sizeof (struct node));
p->data=node_data;
p->next=header->next;
start=p;
header->next=start;
count++;
header->data=count;
 printf("after inserting at the front=\n");
print();
}

void insert_at_end(int node_data)

{
struct node *p=start,*q;
q=(struct node *)malloc(sizeof (struct node));
q->data=node_data;
q->next=NULL;
int temp=header->data;
while(temp>1)
{
p=p->next;
temp--;
}
p->next=q;
count++;
header->data=count;
printf("after inserting at the end=\n");
print();
}

void insert_after(int pos,int node_data)

{
if(pos>header->data)
printf("we can not found the position\n");
else{
struct node *p,*q=start;
p=(struct node *)malloc(sizeof (struct node));
p->data=node_data;
p->next=NULL;
while(pos>1)
{
q=q->next;
pos--;
}
 p->next=q->next;
q->next=p;
count++;
header->data=count;
}
printf("after inserting after given position=\n");
print();
}
int main()
{
header=(struct node *)malloc(sizeof (struct node));
start=(struct node *)malloc(sizeof (struct node));
header->data=count;
header->next=NULL;
insert_at_front(3);
insert_at_front(4);
insert_at_end(5);
insert_at_end(8);
insert_after(2,7);
return 0;
}

Q23. Write a program to demonstrate the operations

performed on stack?
#include<process.h>
#include<stdio.h>
void push();
int pop();
void traverse();
int stack[5];
int pop=-1;
void main()
{
int choice;
char ch;
do
{
clrscr();
printf(“\n1.PUSH”);
printf(“\n2.POP”);
printf(“\n3.TRAVERSE”);
printf(“\n4.EXIT”);
printf(“\nEnter your choice”);
scanf(“%d”, &choice);
switch(choice)
{
Case 1: push();
break;
case 2: printf(“\n The deleted element is %d”, pop());
break;
case 3: traverse();
break;
case 4: exit(0);
}
}
while(choice!=4);
}
void push()
{
int item;
if(top==4)
printf(“\n The stack is full”);
else
{
printf(“Enter the element to be inserted”);
scanf(“%d”, &item);
top=top+1;
stack[Top]=item;
}
}
int pop()
{
int item;
if(top==-1)
printf(“The stack is Empty”);
else
{
item=stack[top];
top=top-1;
}
return(item);
}
void traverse()
{
int i;
if(top==-1)
printf(“The stack is empty”);
else
{
for(i=top;i>=0;i--)
{
printf(“\n %d”,stack[i]);
}
}
}

Q24. Write a program to demonstrate the linked list

implementation of stack?
#include<process.h>
#include<stdio.h>
struct stack
{
int no;
struct stack *next;
}
*top=NULL;
typedef struct stack st;
void push();
int pop();
void display();
void main()
{
char ch;
int choice, item;
do
{
clrscr();
printf(“\n1 : push”);
printf(“\n2 :pop”);
printf(“\n3 :display”);
printf(“\n4 :exit”);
printf(“\n Enter your choice”);
scanf(“%d”, &choice);
switch(choice)
{
case 1 : push();
break;
case 2 : item=pop();
printf(“The deleted element is %d”, item);
break;
case 3 :display();
break;
case 4 : exit(0);
}
}
while(choice!=4);
}
void push()
{
st*P;
P=(st*) malloc(sizeof(st));
printf(“\n Enter the number”);
scanf(“%d”, &P->no);
P->next=top;
top=P;
int pop()
{
st*P;
P=start;
if(top==NULL)
printf(“stack is already empty”);
else
{
top=top->next;
return(P->no);
free(P);
}
}
void display()
{
st*P;
P=top;
while(P!=NULL)
{
printf(“\n no=%d”, P-> no);
P=P->next;
}
printf(“\n no =%d”, P->no);
}
Q25. Write a program to convert infix expression to
postfix form?
#include<stdio.h>
#include<string.h>
char stack[50];
int top=-1;
void in_to_post(char infix[]);
void push(char);
char pop();
void main()
{
char infix[25];
printf(“Enter the infix expression”);
gets(infix);
in_to_post(infix);
getch();
}
void push(char symb)
{
if(top>=49)
{
printf(“stack overflow”);
getch();
return;
}
else
{
top=top+1;
stack[top]= symb;
}
}
char pop()
{
char item;
if(top==-1)
{
printf(“stack empty”);
getch();
return(0);
}
else
{
item=stack[top];
top--;
}
return(item);
}
int preced(char ch)
{
if (ch==47)
{
return(5);
}
else
if(ch=42)
{
return(4);
}
else if(ch=43)
{
return(3);
}
else
return(2);
}
void in_to_post(char infix[])
{
int length;
static int index=0,pos=0;
char symbol, temp;
char postfix[40];
length=strlen(infix);
push(‘#’);
while(index<length)
{
symbol=infix[index];
switch(symbol)
{
case’(‘ : push(symbol));
break;
case’)’ : temp=pop();
while(temp!=’(‘))
{
postfix[pos]=temp;
pos++;
temp=pop();
}
break;
case’+’:
case’-‘:
case’*’:
case’/’:
case’^’:
while(preced(stack[top])>=preced(symbol))
{
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default : postfix[pos++] = symbol;
break;
}
index++;
}
while(top>0)
{
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]=’\0’;
puts(postfix);
return;
}
Q26. Write a program to implement queue using array?
#include<process.h>
#include<stdio.h>
int queue[5];
long front, rear;
void main()
{
int choice, info;
clrscr();
initqueue();
do
{
clrscr();
printf(“ MENU \n”);
printf(“1. Insert an element in queue\n”);
printf(“2. Delete an element from queue\n”);
printf(“3. Display the queue\n”);
printf(“4. Exit!\n”);
printf(“ Your choice :”);
scanf(choice)
{
Case 1 : if(rear<4)
{
printf(“enter the number”);
scanf(“%d”, &info);
if(front==-1)
{
front=0;
rear=0;
}
else
rear=rear+1;
queue[rear]=info;
}
else
printf(“queue is full”);
getch();
break;
case 2 : int info;
if(front!=-1)
{
info=queue[front];
if(front==rear)
{
front=-1
rear=-1;
}
else
front=front+1;
printf(“no deleted is =%d”,info);
}
else
printf(“queue is empty”);
getch();
break;
case 3 :display();
getch();
break;
case 4 : exit(0);
default: printf(“You entered wrong choice!”);
}
}
while(choice!=4);
}
void initqueue()
{
front=rear=-1;
}
void display()
{
int i;
for(i=front; i<=rear; i++)
printf(“%i\n”,queue[i]);
}
Q27. Write a program to illustrate the working of a queue
when implemented using pointers?
#include<stdio.h>
#include<stdlib.h>
#define max 10
int insertq ( int queue[max], int *rear , int *data)
{
      if ( *rear == max -1 )
            return(-1);
      else
      {
            *rear = *rear + 1;
            queue[*rear] = *data;
            return(1);
      }
}
int delq( int queue[max], int *front, int *rear , int *data)
{
      if ( *front == *rear)
            return(-1);
      else
      {
            (*front)++;
            *data = queue[*front];
            return(1);
      }
}
int main()
{
      int queue[max],data;
      int front,rear,reply,option;
      //... init queue
      front = rear = -1;
      printf("\tMenu");
      printf("\n----------------------------");
      printf("\n 1. Insert element in queue");
      printf("\n 2. Delete element from queue");
      printf("\n 3. Exit");
      printf("\n----------------------------");
      while(1)
      {
            printf("\nChoose operation : ");
            scanf("%d",&option);
            switch(option)
            {
                  case 1 ://insert
                        printf("\nEnter Number : ");
                        scanf("%d",&data);
                        reply = insertq(queue,&rear,&data);
                        if ( reply == - 1)
                              printf("Queue is full");
                        else
                              printf("%d is inserted in queue.\n",data);
                        break;
                  case 2 : //dele
                        reply = delq(queue,&front,&rear,&data);
                        if ( reply == -1 )
                              printf("Queue is empty ");
                        else
                              printf("\nDeleted number is : %d\n", data);
                              break;
                        case 3 : exit(0);
            }
      }
}

Q28. Write a program to implement circular queue using

array?
#include<process.h>
#include<stdio.h>
#define MAXSIZE 5
int cq[10];
int front=-1, rear=-1;
int choice;
char ch;
void main()
{
do
{
clrscr();
printf(“----1. Insert----\n”);
printf(“----2. Delete----\n”);
printf(“----3. Display----\n”);
printf(“----4. Exit----\n”);
printf(“Enter your choice\n”);
scanf(“%d”, &choice);
switch(choice)
{
Case 1: cqinsert();
break;
case 2: cqdelete();
getch();
break;
case 3: cqdisplay();
getch();
break;
case 4: Exit(0);
}
}
while(choice!=4);
}
cqinsert()
{
int num;
if (front==(rear+1)% MAXSIZE)
{
printf(“queue is full\n”);
return;
}
else
{
printf(“Enter the element to e inserted\n”);
scanf(“%d”,&num);
if(front==-1)
front=rear=0;
else
rear=(rear+1)% MAXSIZE;
cq[rear]=num;
}
}
void cqdelete()
{
int num;
if(front==-1)
printf(“queue is empty\n”);
else
{
num=cq[front];
printf(“Deleted element is =%d\n”, cq[front]);
if(front==rear)
front=rear=-1;
else
front=(front+1)% MAXSIZE;
}
}
Void cqdisplay()
{
int i;
if(front!=-1)
{
for(i=front; i!=rear;(i+1)% MAXSIZE)
{
printf(“%d”, cq[i]);
}
else
printf(“circular queue is empty”);
}
}
Q29. Write a program to implement binary tree
traversals: Inorder , Preorder , Postorder ?
#include<stdio.h>
Struct node
{
Int sum;
Struct node *left;
Struct node *right;
};
Typedef struct node node;
Node *root =NULL;
Node *insert(node *tree, long num);
Void preorder (node *tree);
Void inorder(node *tree );
Void postorder(node *tree);
Int count=1;
Main()
{
Int choice;
Long digit;
Do
{
Choice= select();
Switch(choice);
{
Case 1: puts(“Enter integer : To quit enter 0”);
Scanf(“%d”,&digit);
While(digit!=0)
{ root = insert (root, digit);
Scanf(“%d”,&digit);
Continue;
Case 2 : puts(“\n preorder traversing TREE ”);
Preorder (root): continue;

Case 3: puts(“\n intorder traversing TREE ”);

inorder (root): continue;
Case 4 : puts(“\n postorder traversing TREE ”);
Postorder (root): continue;
Case 5: puts(“END ”); exit(0);
}
} while (choice !=5);
}
Int select()
{
Int selection;
Do
{ puts(“Enter 1:Insert a node in the BT”);
puts(“Enter 2 : Display (preorder) the BT”);
puts(“Enter 3 :Display (inorder) the BT”);
puts(“Enter 4: Display (postorder)the BT”);
puts(“Enter 5: END”);
puts(“Enter your choice”);
scanf(“%d”, selection);
if ((selection<1)|| (selection>5))
{
Puts (“wrong choice: try again”);
Getch();
}
}
While ((selection<1) || (selection >5));
Return (selection);
}
Node *insert (node *P, long digit)
{ If (P==NULL)
{ P=(node *) malloc (sizeof(node));
P->left=P -> right =NULL;
P->num = digit; count++;
}
Else
If (count %2==0)
P-> left =insert (P-> left, digit);
Else
P-> right =insert (P-> right, digit);
Return(P);
}
Void preorder(node *P)
{ if (p!=NULL)
{ printf(“%d\n”,p->num );
Preorder(P-> left);
Preorder(P-> right);
}
}

Void inorder(node *P)

{ if (p!=NULL)
{ inorder(P-> left);
printf(“%d\n”, p->num );
inorder(P-> right);
}
}
Void postorder(node *P)
{ if (p!=NULL)
{ postorder(P-> left);
postorder(P-> right);
printf(“%d\n”, p->num );
}
}
Q30. Write a program to perform insertion, deletion and
traversal in binary search tree?
# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *lchild;
struct node *rchild;
}*root;

void find(int item,struct node **par,struct node **loc)

{
struct node *ptr,*ptrsave;

if(root==NULL) /*tree empty*/

{
 *loc=NULL;
*par=NULL;
return;
}
if(item==root->info) /*item is at root*/
{
*loc=root;
*par=NULL;
return;
}
/*Initialize ptr and ptrsave*/
if(item<root->info)
ptr=root->lchild;
else
ptr=root->rchild;
ptrsave=root;

while(ptr!=NULL)
{
if(item==ptr->info)
{ *loc=ptr;
*par=ptrsave;
return;
}
ptrsave=ptr;
if(item<ptr->info)
ptr=ptr->lchild;
 else
ptr=ptr->rchild;
}/*End of while */
*loc=NULL; /*item not found*/
*par=ptrsave;
}/*End of find()*/

void insert(int item)

{ struct node *tmp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL)
{
printf("Item already present");
return;
}

tmp=(struct node *)malloc(sizeof(struct node));

tmp->info=item;
tmp->lchild=NULL;
tmp->rchild=NULL;

if(parent==NULL)
root=tmp;
else
if(item<parent->info)
parent->lchild=tmp;
else
 parent->rchild=tmp;
}/*End of insert()*/

void case_a(struct node *par,struct node *loc )

{
if(par==NULL) /*item to be deleted is root node*/
root=NULL;
else
if(loc==par->lchild)
par->lchild=NULL;
else
par->rchild=NULL;
}/*End of case_a()*/

void case_b(struct node *par,struct node *loc)

{
struct node *child;

/*Initialize child*/
if(loc->lchild!=NULL) /*item to be deleted has lchild */
child=loc->lchild;
else /*item to be deleted has rchild */
child=loc->rchild;

if(par==NULL ) /*Item to be deleted is root node*/

root=child;
 else
if( loc==par->lchild) /*item is lchild of its parent*/
par->lchild=child;
else /*item is rchild of its parent*/
par->rchild=child;
}/*End of case_b()*/

void case_c(struct node *par,struct node *loc)

{
struct node *ptr,*ptrsave,*suc,*parsuc;

/*Find inorder successor and its parent*/

ptrsave=loc;
ptr=loc->rchild;
while(ptr->lchild!=NULL)
{
ptrsave=ptr;
ptr=ptr->lchild;
}
suc=ptr;
parsuc=ptrsave;

if(suc->lchild==NULL && suc->rchild==NULL)

case_a(parsuc,suc);
else
case_b(parsuc,suc);
 if(par==NULL) /*if item to be deleted is root node */
root=suc;
else
if(loc==par->lchild)
par->lchild=suc;
else
par->rchild=suc;

suc->lchild=loc->lchild;
suc->rchild=loc->rchild;
}/*End of case_c()*/
int del(int item)
{
struct node *parent,*location;
if(root==NULL)
{
printf("Tree empty");
return 0;
}

find(item,&parent,&location);
if(location==NULL)
{
printf("Item not present in tree");
return 0;
}
 if(location->lchild==NULL && location->rchild==NULL)
case_a(parent,location);
if(location->lchild!=NULL && location->rchild==NULL)
case_b(parent,location);
if(location->lchild==NULL && location->rchild!=NULL)
case_b(parent,location);
if(location->lchild!=NULL && location->rchild!=NULL)
case_c(parent,location);
free(location);
}/*End of del()*/

int preorder(struct node *ptr)

{
if(root==NULL)
{
printf("Tree is empty");
return 0;
}
if(ptr!=NULL)
{
printf("%d ",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);
}
}/*End of preorder()*/

void inorder(struct node *ptr)

{
if(root==NULL)
{
printf("Tree is empty");
return;
}
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);
}
}/*End of inorder()*/

void postorder(struct node *ptr)

{
if(root==NULL)
{
printf("Tree is empty");
return;
}
if(ptr!=NULL)
{
postorder(ptr->lchild);
postorder(ptr->rchild);
printf("%d ",ptr->info);
}
}/*End of postorder()*/

void display(struct node *ptr,int level)

{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display()*/
main()
{
int choice,num;
root=NULL;
while(1)
{
printf("\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n");
printf("5.Postorder Traversal\n");
printf("6.Display\n");
printf("7.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num);
break;
case 2:
printf("Enter the number to be deleted : ");
scanf("%d",&num);
del(num);
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
 display(root,1);
break;
case 7:
break;
default:
printf("Wrong choice\n");
}/*End of switch */
}/*End of while */
}/*End of main()*/