A

Practical assignment
on
“ Program based on data structure ”

Bachelor of Science in Information Technology

[B.Sc. 3rd Year]
Session 2024

Submitted To
Department of Information Technology
Government Nagarjun Post Graduate College of Science,
Raipur (C.G.)

Guided by: Submitted by:

Dr. Yogeshwary Pal Meghshankar Sahu
Assistant Professor(IT dept.) Roll no.:-
 Acknowledgements

I extend my hearties thanks and express my sincere gratitude to

my progessor Dr. Yogeshwary Pal for giving me the
opportunity to do the wonderful project of IT on “ Program
based on data structure ” . he has also helped in
completing my project, I have learnt increased.

I express my sincere gratitude to my dear parents and friends

who have helped me a lot.
 Index
s.n. Program’s name p.n.
1. Write a program to find largest among three number . 1
2. Write a program to find average of five student marks. 2
3. Write a program to print Matrix . 3
4. Write a program to print the diagonal matrix of the Matrix . 4
5. Write a program to Add., Sub., Mul. and inverse of Matrix . 5
6. Write a program to count the element to given Array . 9
7. Write a program to print the all element in the Array . 10
8. Write a program to search given number in Array. 11
9. Write a program to insert an item into linear Array . 13
10. Write a program to delete an item from the linear Array . 15
11. Write a program into search with help of Binary Searching . 17
12. Write a program to print the all element of linear Linked list . 19
13. Write a program to search an item into Linked list . 22
14. Write a program to find the location of an item into sorted Linked 25
list .

15. Write a program to insert new node into linked list as First Node . 28

16. Write a program to insert new node into linked list as Particular 30
Node.

17. Write a program to insert new node into linked list as End Node . 33
18. Write a program to insert an element into Stack . 35
19. Write a program to delete an element from Stack . 36
20. Write a program to insert an element into Queue . 38
21. Write a program to delete an element from Queue . 42
22. Write a program in Bubble Sort . 46
23. Write a program to sort the given element using Quick Sort . 48
24. Write a program to sort the given element using Insertion Sort . 51
25. Write a program to sort the given element using Selection Sort . 53
26. Write a program to print the all nodes of Tree using Preorder 55
traversal .

27. Write a program to print the all nodes of Tree using Inorder 57
traversal .

28. Write a program to print the all nodes of Tree using Postorder 59
traversal .

29. Write a program to insert an item into BST(binary search tree) . 61

30. Write a program to delete an item from BST(binary search tree) . 64
31. Write a program to demonstrate BFS(breadth first search) . 69
32. Write a program to demonstrate DFS(depth first search) . 73
 1

1.Write a program to find largest among three number .

Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
int a, b, c;
cout << "Enter three numbers: ";
cin >> a >> b >> c;
int largest;
if (a > b && a > c)
{
largest = a;
}
else if (b > a && b > c)
{
largest = b;
}
else
{
largest = c;
}
cout << "The largest number is: " << largest << endl;
getch();
return 0;
}
Output:-
 2

2.Write a program to find average of five student

marks.
Code:-
#include<iostream.h>
#include<conio.h>
int main()
{ clrscr();
float marks[5];
float sum = 0.0, average = 0.0;
cout << "Enter the marks of five students: " << endl;
for (int i = 0; i < 5; i++)
{
cin >> marks[i];
sum += marks[i];
}
average = sum / 5.0;
cout << "The average of the marks is: " << average << endl;
getch();
return 0;
}
Output:-
 3

3.Write a program to print Matrix .

Code:-
#include<iostream.h>

#include<conio.h>
int main()
{
clrscr();
const int m = 3, n = 3;
int mat[m][n] = {{3, 8, 5}, {1, 5, 6}, {4, 7, 9}};
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << mat[i][j] << " ";
}
cout << endl;
}
getch();
return 0;
}
Output:-
 4

4.Write a program to print the diagonal matrix of the

Matrix .
Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
const int m = 3, n = 3;
int mat[m][n] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

// print the diagonal matrix

for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
cout << mat[i][j] << " ";
else
cout << "0 ";
}
cout << endl;
}
return 0;
}
Output:-
 5

5.Write a program to Add., Sub., Mul. and inverse of

Matrix .
Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
const int n = 2;
int i,j;
int mat1[n][n] = {{5, 6}, {7, 8}};
int mat2[n][n] = {{4, 2}, {1, 3}};
int sum[n][n]; // declare a matrix to store the sum
int diff[n][n]; // declare a matrix to store the diffence
int prod[n][n]; // declare a matrix to store the product
double inv[n][n]; // declare a matrix to store the inverse

// add the matrices element-wise

for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum[i][j] = mat1[i][j] + mat2[i][j];
}
}
cout << "The sum of the matrices is:\n";
for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << sum[i][j] << " ";
}
cout << endl;
}
 6

// subtract the matrices element-wise

for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
diff[i][j] = mat1[i][j] - mat2[i][j];
}
}
cout << "The difference of the matrices is:\n";
for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << diff[i][j] << " ";
}
cout << endl;
}

// multiply the matrices

