A

Practical File
On

Data Structures and Algorithm Lab

Submitted In Partial Fulfilment of the requirements for the award of degree of
Bachelor of Technology
In
Computer Science & Engineering
From

Engineering College Bikaner

Affiliated to

Bikaner Technical University, Bikaner

(Session:2023-2027)

Submitted by : Sanjay Kumar Submitted to

University Roll No. : 23EEBCS101 Dr. Rituraj Soni
Assistant Professor
Department of CSE
DSA Practical File Session 2023-27

Program Specific Outcomes (PSOs):

PSO1: Technological Skill: The ability to understand, analyze and develop computer programs in
the areas related to algorithms, system software, multimedia, web design, big data analytics, and
networking for efficient design of computer-based systems of varying complexity.
PSO2: Strategy Development Skill: The ability to apply standard practices and strategies in
software project development using open-ended programming environments to deliver a quality
product for business success.
PSO3: Research Skill: Be able to route their talents in to post graduate and research programs,
promoting remarkable advancements in emerging areas.
PSO4 : Social Enhancement: The ability to apply the knowledge of the technology for social
enhancement and self-improvement.

Course Outcomes (COs)

CO1 Be able to design and analyze the time and space efficiency of the data structure.
CO2 Be capable to identity the appropriate data structure for given problem.
CO3 Have practical knowledge on the applications of data structures.
CO4 To design and implementation of various basic and advanced data structures.

CO5 To introduce various techniques for representation of the data in the real world.

1
DSA Practical File Session 2023-27

INDEX

S.N Name of Practical Date Signature

1. Write an C code for insertion and deletion of element in 1-D Array.
2. Let A and B be two 2D Arrays
a. Write a C Code for adding elements of arrays A and B.
b. Write C Code for subtracting elements of arrays A and B.
c. Write C Code for multiplication of elements of Arrays A and B.
3. Write algorithm and C Program to implement for the following sorting.
Also write the time and space complexity of each algorithm.
a) Bubble Sort
b) Insertion Sort
c) Shell Sort
d) Selection Sort
e) Merge Sort
f) Quick Sort
g) Heap Sort
h) Radix Sort
i) Counting Sort
4. Write a C Code to implement Linear Search in Array.
5. Write a C Code to implement Binary Search in Array.
6. Write a program in C to implement PUSH and POP in stack using
arrays.
7. Write a program in C to implement stack using Linked List.
8. Write a program for factorial calculation and Fibonacci series
calculation using recursion.
9. Write a C program to convert infix expression in postfix and prefix
using stack.
10. Write a C program to evaluate postfix expression using Stack.
11. Write a C Program for insertion and deletion in Linear Queue.
12. Write a C program for insertion and deletion elements in Circular
Queue.
13. Write a program in C to implement Linear Queue using Linked List.
14. Write a C Program to insertion and deletion operation in single linked
List.
15. Write a C Program to insertion and deletion operation in double linked
List.
16. Write a C program for creating, insertion, deletion and searching in
Binary search tree
17. Write a C Program to implement BFS algorithm in Graph.
18. Write a C Program to implement DFS algorithm in Graph.
19. Write a C Program to implement Kruskal Algorithm in Graph.
20. Write a C Program to implement Prims Algorithm in Graph.

2
DSA Practical File Session 2023-27

Program 1: Write an C code for insertion and deletion of element in 1-D Array.

#include <stdio.h>

#define MAX_SIZE 100

void insert(int arr[], int *size, int element, int position) {

if (*size >= MAX_SIZE) {
printf("Array is full. Cannot insert.\n");
return;
}

if (position < 0 || position > *size) {

printf("Invalid position.\n");
return;
}

for (int i = *size; i > position; i--) {

arr[i] = arr[i - 1];
}

arr[position] = element;
(*size)++;
}

void delete(int arr[], int *size, int position) {

if (*size == 0) {
printf("Array is empty. Cannot delete.\n");
return;
}

if (position < 0 || position >= *size) {

printf("Invalid position.\n");
return;
}

for (int i = position; i < *size - 1; i++) {

arr[i] = arr[i + 1];
}

(*size)--;
}

void printArray(int arr[], int size) {

printf("Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[MAX_SIZE];
int size = 0;
insert(arr, &size, 10, 0);
insert(arr, &size, 20, 1);
3
DSA Practical File Session 2023-27

insert(arr, &size, 30, 2);

insert(arr, &size, 40, 1);

printf("After insertion:\n");
printArray(arr, size);

delete(arr, &size, 1);

printf("After deletion:\n");
printArray(arr, size);

returrn ;
}

Output
After insertion:
Array: 10 40 20 30
After deletion:
Array: 10 20 30

4
DSA Practical File Session 2023-27

Program 2 : Let A and B be two 2D arrays

a.Write a C code for adding elements of arrays A and B

#include <stdio.h>

#define ROWS 3
#define COLS 3

void addArrays(int A[ROWS][COLS], int B[ROWS][COLS], int result[ROWS][COLS]) {

for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
result[i][j] = A[i][j] + B[i][j];
}
}
}

void printArray(int arr[ROWS][COLS]) {

for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}

