VIDYA FIRST GRADE COLLEGE

TUMKUR
DEPERATMENT OF COMPUTER
SCIENCE
1ST YEAR 2ND SEM BCA

Data Structure Using C Lab -Lab Manual

 LIST OF PRACTICAL PROGRAMS
PART A:
1. Develop a Program in C for the operations on Strings like finding the string of length, copying two
strings, comparing of two string and pattern matching & replacing. Support the program with functions for
each of the above operations. Don't use Built-in functions
2. Write a C program to read name and roll number of n number of students from user and store them in a
file.
3. Write a C Program to implement dynamic array, find smallest and largest element of the array.
4. Write a C Program read, display and to find the trace of a square matrix
5. Write a C Program to read, display and add two m x n matrices using functions
6. Write a C Program to read, display and multiply two m x n matrices using functions
7. Write a C Program to read the names of cities and arrange them alphabetically.
8. Write a C Program to search an element using linear search technique.
9. Write a C Program to sort the given list using selection sort technique.
10. Write a program to implement merge sort.
PART B:
1. Program to implement linear linked list to perform insert and delete operations on it.
2. Write a C Program to implement Stack and its different operations.
3. Write a C Program to convert an infix expression to postfix.
4. Write a C Program to evaluate a postfix infix expression.
5. Write a C Program to implement simple queue and its different operations.
6. Write a program to implement circular queue using array.
7. Program to create and display different traversal of a binary tree.
8. Write a program to implement BFS.
9. Write a program to implement DFS.
10. Write a program to implement AVL Tree
PART A:
1. Develop a Program in C for the operations on Strings like finding the string of length,
copying two strings, comparing of two string and pattern matching & replacing. Support the
program with functions for each of the above operations. Don't use Built-in functions.
#include<stdio.h>
#include<conio.h> // For clrscr() and getch()

void main()
{
char str1[80], str2[80];
int i, len = 0, k = 0,
ch;

clrscr(); // Clear the screen (Turbo C specific)

printf("Enter first string:\n");
scanf("%s", str1);
printf("Enter second string:\n");
scanf("%s", str2);
printf("Enter your choice:\n");
scanf("%d", &ch);

switch(ch) {
case 1:
for(i = 0; str1[i] != '\0'; i++) {
len++;
}
printf("The length of the string is %d", len);
break;

case 2:
for(i = 0; str1[i] != '\0'; i++)
{ str2[i] = str1[i];
}
str2[i] = '\0'; // Terminate the string properly
 printf("\nCopying of second string = %s", str2);
break;

case 3:
for(i = 0; str1[i] != '\0' && str2[i] != '\0'; i++)
{ if(str1[i] != str2[i]) {
k = 1;
break;
}
}
if(k == 0 && str1[i] == str2[i])
{ printf("\nBoth strings are equal.");
} else if(k > 0) {
printf("\nString 1 is greater than string 2: %s > %s", str1, str2);
} else {
printf("\nString 1 is lesser than string 2: %s < %s", str1, str2);
}
break;

case 4:
for(i = 0; str1[i] != '\0' && str2[i] != '\0'; i++)
{ if(str1[i] != str2[i]) {
k = 1;
break;
}
}
if(k == 0 && str1[i] == str2[i]) {
printf("\nPattern matching: Both strings are the same.");
} else {
printf("\nPattern matching: Both strings are not the same.");
}
break;

default:
 printf("Invalid choice.\n");
break;
}

getch();
}
Output:
Example 1: Length of String (Choice 1)
 Input:
o First string: "Hello"
o Second string: "World"
o Choice: 1 (to calculate the length of the first string)
 Output:
The length of the string is 5
Example 2: Copying a String (Choice 2)
 Input:
o First string: "Hello"
o Second string: "World"
o Choice: 2 (to copy the first string to the second string)
 Output:
Copying of second string = Hello
Example 3: Comparing Two Strings (Choice 3)
 Input:
o First string: "Hello"
o Second string: "Hello"
o Choice: 3 (to compare the two strings)
 Output:
Both strings are equal.
Example 4: Comparing Two Strings (Choice 3 - Different Strings)
 Input:
o First string: "Hello"
o Second string: "World"
o Choice: 3 (to compare the two strings)
Output:
 o String 1 is lesser than string 2: Hello < World
Example 5: Pattern Matching (Choice 4 - Same Strings)
o Input:
o First string: "Hello"
o Second string: "Hello"
o Choice: 4 (to check if both strings are the same)
o Second string: "World"
o Choice: 3 (to compare the two strings)
Output:
o String 1 is lesser than string 2: Hello < World
Example 6: Pattern Matching (Choice 4 - Different Strings)
 Input:
o First string: "Hello"
o Second string: "World"
o Choice: 4 (to check if both strings are the same)
Output:
 Pattern matching: Both strings are not the same.
Example 7: Invalid Choice (Default Case)
 Input:
o First string: "Hello"
o Second string: "World"
o Choice: 5 (an invalid choice)
 Output
 Invalid choice.
 2. Write a C program to read name and roll number of n number of students from user and
store them in a file.
#include<stdio.h>
struct student
{
int rno,sem;
float per;
char name[20],course[20];
}s;
void main()
{
FILE *sfile;
clrscr();
sfile=fopen("student.txt","w");
printf("Enter record of student\
n"); printf("Enter student name:\
n"); scanf("%s",&s.name);
printf("Enter roll number:\n");
scanf("%d",&s.rno);
printf("Enter semester:\n");
scanf("%d",&s.sem);
printf("Enter course:\n");
scanf("%s",&s.course);
printf("Enter percentage of student:\n");
scanf("%f",&s.per);
fprintf(sfile,"Name=%s\n rno=%d\n sem=%d\n course=%s\nper=%f\n",s.name,s.rno,s.sem,s.course,s.per);
printf("\n student record stored in file....");
fclose(sfile);
getch();
}
Output:
Enter record of student
Enter student name:
Arun
Enter roll number:
2023
Enter semester:
2
Enter course:
BCA
Enter percentage of student:
89.
Student record stored in file successfully...
// u can see the student record stored file: go to c-drive->turbo c or c++->bin->student.txt:
Name=ARUN
rno=101
sem=2
course=bca
per=89.000000
3. Write a C Program to implement dynamic array, find smallest and largest element of the array.
#include<stdio.h>
#include<stdlib.h>
void main()
{
int *ptr,n,i,max,min;
clrscr();
printf("\n Enter size of an array \n");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof (int));
printf("\n Enter %d elements \n",n);
for(i=0;i<n;i++)
{
scanf("%d",&ptr[i]);
}
for(i=0;i<n;i++)
{
printf("ptr[%d]:%d \n",i,ptr[i]);
}
max=min=ptr[0];
for(i=0;i<n;i++)
{
if(ptr[i]>max)
max=ptr[i];
if(ptr[i]<min)
min=ptr[i];
}
printf("Largest elements is %d \n",max);
printf("smallest elements is %d \n",min);
getch();
}
Output:
Enter size of an array
4
Enter 4 elements
10
20
3
1
ptr[0]:10
ptr[1]:20
ptr[2]:3
ptr[3]:1
Largest elements is 20
smallest elements is 1
4. Write a C Program read, display and to find the trace of a square matrix
#include<stdio.h>
#include<conio.h>
void main() {
int a[10][10],r,c,i,j,sum=0;
clrscr();
printf("Enter the number of rows and columns:\n");
scanf("%d%d",&r,&c);
if(r==c)
{
printf("Enter %dX%d elements in the matrix\n",r,c);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf("%d",&a[i][j]);
printf("The matrix entered is:\n");
for(i=0;i<r;i++)
{
for(j=0;j<r;j++)
printf("%6d",a[i][j]);
printf("\n");
}
for(i=0;i<r;i++)
sum=sum+a[i][i];
printf("The trace of the matrix is %d",sum);
}
else
printf("It is not a square matrix!");
getch();
}
Output:
Enter the number of rows and columns:
2 2
Enter 2X2 elements in the matrix
1 2 3 4
The matrix entered is:
1 2
3 4
The trace of the matrix is 5
5. Write a C Program to read, display and add two m x n matrices using functions
#include<stdio.h>
#include<conio.h>
void readarray(int a[10][10],int row, int col)
{ int i,j;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
scanf("%d",&a[i][j]);
}
void addarray(int m1[10][10],int m2[10][10],int m3[10][10],int row, int col)
{ int i,j;
for(i=1;i<=row;i++) for(j=1;j<=col;j+
+) m3[i][j]=(m1[i][j]+m2[i][j]);
}
void printarray(int m[10][10],int row,int col) {
int i,j;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++) {
printf("%6d",m[i][j]);
}
printf("\n");
}
void main()
{
int m1[10][10],m2[10][10],m3[10][10],row,col;
clrscr();
printf("Enter order of rows:\n"); scanf("%d
%d",&row,&col);
printf("Enter %d elements for martix 1: \n",row*col);
readarray(m1,row,col);
printf("Enter %d elements for matrix 2: \
n",row*col); readarray(m2,row,col);
addarray(m1,m2,m3,row,col);
printf("The entered matrix 1 is:\n");
printarray(m1,row,col);
printf("The entered matrix 2 is:\n");
printarray(m2,row,col);
printf("The Addition of matrix is:\n");
printarray(m3,row,col);
getch();
}
Output:
Enter order of rows:
2
2
Enter 4 elements for martix 1:
1 2 3 4
Enter 4 elements for matrix 2:
1 2 3 4
The entered matrix 1 is:
1 2
3 4
The entered matrix 2 is:
1 2
3 4
The Addition of matrix is:
2 4
6 8
6. Write a C Program to read, display and multiply two m x n matrices using functions.
#include<stdio.h>
#include<conio.h>
void readarray(int a[10][10],int row,int col)
{ int i,j;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
scanf("%d",&a[i][j]);
}
void mularray(int m1[10][10],int m2[10][10],int m3[10][10],int row, int col)
{ int i,j,k;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++) {
m3 [i][j]=0;
for(k=1;k<=col;k++) {
m3 [i][j]=m3[i][j] + m1[i][k] * m2[k][j];
} } }
void printarray(int m[10][10],int row,int col) {
int i,j;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
{
printf("%6d",m[i][j]);
}
printf("\n");
}
void main() {
int m1[10][10],m2[10][10],m3[10][10],row,col;
clrscr();
printf("Enter order of rows:\n"); scanf("%d
%d",&row,&col);
printf("Enter %d elements for matrix 1: \n",row*col);
readarray(m1,row,col);
printf("Enter %d elements for matrix 2: \n",row*col);
readarray(m2,row,col);
printf("The entered matrix 1 is:\n");
printarray(m1,row,col);
printf("The entered matrix 2 is:\n");
printarray(m2,row,col);
 mularray(m1,m2,m3,row,col);
printf("The Product of matrix is:\n");
printarray(m3,row,col);
getch();
}
Output:
Enter order of rows:
3 3
Enter 9 elements for matrix 1:
1 2 3 4 5 6 7 8 9
Enter 9 elements for matrix 2:
9 8 7 6 5 4 3 2 1
The entered matrix 1 is:
1 2 3
4 5 6
7 8 9
The entered matrix 2 is:
9 8 7
6 5 4
3 2 1
The Product of matrix is:
30 24 18
84 69 54
138 114 90

7. Write a C Program to read the names of cities and arrange them alphabetically.
#include<stdio.h>
#include<string.h>
void main()
{
int i,j,n;
char city[100][100],cname[100];
clrscr();
printf("Enter number of cities :\n");
scanf("%d",&n);
printf("Enter cities name are:\
n"); for(i=0;i<n;i++)
scanf("%s",city[i]);
printf("Before sorting:\n");
for(i=0;i<n;i++) printf("%s\
n",city[i]); for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(strcmp(city[i],city[j])>0)
{
strcpy(cname,city[i]);
strcpy(city[i],city[j]);
strcpy(city[j],cname);
}}}
printf("The after sorted order of names are:\n");
for(i=0;i<n;i++)
printf("%s\n",city[i]);
getch();
}
Output:
Enter number of cities :6
Enter cities name are:
Mumbai
Delhi
Kolkata
Chennai
Bangalore
Tumkur
Before sorting:
Mumbai
Delhi
Kolkata
Chennai
Bangalore
Tumkur
The after sorted order of names are:
Bangalore
Chennai
Delhi
Kolkata
Mumbai
Tumkur
8. Write a C Program to search an element using linear search technique.
#include <stdio.h>
void main() {
int n,a[100],key,i,loc=0;
clrscr();
printf("\n Enter the size of array\n");
scanf("%d",&n);
printf("\n Enter array elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter key element\n");
scanf("%d",&key);
for(i=0;i<n;i++){
if(key==a[i])
{
loc=1;
break;
}
}
if(loc==1)
printf("Key element %d is found at the Location = %d ",a[i],loc=i+1);
else
printf("Key element is not found");
getch();
}
Output:
Enter the size of array
3
Enter array elements
10
20
30
Enter key element
20
Key element 20 is found at the Location = 2