for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
prod[i][j] = 0;
for (int k = 0; k < n; k++)
{
prod[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
cout << "The product of the matrices is:\n";
for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
 7

{
cout << prod[i][j] << " ";
}
cout << endl;
}

// find the determinant of the matrix

int det = mat1[0][0] * mat1[1][1] - mat1[0][1] * mat1[1][0];
if (det == 0)
{
cout << "The matrix is singular and has no inverse.\n";
return 0;
}
int adj[n][n]; // find the adjoint of the matrix
adj[0][0] = mat1[1][1];
adj[0][1] = -mat1[0][1];
adj[1][0] = -mat1[1][0];
adj[1][1] = mat1[0][0];
// find the inverse of the matrix by dividing the adjoint by the
determinant
for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
inv[i][j] = (double)adj[i][j] / det;
}
}
cout << "The inverse of the matrix is:\n";
for ( i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << inv[i][j] << " ";
}
 8

cout << endl;

}
getch();
return 0;
}
Output:-
 9

6.Write a program to count the element to given

Array .
Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
int arr[10] = {17, 99, 8, 23, 12, 4, 2, 7, 54, 1};
int count = 0; // Declare a variable to store the number of
elements
// Use the sizeof operator to calculate the number of elements
// Divide the size of the array by the size of one element
count = sizeof(arr) / sizeof(arr[0]);
cout << "The number of elements in the array is: " << count <<
endl;
getch();
return 0;
}
Output:-
 10

7.Write a program to print the all element in the

Array .
Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
int arr[] = {55, 49, 95, 446, 13};
// get the size of the array
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
getch();
return 0;
}
Output:-
 11

8.Write a program to search given number in Array.

Code:-
#include<iostream.h>
#include<conio.h>
int searchNumber(int arr[], int size, int num)
{
for (int i = 0; i < size; i++)
{
if (arr[i] == num)
{
return i; // Return the index of the element
}
}
return -1; // Return -1 if the number is not found
}
int main()
{
int arr[10] = {59, 48, 46, 40, 98, 21, 67, 84, 47, 34};
int num;
cout << "Enter the number to be searched: ";
cin >> num;
// Call the search function and store the result
int result = searchNumber(arr, 10, num);
if (result == -1)
{
cout << "The number " << num << " is not found in the
array." << endl;
}
else
{
cout << "The number " << num << " is found at index " <<
result << " in the array." << endl;
}
getch();
 12

return 0;
}
Output:-
 13

9.Write a program to insert an item into linear Array .

Code:-
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
const int MAX_SIZE = 10;
int arr[MAX_SIZE];
int size;
int item;
int pos; // the position to insert
cout << "Enter the size of the array (less than or equal to " <<
MAX_SIZE << "): ";
cin >> size;
if (size > MAX_SIZE)
{
cout << "Invalid size.\n";
return 0;
}
cout << "Enter " << size << " elements of the array: ";
for (int i = 0; i < size; i++)
{
cin >> arr[i];
}
cout << "Enter the item to insert: ";
cin >> item;
cout << "Enter the position to insert (between 1 and " << size +
1 << "): ";
cin >> pos;
if (pos < 1 || pos > size + 1)
{
cout << "Invalid position.\n";
return 0;
 14

}
// check if the array is full
if (size == MAX_SIZE)
{
cout << "The array is full. Cannot insert.\n";
return 0;
}
// shift the elements from the position to the end of the array
one position forward
for ( i = size; i >= pos; i--)
{
arr[i] = arr[i - 1];
}
// insert the item at the position and update the size of the
array
arr[pos - 1] = item;
size++;
// print the new array
cout << "The new array is: ";
for ( i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
getch();
return 0;
}
Output:-
 15

10.Write a program to delete an item from the linear

Array .
Code:-
#include<iostream.h>
#include<conio.h>
// A function to find the index of an element in an array
int findIndex(int arr[], int n, int x)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == x)
{
return i; // return the index if found
}
}
return -1; // return -1 if not found
}
// A function to delete an element from an array and shift the
remaining elements
int deleteElement(int arr[], int n, int x)
{
int index = findIndex(arr, n, x); // find the index of the element
to delete
if (index == -1)
{
cout << "Element not found" << endl;
return n; // return the original size if not found
}
for (int i = index; i < n - 1; i++)
{
arr[i] = arr[i + 1]; // shift the elements to the left
}
return n - 1; // return the new size after deletion
}
 16

// A function to print an array

void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = {56, 78, 16, 4, 86}; // an example array
int n = sizeof(arr) / sizeof(arr[0]); // the size of the array
int x = 16; // the element to delete
cout << "Array before deletion: " << endl;
printArray(arr, n);
n = deleteElement(arr, n, x); // delete the element and get the
new size
cout << "Array after deletion: " << endl;
printArray(arr, n);
getch();
return 0;
}
Output:-
 17

11.Write a program into search with help of Binary

Searching .
Code:-
#include<iostream.h>
#include<conio.h>

int binarySearch(int arr[],int x,int low,int high)

{
if (low > high) // Base case: the search interval is empty
{
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == x)
{
return mid;
}
else if (arr[mid] > x)
{ // x is smaller than the middle element, so search in the left
half
return binarySearch(arr, x, low, mid - 1);
}
else
{ // x is larger than the middle element, so search in the right
half
return binarySearch(arr, x, mid + 1, high);
}
}
int main()
{
int arr[] = {4, 6, 9, 10, 17, 23, 32, 62, 67, 91};
// The size of the array
int n = sizeof(arr) / sizeof(arr[0]);
int x = 23; // A sample value to be searched
 18

int result = binarySearch(arr, x, 0, n - 1);

if (result == -1)
{
cout << "Element is not present in the array" << endl;
}
else
{
cout << "Element is present at index " << result << endl;
}
getch();
return 0;
}
Output:-
 19

12.Write a program to print the all element of linear

