A

PRACTICAL FILE

OF

“DATA STRUCTURES AND ALGORITHMS LAB’’

CSP-003

Session: 2023-24

SUBMITTED BY:- SUBMITTED TO:-

NAME: ABHAY CHAND NAME: NEHA BISHT

BRANCH: AI/ML 2nd YEAR (Assistant Professor)

COURSE: B-Tech

ROLL NO: 221620122001

 INDEX

S No. DATE TITLE SIGN

1 / /2023 Linear search

2 / /2023 Binary search

3 / /2023 Bubble sort

4 / /2023 Quick sort

5 / /2023 Merge sort

6 / /2023 Infix to postfix

7 / /2023 Stack implementation using array

8 / /2023 Stack implementation using linked list

9 /11/2023 Operations on Binary Tree (insertion and

deletion )
10 /11/2023 Write programs for implementing BFS and DFS
for a given graph
1. LINEAR SEARCH
#include <stdio.h>
int linear_search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target)
return i; // Return the index if the target is found
}
return -1; // Return -1 if the target is not found
}

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

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

return 0;
}

Output:
2. BINARY SEARCH
#include <stdio.h>

int binary_search(int arr[], int size, int target) {

int left = 0;
int right = size - 1;

while (left <= right) {

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

// Check if the target is present at mid

if (arr[mid] == target)
return mid;

// If the target is greater, ignore the left half

if (arr[mid] < target)
left = mid + 1;

// If the target is smaller, ignore the right half

else
right = mid - 1;
}

// If the target is not present in the array

return -1;
}

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

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

return 0;
}
Output :
3. BUBBLE SORT
#include <stdio.h>

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] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

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

printf("Array before sorting:\n");

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

bubbleSort(arr, n);

printf("Array after sorting:\n");

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

return 0;
}

Output :
4. QUICK SORT
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
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 pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

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

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

printf("Array before sorting:\n");

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

printf("\n");

quickSort(arr, 0, n - 1);

printf("Array after sorting:\n");

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

return 0;}
Output :
5. MERGE SORT
#include <stdio.h>
// Merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temporary arrays back into arr[l..r]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[], if there are any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// l is for left index and r is right index of the sub-array of arr to be

sorted
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted halves

merge(arr, l, m, r);
}
}

// Utility function to print an array

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

// Driver program to test above functions

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

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);

return 0;
}

Output :
6. INFIX TO POSTFIX
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h> // Include this header for isalnum function
#define MAX_SIZE 100
// 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;
}
// Function to push an element to 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 '$'; // Placeholder for empty stack
}
// Function to get the precedence of an operator
int getPrecedence(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;}
// Function to convert infix to postfix
void infixToPostfix(char* infix, char* postfix) {
struct Stack* stack = createStack(strlen(infix));
int i, j;
i = j = 0;
while (infix[i] != '\0') {
if (isalnum(infix[i])) {
postfix[j++] = infix[i++];
} else if (infix[i] == '(') {
push(stack, infix[i++]);
} else if (infix[i] == ')') {
while (!isEmpty(stack) && stack->array[stack->top] != '(') {
postfix[j++] = pop(stack);
}
if (!isEmpty(stack) && stack->array[stack->top] != '(') {
printf("Invalid expression\n");
return;
} else {
pop(stack);
}
i++;
} else { // Operator
while (!isEmpty(stack) && getPrecedence(infix[i]) <=
getPrecedence(stack->array[stack->top])) {
postfix[j++] = pop(stack);
}
push(stack, infix[i++]);
}
}

// Pop any remaining operators from the stack

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

postfix[j] = '\0';
}

// Example usage
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}
OUTPUT :
7. IMPLEMENTATION OF STACK USING ARRAY
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Structure to represent a stack

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

// Function to initialize the stack

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

// Function to check if the stack is empty

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

// Function to check if the stack is full

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

// Function to push an element onto the stack

void push(struct Stack* stack, int item) {
if (isFull(stack)) {
printf("Stack Overflow\n");
return;
}
stack->array[++stack->top] = item;
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
return -1; // Placeholder for underflow
}
return stack->array[stack->top--];
}

// Function to peek at the top element of the stack

int peek(struct Stack* stack) {
 if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // Placeholder for empty stack
}
return stack->array[stack->top];
}

// Example usage
int main() {
struct Stack stack;
initializeStack(&stack);

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

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

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

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

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

return 0;
}

Output :
8. IMPLEMENTATION OF STACK USING LINKED LIST
#include <stdio.h>
#include <stdlib.h>

// Node structure for the linked list

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

// Stack structure
struct Stack {
struct Node* top;
};

// Function to create a new node

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

// Function to check if the stack is empty

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