int main() {
int A[ROWS][COLS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int B[ROWS][COLS] = {{10, 11, 12}, {13, 14, 15}, {16, 17, 18}};
int result[ROWS][COLS];

printf("Array A:\n");
printArray(A);

printf("Array B:\n");
printArray(B);

addArrays(A, B, result);

printf("Result (A + B):\n");
printArray(result);

return 0;
}
``"

Output
Array A:
123
456
789
Array B:
10 11 12
13 14 15
16 17 18
Result (A + B):
5
DSA Practical File Session 2023-27

11 13 15
17 19 21
23 25 27

b. Write a C code for subtracting elements of arrays A and B

#include <stdio.h>

#define ROWS 3
#define COLS 3

void subtractArrays(int A[ROWS][COLS], int B[ROWS][COLS], int result[ROWS][COLS]) {

for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
result[i][j] = A[i][j] - B[i][j];
}
}
}

void printArray(int arr[ROWS][COLS]) {

for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}

int main() {
int A[ROWS][COLS] = {{10, 20, 30}, {40, 50, 60}, {70, 80, 90}};
int B[ROWS][COLS] = {{5, 10, 15}, {20, 25, 30}, {35, 40, 45}};
int result[ROWS][COLS];

printf("Array A:\n");
printArray(A);

printf("Array B:\n");
printArray(B);

subtractArrays(A, B, result);

printf("Result (A - B):\n");
printArray(result);

return 0;
}
``

Output
Array A:
10 20 30
40 50 60
70 80 90
Array B:
5 10 15
6
DSA Practical File Session 2023-27

20 25 30
35 40 45
Result (A - B):
5 10 15
20 25 30
35 40 45

c. Write a C code for multiplication of elements of array A and B

#include <stdio.h>

#define ROWS_A 3
#define COLS_A 3
#define ROWS_B 3
#define COLS_B 3

void multiplyArrays(int A[ROWS_A][COLS_A], int B[ROWS_B][COLS_B], int result[ROWS_A][COLS_B])