Linked list .
Code:-
#include<iostream.h>
#include<conio.h>
// A struct to represent a node of the linked list
struct Node
{
int data; // The data stored in the node
Node* next; // The pointer to the next node
};
// A class to represent a linked list
class LinkedList
{
private:
Node* head; // The pointer to the head node
Node* tail; // The pointer to the tail node
public:
// A constructor to initialize an empty linked list
LinkedList()
{
head = NULL;
tail = NULL;
}
// A method to insert a new node at the end of the list
void insert(int data)
{
Node* newNode = new Node(); // Create a new node with the
given data
newNode->data = data;
newNode->next = NULL;
// If the list is empty, make the new node the head and the
tail
if (head == NULL)
 20

{
head = newNode;
tail = newNode;
}
// Otherwise, make the new node the tail and update the old
tail's next pointer
else
{
tail->next = newNode;
tail = newNode;
}
}
// A method to print all the elements of the list
void print()
{

Node* temp = head; // Start from the head node

while (temp != NULL)
{
cout << temp->data << " "; // Print the data of the current
node
temp = temp->next; // Move to the next node
}
// Print a new line
cout << endl;
}
};

int main()
{
clrscr();
// Create a linked list object
LinkedList list;
// Insert some elements into the list
 21

list.insert(13);
list.insert(5);
list.insert(7);
list.insert(8);
list.insert(19);
list.print();
getch();
return 0;
}
Output:-
 22

13.Write a program to search an item into Linked list

.
Code:-
#include<iostream.h>
#include<conio.h>

// A class to represent a node of the linked list

class Node
{
public:
int data; // The data stored in the node
Node* next; // The pointer to the next node
// A constructor to initialize a node with the given data
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
// A class to represent a linked list
class LinkedList
{
private:
Node* head; // The pointer to the head node
public:
// A constructor to initialize an empty linked list
LinkedList()
{
head = NULL;
}
// A method to insert a new node at the end of the list
void insert(int data)
{
 23

Node* newNode = new Node(data); // Create a new node with

the given data
// If the list is empty, make the new node the head
if (head == NULL)
{
head = newNode;
}
// Otherwise, find the tail node and update its next pointer
else
{
Node* tail = head;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
// A method to search an item in the list
int search(int item)
{
Node* current = head; // Start from the head node
int index = 0; // Initialize an index variable
while (current != NULL)
{
if (current->data == item)
{
// Return the index of the node where the item is found
return index;
}
current = current->next; // Move to the next node and
increment the index
index++;
}
 24

return -1; // Return -1 if the item is not found in the list

}
};

int main()
{ clrscr();
// Create a linked list object
LinkedList list;
// Insert some elements into the list
list.insert(98);
list.insert(27);
list.insert(23);
list.insert(45);
list.insert(65);
cout << "Searching for 27: " << list.search(27) << endl;
cout << "Searching for 65: " << list.search(65) << endl;
getch();
return 0;
}
Output:-
 25

14.Write a program to find the location of an item

into sorted Linked list .
Code:-
#include<iostream.h>
#include<conio.h>

// Define a node structure for the linked list

struct Node
{
int data; // The data stored in the node
Node* next; // The pointer to the next node
};
// A function to create a new node and return its pointer
Node* createNode(int data)
{
Node* newNode = new Node(); // Allocate memory for the node
newNode->data = data; // Set the data
newNode->next = NULL; // Set the next pointer to NULL
return newNode;
}
// A function to insert a node at the end of a linked list
void insertNode(Node** head, int data)
{
Node* newNode = createNode(data); // Create a new node
if (*head == NULL)
{ // If the list is empty
*head = newNode; // Set the head to the new node
}
else
{ // If the list is not empty
Node* temp = *head; // Create a temporary pointer to the head
while (temp->next != NULL)
{ // Traverse the list until the last node
temp = temp->next; // Move the pointer to the next node
 26

}
temp->next = newNode; // Insert the new node at the end
}
}
// A function to print a linked list
void printList(Node* head)
{
Node* temp = head; // Create a temporary pointer to the head
while (temp != NULL)
{ // Traverse the list until the end
cout << temp->data << " -> "; // Print the data of the node
temp = temp->next; // Move the pointer to the next node
}
cout << "NULL\n"; // Print NULL to indicate the end of the list
}
// A function to find the location of an item in a sorted linked list
int findLocation(Node* head, int item)
{
Node* temp = head; // Create a temporary pointer to the head
int index = 0; // Initialize the index to 0
while (temp != NULL)
{ // Traverse the list until the end
if (temp->data == item)
{ // If the data of the node matches the item
return index; // Return the index of the node
}
temp = temp->next; // Move the pointer to the next node
index++; // Increment the index
}
return -1; // Return -1 if the item is not found
}

int main()
{ clrscr();
 27

Node* head = NULL; // Create an empty linked list

// Insert some nodes in ascending order
insertNode(&head, 2);
insertNode(&head, 6);
insertNode(&head, 7);
insertNode(&head, 10);
insertNode(&head, 15);
cout << "The linked list is:\n";
printList(head);
cout << "The location of 2 is: " << findLocation(head, 2) << "\n";
cout << "The location of 15 is: " << findLocation(head, 15) <<
"\n";
cout << "The location of 7 is: " << findLocation(head, 7) << "\n";
getch();
return 0;
}
Output:-
 28

15.Write a program to insert new node into linked list

as First Node .
Code:-
#include<iostream.h>
#include<conio.h>

// Define a node structure for the linked list

struct Node
{
int data; // The data stored in the node
Node* next; // The pointer to the next node
};
// A function to create a new node and return its pointer
Node* createNode(int data)
{
Node* newNode = new Node(); // Allocate memory for the node
newNode->data = data; // Set the data
newNode->next = NULL; // Set the next pointer to NULL
return newNode; // Return the node pointer
}
// A function to insert a node at the beginning of a linked list
void insertAtHead(Node** head, int data)
{
Node* newNode = createNode(data); // Create a new node
newNode->next = *head; // Link the new node to the head of
the list
*head = newNode; // Update the head pointer to the new node
}
// A function to print a linked list
void printList(Node* head)
{
Node* temp = head; // Create a temporary pointer to the head
while (temp != NULL)
{ // Traverse the list until the end
 29

cout << temp->data << " -> "; // Print the data of the node
temp = temp->next; // Move the pointer to the next node
}
cout << "NULL\n"; // Print NULL to indicate the end of the list
}

int main()
{
Node* head = NULL; // Create an empty linked list
// Insert some nodes at the beginning of the list
insertAtHead(&head, 56);
insertAtHead(&head, 13);
insertAtHead(&head, 35);
insertAtHead(&head, 82);
insertAtHead(&head, 1);
cout << "The linked list is:\n";
printList(head);
getch();
return 0;
}
Output:-
 30

16.Write a program to insert new node into linked list

as Particular Node.
Code:-
#include<iostream.h>
#include<conio.h>
//using namespace std;
// Define a node structure for the linked list
struct Node
{
int data; // The data stored in the node
Node* next; // The pointer to the next node
};
// A function to create a new node and return its pointer
Node* createNode(int data)
{
Node* newNode = new Node(); // Allocate memory for the node
newNode->data = data; // Set the data
newNode->next = NULL; // Set the next pointer to NULL
return newNode; // Return the node pointer
}
// A function to insert a node at a given position in a linked list
void insertAtPosition(Node** head, int data, int position)
{
Node* newNode = createNode(data); // Create a new node
if (position == 0)
{ // If the position is 0, insert at the head
newNode->next = *head; // Link the new node to the head of
the list
*head = newNode; // Update the head pointer to the new node
}
else
{ // If the position is not 0, insert after the previous node
Node* temp = *head; // Create a temporary pointer to the head
int index = 0; // Initialize the index to 0
 31

while (temp != NULL && index < position - 1)

{ // Traverse the list until the previous node or the end
temp = temp->next; // Move the pointer to the next node
index++; // Increment the index
}
if (temp == NULL)
{ // If the position is invalid
cout << "Invalid position\n"; // Print an error message
}
else
{ // If the position is valid
newNode->next = temp->next; // Link the new node to the
next node
temp->next = newNode; // Link the previous node to the new
node
}
}
}
// A function to print a linked list
void printList(Node* head)
{
Node* temp = head; // Create a temporary pointer to the head
while (temp != NULL)
{ // Traverse the list until the end
cout << temp->data << " -> "; // Print the data of the node
temp = temp->next; // Move the pointer to the next node
}
cout << "NULL\n"; // Print NULL to indicate the end of the list
}

int main()
{ clrscr();
Node* head = NULL; // Create an empty linked list
// Insert some nodes at the beginning of the list
 32

insertAtPosition(&head, 5, 0);
insertAtPosition(&head, 10, 0);
insertAtPosition(&head, 15, 0);
insertAtPosition(&head, 20, 0);
cout << "The linked list is:\n";
printList(head);
// Insert some nodes at different positions in the list
insertAtPosition(&head, 0, 4); // Insert at the end
insertAtPosition(&head, 13, 2); // Insert in the middle
insertAtPosition(&head, 23, 0); // Insert at the head
insertAtPosition(&head, 9, 10); // Invalid position
cout << "The linked list is:\n";
printList(head);
getch();
return 0;
}
Output:-
 33

17.Write a program to insert new node into linked list

as End Node.
Code:-
#include<iostream.h>
#include<conio.h>
//using namespace std;
// Define a node structure for the linked list
struct Node
{
int data; // The data stored in the node
Node* next; // The pointer to the next node
};
// A function to create a new node and return its pointer
Node* createNode(int data)
{
Node* newNode = new Node(); // Allocate memory for the node
newNode->data = data; // Set the data
newNode->next = NULL; // Set the next pointer to NULL
return newNode; // Return the node pointer
}
// A function to insert a node at the end of a linked list
void insertAtEnd(Node** head, int data)
{
Node* newNode = createNode(data); // Create a new node
if (*head == NULL)
{ // If the list is empty
*head = newNode; // Set the head to the new node
}
else
{ // If the list is not empty
Node* temp = *head; // Create a temporary pointer to the head
while (temp->next != NULL)
{ // Traverse the list until the last node
temp = temp->next; // Move the pointer to the next node
 34

}
temp->next = newNode; // Link the last node to the new node
}
}
// A function to print a linked list
void printList(Node* head)
{
Node* temp = head; // Create a temporary pointer to the head
while (temp != NULL)
{ // Traverse the list until the end
cout << temp->data << " -> "; // Print the data of the node
temp = temp->next; // Move the pointer to the next node
}
cout << "NULL\n"; // Print NULL to indicate the end of the list
}
// A main function to test the program
int main()
{ clrscr();
Node* head = NULL; // Create an empty linked list
// Insert some nodes at the beginning of the list
insertAtEnd(&head, 8);
insertAtEnd(&head, 4);
insertAtEnd(&head, 16);
insertAtEnd(&head, 8);
insertAtEnd(&head, 6);
cout << "The linked list is:\n";
printList(head);
getch();
return 0;
}
Output:-
 35

18.Write a program to insert an element into Stack .

Code:-
#include<stdio.h>
#include<conio.h>
#define SIZE 4

int top = -1, stack[SIZE];

void push(int element)
{
if (top == SIZE - 1)
{
printf("Stack is full\n");
}
else
{
top = top + 1;
stack[top] = element;
printf("Inserted element: %d\n", element);
}
}
int main()
{
clrscr();
int x;
printf("Enter the element to be inserted: ");
scanf("%d", &x);
push(x);
getch();
return 0;
}
Output:-
 36

19.Write a program to delete an element from Stack .

Code:-
#include <stdio.h>
#include<conio.h>
#define SIZE 3

int top = -1, stack[SIZE];

void pop()
{
if (top == -1)
{
printf("Stack is empty\n");
}
else
{
int x = stack[top];
top = top - 1;
printf("Deleted element: %d\n", x);
}
}

int main()
{
clrscr();
int i;
// insert some elements into the stack
for (i = 0; i < SIZE; i++)
{
top = top + 1;
stack[top] = i + 1;
printf("Inserted element: %d\n", stack[top]);
}
// delete some elements from the stack
for (i = 0; i < SIZE; i++)
 37

{
pop();
}
getch();
return 0;
}
Output:-
 38

20.Write a program to insert an element into Queue .

Code:-
#include<stdio.h>
#include<conio.h>
#define MAX 50

void enqueue(int); // function to insert an element into the queue

void dequeue(); // function to remove an element from the queue
void show(); // function to display the queue contents

int queue[MAX]; // array to store the queue elements

int front = -1; // variable to store the front index of the queue
int rear = -1; // variable to store the rear index of the queue

int main()
{
clrscr();
int choice, item;
while (1)
{
printf("1. Enqueue\n"); // insert an element into the queue
printf("2. Dequeue\n"); // remove an element from the queue
printf("3. Show\n"); // display the queue contents
printf("4. Exit\n"); // exit the program
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the element to be inserted: ");
scanf("%d", &item);
enqueue(item); // call the enqueue function with the item
as argument
break;
 39

case 2:
dequeue(); // call the dequeue function
break;
case 3:
show(); // call the show function
break;
case 4:
return 0; // exit the program
default:
printf("Invalid choice\n");
}
}
}
void enqueue(int item)
{
if (rear == MAX - 1)
{ // check if the queue is full
printf("Queue is full\n");
}
else
{
if (front == -1)
{ // check if the queue is empty
front = 0; // set the front index to 0
}
rear++; // increment the rear index
queue[rear] = item; // insert the item at the rear index
printf("Inserted %d\n", item);
}
}
void dequeue()
{
if (front == -1 || front > rear)
{ // check if the queue is empty
 40

printf("Queue is empty\n");
}
else
{
printf("Deleted %d\n", queue[front]); // print the element at
the front index
front++; // increment the front index
}
}
void show()
{
if (front == -1 || front > rear)
{ // check if the queue is empty
printf("Queue is empty\n");
}
else
{
printf("Queue: ");
for (int i = front; i <= rear; i++)
{ // loop from front to rear index
printf("%d ", queue[i]); // print the element at the current
index
}
printf("\n");
}
}
Output:-
41
 42

21.Write a program to delete an element from Queue

.
Code:-
#include<stdio.h>
#include<conio.h>
#define MAX 50

void enqueue(int); // function to insert an element into the queue

void dequeue(); // function to remove an element from the queue
void show(); // function to display the queue contents

int queue[MAX]; // array to store the queue elements

int front = -1; // variable to store the front index of the queue
int rear = -1; // variable to store the rear index of the queue

int main()
{
clrscr();
int choice, item;
while (1)
{
printf("1. Enqueue\n"); // insert an element into the queue
printf("2. Dequeue\n"); // remove an element from the queue
printf("3. Show\n"); // display the queue contents
printf("4. Exit\n"); // exit the program
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the element to be inserted: ");
scanf("%d", &item);
enqueue(item); // call the enqueue function with the item
as argument
 43

break;
case 2:
dequeue(); // call the dequeue function
break;
case 3:
show(); // call the show function
break;
case 4:
return 0; // exit the program
default:
printf("Invalid choice\n");
}
}
}

void enqueue(int item)

{
if (rear == MAX - 1)
{ // check if the queue is full
printf("Queue is full\n");
}
else
{
if (front == -1)
{ // check if the queue is empty
front = 0; // set the front index to 0
}
rear++; // increment the rear index
queue[rear] = item; // insert the item at the rear index
printf("Inserted %d\n", item);
}
}

void dequeue()
 44

{
if (front == -1 || front > rear)
{ // check if the queue is empty
printf("Queue is empty\n");
}
else
{
printf("Deleted %d\n", queue[front]); // print the element at
the front index
front++; // increment the front index
}
}

void show()
{
if (front == -1 || front > rear)
{ // check if the queue is empty
printf("Queue is empty\n");
}
else
{
printf("Queue: ");
for (int i = front; i <= rear; i++)
{ // loop from front to rear index
printf("%d ", queue[i]); // print the element at the current
index
}
printf("\n");
}
}
Outut:-
45
 46

22.Write a program in Bubble Sort .

Code:-
#include<stdio.h>
#include<conio.h>
// A function to swap two elements in an array
void swap(int* arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A function to implement bubble sort algorithm
void bubbleSort(int arr[], int n)
{
int i, j;
int swapped = 0; // A flag to indicate whether any swap
occurred in the current pass
for (i = 0; i < n - 1; i++)
{
swapped = 0; // Reset the flag for each pass
for (j = 0; j < n - i - 1; j++)
{
// Compare adjacent elements and swap them if they are out
of order
if (arr[j] > arr[j + 1])
{
swap(arr, j, j + 1);
// Set the flag to 1 if any swap occurred
swapped = 1;
}
}
// If no swap occurred in the current pass, the array is
already sorted
if (swapped == 0)
 47

{
break;
}
}
}
// A function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}

int main()
{
clrscr();
int arr[] = {4, 52, 10, 45, 34};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
getch();
return 0;
}
Output:-
 48

23.Write a program to sort the given element using

Quick Sort .
Code:-
#include<iostream.h>
#include<conio.h>
// A function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// A function to partition the array around the pivot
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // Choose the rightmost element as the
pivot
int i = low - 1; // Set the index of the smaller element
// Traverse the array from low to high - 1
for (int j = low; j <= high - 1; j++)
{
// If the current element is smaller than or equal to the
pivot
if (arr[j] <= pivot)
{
i++; // Increment the index of the smaller element
swap(&arr[i], &arr[j]); // Swap the current element with
the smaller element
}
}
swap(&arr[i + 1], &arr[high]); // Swap the pivot element with
the element at i + 1
return i + 1; // Return the index of the pivot element
}
 49

// A function to implement Quick Sort

void quickSort(int arr[], int low, int high)
{
if (low < high) // If the array has more than one element
{
int pi = partition(arr, low, high); // Partition the array and
get the index of the pivot element
quickSort(arr, low, pi - 1); // Recursively sort the left
subarray
quickSort(arr, pi + 1, high); // Recursively sort the right
subarray
}
}
// A function to print the array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
// A driver program to test the Quick Sort function
int main()
{
clrscr();
int arr[] = {21, 19, 45, 48, 79, 85};
int n = sizeof(arr) / sizeof(arr[0]); // Get the size of the array
cout << "Unsorted array: " << endl;
printArray(arr, n);
quickSort(arr, 0, n - 1); // Sort the array using Quick Sort
cout << "Sorted array: " << endl; // Print the array after
sorting
printArray(arr, n);
 50

getch();
return 0;
}
Output:-
 51

24.Write a program to sort the given element using

Insertion Sort .
Code:-
#include<iostream.h>
#include<conio.h>
// A function to sort the array using Insertion Sort
void insertionSort(int arr[], int n)
{
// Loop from the second element to the last element
for (int i = 1; i < n; i++)
{
int key = arr[i]; // Store the current element in a variable
key
int j = i - 1; // Set the index of the previous element
// Compare key with each element on the left of it until an
element smaller than it is found
// or j becomes -1
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j]; // Shift the larger element to the right
j--; // Decrement j
}
arr[j + 1] = key; // Insert key at the correct position
}
}
// A function to print the array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
 52

