BUNDELKHAND INSTITUTE OF

ENGINEERING AND TECHNOLOGY

JHANSI

SESSION: 2023-2024

NAME:- SOURAV SHARMA

BRANCH:- COMPUTER SCIENCE AND

ENGINEERING

SUBJECT:- DATA STRUCTURE LAB

SEMESTER:- 3rd

ROLL NUMBER:- 2200430100054

 INDEX

[Link]. TITLE DATE SIGN.

01. EXPERIMENT:-01 19/08/23

02. EXPERIMENT:-02 26/08/23

03. EXPERIMENT:-03 02/08/23

04. EXPERIMENT:-04 16/09/23

05. EXPERIMENT:-05 23/09/23

06. EXPERIMENT:-06 30/09/23

07. EXPERIMENT:-07 07/09/23

08. EXPERIMENT:-08 28/10/23

09. EXPERIMENT:-09 04/11/23

10. EXPERIMENT:-10 04/11/23

 EXPERIMENT:-01

OBJECTIVE:-

Implementing Sorting Techniques: Bubble Sort, Insertion Sort, Selection Sort, Shell , Sort, Radix
Sort, Quick sort

CODE:-

For all the sorting methods we are going to take the same set of numbers except some.
17,5,9,12,3,7,22,8,19,14

BUBBLE SORTING:-
#include <stdio.h>

void swap(int *xp, int *yp) {

int temp = *xp;
*xp = *yp;
*yp = temp;
}

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

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

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

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

int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr)/sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted array: \n");

printArray(arr, n);

return 0;}

1
 OUTPUT:-

INSERTION SORT:-

#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;

/* Move elements of arr[0..i-1] that are greater than key to one

position ahead of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

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

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

int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

insertionSort(arr, n);

printf("Sorted array: \n");

printArray(arr, n);
return 0;}
OUTPUT:-

2
SELECTION SORT:-
#include <stdio.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;

// One by one move the boundary of the unsorted subarray

for (i = 0; i < n-1; i++) {
// Find the minimum element in the unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);
}
}

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

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

int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);

return 0;
}
OUTPUT:-

3
SHELL SORT:-
#include <stdio.h>

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

for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}

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

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

int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

shellSort(arr, n);

printf("Sorted array using Shell sort: \n");

printArray(arr, n);
return 0;}
OUTPUT:-

RADIX SORT:-
#include <stdio.h>

// Function to find the maximum number in the array

int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)

4
 if (arr[i] > max)
max = arr[i];
return max;
}

// Using counting sort to sort the elements based on significant places

void countingSort(int arr[], int n, int exp) {
const int MAX = 10; // Assuming decimal numbers (0-9)
int output[n];
int count[MAX];

// Initialize count array to zero

for (int i = 0; i < MAX; i++)
count[i] = 0;

// Store count of occurrences in count[]

for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] contains actual position of this

digit in output[]
for (int i = 1; i < MAX; i++)
count[i] += count[i - 1];

// Build the output array

for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Copy the output array to arr[], so that arr[] now contains sorted
numbers according to the current digit
for (int i = 0; i < n; i++)
arr[i] = output[i];
}

// Radix sort function

void radixSort(int arr[], int n) {
// Find the maximum number to determine the number of digits
int max = getMax(arr, n);

// Do counting sort for every digit

for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}

// Print an array
void printArray(int arr[], int n) {

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

// Main function
int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

radixSort(arr, n);

printf("Sorted array using Radix sort: \n");

printArray(arr, n);

return 0;
}
OUTPUT:-

QUICK SORT :-

#include <stdio.h>

// Function to partition the array and return the pivot index

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose the rightmost element as the pivot
int i = low - 1; // Index of smaller element

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

if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// Swap arr[i+1] and arr[high] (pivot)

int temp = arr[i + 1];

6
 arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

// Function to perform Quick Sort

void quickSort(int arr[], int low, int high) {
if (low < high) {
// Find the pivot index such that elements smaller than the
pivot are on the left
// and elements greater than the pivot are on the right
int pivotIndex = partition(arr, low, high);

// Recursively sort the sub-arrays

quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

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

// Main function
int main() {
int arr[] = {17, 5, 9, 12, 3, 7, 22, 8, 19, 14};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

// Perform Quick Sort

quickSort(arr, 0, n - 1);

printf("Sorted array using Quick sort: \n");

printArray(arr, n);

return 0;
}
OUTPUT:-

7
 EXPERIMENT:-02

OBJECTIVE:-

Implementing Searching and Hashing Techniques: Linear search, Binary search, Methods for
Hashing: Modulo Division, Digit Extraction, Fold shift, Fold Boundary, Linear Probe for Collision
Resolution. Direct and Subtraction hashing

CODE:-

For the code we are using the same set of numbers for all the searching techniques.
10,25,7,42,15,31,19,5,28,12
Where we will be searching for 15’s index.
LINEAR SEARCH:-
#include <stdio.h>

// Linear search function

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

int main() {
int arr[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(arr) / sizeof(arr[0]);

int key = 15; // Key to search for

printf("Original array: \n");

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

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

if (result != -1) {
printf("Element %d found at index %d.\n", key, result);
} else {
printf("Element %d not found in the array.\n", key);
}
return 0;}

8
 OUTPUT:-

BINARY SEARCH:-
#include <stdio.h>

// Binary search function (assumes the array is sorted)

int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;

if (arr[mid] == key) {
return mid; // Return the index if the key is found
}

if (arr[mid] < key) {

low = mid + 1;
} else {
high = mid - 1;
}
}

return -1; // Return -1 if the key is not found

}

int main() {
int arr[] = {5, 7, 10, 12, 15, 19, 25, 28, 31, 42};
int n = sizeof(arr) / sizeof(arr[0]);

int key = 15; // Key to search for

printf("Original array: \n");

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

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

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

9
 return 0;
}
OUTPUT:-

METHODS FOR HASHING:-

MODULO DIVISION:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using Modulo Division

int hashFunction(int key, int size) {
return key % size;
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

10
 for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

// Print the hash table

printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}
OUTPUT:-

11
 DIGIT EXTRACTION:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using digit extraction

int hashFunction(int key, int size) {
return key % 10; // Extract the last digit
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

12
 for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

// Print the hash table

printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}
OUTPUT:-

FOLD SHIFT:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using fold-shift

int hashFunction(int key, int size) {
int hash = 0;

// Fold the key into chunks of 2 digits and add them up

while (key > 0) {
hash += key % 100;
key /= 100;

13
 }

// Shift the result to fit into the table size

return hash % size;
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

14
 // Print the hash table
printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}

OUTPUT:-

FOLD BOUNDARY:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using fold boundary

int hashFunction(int key, int size) {
int hash = 0;
int boundary = 100; // Set the fold boundary

// Fold the key into chunks determined by the boundary and add them
up
while (key > 0) {
hash += key % boundary;
key /= boundary;

15
 }

// Take the modulus to fit into the table size

return hash % size;
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

16
 // Print the hash table
printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}
OUTPUT:-

LINEAR PROBE FOR COLLISION RESOLUTION:-

Already used in above code.
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using fold boundary

int hashFunction(int key, int size) {
int hash = 0;
int boundary = 100; // Set the fold boundary

// Fold the key into chunks determined by the boundary and add them
up
while (key > 0) {

17
 hash += key % boundary;
key /= boundary;
}

// Take the modulus to fit into the table size

return hash % size;
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);

18
 }

// Print the hash table

printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}
OUTPUT:-

DIRECT HASHING:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

// Hash function using direct hashing

int hashFunction(int key, int size) {
return key % size; // Use the key directly as an index
}

// Insert function for direct hashing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Directly insert at the calculated index

hashTable[index] = key;

19
}

// Search function for direct hashing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

// Print the hash table

printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}

return 0;
}

20
 OUTPUT:-

SUBTRACTION HASHING:-
#include <stdio.h>

#define SIZE 10 // Size of the hash table

#define SUBTRACTION_VALUE 5 // Value to subtract in subtraction hashing

// Hash function using subtraction hashing

int hashFunction(int key, int size) {
return (key - SUBTRACTION_VALUE) % size;
}

// Insert function for linear probing

void insert(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to handle collisions

while (hashTable[index] != -1) {
index = (index + 1) % size;
}

hashTable[index] = key;
}

// Search function for linear probing

int search(int hashTable[], int size, int key) {
int index = hashFunction(key, size);

// Linear probing to find the key

while (hashTable[index] != key && hashTable[index] != -1) {
index = (index + 1) % size;
}

// If the key is found, return the index; otherwise, return -1

return (hashTable[index] == key) ? index : -1;
}

21
int main() {
int hashTable[SIZE];

// Initialize hash table with -1 (indicating empty slots)

for (int i = 0; i < SIZE; i++) {
hashTable[i] = -1;
}

// Set of numbers to insert and search

int numbers[] = {10, 25, 7, 42, 15, 31, 19, 5, 28, 12};
int n = sizeof(numbers) / sizeof(numbers[0]);

// Insert numbers into the hash table

for (int i = 0; i < n; i++) {
insert(hashTable, SIZE, numbers[i]);
}

// Print the hash table

printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
printf("%d: %d\n", i, hashTable[i]);
}

// Search for a key in the hash table

int keyToSearch = 15;
int result = search(hashTable, SIZE, keyToSearch);

if (result != -1) {
printf("Element %d found at index %d.\n", keyToSearch, result);
} else {
printf("Element %d not found in the hash table.\n",
keyToSearch);
}
return 0;
}
OUTPUT:-

22
 EXPERIMENT:-03

OBJECTIVE:-

Implementing Stacks: Array implementation, Linked List implementation, Evaluation of postfix

expression and balancing of parenthesis , Conversion of infix notation to postfix notation.

CODE:-

IMPLEMENTING STACKS:-

ARRAY IMPLEMENTATION:-
#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100 // Maximum size of the stack

// Structure to represent a stack

struct Stack {
int arr[MAX_SIZE];
int top;
};

// Function to initialize an empty stack

void initializeStack(struct Stack *stack) {
stack->top = -1; // Set the top index to -1 to indicate an empty
stack
}

// Function to check if the stack is empty

bool isEmpty(struct Stack *stack) {
return stack->top == -1;
}

// Function to check if the stack is full

bool isFull(struct Stack *stack) {
return stack->top == MAX_SIZE - 1;
}

// Function to push an element onto the stack

void push(struct Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow: Cannot push %d, the stack is full.\n",
value);
} else {
stack->top++;

23
 stack->arr[stack->top] = value;
printf("Pushed %d onto the stack.\n", value);
}
}

// Function to pop an element from the stack

int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack Underflow: Cannot pop from an empty stack.\n");
return -1; // Return a sentinel value indicating underflow
} else {
int poppedValue = stack->arr[stack->top];
stack->top--;
printf("Popped %d from the stack.\n", poppedValue);
return poppedValue;
}
}

// Function to get the top element of the stack without popping

int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return -1; // Return a sentinel value indicating empty stack
} else {
return stack->arr[stack->top];
}
}

// Function to print the elements of the stack

void printStack(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->arr[i]);
}
printf("\n");
}
}

int main() {
struct Stack stack;
initializeStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

24
 printStack(&stack);

printf("Top element: %d\n", peek(&stack));

pop(&stack);
pop(&stack);

printStack(&stack);

printf("Top element: %d\n", peek(&stack));

pop(&stack);

return 0;
}
OUTPUT:-

LINKED LIST IMPLEMENTATION:-

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

// Structure to represent a node in the linked list

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

// Structure to represent a stack

struct Stack {
struct Node *top;
};

// Function to initialize an empty stack

void initializeStack(struct Stack *stack) {
stack->top = NULL; // Set the top pointer to NULL to indicate an
empty stack
}

// Function to check if the stack is empty

25
bool isEmpty(struct Stack *stack) {
return stack->top == NULL;
}

// Function to push an element onto the stack

void push(struct Stack *stack, int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed. Cannot push %d.\n", value);
return;
}

newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;

printf("Pushed %d onto the stack.\n", value);

}

// Function to pop an element from the stack

int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack Underflow: Cannot pop from an empty stack.\n");
return -1; // Return a sentinel value indicating underflow
} else {
struct Node *temp = stack->top;
int poppedValue = temp->data;
stack->top = temp->next;
free(temp);
printf("Popped %d from the stack.\n", poppedValue);
return poppedValue;
}
}

// Function to get the top element of the stack without popping

int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return -1; // Return a sentinel value indicating empty stack
} else {
return stack->top->data;
}
}

// Function to print the elements of the stack

void printStack(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");

26
 } else {
printf("Stack elements: ");
struct Node *current = stack->top;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
}

// Function to free the memory allocated for the stack

void freeStack(struct Stack *stack) {
while (stack->top != NULL) {
struct Node *temp = stack->top;
stack->top = temp->next;
free(temp);
}
}

int main() {
struct Stack stack;
initializeStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

printStack(&stack);

printf("Top element: %d\n", peek(&stack));

pop(&stack);
pop(&stack);

printStack(&stack);

printf("Top element: %d\n", peek(&stack));

pop(&stack);

// Free the memory allocated for the stack

freeStack(&stack);

return 0;
}

27
 OUTPUT:-

EVALUATION OF POSTFIX EXPRESSION:-

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

// Structure to represent a node in the stack

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

// Structure to represent a stack

struct Stack {
struct Node *top;
};

// Function to initialize an empty stack

void initializeStack(struct Stack *stack) {
stack->top = NULL;
}

// Function to check if the stack is empty

int isEmpty(struct Stack *stack) {
return stack->top == NULL;
}

// Function to push an element onto the stack

void push(struct Stack *stack, int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed. Cannot push %d.\n", value);
exit(EXIT_FAILURE);
}

newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;

28
}

// Function to pop an element from the stack

int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Error: Stack underflow.\n");
exit(EXIT_FAILURE);
} else {
struct Node *temp = stack->top;
int poppedValue = temp->data;
stack->top = temp->next;
free(temp);
return poppedValue;
}
}

// Function to perform arithmetic operations

int performOperation(int operand1, int operand2, char operator) {
switch (operator) {
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
if (operand2 == 0) {
printf("Error: Division by zero.\n");
exit(EXIT_FAILURE);
}
return operand1 / operand2;
default:
printf("Error: Invalid operator.\n");
exit(EXIT_FAILURE);
}
}

// Function to evaluate a postfix expression

int evaluatePostfix(char postfix[]) {
struct Stack stack;
initializeStack(&stack);

for (int i = 0; postfix[i] != '\0'; i++) {

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

29
 int operand1 = pop(&stack);
int result = performOperation(operand1, operand2,
postfix[i]);
push(&stack, result);
}
}

if (!isEmpty(&stack) && [Link]->next == NULL) {

return pop(&stack);
} else {
printf("Error: Invalid postfix expression.\n");
exit(EXIT_FAILURE);
}
}

int main() {
char postfixExpression[] = "23*5+";
int result = evaluatePostfix(postfixExpression);
printf("Result of postfix expression %s is: %d\n",
postfixExpression, result);

return 0;
}
OUTPUT

BALANCING OF PARENTHESIS:-
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // Include the string.h header

// Define a structure for the stack

struct Stack {
int top;
unsigned capacity;
char* array;
};

// Function to create a stack

struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (char*)malloc(stack->capacity * sizeof(char));
return stack;
}

30
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Function to push an element onto the stack

void push(struct Stack* stack, char item) {
stack->array[++stack->top] = item;
}

// Function to pop an element from the stack

char pop(struct Stack* stack) {
if (!isEmpty(stack))
return stack->array[stack->top--];
return '\0';
}

// Function to check if parentheses are balanced

int areParenthesesBalanced(char* exp) {
struct Stack* stack = createStack(strlen(exp));

for (int i = 0; exp[i]; i++) {

if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
push(stack, exp[i]);
} else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
if (isEmpty(stack)) {
free(stack->array);
free(stack);
return 0; // Unbalanced parentheses
}

char popped = pop(stack);

if ((exp[i] == ')' && popped != '(') ||
(exp[i] == '}' && popped != '{') ||
(exp[i] == ']' && popped != '[')) {
free(stack->array);
free(stack);
return 0; // Unbalanced parentheses
}
}
}

int result = isEmpty(stack); // Check if there are unmatched opening

parentheses left

free(stack->array);
free(stack);

31
 return result;
}

int main() {
char expression[100];

printf("Enter the expression: ");

fgets(expression, sizeof(expression), stdin);

if (areParenthesesBalanced(expression)) {
printf("The parentheses are balanced.\n");
} else {
printf("The parentheses are not balanced.\n");
}

return 0;
}
OUTPUT

CONVERSION OF INFIX NOTATION TO POSTFIX NOTATION:-

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

// Structure to represent a stack

struct Stack {
int top;
unsigned capacity;
char* array;
};

// Function to create a stack

struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (char*)malloc(stack->capacity * sizeof(char));
return stack;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

32
// Function to push an element onto the stack
void push(struct Stack* stack, char item) {
stack->array[++stack->top] = item;
}

// Function to pop an element from the stack

char pop(struct Stack* stack) {
if (!isEmpty(stack))
return stack->array[stack->top--];
return '\0';
}

// Function to get the top element from the stack without popping
char peek(struct Stack* stack) {
if (!isEmpty(stack))
return stack->array[stack->top];
return '\0';
}

// Function to check if a character is an operator

int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

// Function to get the precedence of an operator

int precedence(char ch) {
if (ch == '+' || ch == '-')
return 1;
else if (ch == '*' || ch == '/')
return 2;
return 0;
}

// Function to convert infix expression to postfix expression

void infixToPostfix(char* infix, char* postfix) {
struct Stack* stack = createStack(strlen(infix));
int i, j;

for (i = 0, j = 0; infix[i]; i++) {

// If the scanned character is an operand, add it to the output
if ((infix[i] >= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' &&
infix[i] <= 'Z')) {
postfix[j++] = infix[i];
}
// If the scanned character is an '(', push it onto the stack
else if (infix[i] == '(') {
push(stack, infix[i]);

33
 }
// If the scanned character is an ')', pop and output from the
stack until '(' is encountered
else if (infix[i] == ')') {
while (!isEmpty(stack) && peek(stack) != '(') {
postfix[j++] = pop(stack);
}
if (!isEmpty(stack) && peek(stack) != '(') {
printf("Invalid expression\n");
return;
} else {
pop(stack); // Discard the '(' from the stack
}
}
// If an operator is encountered
else if (isOperator(infix[i])) {
while (!isEmpty(stack) && precedence(infix[i]) <=
precedence(peek(stack))) {
postfix[j++] = pop(stack);
}
push(stack, infix[i]);
}
}

// Pop all the remaining operators from the stack

while (!isEmpty(stack)) {
postfix[j++] = pop(stack);
}

postfix[j] = '\0'; // Null-terminate the postfix expression

}

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

printf("Enter the infix expression: ");

scanf("%s", infix);

infixToPostfix(infix, postfix);

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

return 0;
}
OUTPUT:-

34
 EXPERIMENT:-04

OBJECTIVE:-

Implementing Queue: Linked List implementation of ordinary queue, Array implementation of

circular queue, Linked List implementation of priority queue, Double ended queue

CODE:-

LINKED LIST IMPLEMENTATION OF ORDINARY QUEUE :-

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

// Node structure for the linked list

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

// Queue structure
struct Queue {
struct Node* front;
struct Node* rear;
};

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty queue

struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
if (queue == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
queue->front = queue->rear = NULL;
return queue;
}

35
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return (queue->front == NULL);
}

// Function to enqueue an element into the queue

void enqueue(struct Queue* queue, int value) {
struct Node* newNode = createNode(value);
if (isEmpty(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}

// Function to dequeue an element from the queue

int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty, cannot dequeue\n");
exit(EXIT_FAILURE);
}

int value = queue->front->data;

struct Node* temp = queue->front;

if (queue->front == queue->rear) {
queue->front = queue->rear = NULL;
} else {
queue->front = queue->front->next;
}

free(temp);
return value;
}

// Function to display the elements in the queue

void displayQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return;
}

struct Node* current = queue->front;

while (current != NULL) {
printf("%d ", current->data);
current = current->next;

36
 }
printf("\n");
}

// Function to free the memory allocated for the queue

void freeQueue(struct Queue* queue) {
while (!isEmpty(queue)) {
dequeue(queue);
}
free(queue);
}

int main() {
struct Queue* queue = createQueue();

enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);

printf("Queue elements: ");

displayQueue(queue);

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

printf("Queue elements after dequeue: ");

displayQueue(queue);

freeQueue(queue);

return 0;
}

OUTPUT:-

37
 ARRAY IMPLEMENTATION OF CIRCULAR QUEUE:-
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5

// Circular Queue structure

struct CircularQueue {
int front, rear;
int array[MAX_SIZE];
};

// Function to initialize an empty circular queue

void initializeQueue(struct CircularQueue* queue) {
queue->front = queue->rear = -1;
}

// Function to check if the circular queue is empty

int isEmpty(struct CircularQueue* queue) {
return (queue->front == -1 && queue->rear == -1);
}

// Function to check if the circular queue is full

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

// Function to enqueue an element into the circular queue

void enqueue(struct CircularQueue* queue, int value) {
if (isFull(queue)) {
printf("Queue is full, cannot enqueue\n");
return;
}

if (isEmpty(queue)) {
queue->front = queue->rear = 0;
} else {
queue->rear = (queue->rear + 1) % MAX_SIZE;
}

queue->array[queue->rear] = value;
}

// Function to dequeue an element from the circular queue

int dequeue(struct CircularQueue* queue) {
int value;

if (isEmpty(queue)) {

38
 printf("Queue is empty, cannot dequeue\n");
exit(EXIT_FAILURE);
}

value = queue->array[queue->front];

if (queue->front == queue->rear) {
initializeQueue(queue);
} else {
queue->front = (queue->front + 1) % MAX_SIZE;
}

return value;
}

// Function to display the elements in the circular queue

void displayQueue(struct CircularQueue* queue) {
int i;
if (isEmpty(queue)) {
printf("Queue is empty\n");
return;
}

printf("Queue elements: ");

i = queue->front;
do {
printf("%d ", queue->array[i]);
i = (i + 1) % MAX_SIZE;
} while (i != (queue->rear + 1) % MAX_SIZE);

printf("\n");
}

int main() {
struct CircularQueue queue;
initializeQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);

displayQueue(&queue);

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

enqueue(&queue, 60);

39
 displayQueue(&queue);

return 0;
}

OUTPUT:-

LINKED LIST IMPLEMENTATION OF PRIORITY QUEUE:-

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

// Node structure for the linked list

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

// Priority Queue structure

struct PriorityQueue {
struct Node* front;
};

// Function to create a new node

struct Node* createNode(int value, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->priority = priority;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty priority queue

40
struct PriorityQueue* createPriorityQueue() {
struct PriorityQueue* pq = (struct
PriorityQueue*)malloc(sizeof(struct PriorityQueue));
if (pq == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
pq->front = NULL;
return pq;
}

// Function to enqueue an element into the priority queue

void enqueue(struct PriorityQueue* pq, int value, int priority) {
struct Node* newNode = createNode(value, priority);

// If the priority queue is empty or the new node has higher

priority than the front
if (pq->front == NULL || priority > pq->front->priority) {
newNode->next = pq->front;
pq->front = newNode;
} else {
struct Node* current = pq->front;

// Traverse the list to find the correct position to insert the

new node
while (current->next != NULL && priority <= current->next-
>priority) {
current = current->next;
}

newNode->next = current->next;
current->next = newNode;
}
}

// Function to dequeue an element from the priority queue

int dequeue(struct PriorityQueue* pq) {
if (pq->front == NULL) {
printf("Priority Queue is empty, cannot dequeue\n");
exit(EXIT_FAILURE);
}

int value = pq->front->data;

struct Node* temp = pq->front;
pq->front = pq->front->next;
free(temp);

return value;

41
}

// Function to display the elements in the priority queue

void displayPriorityQueue(struct PriorityQueue* pq) {
if (pq->front == NULL) {
printf("Priority Queue is empty\n");
return;
}

struct Node* current = pq->front;

while (current != NULL) {
printf("Value: %d, Priority: %d\n", current->data, current-
>priority);
current = current->next;
}
}

// Function to free the memory allocated for the priority queue

void freePriorityQueue(struct PriorityQueue* pq) {
while (pq->front != NULL) {
dequeue(pq);
}
free(pq);
}

int main() {
struct PriorityQueue* pq = createPriorityQueue();

enqueue(pq, 10, 2);

enqueue(pq, 20, 1);
enqueue(pq, 30, 3);

printf("Priority Queue elements:\n");

displayPriorityQueue(pq);

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

printf("Priority Queue elements after dequeue:\n");

displayPriorityQueue(pq);

freePriorityQueue(pq);

return 0;
}

42
 OUTPUT:-

DOUBLE ENDED QUEUE:-

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

// Node structure for the doubly linked list

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

// Double-Ended Queue structure

struct Deque {
struct Node* front;
struct Node* rear;
};

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;

43
 newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty deque

struct Deque* createDeque() {
struct Deque* deque = (struct Deque*)malloc(sizeof(struct Deque));
if (deque == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
deque->front = deque->rear = NULL;
return deque;
}

// Function to check if the deque is empty

int isEmpty(struct Deque* deque) {
return (deque->front == NULL && deque->rear == NULL);
}

// Function to insert an element at the front of the deque

void insertFront(struct Deque* deque, int value) {
struct Node* newNode = createNode(value);

if (isEmpty(deque)) {
deque->front = deque->rear = newNode;
} else {
newNode->next = deque->front;
deque->front->prev = newNode;
deque->front = newNode;
}
}

// Function to insert an element at the rear of the deque

void insertRear(struct Deque* deque, int value) {
struct Node* newNode = createNode(value);

if (isEmpty(deque)) {
deque->front = deque->rear = newNode;
} else {
newNode->prev = deque->rear;
deque->rear->next = newNode;
deque->rear = newNode;
}
}

44
// Function to delete an element from the front of the deque
int deleteFront(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty, cannot delete from the front\n");
exit(EXIT_FAILURE);
}

int value = deque->front->data;

struct Node* temp = deque->front;

if (deque->front == deque->rear) {
deque->front = deque->rear = NULL;
} else {
deque->front = deque->front->next;
deque->front->prev = NULL;
}

free(temp);
return value;
}

// Function to delete an element from the rear of the deque

int deleteRear(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty, cannot delete from the rear\n");
exit(EXIT_FAILURE);
}

int value = deque->rear->data;

struct Node* temp = deque->rear;

if (deque->front == deque->rear) {
deque->front = deque->rear = NULL;
} else {
deque->rear = deque->rear->prev;
deque->rear->next = NULL;
}

free(temp);
return value;
}

// Function to display the elements in the deque from front to rear

void displayDeque(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty\n");
return;
}

45
 struct Node* current = deque->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

// Function to free the memory allocated for the deque

void freeDeque(struct Deque* deque) {
while (!isEmpty(deque)) {
deleteFront(deque);
}
free(deque);
}

int main() {
struct Deque* deque = createDeque();

insertFront(deque, 10);
insertFront(deque, 20);
insertRear(deque, 30);
insertRear(deque, 40);

printf("Deque elements from front to rear: ");

displayDeque(deque);

printf("Deleted element from the front: %d\n", deleteFront(deque));

printf("Deleted element from the rear: %d\n", deleteRear(deque));

printf("Deque elements after deletion: ");

displayDeque(deque);

freeDeque(deque);

return 0;
}
OUTPUT:-

46
 EXPERIMENT:-05

OBJECTIVE:-

Implementing Linked List: Singly Linked Lists, Circular Linked List, Doubly Linked Lists :
Insert, Display, Delete, Search, Count, Reverse(SLL), Polynomial , Addition

CODE:-

SINGLY LINKED LISTS:-

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

// Node structure for the linked list

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

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Function to insert a new node at the beginning of the linked list

struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);
newNode->next = head;
return newNode;
}

// Function to insert a new node at the end of the linked list

struct Node* insertAtEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode;
}

struct Node* current = head;

while (current->next != NULL) {
current = current->next; }

47
 current->next = newNode;
return head;
}

// Function to insert a new node at a specific position in the linked

list
struct Node* insertAtPosition(struct Node* head, int value, int
position) {
if (position < 1) {
printf("Invalid position\n");
return head;
}

struct Node* newNode = createNode(value);

if (position == 1) {
newNode->next = head;
return newNode;
}

struct Node* current = head;

for (int i = 1; i < position - 1 && current != NULL; i++) {
current = current->next;
}

if (current == NULL) {
printf("Invalid position\n");
return head;
}

newNode->next = current->next;
current->next = newNode;
return head;
}

// Function to delete a node at the beginning of the linked list

struct Node* deleteAtBeginning(struct Node* head) {
if (head == NULL) {
printf("List is empty, cannot delete from the beginning\n");
return head;
}

struct Node* temp = head;

head = head->next;
free(temp);
return head;
}

48
// Function to delete a node at the end of the linked list
struct Node* deleteAtEnd(struct Node* head) {
if (head == NULL) {
printf("List is empty, cannot delete from the end\n");
return head;
}

if (head->next == NULL) {
free(head);
return NULL;
}

struct Node* current = head;

while (current->next->next != NULL) {
current = current->next;
}

free(current->next);
current->next = NULL;
return head;
}

// Function to display the elements in the linked list

void displayList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

// Function to free the memory allocated for the linked list

void freeList(struct Node* head) {
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}
}

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

head = insertAtEnd(head, 10);

head = insertAtEnd(head, 20);
head = insertAtBeginning(head, 5);
head = insertAtPosition(head, 15, 2);

49
 printf("Linked list elements: ");
displayList(head);

head = deleteAtBeginning(head);
head = deleteAtEnd(head);

printf("Linked list elements after deletion: ");

displayList(head);

freeList(head);

return 0;
}

OUTPUT:-

CIRCULAR LINKED LIST:-

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

// Node structure for the circular linked list

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

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Function to insert a new node at the beginning of the circular linked

list

50
struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);

if (head == NULL) {
newNode->next = newNode; // Point to itself for the first node
return newNode;
}

// Find the last node in the circular linked list

struct Node* last = head;
while (last->next != head) {
last = last->next;
}

// Insert the new node at the beginning

newNode->next = head;
last->next = newNode;
return newNode;
}

// Function to insert a new node at the end of the circular linked list
struct Node* insertAtEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);

if (head == NULL) {
newNode->next = newNode; // Point to itself for the first node
return newNode;
}

// Find the last node in the circular linked list

struct Node* last = head;
while (last->next != head) {
last = last->next;
}

// Insert the new node at the end

newNode->next = head;
last->next = newNode;
return head;
}

// Function to display the elements in the circular linked list

void displayList(struct Node* head) {
if (head == NULL) {
printf("Circular linked list is empty\n");
return;
}

51
 struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);

printf("\n");
}

// Function to free the memory allocated for the circular linked list
void freeList(struct Node* head) {
if (head == NULL) {
return;
}

struct Node* current = head;

struct Node* temp;

do {
temp = current;
current = current->next;
free(temp);
} while (current != head);
}

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

head = insertAtEnd(head, 10);

head = insertAtEnd(head, 20);
head = insertAtBeginning(head, 5);

printf("Circular Linked List elements: ");

displayList(head);

freeList(head);

return 0;
}

OUTPUT:-

52
DOUBLY LINKED LISTS :

INSERT, DISPLAY, DELETE, SEARCH, COUNT, REVERSE(SLL), POLYNOMIAL ,

ADDITION

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

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

typedef struct Node Node;

Node* createNode(int value) {

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

Node* insertAtBeginning(Node* head, int value) {

Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode;
}

Node* insertAtEnd(Node* head, int value) {

Node* newNode = createNode(value);
if (head == NULL) {
return newNode;
}

Node* current = head;

while (current->next != NULL) {
current = current->next;
}

current->next = newNode;
newNode->prev = current;
return head;

53
}

Node* deleteNode(Node* head, int key) {

Node* current = head;
while (current != NULL && current->data != key) {
current = current->next;
}

if (current == NULL) {
return head;
}

if (current->prev != NULL) {
current->prev->next = current->next;
} else {
head = current->next;
}

if (current->next != NULL) {
current->next->prev = current->prev;
}

free(current);
return head;
}

Node* search(Node* head, int key) {

Node* current = head;
while (current != NULL && current->data != key) {
current = current->next;
}
return current;
}

int countNodes(Node* head) {

int count = 0;
Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}

Node* reverseList(Node* head) {

Node *current = head, *temp = NULL;
while (current != NULL) {
temp = current->prev;

54
 current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL) {
head = temp->prev;
}
return head;
}

void displayList(Node* head) {

Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

Node* addPolynomials(Node* poly1, Node* poly2) {

Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->data > poly2->data) {
result = insertAtEnd(result, poly1->data);
poly1 = poly1->next;
} else if (poly1->data < poly2->data) {
result = insertAtEnd(result, poly2->data);
poly2 = poly2->next;
} else {
result = insertAtEnd(result, poly1->data);
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
result = insertAtEnd(result, poly1->data);
poly1 = poly1->next;
}
while (poly2 != NULL) {
result = insertAtEnd(result, poly2->data);
poly2 = poly2->next;
}
return result;
}

void freeList(Node* head) {

Node* current = head;
Node* next;

55
 while (current != NULL) {
next = current->next;
free(current);
current = next;
}
}

int main() {
Node* list = NULL;
list = insertAtEnd(list, 10);
list = insertAtEnd(list, 20);
list = insertAtBeginning(list, 5);

printf("Original Doubly Linked List: ");

displayList(list);

list = deleteNode(list, 20);

printf("Doubly Linked List after deletion: ");

displayList(list);

int keyToSearch = 10;

Node* searchResult = search(list, keyToSearch);
if (searchResult != NULL) {
printf("Node with data %d found.\n", keyToSearch);
} else {
printf("Node with data %d not found.\n", keyToSearch);
}

printf("Number of nodes in the list: %d\n", countNodes(list));

list = reverseList(list);
printf("Reversed Doubly Linked List: ");
displayList(list);

Node* poly1 = NULL;

Node* poly2 = NULL;
poly1 = insertAtEnd(poly1, 2);
poly1 = insertAtEnd(poly1, 4);
poly1 = insertAtEnd(poly1, 6);

poly2 = insertAtEnd(poly2, 1);

poly2 = insertAtEnd(poly2, 3);
poly2 = insertAtEnd(poly2, 5);

Node* resultPoly = addPolynomials(poly1, poly2);

printf("Result of Polynomial Addition: ");
displayList(resultPoly);

56
 // Free memory
freeList(list);
freeList(poly1);
freeList(poly2);
freeList(resultPoly);

return 0;
}
OUTPUT:-

57
 EXPERIMENT:-06

OBJECTIVE:-

IMPLEMENTING TREES: BINARY SEARCH TREE : Create, Recursive traversal:

preorder, post order, in order, Search Largest , Node, Smallest Node, Count number of nodes
Heap: Min Heap, Max Heap: reheap Up, reheap Down, Delete , Expression Tree, Heapsort.

CODE:-

BINARY SEARCH TREE : CREATE, RECURSIVE TRAVERSAL: PREORDER, POST

ORDER, IN ORDER, SEARCH LARGEST , NODE, SMALLEST NODE, COUNT
NUMBER OF NODES

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

// Structure for a node in the BST

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

// Function to create a new node

struct Node *createNode(int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(EXIT_FAILURE);
}

newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

// Function to insert a value into the BST

struct Node *insert(struct Node *root, int value) {
if (root == NULL) {
return createNode(value);
}

if (value < root->data) {

58
 root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}

return root;
}

// Function for in-order traversal (left, root, right)

void inorderTraversal(struct Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Function for pre-order traversal (root, left, right)

void preorderTraversal(struct Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

// Function for post-order traversal (left, right, root)

void postorderTraversal(struct Node *root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}

// Function to find the node with the largest value in the BST
struct Node *findLargestNode(struct Node *root) {
while (root->right != NULL) {
root = root->right;
}
return root;
}

// Function to find the node with the smallest value in the BST
struct Node *findSmallestNode(struct Node *root) {
while (root->left != NULL) {
root = root->left;
}

59
 return root;
}

// Function to count the number of nodes in the BST

int countNodes(struct Node *root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
// Create an empty BST
struct Node *root = NULL;

// Insert values into the BST

root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// Perform recursive traversals

printf("In-order traversal: ");
inorderTraversal(root);
printf("\n");

printf("Pre-order traversal: ");

preorderTraversal(root);
printf("\n");

printf("Post-order traversal: ");

postorderTraversal(root);
printf("\n");

// Search for the largest and smallest nodes

struct Node *largestNode = findLargestNode(root);
struct Node *smallestNode = findSmallestNode(root);

printf("Largest Node: %d\n", largestNode->data);

printf("Smallest Node: %d\n", smallestNode->data);

// Count the number of nodes

int nodeCount = countNodes(root);
printf("Number of nodes in the BST: %d\n", nodeCount);
return 0:}

60
 OUTPUT:-

HEAP:
MIN HEAP,MAX HEAP: REHEAP UP, REHEAP DOWN, DELETE , EXPRESSION
TREE, HEAPSORT.
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a heap

struct Heap {
int* array;
int capacity;
int size;
};

// Function to create a new heap

struct Heap* createHeap(int capacity) {
struct Heap* heap = (struct Heap*)malloc(sizeof(struct Heap));
heap->array = (int*)malloc(sizeof(int) * capacity);
heap->capacity = capacity;
heap->size = 0;
return heap;
}

// Function to swap two elements in the heap

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to heapify the heap upwards

void reheapUp(struct Heap* heap, int index) {
while (index > 0 && heap->array[index] < heap->array[(index - 1) /
2]) {

61
 swap(&heap->array[index], &heap->array[(index - 1) / 2]);
index = (index - 1) / 2;
}
}

// Function to heapify the heap downwards

void reheapDown(struct Heap* heap, int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;

if (left < heap->size && heap->array[left] < heap->array[smallest])

{
smallest = left;
}

if (right < heap->size && heap->array[right] < heap-

>array[smallest]) {
smallest = right;
}

if (smallest != index) {
swap(&heap->array[index], &heap->array[smallest]);
reheapDown(heap, smallest);
}
}

// Function to insert a new element into the heap

void insert(struct Heap* heap, int value) {
if (heap->size == heap->capacity) {
printf("Heap overflow\n");
return;
}

heap->array[heap->size] = value;
heap->size++;
reheapUp(heap, heap->size - 1);
}

// Function to delete the minimum element from the heap

int deleteMin(struct Heap* heap) {
if (heap->size <= 0) {
printf("Heap underflow\n");
return -1;
}

int min = heap->array[0];

heap->array[0] = heap->array[heap->size - 1];

62
 heap->size--;
reheapDown(heap, 0);

return min;
}

// Function to create an expression tree

struct ExpressionTreeNode {
char value;
struct ExpressionTreeNode* left;
struct ExpressionTreeNode* right;
};

struct ExpressionTreeNode* createExpressionTreeNode(char value) {

struct ExpressionTreeNode* node = (struct
ExpressionTreeNode*)malloc(sizeof(struct ExpressionTreeNode));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}

// Function to perform heapsort

void heapsort(int arr[], int n) {
struct Heap* heap = createHeap(n);

// Insert elements into the heap

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

// Extract elements from the heap and put them back into the array
for (int i = 0; i < n; i++) {
arr[i] = deleteMin(heap);
}

// Free the allocated memory for the heap

free(heap->array);
free(heap);
}

int main() {
// Example usage

// Min Heap
struct Heap* minHeap = createHeap(10);
insert(minHeap, 4);
insert(minHeap, 2);

63
 insert(minHeap, 7);
insert(minHeap, 1);

printf("Min Heap: %d ", deleteMin(minHeap)); // Output: 1

printf("%d ", deleteMin(minHeap)); // Output: 2
printf("%d\n", deleteMin(minHeap)); // Output: 4

// Max Heap
struct Heap* maxHeap = createHeap(10);
maxHeap->array[0] = 4;
maxHeap->array[1] = 2;
maxHeap->array[2] = 7;
maxHeap->array[3] = 1;
maxHeap->size = 4;

printf("Max Heap: %d ", deleteMin(maxHeap)); // Output: 7

printf("%d ", deleteMin(maxHeap)); // Output: 4
printf("%d\n", deleteMin(maxHeap)); // Output: 2

// Expression Tree
struct ExpressionTreeNode* root = createExpressionTreeNode('*');
root->left = createExpressionTreeNode('+');
root->right = createExpressionTreeNode('-');
root->left->left = createExpressionTreeNode('2');
root->left->right = createExpressionTreeNode('3');
root->right->left = createExpressionTreeNode('5');
root->right->right = createExpressionTreeNode('4');

// Heapsort
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapsort(arr, n);

printf("Sorted array: ");

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

return 0;
}
OUTPUT:-

64
 EXPERIMENT:-07

OBJECTIVE:-

Implementing Graphs: Represent a graph using the Adjacency Matrix, BFS, Find the minimum
spanning tree (using any method Kruskal’s Algorithm or Prim’s Algorithm) Self Learning Topics :
Shortest Path Algorithm

CODE:-

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

// Maximum number of vertices in the graph

#define MAX_VERTICES 100

// Structure to represent an undirected, weighted graph

struct Graph {
int vertices;
int** adjacencyMatrix;
};

// Function to create a new graph with a given number of vertices

struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->vertices = vertices;

// Allocate memory for the adjacency matrix

graph->adjacencyMatrix = (int**)malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->adjacencyMatrix[i] = (int*)malloc(vertices *
sizeof(int));
for (int j = 0; j < vertices; j++) {
graph->adjacencyMatrix[i][j] = 0; // Initialize all entries
to 0
}
}

return graph;
}

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int source, int destination, int
weight) {
// Assuming the graph is undirected
graph->adjacencyMatrix[source][destination] = weight;

65
 graph->adjacencyMatrix[destination][source] = weight;
}

// Function to perform Breadth-First Search (BFS)

void BFS(struct Graph* graph, int startVertex) {
int* visited = (int*)malloc(graph->vertices * sizeof(int));
for (int i = 0; i < graph->vertices; i++) {
visited[i] = 0; // Initialize all vertices as not visited
}

int queue[MAX_VERTICES];
int front = -1, rear = -1;

visited[startVertex] = 1;
queue[++rear] = startVertex;

while (front != rear) {

int currentVertex = queue[++front];
printf("%d ", currentVertex);

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

if (graph->adjacencyMatrix[currentVertex][i] && !visited[i])
{
visited[i] = 1;
queue[++rear] = i;
}
}
}

free(visited);
}

// Structure to represent an edge in the graph

struct Edge {
int source, destination, weight;
};

// Structure to represent a subset for Union-Find

struct Subset {
int parent, rank;
};

// Function to find the set of an element in Union-Find

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

66
}

// Function to perform Union of two sets in Union-Find

void unionSets(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank) {

subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Function to compare two edges based on weight (used for sorting)

int compareEdges(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Function to find the minimum spanning tree using Kruskal's Algorithm

void kruskalMST(struct Graph* graph) {
int vertices = graph->vertices;
struct Edge* edges = (struct Edge*)malloc(vertices * vertices *
sizeof(struct Edge));

// Extracting edges from the adjacency matrix

int edgeCount = 0;
for (int i = 0; i < vertices; i++) {
for (int j = i + 1; j < vertices; j++) {
if (graph->adjacencyMatrix[i][j] != 0) {
edges[edgeCount].source = i;
edges[edgeCount].destination = j;
edges[edgeCount].weight = graph->adjacencyMatrix[i][j];
edgeCount++;
}
}
}

// Sort edges in ascending order based on weight

qsort(edges, edgeCount, sizeof(struct Edge), compareEdges);

// Allocate memory for the subsets array

struct Subset* subsets = (struct Subset*)malloc(vertices *
sizeof(struct Subset));

67
 // Initialize subsets
for (int i = 0; i < vertices; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}

printf("Minimum Spanning Tree using Kruskal's Algorithm:\n");

for (int i = 0; i < edgeCount; i++) {
int x = find(subsets, edges[i].source);
int y = find(subsets, edges[i].destination);

if (x != y) {
printf("%d - %d : %d\n", edges[i].source,
edges[i].destination, edges[i].weight);
unionSets(subsets, x, y);
}
}

free(edges);
free(subsets);
}

// Function to find the index of the vertex with the minimum distance
value
int minDistance(int distance[], int visited[], int vertices) {
int min = INT_MAX, minIndex;

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

if (!visited[v] && distance[v] < min) {
min = distance[v];
minIndex = v;
}
}

return minIndex;
}

// Function to print the constructed distance array

void printShortestPath(int distance[], int n) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; i++) {
printf("%d \t\t %d\n", i, distance[i]);
}
}

// Function to implement Dijkstra's algorithm for finding the shortest

path
void dijkstra(struct Graph* graph, int startVertex) {

68
 int vertices = graph->vertices;
int* distance = (int*)malloc(vertices * sizeof(int));
int* visited = (int*)malloc(vertices * sizeof(int));

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

distance[i] = INT_MAX;
visited[i] = 0;
}

distance[startVertex] = 0;

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

int u = minDistance(distance, visited, vertices);
visited[u] = 1;

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

if (!visited[v] && graph->adjacencyMatrix[u][v] &&
distance[u] != INT_MAX &&
distance[u] + graph->adjacencyMatrix[u][v] <
distance[v]) {
distance[v] = distance[u] + graph-
>adjacencyMatrix[u][v];
}
}
}

printf("Shortest Paths from Vertex %d using Dijkstra's

Algorithm:\n", startVertex);
printShortestPath(distance, vertices);

free(distance);
free(visited);
}

int main() {
// Example usage

// Create a graph with 5 vertices

struct Graph* graph = createGraph(5);

// Add edges to the graph

addEdge(graph, 0, 1, 2);
addEdge(graph, 0, 3, 1);
addEdge(graph, 1, 2, 4);
addEdge(graph, 1, 3, 3);
addEdge(graph, 1, 4, 5);
addEdge(graph, 2, 4, 1);
addEdge(graph, 3, 4, 7);

69
 // Perform BFS starting from vertex 0
printf("Breadth-First Search (BFS) starting from vertex 0:\n");
BFS(graph, 0);
printf("\n");

// Find the minimum spanning tree using Kruskal's Algorithm

kruskalMST(graph);

// Find the shortest paths using Dijkstra's Algorithm starting from

vertex 0
dijkstra(graph, 0);

// Free allocated memory for the graph

for (int i = 0; i < graph->vertices; i++) {
free(graph->adjacencyMatrix[i]);
}
free(graph->adjacencyMatrix);
free(graph);

return 0;
}

OUTPUT:-

70