// Function to push a new element onto the stack

void push(struct Stack* stack, int data) {
struct Node* node = newNode(data);
node->next = stack->top;
stack->top = node;
printf("%d pushed to stack\n", data);
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // You may choose a different value to indicate an
error
}
struct Node* temp = stack->top;
int popped = temp->data;
stack->top = temp->next;
free(temp);
 return popped;
}

// Function to display the elements of the stack

void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return;
}
struct Node* current = stack->top;
printf("Stack elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

// Example usage
int main() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;

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

display(stack);

printf("%d popped from stack\n", pop(stack));

display(stack);

Output :
9. OPERATION ON BINARY TREE
#include <stdio.h>
#include <stdlib.h>

#define DEGREE 2

void split_child(int tree[], int i);

void btree_insert(int tree[], int *n, int key);
void btree_delete(int tree[], int *n, int key);

void print_btree(int tree[], int n);

int main() {
int btree[100] = {0}; // Assuming a maximum of 100 elements in the tree
int n = 0; // Number of elements in the tree

// Example B-tree operations

btree_insert(btree, &n, 10);
btree_insert(btree, &n, 20);
btree_insert(btree, &n, 5);
btree_insert(btree, &n, 6);

// Print the B-tree

printf("B-tree after insertion: ");
print_btree(btree, n);

int key = 5;
btree_delete(btree, &n, key);

// Print the B-tree after deletion

printf("B-tree after deletion of %d: ", key);
print_btree(btree, n);

return 0;
}

void split_child(int tree[], int i) {

// Implementation of splitting child in B-tree
}

void btree_insert(int tree[], int *n, int key) {

if (*n == 0) {
tree[0] = key;
(*n)++;
return;
}
 int i = *n - 1;
while (i >= 0 && key < tree[i]) {
tree[i + 1] = tree[i];
i--;
}

tree[i + 1] = key;
(*n)++;

if (*n > 2 * DEGREE - 1) {

split_child(tree, i + 1);
}
}

void btree_delete(int tree[], int *n, int key) {

// Implementation of B-tree deletion
}

void print_btree(int tree[], int n) {

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

Output :
10. WRITE PROGRAMS FOR IMPLEMENTING BFS AND DFS

FOR A GIVEN GRAPH

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

#define MAX_VERTICES 100

// Node structure for adjacency list

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

// Graph structure
struct Graph {
int numVertices;
struct Node* adjList[MAX_VERTICES];
};

// Queue structure for BFS

struct Queue {
int front, rear;
int capacity;
int* array;
};

// Function to create a new node

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

// Function to create a graph

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

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

graph->adjList[i] = NULL;

return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;

// Add edge from dest to src

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

// Function to create a new queue

struct Queue* createQueue(int capacity) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->rear = -1;
queue->array = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}

// Function to check if the queue is empty

bool isEmpty(struct Queue* queue) {
return queue->front == -1;
}

// Function to enqueue an item

void enqueue(struct Queue* queue, int item) {
if (queue->rear == queue->capacity - 1)
return;
if (queue->front == -1)
queue->front = 0;
queue->array[++queue->rear] = item;
}

// Function to dequeue an item

int dequeue(struct Queue* queue) {
if (isEmpty(queue))
return -1;
int item = queue->array[queue->front++];
if (queue->front > queue->rear)
queue->front = queue->rear = -1;
return item;
}

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

void BFS(struct Graph* graph, int startVertex) {
 struct Queue* queue = createQueue(graph->numVertices);
bool visited[MAX_VERTICES] = {false};

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

visited[startVertex] = true;
enqueue(queue, startVertex);

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

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

while (temp != NULL) {
int adjVertex = temp->data;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
enqueue(queue, adjVertex);
}
temp = temp->next;
}
}

printf("\n");
}

// Function to perform Depth-First Search (DFS) recursive helper function

void DFSHelper(struct Graph* graph, int currentVertex, bool visited[]) {
visited[currentVertex] = true;
printf("%d ", currentVertex);

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

while (temp != NULL) {
int adjVertex = temp->data;
if (!visited[adjVertex])
DFSHelper(graph, adjVertex, visited);
temp = temp->next;
}
}

// Function to perform Depth-First Search (DFS)

void DFS(struct Graph* graph, int startVertex) {
printf("DFS starting from vertex %d: ", startVertex);
bool visited[MAX_VERTICES] = {false};
DFSHelper(graph, startVertex, visited);
printf("\n");
}
int main() {
struct Graph* graph = createGraph(5);

// Adding edges to the graph

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

// Performing BFS starting from vertex 0

BFS(graph, 0);

// Performing DFS starting from vertex 0

DFS(graph, 0);

return 0;
}

Output: