AY 2024-25

II Semester

CSMC103: DATA STRUCTURES AND ALGORITHMS

LAB REPORT

SUBMITTED BY MADHAV KUMAR (24241)

SCHOOL OF COMPUTING

INDIAN INSTITUTE OF INFORMATION TECHNOLOGY UNA

SALOH, HIMACHAL PRADESH -177209

MAY 2025

Page 1
 TABLE OF CONTENTS
S. No Objective Page No. Date Signature
1 EXPERIMENT 1: Linear Search 3-4

2 EXPERIMENT 2: Binary Search 5-6

3 EXPERIMENT 3: Bubble Sort 7-8

4 EXPERIMENT 4: Quick Sort 9-10

5 EXPERIMENT 5: Tower Of Hanoi With 11-12

Recursion

6 EXPERIMENT 6: Recursive Pattern 13-14

Printing
7 EXPERIMENT 7 : Array Operations 15- 16

8 EXPERIMENT 8 : 2D AND 3D Operations 17 - 18

9 EXPERIMENT 9 : Singly Linked Lists 19 - 21

10 EXPERIMENT 10: Circular Doubly Linked 22-24
List
11 EXPERIMENT 11: STACK 25-26
12 EXPERIMENT 12 :Infix to Postfix/ Prefix 27-29
with Evaluation
13 EXPERIMENT 13 : To implement circular 30-32
queue and understand its operations
(insertion and deletion) in C.
14 EXPERIMENT 14 : To implement a 33-35
priority queue using a linked list and
understand its operations (insertion based
on priority and deletion of the highest
priority element) in C.
15 EXPERIMENT 15 : Write a code to 36-40
create a BST and perform searching,
insertion and deletion operations by
considering all the possible cases.

Page 2
 EXPERIMENT No. 1
Linear Search Operation on Array

I. OBJECTIVE:
To implement and understand the linear search operation on an array in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input size of array (n)
3. Input n elements into array 4. Input key element to search
5. For i = 0 to n-1:
- If arr[i] equals key, return i
6. If no match found, return -1
7. End

IV. CODE:
#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for(int i = 0; i < n; i++) { if(arr[i]
== key) return i;
}
return -1;
} int main() { int n, key;
printf("Enter size of array: ");
scanf("%d", &n); int arr[n];
printf("Enter %d elements: ", n);
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]); printf("Enter
element to search: "); scanf("%d",
&key); int result = linearSearch(arr,
n, key); if(result == -1)
printf("Element not found\n"); else
printf("Element found at index %d\n", result);
return 0;
}

V. OUTPUT:

Page 3
 Figure 1
VI. LEARNING OUTCOMES:
1. Understood the concept of linear search.
2. Learned to implement array traversal in C. 3. Gained knowledge of
sequential search efficiency (O(n)).

VII. INFERENCE:
The linear search successfully located the element 45 at index 2 in an unsorted array.

Page 4
 EXPERIMENT No. 2
Binary Search Operation on Array

I. OBJECTIVE:
To implement and understand the binary search operation on a sorted array in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input size of array (n)
3. Input n elements in sorted order
4. Input key element to search 5. Set low = 0, high = n-1
6. While low <= high:
- Calculate mid = low + (high - low) / 2
- If arr[mid] equals key, return mid
- If arr[mid] < key, set low = mid + 1
- Else, set high = mid - 1
7. Return -1 if not found
8. End

IV. CODE:
#include <stdio.h>
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;
if(arr[mid] < key) low = mid + 1; else
high = mid - 1;
}
return -1;
} int main()
{ int n,
key;
printf("Ente
r size of
sorted array:
");
scanf("%d", &n); int arr[n]; printf("Enter
%d elements in sorted order: ", n); for(int i = 0;
Page 5
i < n; i++) scanf("%d", &arr[i]);
printf("Enter element to search: "); scanf("%d",
&key); int result = binarySearch(arr, 0, n-1,
key); if(result == -1) printf("Element not
found\n"); else printf("Element found at
index %d\n", result); return 0;
}

V. OUTPUT:

Figure 2

VI. LEARNING OUTCOMES:

1. Learned binary search algorithm.
2. Understood the importance of sorted data for binary search. 3. Gained
insight into O(log n) time complexity.

VII. INFERENCE:
The binary search efficiently found the element 45 at index 2 in a sorted array.

Page 6
 EXPERIMENT No. 3
Bubble Sort in Array

I. OBJECTIVE:
To implement and understand the bubble sort algorithm on an array in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input size of array (n) 3. Input n elements into array
4. For i = 0 to n-1:
- For j = 0 to n-i-1:
- If arr[j] > arr[j+1], swap arr[j] and arr[j+1]
5. Print sorted array
6. End

IV. CODE:
#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])
{ int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
} int main()
{
int n; printf("Enter size of
array: "); scanf("%d", &n);
int arr[n]; printf("Enter %d
elements: ", n); for(int i = 0; i <
n; i++) scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n"); return 0;
}

Page 7
V. OUTPUT:

Figure 3
VI. LEARNING OUTCOMES:
1. Learned bubble sort algorithm.
2. Understood swapping technique in sorting. 3. Recognized O(n^2)
time complexity.

VII. INFERENCE:
Bubble sort successfully sorted the array in ascending order.

Page 8
 EXPERIMENT No. 4
Quick Sort in Array

I. OBJECTIVE:
To implement and understand the quick sort algorithm on an array in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input size of array (n) 3. Input n elements into array
4. quickSort(arr, low, high): - If low < high:
- pi = partition(arr, low, high)
- quickSort(arr, low, pi-1)
- quickSort(arr, pi+1, high)
5. partition(arr, low, high):
- Set pivot = arr[high]
- Set i = low-1
- For j = low to high-1:
- If arr[j] < pivot, increment i, swap arr[i] and arr[j]
- Swap arr[i+1] and arr[high]
- Return i+1
6. Print sorted array
7. End

IV. CODE: #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 - 1; j++) {
if(arr[j] < pivot) { i++;
swap(&arr[i], &arr[j]);

Page 9
 }
}
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 n; printf("Enter size of
array: "); scanf("%d", &n);
int arr[n]; printf("Enter %d
elements: ", n); for(int i = 0; i <
n; i++) scanf("%d", &arr[i]);
quickSort(arr, 0, n-1);
printf("Sorted array: "); for(int i
= 0; i < n; i++) printf("%d ",
arr[i]); printf("\n"); return 0;
}

V. OUTPUT:

Figure 4.
VI. LEARNING OUTCOMES:
1. Learned quick sort algorithm.
2. Understood partitioning in sorting.
3. Recognized average O(n log n) time complex VII. INFERENCE:

Quick sort efficiently sorted the array using the divide-and-conquer approach

Page 10
 EXPERIMENT No. 5
Tower of Hanoi with Recursion

I. OBJECTIVE:
To implement and understand the Tower of Hanoi problem using recursion in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input number of disks (n)
3. towerOfHanoi(n, source, auxiliary, destination): - If n == 1:
- Print "Move disk 1 from source to destination"
- Return
- towerOfHanoi(n-1, source, destination, auxiliary)
- Print "Move disk n from source to destination"
- towerOfHanoi(n-1, auxiliary, source, destination)
4. End

IV. CODE:
#include <stdio.h>
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if(n == 1) { printf("Move disk 1 from %c to %c\n", source,
destination); return;
}
towerOfHanoi(n-1, source, destination, auxiliary);
printf("Move disk %d from %c to %c\n", n, source, destination);
towerOfHanoi(n-1, auxiliary, source, destination);
} int main()
{
int n; printf("Enter number of
disks: "); scanf("%d", &n);
towerOfHanoi(n, 'A', 'B', 'C');
return 0;
}

V. OUTPUT:

Page 11
Figure 5
VI. LEARNING OUTCOMES:
1. Learned recursive problem-solving.
2. Understood the Tower of Hanoi algorithm. 3. Gained insight into recursion
depth and complexity (O(2^n)).

VII. INFERENCE:
The Tower of Hanoi problem was solved recursively, showing all moves for 3 disks.

Page 12
 EXPERIMENT No. 6
Recursive Pattern Printing

I. OBJECTIVE:
To implement a recursive program in C to print a specific pattern based on input n.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input value n
3. printPattern(n, level):
- If n <= 0, return
- Print spaces based on level
- Print n * (n + 3)
- Call printPattern(n-1, level + 1)
4. End

IV. CODE: :
#include <stdio.h>

void printPattern(int n) {
int value = n * (n + 3);

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

int num = value;

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

printf("%d\t", num); num
-= (n - j + 1) * 2;
}
printf("\n");
}
}