9. Write a C Program to sort the given list using selection sort technique.
#include <stdio.h>
void main() {
int a[100],n,i,j,swap;
printf(" Enter size of array\n");
scanf("%d",&n);
printf("Enter array elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]); for(i=0;i<n;i+
+)
{
int min=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[min])
{
min=j;
}
}
if(min!=i)
{
swap=a[i];
a[i]=a[min];
a[min]=swap;
}}
printf("Selection sorted array is \n");
for(i=0;i<n;i++)
printf("%d \n",a[i]);
getch();
}
Output:
Enter size of array
4
Enter array elements
2
1
5
3
Selection sorted array is
1 2 3 5
10. Write a program to implement merge sort.
#include <stdio.h>
void mergesort(int
a[],int,int); void merge(int
a[],int,int,int); void main() {
int a[50],n,i;
clrscr()
printf(" Enter size of array\n");
scanf("%d",&n);
printf("Enter array elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("merge sorted array element is \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
getch();
}
void mergesort(int a[],int lb,int ub)
{
int mid;
if (lb <ub)
{
mid=(lb+ub)/2;
mergesort(a, lb, mid);
mergesort(a, mid+1, ub);
merge(a, lb, mid, ub);
}
}
void merge(int a [], int lb, int mid, int ub)
{
int temp[50],i=lb, j=mid+1, k=lb;
while (i<=mid && j<=ub)
{
if(a[i]<=a[j])
temp[k++] =a[i++];
else
temp[k++] =a[j++];
}
if(i>mid) {
while(j<=ub)
temp[k++] =a[j++];
}
else {
while(i<=mid)
temp[k++] =a[i++];
}
for (k=lb;k<=ub;k++)
a[k]=temp[k];
}
Output:
Enter size of array
4
Enter array elements
20
50
30
10
merge sorted array element is
10 20 30 50
PART B:
1. Program to implement linear linked list to perform insert and delete operations on it.
# include <stdio.h>
# include
<stdlib.h> void
create();
void display();
void IAB(); void DFB();
struct node
{
int data;
struct node *next;
}*new,*head,*temp,*d;
void main() {
int choice;
clrscr();
while(1)
{
printf("..........MENU......\n");
printf("1.Create \n");
printf("2.Display \n");
printf("3.Insert at Beginning \n");
printf("4.Delete from Beginning \
n"); printf("5.Exit\n");
printf("Enter your choice:"); scanf("%d", &choice);
switch(choice)
{
case 1 : create();break;
case 2 : display();break;
case 3 : IAB();break;
case 4 : DFB();break;
case 5 : exit(0);
default : printf("wrong choice\n"); break;
}
}getch();
}
void create()
{
int value;
char choice;
do{
new=(struct node*) malloc (sizeof(struct node));
printf("Enter a data value for the node:");
scanf("%d", &value);
new->data=value;
new->next=NULL;
 if(head==NULL)
{
head=temp=new;
}
else
{
temp->next=new;
temp=new;
}
printf("Do u want to add one more node to the list [n/y]:");
fflush (stdin);
scanf("\n %c", &choice);
}while(choice=='y');
}
void display()
{
temp=head;
int count=0,value;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
count=count+1;
}
printf("NULL\n");
printf("Total number of nodes =%d \n", count);
}
void IAB()
{
int value;
new=(struct node*)malloc(sizeof (struct node));
printf("Enter a value:");
scanf("%d",
&value); new-
>data=value; new-
>next=head;
head=new;
display();
}
void DFB()
{
temp=head;
printf("Deleted node is %d:", temp-
>data); head=head->next;
temp->next=NULL;
free(temp);
display();
}
Output:
..........MENU......
1. Create
2. Display
3. Insert at Beginning
4. Delete from Beginning
5. Exit
Enter your choice:1
Enter a data value for the node:1
Do u want to add one more node to the list [n/y]:y
Enter a data value for the node:2
Do u want to add one more node to the list [n/y]:y
Enter a data value for the node:3
Do u want to add one more node to the list [n/y]:n
..........MENU......
1. Create
2. Display
3. Insert at Beginning
4. Delete from Beginning
5. Exit
Enter your
choice:2 1->2->3-
>NULL
Total number of nodes =3
..........MENU......
1. Create
2. Display
3. Insert at Beginning
4. Delete from Beginning
5. Exit
Enter your choice:3
Enter a value:0
0->1->2->3->NULL
Total number of nodes =4
..........MENU......
1. Create
2. Display
3. Insert at Beginning
4. Delete from Beginning
5. Exit
Enter your choice:4
Deleted node is 0:1->2->3->NULL
Total number of nodes =3