// A driver program to test the Insertion Sort function

int main()
{
clrscr();
int arr[] = {48, 416, 122, 46, 6};
int n = sizeof(arr) / sizeof(arr[0]); // Get the size of the array
cout << "Unsorted array: " << endl;
printArray(arr, n);
insertionSort(arr, n); // Sort the array using Insertion Sort
cout << "Sorted array: " << endl;
printArray(arr, n);
getch();
return 0;
}
Output:-
 53

25.Write a program to sort the given element using

Selection Sort .
Code:-
#include<iostream.h>
#include<conio.h>
void swap (int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort (int arr [], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr [j] < arr [min_idx])
min_idx = j;
swap (&arr [min_idx], &arr [i]);
}
}

void printArray (int arr [], int size)

{
int i;
for (i=0; i < size; i++)
cout << arr [i] << " ";
cout << endl;
}

int main ()
{
 54

clrscr();
int arr [] = {46, 78, 32, 95, 11};
int n = sizeof(arr)/sizeof(arr [0]);
selectionSort (arr, n);
cout << "Sorted array: ";
printArray (arr, n);
getch();
return 0;
}
Output:-
 55

26.Write a program to print the all nodes of Tree

using Preorder traversal .
Code:-
#include<iostream.h>
#include<conio.h>
// Structure of a Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
Node (int v)
{
data = v;
left = right = NULL;
}
};
// Function to print Preorder traversal
void printPreorder (struct Node* node)
{
if (node == NULL)
return; // Deal with the node
cout << node->data << " ";
printPreorder (node->left); // Recur on left subtree
printPreorder (node->right); // Recur on right subtree
}
// Driver code
int main ()
{
clrscr();
// creat sample tree
/* 5
/ \
2 7
/\ \
 56

1 9 6 */
struct Node* root = new Node (5);
root->left = new Node (2);
root->right = new Node (7);
root->left->left = new Node (1);
root->left->right = new Node (9);
root->right->right = new Node (6);
cout << "Preorder traversal of binary tree is: \n";
printPreorder (root); // Function call
getch();
return 0;
}
Output:-
 57