int main() {
int n; printf("Enter the
value n: "); scanf("%d",
&n); printPattern(n);
return 0;
}

Page 13
V. OUTPUT:

Figure 6

VI. LEARNING OUTCOMES:

1. Learned to use recursion for pattern generation.
2. Understood spacing in recursive output. 3. Gained skills in recursive
function design.

VII. INFERENCE:
The recursive function correctly printed the specified pattern for n=5.

Page 14
 EXPERIMENT No. 7
Array Operations

I. OBJECTIVE:
To implement array operations (creation, traversal, insertion, deletion, concatenation) in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. create(): Input size and elements
3. traverse(): Print all elements
4. insert(): Shift elements right, insert at position
5. delete(): Shift elements left, remove at position
6. concatenate(): Append second array to first
7. End

IV. CODE:
#include <stdio.h> #include
<stdlib.h> void create(int arr[], int
*n) { printf("Enter size: ");
scanf("%d", n); printf("Enter %d
elements: ", *n); for(int i = 0; i <
*n; i++) scanf("%d", &arr[i]);
}
void traverse(int arr[], int n) {
printf("Array: "); for(int i
= 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
void insert(int arr[], int *n, int pos, int val) {
for(int i = *n; i > pos; i--) arr[i] = arr[i-
1]; arr[pos] = val;
(*n)++; } void delete(int arr[], int
*n, int pos) { for(int i = pos; i <
*n-1; i++) arr[i] = arr[i+1];
(*n)--; }
void concatenate(int arr1[], int *n1, int arr2[], int n2)
{ for(int i = 0; i < n2; i++)
arr1[*n1 + i] = arr2[i];

Page 15
 *n1 += n2;
} int main()
{
int arr1[100], arr2[100], n1, n2;
create(arr1, &n1); traverse(arr1,
n1); insert(arr1, &n1, 1, 99);
traverse(arr1, n1); delete(arr1,
&n1, 0); traverse(arr1, n1);
create(arr2, &n2);
concatenate(arr1, &n1, arr2, n2);
traverse(arr1, n1); return 0;
}

V. OUTPUT:

Figure 7
VI. LEARNING OUTCOMES:
1. Learned basic array operations.
2. Understood array manipulation techniques. 3. Gained skills in managing
array size dynamically.

VII. INFERENCE:
All array operations were successfully performed and verified.

Page 16
 EXPERIMENT No. 8
2D and 3D Array Representation

I. OBJECTIVE: To implement 2D and 3D array input and display in

row-major and column-major order in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. For 2D array:
- Input rows (r) and columns (c)
- Input r*c elements
- Row-major: Print row-wise - Column-major: Print column-wise
3. For 3D array:
- Input dimensions (r, c, d)
- Input r*c*d elements
- Row-major: Print in sequence
4. End

IV. CODE:
#include <stdio.h> int
main() {
int r, c, d; // 2D Array printf("Enter rows
and columns for 2D array: "); scanf("%d %d",
&r, &c); int arr2D[r][c]; printf("Enter %d
elements:\n", r*c); for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++) scanf("%d",
&arr2D[i][j]); printf("Row Major:\n"); for(int
i = 0; i < r; i++) for(int j = 0; j < c; j++)
printf("%d ", arr2D[i][j]); printf("\nColumn
Major:\n"); for(int j = 0; j < c; j++) for(int i
= 0; i < r; i++) printf("%d ", arr2D[i][j]);
printf("\n");

// 3D Array printf("Enter dimensions for 3D

array (r,c,d): "); scanf("%d %d %d", &r, &c,
&d);
int arr3D[r][c][d]; printf("Enter %d
elements:\n", r*c*d); for(int i = 0; i <
r; i++) for(int j = 0; j < c; j++)
for(int k = 0; k < d; k++)
scanf("%d", &arr3D[i][j][k]);
printf("Row Major:\n"); for(int i = 0; i
< r; i++) for(int j = 0; j < c; j++)
Page 17
for(int k = 0; k < d; k++)
printf("%d ", arr3D[i][j][k]); printf("\
n"); return 0;
}