{
for (int i = 0; i < ROWS_A; i++) {
for (int j = 0; j < COLS_B; j++) {
result[i][j] = 0;
for (int k = 0; k < COLS_A; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
}

void printArray(int arr[ROWS_A][COLS_B]) {

for (int i = 0; i < ROWS_A; i++) {
for (int j = 0; j < COLS_B; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}

int main() {
int A[ROWS_A][COLS_A] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int B[ROWS_B][COLS_B] = {{10, 11, 12}, {13, 14, 15}, {16, 17, 18}};
int result[ROWS_A][COLS_B];

printf("Array A:\n");
printArray(A);

printf("Array B:\n");
printArray(B);

multiplyArrays(A, B, result);

printf("Result (A * B):\n");
printArray(result);

return 0;
}
```
7
DSA Practical File Session 2023-27

Output:

Array A:
123
456
789
Array B:
10 11 12
13 14 15
16 17 18
Result (A * B):
84 90 96
201 216 231
318 342 366

8
DSA Practical File Session 2023-27

Program 3: Write the algorithm and C program to implement for the following sorting.
Also write the time and space complexity of each algorithm.

a.Bubble Sort

Algorithm:

1. Start from the first element of the array.

2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Repeat steps 2-3 until the end of the array is reached.
5. Repeat steps 1-4 until no more swaps are needed.

C Program:

#include <stdio.h>

void swap(int *a, int *b) {

int temp = *a;
*a = *b;
*b = temp;
}

void bubbleSort(int arr[], int n) {

int i, j;
for (i = 0; i < n - 1; i++) {
int swapped = 0;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break;
}
}

void printArray(int arr[], int n) {

int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);
9
DSA Practical File Session 2023-27

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n) - already sorted array

- Average-case: O(n^2)
- Worst-case: O(n^2)

Space Complexity:

- O(1)

b.Insertion Sort

Algorithm:

1. Start from the second element (index 1) of the array.

2. Compare the current element with the previous elements.
3. Shift the previous elements to the right until a smaller element is found.
4. Insert the current element at the correct position.
5. Repeat steps 2-4 until the end of the array is reached.

C Program:

#include <stdio.h>

void insertionSort(int arr[], int n) {

int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int n) {

int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

10
DSA Practical File Session 2023-27

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

insertionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n) - already sorted array

- Average-case: O(n^2)
- Worst-case: O(n^2)

Space Complexity:

- O(1)

c.Shell Sort

Algorithm:

1. Choose an initial gap size (h).

2. Divide the array into subarrays of size h.
3. Perform insertion sort on each subarray.
4. Reduce the gap size (h) by half.
5. Repeat steps 2-4 until h = 1.

C Program:

#include <stdio.h>

void insertionSort(int arr[], int n, int gap) {

int i, key, j;
for (i = gap; i < n; i++) {
key = arr[i];
j = i - gap;

while (j >= 0 && arr[j] > key) {

arr[j + gap] = arr[j];
j = j - gap;
}
arr[j + gap] = key;
}
11
DSA Practical File Session 2023-27

void shellSort(int arr[], int n) {

int gap = n / 2;

while (gap > 0) {

insertionSort(arr, n, gap);
gap = gap / 2;
}
}

void printArray(int arr[], int n) {

int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

shellSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n log n) - when using optimal gap sequence

- Average-case: O(n log n)
- Worst-case: O(n^2) - when using poor gap sequence

Space Complexity:

- O(1)

d.Selection Sort

Algorithm:

1. Start from the first element (index 0) of the array.

2. Find the minimum element in the unsorted portion of the array.
3. Swap the found minimum element with the first element of the unsorted portion.
12
DSA Practical File Session 2023-27

4. Repeat steps 2-3 until the entire array is sorted.

C Program:

#include <stdio.h>

void selectionSort(int arr[], int n) {

int i, j, minIndex, temp;

for (i = 0; i < n - 1; i++) {

minIndex = i;

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

void printArray(int arr[], int n) {

int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

selectionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

13
DSA Practical File Session 2023-27

- Best-case: O(n^2)
- Average-case: O(n^2)
- Worst-case: O(n^2)

Space Complexity:

- O(1)

e.Merge Sort

Algorithm:

1. Divide the array into two halves.

2. Recursively sort each half.
3. Merge the sorted halves.

C Program:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;
int n2 = right - mid;

int leftArr[n1], rightArr[n2];

for (int i = 0; i < n1; i++) {

leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[mid + 1 + j];
}

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
14
DSA Practical File Session 2023-27

void mergeSort(int arr[], int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n log n)

- Average-case: O(n log n)
- Worst-case: O(n log n)

Space Complexity:

- O(n)

f.Quuck Sort

Algorithm:

1. Choose a pivot element.

2. Partition the array around the pivot.
3. Recursively sort the subarrays.
15
DSA Practical File Session 2023-27

C Program:

#include <stdio.h>

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);

quickSort(arr, low, pivot - 1);

quickSort(arr, pivot + 1, high);
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
16
DSA Practical File Session 2023-27

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n log n)

- Average-case: O(n log n)
- Worst-case: O(n^2)

Space Complexity:

- O(log n)
g.Heap Sort

Algorithm:

1. Build a max heap.

2. Swap the root (maximum) with the last element.
3. Heapify the reduced heap.
4. Repeat steps 2-3 until the heap is empty.

C Program:

#include <stdio.h>

void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--) {

int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
17
DSA Practical File Session 2023-27

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

heapSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

- Best-case: O(n log n)

- Average-case: O(n log n)
- Worst-case: O(n log n)

Space Complexity:

- O(1)

h.Radix Sort

Algorithm:

1. Find the maximum number to determine the number of digits.

2. Initialize 10 buckets (one for each digit 0-9).
3. Iterate through each digit position (from least significant to most significant):
a. Distribute numbers into buckets based on the current digit.
b. Collect numbers from buckets back into the array.
4. Repeat step 3 until all digit positions are processed.

C Program:

#include <stdio.h>

#define MAX_DIGITS 10

int getDigit(int num, int pos) {

18
DSA Practical File Session 2023-27

return (num / (int)pow(10, pos)) % 10;

}

void radixSort(int arr[], int n) {

int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}

int digits = 0;
while (max > 0) {
digits++;
max /= 10;
}

for (int i = 0; i < digits; i++) {

int buckets[MAX_DIGITS] = {0};
int output[n];

for (int j = 0; j < n; j++) {

int digit = getDigit(arr[j], i);
buckets[digit]++;
}

for (int j = 1; j < MAX_DIGITS; j++) {

buckets[j] += buckets[j - 1];
}

for (int j = n - 1; j >= 0; j--) {

int digit = getDigit(arr[j], i);
output[buckets[digit] - 1] = arr[j];
buckets[digit]--;
}

for (int j = 0; j < n; j++) {

arr[j] = output[j];
}
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

19
DSA Practical File Session 2023-27

radixSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 170 45 75 90 802 24 2 66
Sorted array: 2 24 45 66 75 90 170 802

Time Complexity:

- Best-case: O(nk)
- Average-case: O(nk)
- Worst-case: O(nk)

where n is the number of elements and k is the number of digits in the maximum number.

Space Complexity:

- O(n + k)

where n is the number of elements and k is the number of buckets.

i.Counting Sort

Algorithm:

1. Find the maximum element in the array.

2. Initialize a count array with size equal to the maximum element + 1.
3. Count the occurrences of each element in the array.
4. Calculate cumulative counts.
5. Build the output array.

C Program:

#include <stdio.h>

void countingSort(int arr[], int n) {

int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}

int count[max + 1] = {0};

for (int i = 0; i < n; i++) {
count[arr[i]]++;
}

for (int i = 1; i <= max; i++) {

count[i] += count[i - 1];
20
DSA Practical File Session 2023-27

int output[n];

for (int i = n - 1; i >= 0; i--) {

output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}

for (int i = 0; i < n; i++) {

arr[i] = output[i];
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

countingSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

Output
Original array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Time Complexity:

- Best-case: O(n + k)
- Average-case: O(n + k)
- Worst-case: O(n + k)

where n is the number of elements and k is the range of input.

Space Complexity:

- O(n + k)

21
DSA Practical File Session 2023-27

Program 4:Write a C code to implement linear search in array .

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return index if target is found
}
}
return -1; // Return -1 if target is not found
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target;

printf("Array: ");
printArray(arr, n);

printf("Enter the target element: ");

scanf("%d", &target);

int result = linearSearch(arr, n, target);

if (result == -1) {
printf("Target element not found in the array.\n");
} else {
printf("Target element found at index %d.\n", result);
}

return 0;
}

Output
Array: 2 5 8 12 16 23 38 56 72 91
Enter the target element: 23
Target element found at index 5.

22
DSA Practical File Session 2023-27

Program 5:Write a C code to implement binary search tree.

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {

int low = 0;
int high = n - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == target) {
return mid; // Return index if target is found
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Return -1 if target is not found
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target;

printf("Array: ");
printArray(arr, n);

printf("Enter the target element: ");

scanf("%d", &target);

int result = binarySearch(arr, n, target);

if (result == -1) {
printf("Target element not found in the array.\n");
} else {
printf("Target element found at index %d.\n", result);
}

return 0;
}

Output
Array: 2 5 8 12 16 23 38 56 72 91
Enter the target element: 23
Target element found at index 5.
23
DSA Practical File Session 2023-27

Program 6:Write a program in C to implement PUSH and POP in stack using arrays.

#include <stdio.h>

#define MAX_SIZE 5

int stack[MAX_SIZE];
int top = -1;

int isEmpty() {
return (top == -1);
}

int isFull() {
return (top == MAX_SIZE - 1);
}

void push(int element) {

if (isFull()) {
printf("Stack Overflow! Cannot push %d onto the stack.\n", element);
} else {
stack[++top] = element;
printf("%d pushed onto the stack.\n", element);
}
}
int pop() {
if (isEmpty()) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return -1;
} else {
return stack[top--];
}
}
void printStack() {
printf("Stack: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
int main() {
push(10);
push(20);
push(30);
printStack();
printf("Popped element: %d\n", pop());
printStack();
push(40);
push(50);
printStack();
printf("Popped element: %d\n", pop());
printf("Popped element: %d\n", pop());
printf("Popped element: %d\n", pop());
printf("Popped element: %d\n", pop());
24
DSA Practical File Session 2023-27

printf("Popped element: %d\n", pop());

return 0;
}

Output
10 pushed onto the stack.
20 pushed onto the stack.
30 pushed onto the stack.
Stack: 10 20 30
Popped element: 30
Stack: 10 20
40 pushed onto the stack.
50 pushed onto the stack.
Stack: 10 20 40 50
Popped element: 50
Popped element: 40
Popped element: 20
Popped element: 10
Stack Underflow! Cannot pop from an empty stack.

25
DSA Practical File Session 2023-27

Program 7:Write a program in C to implement stack using Linked List .

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

typedef struct Node {

int data;
struct Node* next;
} Node;

typedef struct {
Node* top;
} Stack;

Node* createNode(int data) {

Node* newNode = (Node*) malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

Stack* createStack() {
Stack* stack = (Stack*) malloc(sizeof(Stack));
if (!stack) {
printf("Memory error\n");
return NULL;
}
stack->top = NULL;
return stack;
}

int isEmpty(Stack* stack) {

return stack->top == NULL;
}

void push(Stack* stack, int data) {

Node* newNode = createNode(data);
if (isEmpty(stack)) {
stack->top = newNode;
} else {
newNode->next = stack->top;
stack->top = newNode;
}
}

int pop(Stack* stack) {

if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack.\n");
return -1;
}
int popped = stack->top->data;
Node* temp = stack->top;
26
DSA Practical File Session 2023-27

stack->top = stack->top->next;
free(temp);
return popped;
}

int peek(Stack* stack) {

if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->top->data;
}

void printStack(Stack* stack) {

Node* temp = stack->top;
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

int main() {
Stack* stack = createStack();
push(stack, 10);
push(stack, 20);
push(stack, 30);
printStack(stack); // Output: 30 20 10
printf("Popped element: %d\n", pop(stack)); // Output: 30
printStack(stack); // Output: 20 10
printf("Top element: %d\n", peek(stack)); // Output: 20

return 0;
}

27
DSA Practical File Session 2023-27

Program 8:Write a program for factorial calculation and Fibonacci series calculation using recursion.

Factorial Calculation using Recursion*

#include <stdio.h>

long factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

int main() {
int num;
printf("Enter a positive integer: ");
scanf("%d", &num);

if (num < 0) {
printf("Factorial of negative numbers is not defined.\n");
} else {
printf("Factorial of %d = %ld\n", num, factorial(num));
}

return 0;
}

Output
Enter a positive integer: 5
Factorial of 5 = 120

Fibonacci Series Calculation using Recursion

#include <stdio.h>

int fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

int main() {
int n;
printf("Enter the number of terms in the Fibonacci series: ");
scanf("%d", &n);

printf("Fibonacci Series: ");

for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
28
DSA Practical File Session 2023-27

return 0;
}

Output
Enter the number of terms in the Fibonacci series: 10
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34

29
DSA Practical File Session 2023-27

Program 9:Write a C program to convert infix expression in postfix and prefix using stack .

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

#define MAX_SIZE 100

int isEmpty(char stack[], int top) {

return top == -1;
}

int isFull(int top) {

return top == MAX_SIZE - 1;
}

void push(char stack[], char element, int* top) {

if (isFull(*top)) {
printf("Stack Overflow!\n");
} else {
stack[++(*top)] = element;
}
}

char pop(char stack[], int* top) {

if (isEmpty(stack, *top)) {
printf("Stack Underflow!\n");
return '\0';
} else {
return stack[(*top)--];
}
}

char peek(char stack[], int top) {

if (isEmpty(stack, top)) {
return '\0';
} else {
return stack[top];
}
}

int precedence(char operator) {

switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return 0;
}
30
DSA Practical File Session 2023-27

void infixToPostfix(char infix[], char postfix[]) {

char stack[MAX_SIZE];
int top = -1;
int i = 0, j = 0;

while (infix[i] != '\0') {

if (isalpha(infix[i])) {
postfix[j++] = infix[i++];
} else if (infix[i] == '(') {
push(stack, infix[i++], &top);
} else if (infix[i] == ')') {
while (peek(stack, top) != '(') {
postfix[j++] = pop(stack, &top);
}
pop(stack, &top); // Remove '('
i++;
} else {
while (!isEmpty(stack, top) && precedence(infix[i]) <= precedence(peek(stack, top))) {
postfix[j++] = pop(stack, &top);
}
push(stack, infix[i++], &top);
}
}

while (!isEmpty(stack, top)) {

postfix[j++] = pop(stack, &top);
}

postfix[j] = '\0';
}

void infixToPrefix(char infix[], char prefix[]) {

char stack[MAX_SIZE];
int top = -1;
int i = strlen(infix) - 1, j = strlen(infix) - 1;

while (i >= 0) {
if (isalpha(infix[i])) {
prefix[j--] = infix[i--];
} else if (infix[i] == ')') {
push(stack, infix[i--], &top);
} else if (infix[i] == '(') {
while (peek(stack, top) != ')') {
prefix[j--] = pop(stack, &top);
}
pop(stack, &top); // Remove ')'
i--;
} else {
while (!isEmpty(stack, top) && precedence(infix[i]) < precedence(peek(stack, top))) {
prefix[j--] = pop(stack, &top);
}
push(stack, infix[i--], &top);
}
}
31
DSA Practical File Session 2023-27

while (!isEmpty(stack, top)) {

prefix[j--] = pop(stack, &top);
}
}

int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE], prefix[MAX_SIZE];

printf("Enter an infix expression: ");

scanf("%s", infix);

infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);

infixToPrefix(infix, prefix);
printf("Prefix expression: %s\n", prefix);

return 0;
}

Output
Enter an infix expression: A+B*C
Postfix expression: ABC*+
Prefix expression: +A*BC

32
DSA Practical File Session 2023-27

Program 10: Write a C program to evaluate postfix expression using stack .

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

#define MAX_SIZE 100

int isEmpty(int stack[], int top) {

return top == -1;
}

int isFull(int top) {

return top == MAX_SIZE - 1;
}

void push(int stack[], int element, int* top) {

if (isFull(*top)) {
printf("Stack Overflow!\n");
} else {
stack[++(*top)] = element;
}
}

int pop(int stack[], int* top) {

if (isEmpty(stack, *top)) {
printf("Stack Underflow!\n");
return -1;
} else {
return stack[(*top)--];
}
}

int evaluatePostfix(char postfix[]) {

int stack[MAX_SIZE];
int top = -1;
int i;

for (i = 0; i < strlen(postfix); i++) {

if (isdigit(postfix[i])) {
push(stack, postfix[i] - '0', &top); // Convert char to int
} else {
int operand2 = pop(stack, &top);
int operand1 = pop(stack, &top);

switch (postfix[i]) {
case '+':
push(stack, operand1 + operand2, &top);
break;
case '-':
push(stack, operand1 - operand2, &top);
break;
case '*':
push(stack, operand1 * operand2, &top);
break;
33
DSA Practical File Session 2023-27

case '/':
if (operand2 != 0) {
push(stack, operand1 / operand2, &top);
} else {
printf("Error: Division by zero!\n");
return -1;
}
break;
}
}
}

return stack[top];
}

int main() {
char postfix[MAX_SIZE];

printf("Enter a postfix expression: ");

scanf("%s", postfix);

int result = evaluatePostfix(postfix);

if (result != -1) {
printf("Result: %d\n", result);
}

return 0;
}

Output
Enter a postfix expression: 23+45-*
Result: 16

34
DSA Practical File Session 2023-27

Program 11:Write a C program for insertion and deletion in Linear Queue.

#include <stdio.h>

#define MAX_SIZE 5

typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;

void createQueue(Queue* q) {
q->front = q->rear = -1;
}

int isEmpty(Queue* q) {
return q->front == -1;
}

int isFull(Queue* q) {
return q->rear == MAX_SIZE - 1;
}

void enqueue(Queue* q, int element) {

if (isFull(q)) {
printf("Queue Overflow! Cannot insert %d into the queue.\n", element);
} else if (isEmpty(q)) {
q->front = q->rear = 0;
q->data[q->rear] = element;
} else {
q->rear++;
q->data[q->rear] = element;
}
}

int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Cannot delete from an empty queue.\n");
return -1;
} else if (q->front == q->rear) {
int deleted = q->data[q->front];
q->front = q->rear = -1;
return deleted;
} else {
return q->data[q->front++];
}
}

void displayQueue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
} else {
printf("Queue: ");
for (int i = q->front; i <= q->rear; i++) {
35
DSA Practical File Session 2023-27

printf("%d ", q->data[i]);

}
printf("\n");
}
}

int main() {
Queue q;
createQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
displayQueue(&q);

printf("Dequeued element: %d\n", dequeue(&q));

displayQueue(&q);

enqueue(&q, 40);
enqueue(&q, 50);
displayQueue(&q);

printf("Dequeued element: %d\n", dequeue(&q));

displayQueue(&q);

return 0;
}

Output
Initial Queue:
Queue is empty.

Inserting elements...
Queue after insertion:
Queue: 10 20 30 40 50
Dequeued element: 10
Queue after deletion:
Queue: 20 30 40 50
Dequeued element: 20
Queue after deletion:
Queue: 30 40 50

36
DSA Practical File Session 2023-27

Program 12:Write a C program for insertion and deletion elements in circular Queue.

#include <stdio.h>

#define MAX_SIZE 5

typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} CircularQueue;

void createQueue(CircularQueue* q) {
q->front = q->rear = -1;
}

int isEmpty(CircularQueue* q) {
return q->front == -1;
}

int isFull(CircularQueue* q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}

void enqueue(CircularQueue* q, int element) {

if (isFull(q)) {
printf("Queue Overflow! Cannot insert %d into the queue.\n", element);
} else if (isEmpty(q)) {
q->front = q->rear = 0;
q->data[q->rear] = element;
} else {
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = element;
}
}

int dequeue(CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Cannot delete from an empty queue.\n");
return -1;
} else if (q->front == q->rear) {
int deleted = q->data[q->front];
q->front = q->rear = -1;
return deleted;
} else {
int deleted = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return deleted;
}
}

void displayQueue(CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
} else {
37
DSA Practical File Session 2023-27

printf("Queue: ");
int i = q->front;
do {
printf("%d ", q->data[i]);
i = (i + 1) % MAX_SIZE;
} while (i != (q->rear + 1) % MAX_SIZE);
printf("\n");
}
}

int main() {
CircularQueue q;
createQueue(&q);

printf("Initial Queue: \n");

displayQueue(&q);

printf("Inserting elements...\n");
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50);

printf("Queue after insertion: \n");

displayQueue(&q);

printf("Dequeued element: %d\n", dequeue(&q));

printf("Queue after deletion: \n");
displayQueue(&q);

printf("Dequeued element: %d\n", dequeue(&q));

printf("Queue after deletion: \n");
displayQueue(&q);

return 0;
}

Output
Initial Queue:
Queue is empty.

Inserting elements...
Queue after insertion:
Queue: 10 20 30 40 50
Dequeued element: 10
Queue after deletion:
Queue: 20 30 40 50
Dequeued element: 20
Queue after deletion:
Queue: 30 40 50

38
DSA Practical File Session 2023-27

Program 13:Write a program in C to implement linear queue using Linked List.

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

typedef struct Node {

int data;
struct Node* next;
} Node;

typedef struct {
Node* front;
Node* rear;
} Queue;

Node* createNode(int data) {

Node* newNode = (Node*) malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

Queue* createQueue() {
Queue* q = (Queue*) malloc(sizeof(Queue));
if (!q) {
printf("Memory error\n");
return NULL;
}
q->front = q->rear = NULL;
return q;
}

int isEmpty(Queue* q) {
return q->front == NULL;
}

void enqueue(Queue* q, int data) {

Node* newNode = createNode(data);
if (q->rear) {
q->rear->next = newNode;
q->rear = newNode;
} else {
q->front = q->rear = newNode;
}
}

int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
39
DSA Practical File Session 2023-27

int data = q->front->data;

Node* temp = q->front;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return data;
}

void displayQueue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
} else {
Node* temp = q->front;
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}

int main() {
Queue* q = createQueue();

enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);

printf("Queue: ");
displayQueue(q);

printf("Dequeued element: %d\n", dequeue(q));

printf("Queue: ");
displayQueue(q);

printf("Dequeued element: %d\n", dequeue(q));

printf("Queue: ");
displayQueue(q);

return 0;
}

Output
Queue: 10 20 30 40 50
Dequeued element: 10
Queue: 20 30 40 50
Dequeued element: 20
Queue: 30 40 50

40
DSA Practical File Session 2023-27

Program 14:Write a C program to insertion and deletion operation in single linked list.

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

typedef struct Node {

int data;
struct Node* next;
} Node;

Node* createNode(int data) {

Node* newNode = (Node*) malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void insertAtBeginning(Node** head, int data) {

Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
*head = newNode;
}
}

void insertAtEnd(Node** head, int data) {

Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}

void insertAtPosition(Node** head, int data, int position) {

Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else if (position == 0) {
newNode->next = *head;
*head = newNode;
} else {
Node* temp = *head;
for (int i = 0; i < position - 1; i++) {
if (!temp->next) {
41
DSA Practical File Session 2023-27

printf("Position out of range\n");

return;
}
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}

void deleteFromBeginning(Node** head) {

if (*head == NULL) {
printf("List is empty\n");
} else {
Node* temp = *head;
*head = (*head)->next;
free(temp);
}
}

void deleteFromEnd(Node** head) {

if (*head == NULL) {
printf("List is empty\n");
} else if (!(*head)->next) {
free(*head);
*head = NULL;
} else {
Node* temp = *head;
while (temp->next->next) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
}

void deleteAtPosition(Node** head, int position) {

if (*head == NULL) {
printf("List is empty\n");
} else if (position == 0) {
Node* temp = *head;
*head = (*head)->next;
free(temp);
} else {
Node* temp = *head;
for (int i = 0; i < position - 1; i++) {
if (!temp->next) {
printf("Position out of range\n");
return;
}
temp = temp->next;
}
if (!temp->next) {
printf("Position out of range\n");
return;
}
42
DSA Practical File Session 2023-27

Node* nodeToDelete = temp->next;

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

void displayList(Node* head) {

if (head == NULL) {
printf("List is empty\n");
} else {
while (head) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
}

int main() {
Node* head = NULL;

insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtEnd(&head, 30);
insertAtPosition(&head, 40, 2);

printf("Linked List: ");

displayList(head);

deleteFromBeginning(&head);
deleteFromEnd(&head);
deleteAtPosition(&head, 1);

printf("Linked List after deletion: ");

displayList(head);

return 0;
}

Output
Linked List: 20 10 40 30
Linked List after deletion: 10 30

43
DSA Practical File Session 2023-27

Program 15:Write a C program to insertion and deletion operation in double linked list.

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

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

void insertAtBeginning(struct Node** head, int data) {

struct Node* newNode = createNode(data);
if (*head != NULL) {
newNode->next = *head;
(*head)->prev = newNode;
}
*head = newNode;
printf("Inserted %d at the beginning.\n", data);
}

void insertAtEnd(struct Node** head, int data) {

struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
printf("Inserted %d at the end.\n", data);
}

void deleteFromBeginning(struct Node** head) {

if (*head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
printf("Deleted %d from the beginning.\n", temp->data);
44
DSA Practical File Session 2023-27

free(temp);
}

void deleteFromEnd(struct Node** head) {

if (*head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head;
if (temp->next == NULL) {
*head = NULL;
} else {
while (temp->next != NULL) {
temp = temp->next;
}
temp->prev->next = NULL;
}
printf("Deleted %d from the end.\n", temp->data);
free(temp);
}

void displayList(struct Node* head) {

if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

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

insertAtBeginning(&head, 10);
insertAtBeginning(&head, 5);
insertAtEnd(&head, 20);
insertAtEnd(&head, 25);
displayList(head);

deleteFromBeginning(&head);
displayList(head);
deleteFromEnd(&head);
displayList(head);

return 0;
}

Output

Inserted 10 at the beginning.

45
DSA Practical File Session 2023-27

Inserted 5 at the beginning.

Inserted 20 at the end.
Inserted 25 at the end.
Doubly Linked List: 5 10 20 25
Deleted 5 from the beginning.
Doubly Linked List: 10 20 25
Deleted 25 from the end.
Doubly Linked List: 10 20

46
DSA Practical File Session 2023-27

Program 16:Write a C program for creating, insertion, deletion and searching in Binary Search Tree.

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

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

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

struct Node* insert(struct Node* root, int data) {

if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else if (data > root->data) root->right = insert(root->right, data);
return root;
}

struct Node* minValueNode(struct Node* node) {

struct Node* current = node;
while (current && current->left != NULL) current = current->left;
return current;
}

struct Node* deleteNode(struct Node* root, int data) {

if (root == NULL) return root;
if (data < root->data) root->left = deleteNode(root->left, data);
else if (data > root->data) root->right = deleteNode(root->right, data);
else {
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
struct Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

struct Node* search(struct Node* root, int data) {

if (root == NULL || root->data == data) return root;
if (data < root->data) return search(root->left, data);
47
DSA Practical File Session 2023-27

return search(root->right, data);

}

void inorder(struct Node* root) {

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

int main() {
struct Node* root = NULL;
int choice, data;
while (1) {
printf("\n1. Insert\n2. Delete\n3. Search\n4. Inorder Traversal\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &data);
struct Node* found = search(root, data);
if (found) printf("Value %d found in the BST.\n", data);
else printf("Value %d not found in the BST.\n", data);
break;
case 4:
printf("Inorder traversal: ");
inorder(root);
printf("\n");
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

Output
1. Insert
2. Delete
3. Search
4. Inorder Traversal
48
DSA Practical File Session 2023-27

5. Exit
Enter your choice: 1
Enter value to insert: 50

Enter your choice: 1

Enter value to insert: 30

Enter your choice: 1

Enter value to insert: 70

Enter your choice: 4

Inorder traversal: 30 50 70

Enter your choice: 3

Enter value to search: 30
Value 30 found in the BST.

Enter your choice: 2

Enter value to delete: 30

Enter your choice: 4

Inorder traversal: 50 70

49
DSA Practical File Session 2023-27

Program 17:Write a C program to implement BFS algorithm in Graph .

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

#define MAX 100

struct Queue {
int items[MAX];
int front;
int rear;
};

struct Queue* createQueue() {

struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = -1;
q->rear = -1;
return q;
}

int isEmpty(struct Queue* q) {

return q->front == -1;
}

void enqueue(struct Queue* q, int value) {

if (q->rear == MAX - 1) {
printf("Queue is full\n");
} else {
if (q->front == -1) q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}

int dequeue(struct Queue* q) {

int item;
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
return item;
}
}

void BFS(int adjMatrix[MAX][MAX], int numVertices, int startVertex) {

int visited[MAX] = {0}; // Array to keep track of visited vertices
struct Queue* q = createQueue(); // Create a queue for BFS

visited[startVertex] = 1;
enqueue(q, startVertex);
50
DSA Practical File Session 2023-27

printf("BFS traversal starting from vertex %d: ", startVertex);

while (!isEmpty(q)) {
int currentVertex = dequeue(q);
printf("%d ", currentVertex);

for (int i = 0; i < numVertices; i++) {

if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
visited[i] = 1;
enqueue(q, i);
}
}
}
printf("\n");
}

int main() {
int adjMatrix[MAX][MAX];
int numVertices, startVertex;

printf("Enter the number of vertices: ");

scanf("%d", &numVertices);

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

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

printf("Enter the starting vertex: ");

scanf("%d", &startVertex);

BFS(adjMatrix, numVertices, startVertex);

return 0;
}

Output
Enter the number of vertices: 5
Enter the adjacency matrix:
01100
10110
11001
01001
00110
Enter the starting vertex: 0
BFS traversal starting from vertex 0: 0 1 2 3 4

51
DSA Practical File Session 2023-27

Program 18:Write a C program to implement DFS algorithm in Graph.

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

struct Node {
int vertex;
struct Node* next;
}!

struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};

struct Node* createNode(int vertex) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}

struct Graph* createGraph(int numVertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = numVertices;

graph->adjLists = (struct Node**)malloc(numVertices * sizeof(struct Node*));

graph->visited = (int*)malloc(numVertices * sizeof(int));

for (int i = 0; i < numVertices; i++) {

graph->adjLists[i] = NULL;
graph->visited[i] = 0; // Mark all vertices as not visited
}
return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {

struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;

newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}

void DFS(struct Graph* graph, int vertex) {

struct Node* adjList = graph->adjLists[vertex];
struct Node* temp = adjList;

graph->visited[vertex] = 1;
printf("%d ", vertex);

while (temp != NULL) {

52
DSA Practical File Session 2023-27

int connectedVertex = temp->vertex;

if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
int main() {
int vertices, edges, src, dest, startVertex;

printf("Enter the number of vertices: ");

scanf("%d", &vertices);

printf("Enter the number of edges: ");

scanf("%d", &edges);

struct Graph* graph = createGraph(vertices);

printf("Enter the edges (src dest):\n");

for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
printf("Enter the starting vertex for DFS: ");
scanf("%d", &startVertex);

printf("DFS traversal starting from vertex %d:\n", startVertex);

DFS(graph, startVertex);
printf("\n");

for (int i = 0; i < vertices; i++) {

struct Node* temp = graph->adjLists[i];
while (temp) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
}
free(graph->adjLists);
free(graph->visited);
free(graph);
return 0;
}

Output
Enter the number of vertices: 5
Enter the number of edges: 4
Enter the edges (src dest):
01
02
13
14
Enter the starting vertex for DFS: 0
DFS traversal starting from vertex 0:
53
DSA Practical File Session 2023-27

02143

Program 19:Write a C program to implement Kruskal Algorithm in Graph .

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

struct Edge {
int src, dest, weight;
};

struct Graph {
int V, E;
struct Edge* edges;
};

struct Subset {
int parent, rank;
};

struct Graph* createGraph(int V, int E) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}

int find(struct Subset subsets[], int i) {

if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}

void Union(struct Subset subsets[], int x, int y) {

int rootX = find(subsets, x);
int rootY = find(subsets, y);
if (subsets[rootX].rank < subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}

int compareEdges(const void* a, const void* b) {

struct Edge* edgeA = (struct Edge*)a;
struct Edge* edgeB = (struct Edge*)b;
return edgeA->weight - edgeB->weight;
}

void KruskalMST(struct Graph* graph) {

int V = graph->V;
struct Edge result[V];
54
DSA Practical File Session 2023-27

int e = 0, i = 0;
qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1 && i < graph->E) {
struct Edge nextEdge = graph->edges[i++];
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
Union(subsets, x, y);
}
}
printf("Edges in the Minimum Spanning Tree:\n");
for (i = 0; i < e; i++)
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
free(subsets);
}

int main() {
int V, E;
printf("Enter the number of vertices: ");
scanf("%d", &V);
printf("Enter the number of edges: ");
scanf("%d", &E);
struct Graph* graph = createGraph(V, E);
printf("Enter the edges (src dest weight):\n");
for (int i = 0; i < E; i++)
scanf("%d %d %d", &graph->edges[i].src, &graph->edges[i].dest, &graph->edges[i].weight);
KruskalMST(graph);
free(graph->edges);
free(graph);
return 0;
}

Output
Enter the number of vertices: 4
Enter the number of edges: 5
Enter the edges (src dest weight):
0 1 10
026
035
1 3 15
234
Edges in the Minimum Spanning Tree:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

55
DSA Practical File Session 2023-27

Program 20:Write a C program to implement Prims Algorithm in Graph .

#include <stdio.h>
#include <limits.h>

#define MAX 100

int minKey(int key[], int mstSet[], int V) {

int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}

void primMST(int graph[MAX][MAX], int V) {

int parent[V], key[V], mstSet[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}
key[0] = 0;
parent[0] = -1;

for (int count = 0; count < V - 1; count++) {

int u = minKey(key, mstSet, V);
mstSet[u] = 1;

for (int v = 0; v < V; v++) {

if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

printf("Edge \tWeight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
}

int main() {
int V, graph[MAX][MAX];

printf("Enter the number of vertices: ");

scanf("%d", &V);

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

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
56
DSA Practical File Session 2023-27

}
}

primMST(graph, V);

return 0;
}

Output
Enter the number of vertices: 5
Enter the adjacency matrix:
02060
20385
03007
68009
05790
Edge Weight
0-1 2
0-3 6
1-2 3
1-4 5

57