27.Write a program to print the all nodes of Tree

using Inorder traversal .
Code:-
#include<iostream.h>
#include<conio.h>
// Structure of a Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
Node (int v)
{
data = v;
left = right = NULL;
}
};
// Function to print Inorder traversal
void printInorder (struct Node* node)
{
if (node == NULL)
return;
printInorder (node->left); // Traverse left subtree
cout << node->data << " "; // Print node data
printInorder (node->right); // Traverse right subtree
}
// Driver code
int main ()
{
clrscr();
//creat sample tree
/* 5
/ \
8 3
/\ \
 58

2 7 6 */
struct Node* root = new Node (5);
root->left = new Node (8);
root->right = new Node (3);
root->left->left = new Node (2);
root->left->right = new Node (7);
root->right->right = new Node (6);
cout << "Inorder traversal of binary tree is: \n";
printInorder (root); // Function call
getch();
return 0;
}
Output:-
 59

28.Write a program to print the all nodes of Tree

using Postorder traversal .
Code:-
#include<iostream.h>
#include<conio.h>
// Define a node structure
struct Node
{
int data;
Node* left;
Node* right;
// Constructor to create a new node
Node(int value)
{
data = value;
left = NULL;
right = NULL;
}
};
// Recursive function to print the nodes in postorder
void printPostorder(Node* root)
{
// Base case: if the root is null, return
if (root == NULL)
{
return;
}
printPostorder(root->left); // Recursively print the left subtree
printPostorder(root->right); // Recursively print the right
subtree
cout << root->data << " "; // Print the root data
}
// Driver code to test the program
int main()
 60