2. Write a C Program to implement Stack and its different operations.

#include<stdio.h>
#include<conio.h>
#define MAX 3
int stack[MAX],top=-1;
void push();void pop();void peek(); void
display(); void main()
 {
int item,ch;
clrscr();
while(1)
{
printf("\n1.push\n2.pop\n3.peek \n4.display \n5.exit \n"); printf("\
nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:push();break;
case 2:pop();break;
case 3:peek();break;
case 4:display();break;
case 5:exit(0);
default:printf("\n wrong choice!!!\n");
}}
getch();
}
void push()
{
int ele;
if(top==(MAX-1)){
printf("Overflow and insertion is not possible");
}
else{ top=to
p+1;
printf("Enter an element:");
scanf("%d",&ele);
stack[top]=ele;
}
display();
}
void pop()
{
if(top==-1)
printf("Stack is empty or underflow and deletion is not possible");
else {
printf("Deleted element from stack is:
%d",stack[top]); top=top-1;
}
display();
}
void peek()
{
if(top==-1)
printf("Stack is Empty");
else
printf(" Top most element is: % d\n",stack[top]);
 }
void display()
{
int i;
if(top==-1)
printf("Stack is Empty");
else {
printf("\n Stack elements is:\n Top \
n"); for(i=top;i>=0;i--)
printf("%d \t",stack[i]);
}}
Output:
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:1
Enter an element:1
Stack element is:
Top
1
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:1
Enter an element:2
Stack element is:
Top
2 1
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:1
Enter an element:3
Stack element is:
Top
3 2 1
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:2
Deleted element from stack is :3
Stack element is:
Top
2 1
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:3
Top most element is
:2
1. push
2. pop
3. peek
4. display
5. exit
Enter your choice:4
Stack element is:
Top
2 1
1. push
2. pop
3. peek
4. display
5. exit

3. Write a C Program to convert an infix expression to postfix.

#include<stdio.h>
#include<ctype.h>
char stack[100];
int top=-1;
void push(char x)
{
stack[++top]=x;
}
char pop()
{
return stack[top--];
}
int priority(char ch)
{
if(ch=='(')
return 0;
else if(ch=='+'||ch=='-')
return 1;
else if(ch=='*'||ch=='/')
return 2;
else if(ch=='^')
return 3;
}
void main()
{
char infix[100],postfix[100],ch;
int i=0,j=0;
clrscr();
printf("Enter infix expression:\n");
scanf("%s",&infix); for(i=0;infix[i]!='\
0';i++)
{
ch=infix[i];
if(ch=='(')
push(ch);
else if(ch==')')
{
while(stack[top]!='(' && top!=-1)
{
postfix[j++]=pop();
}
pop();
}
else if(isalpha(ch)||isdigit(ch))
{
postfix[j++]=ch;
}
else{
while(priority(ch) <= priority(stack[top]) &&top!=-1)
{
postfix[j++]=pop();
}
push(ch);
}
}
while(top!=-1)
{
postfix[j++]=pop();
}
postfix[j]='\0';
printf("\n postfix notation=%s",postfix);
getch();
}
Output1:
Enter infix expression:
a+b*c
postfix notation=abc*+

Output 2:
Enter infix expression:
(a+b)*c+(d-a)
postfix notation=ab+c*da-+
4. Write a C Program to evaluate a postfix infix
expression. #include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 50

// Stack structure
int stack[MAX];
int top = -1;

// Function to push an element onto the stack

void push(int value) {
if (top == MAX - 1)
{ printf("Stack overflow\
n"); exit(1);
}
stack[++top] = value;
}

// Function to pop an element from the

stack int pop() {
if (top == -1) {
printf("Stack underflow\n");
exit(1);
}
return stack[top--];
}

// Function to evaluate a postfix expression

int evaluatePostfix(char* exp) {
int i = 0, operand1, operand2, result;
 while (exp[i] != '\0') {
if (isdigit(exp[i])) {
// If the character is a number, push it onto the stack
push(exp[i] - '0');
} else {
// If the character is an operator, pop two operands and apply the operator
operand2 = pop();
operand1 = pop();
switch (exp[i]) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
default:
printf("Invalid operator\n");
exit(1);
}
// Push the result back onto the stack
push(result);
}
i++;
}
// The result will be the only value left in the stack
return pop();
}
int main() {
char postfix[MAX];
int result;

// Read postfix expression from the user

printf("Enter postfix expression: ");
gets(postfix); // Using gets() is acceptable in Turbo C for simplicity

// Evaluate the postfix expression

result = evaluatePostfix(postfix);

// Print the result

printf("Result of postfix evaluation: %d\n", result);

return 0;
}