V. OUTPUT:

Figure 8
VI. LEARNING OUTCOMES:
1. Learned multidimensional array handling.
2. Understood row-major vs column-major representation. 3. Gained skills in
nested loop usage.

VII. INFERENCE:
2D and 3D arrays were correctly represented in row-major and column-major order.

Page 18
 EXPERIMENT No. 9
Singly Linked List Operations

I. OBJECTIVE:
To implement singly linked list operations (creation, traversal, insertion, deletion, concatenation) in
C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. create(): Input nodes, link sequentially
3. traverse(): Print all nodes
4. insert(): Add node at position
5. delete(): Remove node at position
6. concatenate(): Link second list to first
7. End

IV. CODE:
#include <stdio.h> #include
<stdlib.h>
struct Node {
int data;
struct Node* next;
}; struct Node*
create() {
int n;
struct Node *head = NULL, *temp, *prev = NULL;
printf("Enter number of nodes: "); scanf("%d", &n);
for(int i = 0; i < n; i++) { temp = (struct
Node*)malloc(sizeof(struct Node)); printf("Enter
data: "); scanf("%d", &temp->data); temp-
>next = NULL; if(head == NULL) head =
temp; else prev->next = temp; prev =
temp;
}
return head;
} void traverse(struct Node* head)
{ struct Node* temp = head;
while(temp != NULL)
{ printf("%d ", temp->data);
temp = temp->next;
} printf("\
n");
Page 19
} struct Node* insert(struct Node* head, int pos, int val)
{ struct Node *temp = (struct Node*)malloc(sizeof(struct
Node)); temp->data = val; if(pos == 0) { temp->next =
head; return temp;
}
struct Node *curr = head; for(int i = 0; i <
pos-1 && curr != NULL; i++) curr = curr-
>next; temp->next = curr->next; curr->next
= temp; return head;
}
struct Node* delete(struct Node* head, int pos) {
if(head == NULL) return NULL; struct Node
*temp = head; if(pos == 0) { head =
head->next; free(temp); return head;
}
for(int i = 0; i < pos-1 && temp != NULL; i++)
temp = temp->next; struct Node* toDelete =
temp->next; temp->next = toDelete->next;
free(toDelete); return head;
}
struct Node* concatenate(struct Node* head1, struct Node* head2) {
if(head1 == NULL) return head2; struct Node* temp = head1;
while(temp->next != NULL) temp = temp->next; temp-
>next = head2; return head1;
} int main()
{
struct Node *list1 = create();
traverse(list1); list1 =
insert(list1, 1, 99);
traverse(list1); list1 =
delete(list1, 0); traverse(list1);
struct Node *list2 = create();
list1 = concatenate(list1, list2);
traverse(list1); return 0;
}

V. OUTPUT:

Figure 9
VI. LEARNING OUTCOMES:
Page 20
1. Learned linked list structure and operations.
2. Understood dynamic memory allocation. 3. Gained skills in pointer
manipulation.

VII. INFERENCE:
Singly linked list operations were successfully implemented and tested.

EXPERIMENT No. 10
Circular Doubly Linked List Operations

I. OBJECTIVE:

Page 21
To implement circular doubly linked list operations (creation, traversal, insertion, deletion,
concatenation) in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. create(): Input nodes, link circularly with prev and next
3. traverse(): Print nodes in circular order
4. insert(): Add node at position with prev and next links
5. delete(): Remove node, adjust circular links
6. concatenate(): Link two circular lists
7. End

IV. CODE:
#include <stdio.h> #include
<stdlib.h>
struct Node {
int data; struct Node
*prev, *next;
};
struct Node* create() {
int n;
struct Node *head = NULL, *temp, *prevNode = NULL;
printf("Enter number of nodes: "); scanf("%d", &n);
for(int i = 0; i < n; i++) { temp = (struct
Node*)malloc(sizeof(struct Node)); printf("Enter data:
"); scanf("%d", &temp->data); if(head ==
NULL) { head = temp; temp->prev = temp;
temp->next = temp;
} else { temp->next
= head; temp->prev =
prevNode; prevNode-
>next = temp; head-
>prev = temp;
}
prevNode = temp;
} return
head; }
void traverse(struct Node* head) {
if(head == NULL) return; struct
Node* temp = head; do
{ printf("%d ", temp->data);
temp = temp->next; }

Page 22
while(temp != head); printf("\
n");
} struct Node* insert(struct Node* head, int pos, int val)
{ struct Node* temp = (struct Node*)malloc(sizeof(struct
Node)); temp->data = val; if(head == NULL) { temp-
>next = temp; temp->prev = temp; return temp;
}
struct Node* curr = head; for(int i = 0; i < pos
&& curr->next != head; i++) curr = curr-
>next; temp->next = curr->next; temp->prev =
curr; curr->next->prev = temp; curr->next =
temp; if(pos == 0) return temp; return head;
}
struct Node* delete(struct Node* head, int pos)
{ if(head == NULL) return NULL; struct Node
*temp = head, *toDelete; for(int i = 0; i < pos &&
temp->next != head; i++) temp = temp->next;
toDelete = temp; if(temp->next == temp)
{ free(temp); return NULL;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
if(temp == head) head = temp->next;
free(toDelete); return head;
}
struct Node* concatenate(struct Node* head1, struct Node* head2) {
if(head1 == NULL) return head2; if(head2 == NULL) return
head1; struct Node *last1 = head1->prev, *last2 = head2->prev;
last1->next = head2; head2->prev = last1;
last2->next = head1;
head1->prev = last2; return
head1;
} int main()
{
struct Node *list1 = create();
traverse(list1); list1 =
insert(list1, 1, 99);
traverse(list1); list1 =
delete(list1, 0); traverse(list1);
struct Node *list2 = create();
list1 = concatenate(list1, list2);
traverse(list1); return 0;}
V. OUTPUT:

Page 23
 Figure 10
VI. LEARNING OUTCOMES:
1. Learned circular doubly linked list structure.
2. Understood bidirectional linking. 3. Gained skills in complex pointer
management.

VII. INFERENCE:
Circular doubly linked list operations were successfully implemented and verified.

Page 24
 EXPERIMENT No. 11
Stack Operations

I. OBJECTIVE:
To implement and understand stack operations (push, pop, peek) in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Initialize stack with top = -1
3. push(): If not full, increment top, add element
4. pop(): If not empty, return top element, decrement top
5. peek(): Return top element without removing
6. End

IV. CODE:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct Stack { int
top; int
arr[MAX];
};
void init(struct Stack* s) { s-
>top = -1;
} int isEmpty(struct Stack* s)
{ return s->top == -1;
}
int isFull(struct Stack* s)
{ return s->top == MAX-1;
}
void push(struct Stack* s, int val) {
if(isFull(s)) printf("Stack
Overflow\n"); else
s->arr[++s->top] = val;
}
int pop(struct Stack* s)
{ if(isEmpty(s))
{ printf("Stack Underflow\
n"); return -1;
} return s->arr[s-
>top--]; } int peek(struct
Stack* s)
Page 25
{ if(isEmpty(s)) return
-1; return s->arr[s-
>top];
} int main() { struct Stack s;
init(&s); push(&s, 1); push(&s, 2);
push(&s, 3); printf("Top element: %d\
n", peek(&s)); printf("Popped: %d\n",
pop(&s)); printf("Popped: %d\n",
pop(&s)); return 0;
}

V. OUTPUT:

Figure 11

VI. LEARNING OUTCOMES:

1. Learned stack data structure.
2. Understood LIFO principle. 3. Gained skills in stack
implementation.

VII. INFERENCE:
Stack operations were successfully demonstrated with push, pop, and peek.

Page 26
 EXPERIMENT No. 12
Infix to Postfix/Prefix with Evaluation

I. OBJECTIVE:
To implement conversion of infix to postfix notation and evaluate the expression in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Input infix expression
3. infixToPostfix():
- For each character:
- If operand, add to postfix
- If '(', push to stack
- If ')', pop until '('
- If operator, pop higher/equal precedence, push current - Pop remaining operators
4. evaluatePostfix():
- For each character:
- If operand, push to stack
- If operator, pop two operands, perform operation, push result
5. Print postfix and evaluation
6. End

IV. CODE:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack { int
top; int size;
char* arr;
};
void init(struct Stack* s, int size) {
s->top = -1; s->size = size;
s->arr = (char*)malloc(size * sizeof(char));
}
int isEmpty(struct Stack* s)
{ return s->top == -1;
} int isFull(struct Stack* s) {
return s->top == s->size-1;
}
void push(struct Stack* s, char val) { if(!
isFull(s))
Page 27
 s->arr[++s->top] = val;
}
char pop(struct Stack* s) {
if(!isEmpty(s)) return
s->arr[s->top--]; return '\
0';
}
char peek(struct Stack* s) {
if(!isEmpty(s)) return
s->arr[s->top]; return '\
0';
} int precedence(char ch)
{ if(ch == '*' || ch == '/') return
2; if(ch == '+' || ch == '-') return
1; return 0; }
char* infixToPostfix(char* infix) { struct Stack s; init(&s, strlen(infix));
char* postfix = (char*)malloc((strlen(infix) + 1) * sizeof(char)); int j = 0;
for(int i = 0; infix[i]; i++) { if((infix[i] >= '0' && infix[i] <= '9') ||
(infix[i] >= 'a' && infix[i] <= 'z')) { postfix[j++] = infix[i]; } else
if(infix[i] == '(') { push(&s, infix[i]); } else if(infix[i] == ')') {
while(peek(&s) != '(') postfix[j++] = pop(&s); pop(&s);
} else {
while(!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i]))
postfix[j++] = pop(&s); push(&s, infix[i]);
}
}
while(!isEmpty(&s))
postfix[j++] = pop(&s);
postfix[j] = '\0';
free(s.arr); return postfix;
}
int evaluatePostfix(char* postfix) { struct
Stack s; init(&s, strlen(postfix)); for(int i
= 0; postfix[i]; i++) { if(postfix[i] >= '0'
&& postfix[i] <= '9') { push(&s,
postfix[i] - '0');
} else { int b = pop(&s);
int a = pop(&s); switch(postfix[i])
{ case '+': push(&s, a + b);
break; case '-': push(&s, a - b);
break; case '*': push(&s, a * b);
break; case '/': push(&s, a / b);
break;
}
}
} int result =
pop(&s); free(s.arr);
return result;
Page 28
} int main() { char infix[100]; printf("Enter infix
expression: "); scanf("%s", infix); char* postfix =
infixToPostfix(infix); printf("Postfix: %s\n", postfix);
if(strspn(infix, "0123456789+-*/()") == strlen(infix)) {
int result = evaluatePostfix(postfix);
printf("Evaluation: %d\n", result);
}
free(postfix);
return 0;
}

V. OUTPUT:

Figure 12
VI.LEARNING OUTCOMES:
1. Learned expression conversion techniques.
2. Understood stack usage in expression evaluation. 3. Gained skills in
operator precedence handling.

VII. INFERENCE:
The infix expression was correctly converted to postfix and evaluated.

EXPERIMENT No. 13

Page 29
 Queues

I. OBJECTIVE:
To implement circular queue and understand its operations (insertion and
deletion) in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Initialize queue with front = -1, rear = -1, and define size of the queue3. push(): If not full,
increment top, add element
3. enqueue():
 Check if the queue is full:
If (front == 0 && rear == size - 1) OR (rear == (front - 1) % (size - 1)), then overflow
 If queue is empty (front == -1), set front = rear = 0
 Else if rear == size - 1 and front != 0, set rear = 0
 Else increment rear by 1
 Insert element at queue[rear]
4. dequeue():
 Check if the queue is empty:
If front == -1, then underflow
 Store the element at queue[front] for return
 If front == rear, set front = rear = -1 (queue is now empty)
 Else if front == size - 1, set front = 0
 Else increment front by 15. peek(): Return top element without removing
6. peek():If queue is not empty, return queue[front]
7. End

IV. CODE:
#include <stdio.h>
#define SIZE 5

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

void enqueue(int value) {

if ((front == 0 && rear == SIZE - 1) || (rear == (front - 1 + SIZE) % SIZE)) {
printf("Queue is Full (Overflow)\n");
return;
}

if (front == -1) {
front = rear = 0;
} else if (rear == SIZE - 1 && front != 0) {
rear = 0;
} else {
rear = (rear + 1) % SIZE;
}

Page 30
 queue[rear] = value;
printf("Inserted %d\n", value);
}

void dequeue() {
if (front == -1) {
printf("Queue is Empty (Underflow)\n");
return;
}

printf("Deleted %d\n", queue[front]);

if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % SIZE;
}
}

void peek() {
if (front == -1) {
printf("Queue is Empty\n");
} else {
printf("Front element is %d\n", queue[front]);
}
}

void display() {
if (front == -1) {
printf("Queue is Empty\n");
return;
}

printf("Queue: ");
if (rear >= front) {
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
} else {
for (int i = front; i < SIZE; i++)
printf("%d ", queue[i]);
for (int i = 0; i <= rear; i++)
printf("%d ", queue[i]);
}
printf("\n");
}

int main() {
enqueue(6);
enqueue(12);
enqueue(18);
enqueue(24);
enqueue(30);
display();
Page 31
 dequeue();
dequeue();
display();
enqueue(36);
enqueue(50);
display();

peek();

return 0;
}

V. OUTPUT:

VI. LEARNING OUTCOMES:

1. Learned circular queue data structure.
2. Understood FIFO (First-In-First-Out) principle in circular manner.
3. Gained skills in implementing circular queue operations like enqueue, dequeue, and peek in C.
4. Understood handling of overflow and underflow conditions in fixed-size circular queues.

VII. INFERENCE:
Circular queue operations were successfully demonstrated with enqueue, dequeue, and peek.

EXPERIMENT No. 14
Queues
Page 32
I. OBJECTIVE:
To implement a priority queue using a linked list and understand its operations
(insertion based on priority and deletion of the highest priority element) in C.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Define a node structure with fields: data, priority, and next pointer
3. Insert():
 Create a new node with given data and priority
 If the queue is empty or the new node has higher priority than the head, insert it at the
beginning
 Else, traverse the list and insert the new node at the correct position based on priority (lower
number = higher priority)
4. Delete ():
 If the queue is empty, print underflow
 Else, delete the node at the front (highest priority)
5. Display():Traverse and print the data and priority of all nodes
6. End

IV. CODE:
#include <stdio.h>
#include <stdlib.h>

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

struct Node* front = NULL;

struct Node* createNode(int data, int priority) {

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

void insert(int data, int priority) {

struct Node* newNode = createNode(data, priority);

if (front == NULL || priority < front->priority) {

newNode->next = front;
front = newNode;
} else {
struct Node* temp = front;
Page 33
 while (temp->next != NULL && temp->next->priority <= priority) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}

printf("Inserted %d with priority %d\n", data, priority);

}

void delete() {
if (front == NULL) {
printf("Priority Queue is Empty (Underflow)\n");
return;
}

struct Node* temp = front;

printf("Deleted element %d with priority %d\n", temp->data, temp->priority);
front = front->next;
free(temp);
}

void display() {
if (front == NULL) {
printf("Priority Queue is Empty\n");
return;
}

struct Node* temp = front;

printf("Priority Queue:\n");
while (temp != NULL) {
printf("Data: %d, Priority: %d\n", temp->data, temp->priority);
temp = temp->next;
}
}
int main() {
insert(18, 3);
insert(9, 1);
insert(30, 2);
insert(25, 0);

display();

delete();
delete();

display();
return 0;
}
V. OUTPUT:

Page 34
 Figure 14
VI. LEARNING OUTCOMES:
1. Learned about the priority queue data structure.
2. Understood how elements are prioritized and managed using linked lists.
3. Gained skills in inserting and deleting nodes based on priority.

VII. INFERENCE:
Priority queue operations were successfully demonstrated using a linked list. Elements were inserted
based on priority and the highest priority elements were deleted correctly.

EXPERIMENT No. 15
Page 35
 Trees

I. OBJECTIVE:
Write a code to create a BST and perform searching, insertion and deletion
operations by considering all the possible cases.

II. HARDWARE/ SOFTWARE REQUIREMENT:

Hardware: Computer with C compiler
Software: Any C IDE (e.g., CodeBlocks, Dev-C++)

III. ALGORITHM:
1. Start
2. Define a structure for a BST node with fields: data, left, right
3. Insert(root, key):
a. If root is NULL, create a new node and return it
b. If key < root→data, insert in the left subtree
c. Else insert in the right subtree
4. Search(root, key):
a. If root is NULL or root→data == key, return root
b. If key < root→data, search left subtree
c. Else search right subtree
5. Delete(root, key):
a. If root is NULL, return NULL
b. If key < root→data, delete from left subtree
c. Else if key > root→data, delete from right subtree
d. Else:
i. If node has no child: delete and return NULL
ii. If node has one child: return non-null child
iii. If node has two children:
1. Find in-order successor (minimum node in right subtree)
2. Replace node’s data with successor’s data
3. Delete successor recursively

6. Inorder(root):

Page 36
 a. Traverse left
b. Print data
c. Traverse right
7. End

IV. CODE:
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int value;
struct Node* left;
struct Node* right;
} Node;

Node* create(int val) {

Node* temp = (Node*)malloc(sizeof(Node));
temp->value = val;
temp->left = temp->right = NULL;
return temp;
}

Node* minimum(Node* root) {

while (root && root->left)
root = root->left;
return root;
}

void inorder(Node* root) {

if (root) {
inorder(root->left);
printf("%d\t", root->value);
inorder(root->right);
}
}

void lookup(Node* root) {

int key;
printf("Enter value to search:\t");
scanf("%d", &key);
Node* temp = root;
while (temp) {
if (temp->value == key) {
printf("Value Found\n");
return;
} else if (key < temp->value)
temp = temp->left;
else
temp = temp->right;
}
printf("Value Not Found\n");
Page 37
}

void add(Node* root) {

int val;
printf("Enter value to insert:\t");
scanf("%d", &val);
Node* temp = create(val);
Node* current = root;
while (1) {
if (val < current->value) {
if (!current->left) {
current->left = temp;
return;
}
current = current->left;
} else {
if (!current->right) {
current->right = temp;
return;
}
current = current->right;
}
}
}

Node* removeNode(Node* root, int key) {

if (!root)
return NULL;
if (key < root->value)
root->left = removeNode(root->left, key);
else if (key > root->value)
root->right = removeNode(root->right, key);
else {
if (!root->left && !root->right) {
free(root);
return NULL;
} else if (!root->left || !root->right) {
Node* temp = root->left ? root->left : root->right;
free(root);
return temp;
} else {
Node* temp = minimum(root->right);
root->value = temp->value;
root->right = removeNode(root->right, temp->value);
}
}
return root;
}

int main() {
int n, choice;
printf("Enter root value:\t");
scanf("%d", &n);
Page 38
Node* root = create(n);
while (1) {
printf("\n1. Search\n2. Insert\n3. Delete\n4. Exit\n");
scanf("%d", &choice);
switch (choice) {
case 1:
lookup(root);
break;
case 2:
add(root);
printf("\nTree:\n");
inorder(root);
break;
case 3:
printf("Enter value to delete:\t");
scanf("%d", &n);
root = removeNode(root, n);
printf("\nTree:\n");
inorder(root);
break;
default:
printf("Terminating...\n");
return 0;
}}}V. OUTPUT:

Page 39
 Figure 15
VI. LEARNING OUTCOMES:
1.Understood the concept of Binary Search Tree and its recursive structure.
2.Learned insertion, searching, and deletion in BST including all possible deletion cases.
3.Gained practical coding experience in manipulating tree-based data structures in C.

VII. INFERENCE:
The implementation of BST was successfully demonstrated. Operations for insertion, searching, and
deletion (including cases with 0, 1, and 2 children) worked correctly, and the tree maintained BST
properties after each operation.

Page 40