{ clrscr();
// Create a sample tree
// 4
// /\
// 6 7
// / \ \
// 8 10 11
Node* root = new Node(4);
root->left = new Node(6);
root->right = new Node(7);
root->left->left = new Node(8);
root->left->right = new Node(10);
root->right->right = new Node(11);
cout << "Postorder traversal of the tree is: " << endl;
printPostorder(root);
cout << endl;
getch();
return 0;
}
Output:-
 61

29.Write a program to insert an item into BST(binary

search tree) .
Code:-
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
// A structure to represent a node in a BST
struct node
{
int data; // The data of the node
struct node *left, *right; // The pointers to the left and right
children
};
// A function to create a new node with a given data
struct node *newNode(int data)
{
struct node *temp = (struct node *)malloc(sizeof(struct node)); //
Allocate memory for the node
temp->data = data; // Assign the data to the node
temp->left = temp->right = NULL; // Initialize the left and right
pointers to NULL
return temp; // Return the node
}
// A function to insert a new node with a given data in a BST
struct node *insert(struct node *root, int data)
{
// If the tree is empty, return a new node
if (root == NULL) return newNode(data);

// Otherwise, recur down the tree

if (data < root->data) // If the data is smaller than the root's
data, insert in the left subtree
root->left = insert(root->left, data);
 62

else if (data > root->data) // If the data is larger than the root's
data, insert in the right subtree
root->right = insert(root->right, data);

// Return the (unchanged) root pointer

return root;
}
// A function to print the inorder traversal of a BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left); // Recur on the left subtree
printf("%d ", root->data); // Print the root's data
inorder(root->right); // Recur on the right subtree
}
}
// A function to create a sample BST and test the insert function
void test()
{
clrscr();
// Create a sample BST with 7 nodes
struct node *root = NULL;
root = insert(root, 48);
root = insert(root, 12);
root = insert(root, 38);
root = insert(root, 14);
root = insert(root, 89);
root = insert(root, 91);
root = insert(root, 82);

// Print the inorder traversal of the BST

printf("Inorder traversal of the BST: ");
inorder(root);
 63

printf("\n");
}
// The main function
int main()
{
test();
getch();
return 0;
}
Output:-
 64