OUTPUT
Example 1:
 Input: 23+5*
 Output: 25
Example 2:
 Input: 45+3*2-
 Output: 7

5. Write a C Program to implement simple queue and its different operations.

#include<stdio.h>
#define SIZE 50
int queue[SIZE];
int rear = - 1;
int front = - 1;
void insert()
{
int ele;
if (rear == SIZE-1)
printf("Queue Overflow \n");
else
{
rear++;
printf("Enter the element in queue : ");
scanf("%d",&ele);
queue[rear]=ele;
if (front == - 1)
front = 0;
}
}
void delete()
{
if (front == - 1 && rear==-1)
printf("Queue Underflow \n");
else if(front==rear)
{
printf("Element deleted from queue is : %d\n", queue[front]);
front = -1;
rear=-1;
}
else
{
printf("Element deleted from queue is : %d\n", queue[front]);
front++;
}
}
void display()
{
int i;
if (front == - 1 && rear==-1)
printf("Queue is empty \n");
else
{
printf("Queue is :");
for (i = front; i <= rear; i++)
printf("%d\t", queue[i]);
}
}
void main(){
int ch;
clrscr();
while(1){
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch(ch){
case 1:insert();break;
case 2:delete();break;
case 3:display();break;
case 4:exit(1);
default:printf("Wrong choice \n");
}
}
Output:
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 1
Enter the element in queue :1
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 1
Enter the element in queue :2
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 1
Enter the element in queue :3
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 3
Queue is: 1 2 3
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 2
Element deleted from queue is :1
1. Insert element to queue
2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice:
3 Queue is: 2 3
Enter your choice: 2
Element deleted from queue is :1
1. Insert element to queue
 2. Delete element from queue
3. Display all elements of queue
4. Exit
Enter your choice: 4

6. Write a program to implement circular queue using

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

#define MAX 5 // Maximum size of the queue

// Circular Queue structure

int queue[MAX];
int front = -1;
int rear = -1;

// Function to check if the queue is full

int isFull() {
if ((rear + 1) % MAX == front)
{ return 1; // Queue is full
}
return 0;
}

// Function to check if the queue is empty

int isEmpty() {
if (front == -1) {
return 1; // Queue is empty
}
return 0;
}

// Function to insert an element into the circular queue

void enqueue(int value) {
if (isFull()) {
 printf("Queue is full, cannot enqueue %d\n", value);
} else {
if (front == -1) { // First element to insert
front = 0;
}
rear = (rear + 1) % MAX; // Circular
increment queue[rear] = value;
printf("%d enqueued to the queue\n", value);
}
}

// Function to delete an element from the circular queue

int dequeue() {
int value;
if (isEmpty()) {
printf("Queue is empty, cannot dequeue\n");
return -1;
} else {
value = queue[front];
if (front == rear) { // Only one element in the queue
front = rear = -1;
} else {
front = (front + 1) % MAX; // Circular increment
}
printf("%d dequeued from the queue\n", value);
return value;
}
}

// Function to display the elements of the queue

void display() {
if (isEmpty()) {
printf("Queue is empty\n");
} else {
 int i = front;
printf("Queue elements: ");
while (i != rear) {
printf("%d ", queue[i]);
i = (i + 1) % MAX; // Circular increment
}
printf("%d ", queue[rear]); // Print the rear element printf("\
n");
}
}

// Main function
int main() {
int choice, value;
while (1) {
printf("\nCircular Queue Operations:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice)
{ case 1:
printf("Enter value to enqueue: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
 break;
case 4:
printf("Exiting program\n");
return 0;
default:
printf("Invalid choice, try again\n");
}
}

return 0;
}
OUTPUT:
Enter value to enqueue: 20
20 enqueued to the queue
Circular Queue
Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue elements: 10 20
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
10 dequeued from the queue
7. Program to create and display different traversal of a binary tree.
#include <stdio.h>
#include
<stdlib.h> struct
node
{
int item;
struct node* left;
struct node* right;
};
void inordertraversal(struct node* root)
{
if (root == NULL) return;
inordertraversal(root->left);
printf("%d ->", root->item);
inordertraversal(root->right);
}
void preordertraversal(struct node* root)
{
if (root == NULL) return;
printf("%d ->", root->item);
preordertraversal(root->left);
preordertraversal(root->right);
}
void postordertraversal(struct node* root)
{
if (root == NULL) return;
postordertraversal(root->left);
postordertraversal(root->right);
printf("%d ->", root->item);
}
struct node* createnode(value)
{
struct node* newnode = malloc(sizeof(struct
node)); newnode->item = value;
newnode->left = NULL;
newnode->right =
NULL; return newnode;
}
struct node* insertleft(struct node* root, int value)
{
root->left = createnode(value);
return root->left;
}
struct node* insertright(struct node* root, int value)
{
root->right = createnode(value);
return root->right;
}
int main()
{
struct node* root = createnode(1);
int value;
clrscr();
printf("....Binary Tree Traversal. . .\n");
printf("\n Enter leftnode value :
"); scanf("%d",&value);
insertleft(root, value);
printf("\n Enter right node value :
"); scanf("%d",&value);
insertright(root, value);
printf("\n Enter leftnode value :
"); scanf("%d",&value);
insertleft(root->left, value);
printf("\n Enter leftnode value :
"); scanf("%d",&value);
insertright(root->left, value);
printf("\n Enter rightnode value : ");
scanf("%d",&value);
insertleft(root->right, value);
printf("\n Enter rightnode value :
"); scanf("%d",&value);
insertright(root->right, value);
printf("\n...Traversal of the inserted binary tree...\n");
printf("Inorder traversal \n");
inordertraversal(root); printf("\
nPreorder traversal \n");
preordertraversal(root); printf("\
nPostorder traversal \n");
postordertraversal(root);
getch();
}
Output:
.... Binary Tree Traversal....
Enter left node value:4
Enter right node value:6
Enter left node value:42
Enter left node value:3
Enter right node value:2
Enter right node value:33
...Traversal of the inserted binary tree...
Inorder traversal
42->4->3->1->2->6->33->
Preorder traversal
1->4->42->3->6->2->33->
Postorder traversal
42->3->4->2->33->6->1->
8. Write a program to implement BFS.
#include <stdio.h>

#define MAX 10

int a[MAX][MAX], q[MAX] = {0}, visited[MAX] = {0}, n, i, j, f = 0, r = 0;

void bfs(int v)
{
visited[v] = 1;
printf("%d\t", v);
q[r++] = v; // Enqueue the starting vertex

while (f < r)
{
v = q[f++]; // Dequeue the front element

// Explore all adjacent vertices of the current vertex

for (i = 0; i < n; i++)
{
if (a[v][i] == 1 && visited[i] == 0)
{
q[r++] = i; // Enqueue the unvisited adjacent vertex
visited[i] = 1; // Mark it as visited
printf("%d\t", i); // Print the vertex
}
}
}
}

int main()
{
int v;
 // Accept the number of vertices and adjacency matrix
printf("Enter the number of vertices: ");
scanf("%d", &n);

printf("Enter the adjacency matrix:\n");

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
}

// Perform BFS starting from vertex 0 (indexing starts from 0 in C)

printf("BFS traversal starting from vertex 0:\n");
bfs(0); // Starting BFS from vertex 0

return 0;
}OUPUT:
Enter the number of vertices: 4
Enter the adjacency matrix:
0101
1010
0101
1010
BFS traversal starting from vertex 0:
0 1 3 2
9. Write a program to implement DFS.
#include<stdio.h>
#include<stdlib.h>

int adj[100][100], n, visited[100] = {0};

void dfs(int v, int n)

{ int i;
visited[v] = 1;
printf("%d ", v);
for (i = 1; i <= n; i++) {
if (adj[v][i] == 1 && visited[i] == 0)
{ dfs(i, n);
}
}
}

int main()
{ int i, j;
printf("Enter the number of nodes in the graph: ");
scanf("%d", &n);

printf("Enter the adjacency matrix (0 or 1):\n");

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &adj[i][j]);
}
}

printf("Depth First Search starting from node 1:\n");

dfs(1, n);

return 0;
}
Ouput:
Enter the number of nodes in the graph: 4
Enter the adjacency matrix (0 or 1):
0110
1011
1101
0110
Depth First Search starting from node
1: 1 2 3 4

10. Write a program to implement AVL Tree

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

struct Node
{ int data;
struct Node *left;
struct Node *right;
int height;
};

int height(struct Node *N) {

if (N == NULL)
return 0;
return N->height;
}

int getBalance(struct Node *N) {

if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* rightRotate(struct Node *y)
{ struct Node *x = y->left;
struct Node *T2 = x->right;

x->right =
y; y->left =
T2;

y->height = (height(y->left) > height(y->right)) ? height(y->left) + 1 : height(y->right) +

1; x->height = (height(x->left) > height(x->right)) ? height(x->left) + 1 : height(x->right)
+ 1;

return x;
}

struct Node* leftRotate(struct Node *x)

{ struct Node *y = x->right;
struct Node *T2 = y->left;

y->left = x;
x->right = T2;

x->height = (height(x->left) > height(x->right)) ? height(x->left) + 1 : height(x->right) +

1; y->height = (height(y->left) > height(y->right)) ? height(y->left) + 1 : height(y->right)
+ 1;

return y;
}

struct Node* insert(struct Node* node, int data)

{ if (node == NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->data = data;
newNode->left = NULL;
newNode->right =
NULL; newNode->height
= 1; return newNode;
 }

if (data < node->data)

node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else
return node;

node->height = 1 + ((height(node->left) > height(node->right)) ? height(node->left) : height(node-

>right));

int balance = getBalance(node);

if (balance > 1 && data < node->left->data)

return rightRotate(node);

if (balance < -1 && data > node->right->data)

return leftRotate(node);

if (balance > 1 && data > node->left->data)

{ node->left = leftRotate(node->left);
return rightRotate(node);
}

if (balance < -1 && data < node->right->data)

{ node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;
}

void inorder(struct Node* root) {

 if (root != NULL) {
inorder(root->left);
printf("%d ", root-
>data); inorder(root-
>right);
}
}

int main() {
struct Node *root = NULL;

root = insert(root,
10); root =
insert(root, 20); root
= insert(root, 30);
root = insert(root,
15); root =
insert(root, 25); root
= insert(root, 5);

printf("In-order traversal of the AVL tree:\

n"); inorder(root);

return 0;
}
Ouput:
In-order traversal of the AVL tree:
5 10 15 20 25 30