30.Write a program to delete an item from BST(binary

search tree) .
Code:-
#include<iostream.h>
#include<conio.h>
// Define a node structure
struct Node
{
int data;
Node* left;
Node* right;
// Constructor to create a new node
Node(int value)
{
data = value;
left = NULL;
right = NULL;
}
};
// Recursive function to find the minimum value in a BST
Node* findMin(Node* root)
{
// Base case: if the root is null, return null
if (root == NULL)
{
return NULL;
}
// If the root has no left child, it is the minimum value
if (root->left == NULL)
{
return root;
}
// Otherwise, recursively find the minimum in the left subtree
return findMin(root->left);
 65

}
// Recursive function to delete a value from a BST
Node* deleteNode(Node* root, int value)
{
// Base case: if the root is null, return null
if (root == NULL)
{
return NULL;
}
// If the value is smaller than the root, delete it from the left
subtree
if (value < root->data)
{
root->left = deleteNode(root->left, value);
}
// If the value is larger than the root, delete it from the right
subtree
else if (value > root->data)
{
root->right = deleteNode(root->right, value);
}
// If the value is equal to the root, delete the root node
else
{
// If the root has no children, simply delete it
if (root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
// If the root has only one child, replace it with that child
else if (root->left == NULL)
{
Node* temp = root;
 66

root = root->right;
delete temp;
}
else if (root->right == NULL)
{
Node* temp = root;
root = root->left;
delete temp;
}
// If the root has two children, replace it with its inorder
successor
else
{
Node* temp = findMin(root->right); // Find the minimum
value in the right subtree
root->data = temp->data; // Copy the value to the
root
root->right = deleteNode(root->right, temp->data); // Delete
the inorder successor from the right subtree
}
}
return root; // Return the updated root
}
// Recursive function to print the nodes in inorder
void printInorder(Node* root)
{
// Base case: if the root is null, return
if (root == NULL)
{
return;
}
printInorder(root->left); // Recursively print the left subtree
cout << root->data << " "; // Print the root data
printInorder(root->right); // Recursively print the right subtree
 67

}
// Driver code to test the program
int main()
{ clrscr();
// Create a sample tree
// 6
// / \
// 2 7
// / \ / \
// 1 3 5 9
clrscr();
Node* root = new Node(6);
root->left = new Node(2);
root->right = new Node(7);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(9);
cout << "Inorder traversal of the tree is: " << endl;
printInorder(root);
cout << endl;
cout << "Deleting 1..." << endl;
root = deleteNode(root, 1);
cout << "Inorder traversal of the modified tree is: " << endl;
printInorder(root);
cout << endl;
cout << "Deleting 2..." << endl;
root = deleteNode(root, 2);
cout << "Inorder traversal of the modified tree is: " << endl;
printInorder(root);
cout << endl;
cout << "Deleting 6..." << endl;
root = deleteNode(root, 6);
cout << "Inorder traversal of the modified tree is: " << endl;
 68

printInorder(root);
cout << endl;
getch();
return 0;
}
Output:-
 69

31.Write a program to demonstrate BFS(breadth first

search) .
Code:-
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
// A structure to represent a node in an adjacency list
struct node
{
int data; // The data of the node
struct node *next; // A pointer to the next node in the list
};
// A structure to represent an adjacency list
struct list
{
struct node *head; // A pointer to the head node of the list
};
// A structure to represent a graph
struct graph
{
int size; // The number of nodes in the graph
struct list *array; // An array of adjacency lists
};
// A function to create a new node
struct node *newNode(int data)
{
struct node *temp = (struct node *)malloc(sizeof(struct node)); //
Allocate memory for the node
temp->data = data; // Assign the data to the node
temp->next = NULL; // Initialize the next pointer to NULL
return temp; // Return the node
}
// A function to create a graph of a given size
struct graph *createGraph(int size)
 70

{
struct graph *g = (struct graph *)malloc(sizeof(struct graph)); //
Allocate memory for the graph
g->size = size; // Assign the size to the graph
g->array = (struct list *)malloc(size * sizeof(struct list)); //
Allocate memory for the array of lists
for (int i = 0; i < size; i++)
{ // For each list in the array
g->array[i].head = NULL; // Initialize the head pointer to NULL
}
return g; // Return the graph
}
// A function to add an edge to an undirected graph
void addEdge(struct graph *g, int src, int dest)
{
// Add an edge from src to dest
struct node *temp = newNode(dest); // Create a new node for
dest
temp->next = g->array[src].head; // Insert the node at the
beginning of the list
g->array[src].head = temp; // Update the head pointer of the list

// Add an edge from dest to src

temp = newNode(src); // Create a new node for src
temp->next = g->array[dest].head; // Insert the node at the
beginning of the list
g->array[dest].head = temp; // Update the head pointer of the
list
}
// A function to print the BFS traversal of a graph
void bfs(struct graph *g, int start)
{
int *visited = (int *)malloc(g->size * sizeof(int)); // A dynamic
array to mark the visited nodes
 71

for (int i = 0; i < g->size; i++)

{ // For each node in the graph
visited[i] = 0; // Initialize the visited array to 0
}
struct node **queue = (struct node **)malloc(g->size *
sizeof(struct node *)); // A dynamic array to store the nodes to be
visited
int front = 0; // The index of the front of the queue
int rear = 0; // The index of the rear of the queue
queue[rear++] = g->array[start].head; // Enqueue the start node
to the queue
visited[start] = 1; // Mark the start node as visited
printf("BFS traversal: ");
while (front != rear)
{ // While the queue is not empty
struct node *u = queue[front++]; // Dequeue a node from the
queue
printf("%d ", u->data); // Print the node
struct node *v = u->next; // Get the first adjacent node of u
while (v != NULL)
{ // While there are more adjacent nodes of u
if (visited[v->data] == 0)
{ // If the node is not visited
queue[rear++] = g->array[v->data].head; // Enqueue the
node to the queue
visited[v->data] = 1; // Mark the node as visited
}
v = v->next; // Get the next adjacent node of u
}
}
printf("\n");
free(visited); // Free the memory allocated for the visited array
free(queue); // Free the memory allocated for the queue
}
 72

// A function to create a sample graph and test the BFS function

void test()
{
// Create a sample graph with 5 nodes and 6 edges
struct graph *g = createGraph(5);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 3);
addEdge(g, 1, 4);
addEdge(g, 2, 4);
addEdge(g, 3, 4);
// Call the BFS function with node 0 as the start node
bfs(g, 0);
}
// The main function
int main()
{
clrscr();
test();
getch();
return 0;
}
Output:-
 73

32.Write a program to demonstrate DFS(depth first

search) .
Code:-
#include<stdio.h>
#include<conio.h>
#define MAX 5
// maximum number of vertices in the graph
// function to perform DFS traversal
void dfs(int graph[MAX][MAX], int start, int visited[MAX])
{
int i;
// mark the current vertex as visited and print it
visited[start] = 1;
printf("%d ", start);
// loop through the adjacent vertices of the current vertex
for (i = 0; i < MAX; i++)
{
// if the vertex is not visited and there is an edge between
them
if (visited[i] == 0 && graph[start][i] == 1)
{
// recursively call dfs on the adjacent vertex
dfs(graph, i, visited);
}
}
}
// main function
int main()
{
clrscr();
// initialize the graph as a 2D array
int graph[MAX][MAX] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
 74

{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
// initialize the visited array with 0
int visited[MAX] = {0};
// call dfs function with the starting vertex as 0
dfs(graph, 0, visited);
// print a new line
printf("\n");
// return 0 to indicate successful termination
getch();
return 0;
}
Output:-