ASSIGNMENT-1

1(a) C Program to Implement Insertion, Deletion, and Traversal on

an Array

Code:

#include <stdio.h>
#define MAX 100
void insert(int arr[], int *size, int pos, int value) {
if (*size >= MAX) {
printf("Array is full\n");
return;
}
if (pos < 0 || pos > *size) {
printf("Invalid position!\n");
return;
}
for (int i = *size; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value;
(*size)++;
}
void delete(int arr[], int *size, int pos) {
if (*size == 0) {
printf("Array is empty\n");
return;
}
if (pos < 0 || pos >= *size) {
printf("Invalid position!\n");
return;
}
for (int i = pos; i < *size - 1; i++) {
arr[i] = arr[i + 1];
}
(*size)--;

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

int main() {
int arr[MAX] = {1, 2, 3, 4, 5};
int size = 5;

printf("Initial Array: ");

traverse(arr, size);
insert(arr, &size, 2, 10);
printf("After Insertion: ");
traverse(arr, size);
delete(arr, &size, 3);
printf("After Deletion: ");
traverse(arr, size);
return 0;
}

Output:

Initial Array: 1 2 3 4 5
After Insertion: 1 2 10 3 4 5
After Deletion: 1 2 10 4 5

2
1(b) C Program to Implement Linear Search in an Array

Code:

#include <stdio.h>
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {5, 8, 12, 3, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 12;
int index = linearSearch(arr, size, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found\n", key);

return 0;
}

Output:

Element 12 found at index 2.

3
1(c) C Program for Binary Search

Code:

#include <stdio.h>
int binarySearch(int arr[], int size, int key) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11}; // Sorted array
int size = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int index = binarySearch(arr, size, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found\n", key);
return 0;
}

Output:

Element 7 found at index 3

4
1(d) C Program for Interpolation Search

Code:

#include <stdio.h>
int interpolationSearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
int pos = low + (((double)(high - low) / (arr[high] - arr[low])) * (key -
arr[low]));
if (arr[pos] == key)
return pos;
if (arr[pos] < key)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 40;
int index = interpolationSearch(arr, size, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found\n", key);
return 0;
}

Output:

Element 40 found at index 3 .

5
 ASSIGNMENT-2

2(a) C Program to Implement Stack Operations (Push, Pop, Peek,

and Display) with User Input

Code:

#include <stdio.h>
#define MAX 5
int stack[MAX], top = -1;
void push() {
if (top == MAX - 1)
printf("Stack Overflow\n");
else {
int value;
printf("Enter value to push: ");
scanf("%d", &value);
stack[++top] = value;
printf("Pushed %d into stack\n", value);
}
}
void pop() {
if (top == -1)
printf("Stack Underflow\n");
else
printf("Popped %d from stack\n", stack[top--]);
}
void peek() {
if (top == -1)
printf("Stack is empty\n");
else
printf("Top element is %d\n", stack[top]);
}
void display() {
if (top == -1)
printf("Stack is empty\n");

6
 else {
printf("Stack elements: ");
for (int i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}
}
int main() {
int choice;
do {
printf("\nStack Operations:\n1. Push\n2. Pop\n3. Peek\n4.
Display\n5. Exit\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: push(); break;
case 2: pop(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: printf("Exiting...\n"); break;
default: printf("Invalid choice! Try again.\n");
}
} while (choice != 5);
return 0;
}

Output:

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to push: 10
Pushed 10 into stack

Enter your choice: 4

7
Stack elements: 10

Enter your choice: 5

Exiting...

8
2(b) C Program to Check Balanced Parentheses (User Input)

Code:

#include <stdio.h>
int isBalanced(char *expr) {
int count = 0;
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == '(')
count++;
else if (expr[i] == ')') {
if (count == 0)
return 0;
count--;
}
}
return count == 0;
}
int main() {
char expr[100];
printf("Enter an expression: ");
scanf("%s", expr);
if (isBalanced(expr))
printf("Parentheses are balanced\n");
else
printf("Parentheses are not balanced\n");
return 0;
}
Output:
Enter an expression: (5+(3*2))-(8/4)
Parentheses are balanced

Enter an expression: (5+3*(2-4

Parentheses are not balanced

9
2(c) C Program to Convert Infix to Postfix with User Input

Code:

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
stack[++top] = c;
}
char pop() {
return stack[top--];
}
int precedence(char c) {
if (c == '+' || c == '-')
return 1;
if (c == '*' || c == '/')
return 2;
return 0;
}
void infixToPostfix(char *infix) {
char postfix[MAX];
int j = 0;
for (int i = 0; infix[i] != '\0'; i++) {
if (isalnum(infix[i]))
postfix[j++] = infix[i];
else if (infix[i] == '(')
push(infix[i]);
else if (infix[i] == ')') {
while (top != -1 && stack[top] != '(')
postfix[j++] = pop();
pop(); // Remove '('
} else {
while (top != -1 && precedence(stack[top]) >=

10
precedence(infix[i]))
postfix[j++] = pop();
push(infix[i]);
}
}

while (top != -1)

postfix[j++] = pop();

postfix[j] = '\0';
printf("Postfix Expression: %s\n", postfix);
}

int main() {
char infix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix);
return 0;
}

Output:

Enter an infix expression: A+B*C

Postfix Expression: ABC*+

11
 ASSIGNMENT -3

3(a) C Program to Implement Enqueue, Dequeue, Peek, and Display

in a Simple Queue

Code:

#include <stdio.h>
#define MAX 5

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

void enqueue() {
if (rear == MAX - 1)
printf("Queue is full (Overflow)\n");
else {
int value;
printf("Enter value to enqueue: ");
scanf("%d", &value);
if (front == -1) front = 0;
queue[++rear] = value;
printf("Enqueued %d into queue\n", value);
}
}

void dequeue() {
if (front == -1 || front > rear)
printf("Queue is empty (Underflow)\n");
else
printf("Dequeued %d from queue\n", queue[front++]);
}

void peek() {
if (front == -1 || front > rear)
printf("Queue is empty\n");
else

12
 printf("Front element is %d\n", queue[front]);
}

void display() {
if (front == -1 || front > rear)
printf("Queue is empty\n");
else {
printf("Queue elements: ");
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
}
int main() {
int choice;
do {
printf("\nQueue Operations:\n1. Enqueue\n2. Dequeue\n3.
Peek\n4. Display\n5. Exit\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: enqueue(); break;
case 2: dequeue(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: printf("Exiting...\n"); break;
default: printf("Invalid choice! Try again.\n");
}
} while (choice != 5);

return 0;
}

13
Output:

Queue Operations:
1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to enqueue: 10
Enqueued 10 into queue

Enter your choice: 4

Queue elements: 10

Enter your choice: 5

Exiting...

14
3(b) C Program to Implement Enqueue, Dequeue, Peek, and Display
in a Circular Queue

Code:

#include <stdio.h>
#define MAX 5

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

void enqueue() {
if ((rear + 1) % MAX == front)
printf("Queue is full (Overflow)\n");
else {
int value;
printf("Enter value to enqueue: ");
scanf("%d", &value);
if (front == -1) front = 0;
rear = (rear + 1) % MAX;
queue[rear] = value;
printf("Enqueued %d into queue\n", value);
}
}

void dequeue() {
if (front == -1)
printf("Queue is empty (Underflow)\n");
else {
printf("Dequeued %d from queue\n", queue[front]);
if (front == rear) // Reset queue when last element is dequeued
front = rear = -1;
else
front = (front + 1) % MAX;
}
}

void peek() {

15
 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");
else {
printf("Queue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf("\n");
}
}

int main() {
int choice;
do {
printf("\nCircular Queue Operations:\n1. Enqueue\n2. Dequeue\n3.
Peek\n4. Display\n5. Exit\nEnter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: enqueue(); break;
case 2: dequeue(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: printf("Exiting...\n"); break;
default: printf("Invalid choice! Try again.\n");
}
} while (choice != 5);

16
 return 0;
}

Output:

Circular Queue Operations:

1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to enqueue: 10
Enqueued 10 into queue

Enter your choice: 4

Queue elements: 10

Enter your choice: 5

Exiting...

17
3(c) C Program to Evaluate a Postfix Expression Using Stack

Code:

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

#define MAX 100

int stack[MAX], top = -1;

void push(int value) {

stack[++top] = value;
}

int pop() {
return stack[top--];
}

int evaluatePostfix(char *exp) {

for (int i = 0; exp[i] != '\0'; i++) {
if (isdigit(exp[i]))
push(exp[i] - '0'); // Convert char to int
else {
int val2 = pop();
int val1 = pop();
switch (exp[i]) {
case '+': push(val1 + val2); break;
case '-': push(val1 - val2); break;
case '*': push(val1 * val2); break;
case '/': push(val1 / val2); break;
}
}
}
return pop();
}

18
int main() {
char exp[MAX];
printf("Enter a postfix expression (e.g., 23*5+): ");
scanf("%s", exp);
printf("Result: %d\n", evaluatePostfix(exp));
return 0;
}

Output:

Enter a postfix expression (e.g., 23*5+): 23*5+

Result: 11

19
 ASSIGNMENT – 4
a. Write a C program to Implement basic operations on asingly
linked list: insertion, deletion, traversal, and search.
Code:
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node
{
int data;
struct Node* next;
};
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
printf("Inserted %d at the beginning.\n", value);
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL)
{
*head = newNode;
} else
{
struct Node* temp = *head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
printf("Inserted %d at the end.\n", value);

20
}
// Function to delete a node by value
void deleteNode(struct Node** head, int value)
{
struct Node* temp = *head;
struct Node* prev = NULL;
// If the node to be deleted is the head node
if (temp != NULL && temp->data == value)
{
*head = temp->next;
free(temp);
printf("Deleted node with value %d.\n", value);
return;
}
// Search for the node to be deleted
while (temp != NULL && temp->data != value)
{
prev = temp;
temp = temp->next;
}
// If value not found
if (temp == NULL)
{
printf("Value %d not found in the list.\n", value);
return;
}
// Unlink the node
prev->next = temp->next;
free(temp);
printf("Deleted node with value %d.\n", value);
}
// Function to search for a node in the list
void search(struct Node* head, int value)
{
struct Node* temp = head;
int position = 1;
while (temp != NULL)
{
if (temp->data == value)
{

21
 printf("Value %d found at position %d.\n", value, position);
return;
}
temp = temp->next;
position++;
}
printf("Value %d not found in the list.\n", value);
}
// Function to traverse and display the linked list
void traverse(struct Node* head)
{
if (head == NULL)
{
printf("The list is empty.\n");
return;
}
struct Node* temp = head;
printf("Linked List: ");
while (temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Main function to test linked list operations
int main()
{
struct Node* head = NULL;
int choice, value;
while (1)
{
printf("\nLinked List Operations:\n");
printf("1. Insert at Beginning\n2. Insert at End\n3. Delete Node\n4.
Search\n5.
Traverse\n6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{

22
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;
case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value);
insertAtEnd(&head, value);
break;
case 3:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;
case 4:
printf("Enter value to search: ");
scanf("%d", &value);
search(head, value);
break;
case 5:
traverse(head);
break;
case 6:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}

Output:

Linked List Operations:

1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse

23
6. Exit
Enter your choice: 1
Enter value to insert at beginning: 3
Inserted 3 at the beginning.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 2
Enter value to insert at end: 4
Inserted 4 at the end.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 2
Enter value to insert at end: 5
Inserted 5 at the end.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 2
Enter value to insert at end: 6
Inserted 6 at the end.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse

24
6. Exit
Enter your choice: 2
Enter value to insert at end: 7
Inserted 7 at the end.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 5
Linked List: 3 -> 4 -> 5 -> 6 -> 7 -> NULL
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 4
Enter value to search: 5
Value 5 found at position 3.
Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 6
Exiting program.

25
b. Write a C program to Implement basic operations on a doubly
linked list: insertion, deletion, traversal, and search.

Code:

#include <stdio.h>
#include <stdlib.h>
// Node structure for Doubly Linked List
struct Node
{
int data;
struct Node* prev;
struct Node* next;
};
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = *head;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
printf("Inserted %d at the beginning.\n", value);
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL)
{
newNode->prev = NULL;
*head = newNode;
} else
{

26
struct Node* temp = *head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
printf("Inserted %d at the end.\n", value);
}
// Function to delete a node by value
void deleteNode(struct Node** head, int value)
{
struct Node* temp = *head;
// Search for the node to be deleted
while (temp != NULL && temp->data != value)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Value %d not found in the list.\n", value);
return;
}
// If node to be deleted is head
if (temp == *head)
{
*head = temp->next;
if (*head != NULL)
{
(*head)->prev = NULL;
}
} else
{
temp->prev->next = temp->next;
if (temp->next != NULL)
{

27
temp->next->prev = temp->prev;
}
}
free(temp);
printf("Deleted node with value %d.\n", value);
}
// Function to search for a node
void search(struct Node* head, int value)
{
struct Node* temp = head;
int position = 1;
while (temp != NULL)
{
if (temp->data == value)
{
printf("Value %d found at position %d.\n", value, position);
return;
}
temp = temp->next;
position++;
}
printf("Value %d not found in the list.\n", value);
}
// Function to traverse and display the linked list from the beginning
void traverse(struct Node* head)
{
if (head == NULL)
{
printf("The list is empty.\n");
return;
}
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL)
{
printf("%d <-> ", temp->data);
temp = temp->next;

28
}
printf("NULL\n");
}
// Main function to test doubly linked list operations
int main()
{
struct Node* head = NULL;
int choice, value;
while (1)
{
printf("\nDoubly Linked List Operations:\n");
printf("1. Insert at Beginning\n2. Insert at End\n3. Delete Node\n4.
Search\n5.
Traverse\n6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;
case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value);
insertAtEnd(&head, value);
break;
case 3:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;
case 4:
printf("Enter value to search: ");
scanf("%d", &value);
search(head, value);

29
break;
case 5:
traverse(head);
break;
case 6:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}

Output:

Doubly Linked List Operations:

1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 1
Enter value to insert at beginning: 3
Inserted 3 at the beginning.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 2
Enter value to insert at end: 4
Inserted 4 at the end.
Doubly Linked List Operations:
1. Insert at Beginning

30
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 1
Enter value to insert at beginning: 2
Inserted 2 at the beginning.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 2
Enter value to insert at end: 5
Inserted 5 at the end.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 5
Doubly Linked List: 2 <-> 3 <-> 4 <-> 5 <-> NULL
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 3
Enter value to delete: 4
Deleted node with value 4.

31
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 5
Doubly Linked List: 2 <-> 3 <-> 5 <-> NULL
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 4
Enter value to search: 5
Value 5 found at position 3.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse
6. Exit
Enter your choice: 6
Exiting program.

32
c. Write a C program to Implement basic operations on adoubly
linked list: insertion, deletion, traversal, and search in reverse
order.

Code:

#include <stdio.h>
#include <stdlib.h>
// Node structure for Doubly Linked List
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = *head;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
printf("Inserted %d at the beginning.\n", value);
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;

33
}
printf("Inserted %d at the end.\n", value);
}
// Function to delete a node by value
void deleteNode(struct Node** head, int value) {
struct Node* temp = *head;
// Search for the node to be deleted
while (temp != NULL && temp->data != value) {
temp = temp->next;
}
if (temp == NULL) {
printf("Value %d not found in the list.\n", value);
return;
}
// If node to be deleted is head
if (temp == *head) {
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
} else {
temp->prev->next = temp->next;
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
}
free(temp);
printf("Deleted node with value %d.\n", value);
}
// Function to search for a node
void search(struct Node* head, int value) {
struct Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == value) {
printf("Value %d found at position %d.\n", value, position);
return;
}
temp = temp->next;
position++;

34
}
printf("Value %d not found in the list.\n", value);
}
// Function to traverse and display the linked list from the beginning
void traverse(struct Node* head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
struct Node* temp = head;
printf("Doubly Linked List (Forward): ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to reverse traverse the linked list
void reverseTraverse(struct Node* head) {
if (head == NULL) {
printf("The list is empty.\n");
return;
}
struct Node* temp = head;

// Move to the last node

while (temp->next != NULL) {
temp = temp->next;
}
// Traverse backwards
printf("Doubly Linked List (Reverse): ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}
// Main function to test doubly linked list operations
int main() {
struct Node* head = NULL;

35
int choice, value;
while (1) {
printf("\nDoubly Linked List Operations:\n");
printf("1. Insert at Beginning\n2. Insert at End\n3. Delete Node\n4.
Search\n5.
Traverse Forward\n6. Traverse Reverse\n7. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;
case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value);
insertAtEnd(&head, value);
break;
case 3:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;
case 4:
printf("Enter value to search: ");
scanf("%d", &value);
search(head, value);
break;
case 5:
traverse(head);
break;
case 6:
reverseTraverse(head);
break;
case 7:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");

36
}
}
return 0;
}

Output:

Doubly Linked List Operations:

1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 1
Enter value to insert at beginning: 1
Inserted 1 at the beginning.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 2
Enter value to insert at end: 2
Inserted 2 at the end.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 2
Enter value to insert at end: 3
Inserted 3 at the end.
Doubly Linked List Operations:

37
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 2
Enter value to insert at end: 4
Inserted 4 at the end.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 5
Doubly Linked List (Forward): 1 <-> 2 <-> 3 <-> 4 <-> NULL
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 6
Doubly Linked List (Reverse): 4 <-> 3 <-> 2 <-> 1 <-> NULL
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 4
Enter value to search: 2

38
Value 2 found at position 2.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 1
Enter value to insert at beginning: 0
Inserted 0 at the beginning.
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 5
Doubly Linked List (Forward): 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> NULL
Doubly Linked List Operations:
1. Insert at Beginning
2. Insert at End
3. Delete Node
4. Search
5. Traverse Forward
6. Traverse Reverse
7. Exit
Enter your choice: 7
Exiting program.
=== Code Execution Successful ===

39
 ASSIGNMENT – 5
a. Write a C program to Implement the selection sortalgorithm.
Code:
#include <stdio.h>
// Function to perform selection sort
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
// Assume the minimum is at the current index
minIndex = i;
// Find the minimum element in the remaining array
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the
unsorted part
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// Display array after each pass (optional)
printf("Pass %d: ", i + 1);
for (int k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main()
{

40
int n, i;
// User input for array size
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// User input for array elements
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nOriginal array: ");
printArray(arr, n);
// Sorting the array using selection sort
selectionSort(arr, n);
// Display the sorted array
printf("\nSorted array: ");
printArray(arr, n);
return 0;
}
Output:
Enter the number of elements: 6
Enter 6 elements: 23
45
67
34
78
12
Original array: 23 45 67 34 78 12
Pass 1: 12 45 67 34 78 23
Pass 2: 12 23 67 34 78 45
Pass 3: 12 23 34 67 78 45
Pass 4: 12 23 34 45 78 67
Pass 5: 12 23 34 45 67 78
Sorted array: 12 23 34 45 67 78

41
b. Write a C program to Implement the bubble sort algorithm.

Code:

#include <stdio.h>
// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
int i, j, temp, swapped;
for (i = 0; i < n - 1; i++) {
swapped = 0; // To optimize for already sorted arrays
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap adjacent elements if they are in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}}
// Display the array after each pass (optional)
printf("Pass %d: ", i + 1);
for (int k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
// If no swapping occurs, the array is already sorted
if (swapped == 0) {
break;
}
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main() {
int n, i;
// User input for array size
printf("Enter the number of elements: ");

42
 scanf("%d", &n);
int arr[n];
// User input for array elements
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nOriginal array: ");
printArray(arr, n);
// Sorting the array using bubble sort
bubbleSort(arr, n);
// Display the sorted array
printf("\nSorted array: ");
printArray(arr, n);
return 0;
}
Output:

Enter the number of elements: 7

Enter 7 elements: 67
45
34
23
12
11
88
Original array: 67 45 34 23 12 11 88
Pass 1: 45 34 23 12 11 67 88
Pass 2: 34 23 12 11 45 67 88
Pass 3: 23 12 11 34 45 67 88
Pass 4: 12 11 23 34 45 67 88
Pass 5: 11 12 23 34 45 67 88
Pass 6: 11 12 23 34 45 67 88
Sorted array: 11 12 23 34 45 67 88
=== Code Execution Successful ==

43
c. Write a C program to Implement the insertion sort.

Code:

#include <stdio.h>
// Function to perform insertion sort
void insertionSort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i]; // Select the current element
j = i - 1;
// Shift elements of sorted part to find the correct position for key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert key at correct position
// Display the array after each pass (optional)
printf("Pass %d: ", i);
for (int k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main() {
int n, i;
// User input for array size
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// User input for array elements
printf("Enter %d elements: ", n);

44
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nOriginal array: ");
printArray(arr, n);
// Sorting the array using insertion sort
insertionSort(arr, n);
// Display the sorted array
printf("\nSorted array: ");
printArray(arr, n);

return 0;
}

Output:

Enter the number of elements: 5

Enter 5 elements: 23
567
89
11
99
Original array: 23 567 89 11 99
Pass 1: 23 567 89 11 99
Pass 2: 23 89 567 11 99
Pass 3: 11 23 89 567 99
Pass 4: 11 23 89 99 567
Sorted array: 11 23 89 99 567
=== Code Execution Successful ===

45
 ASSIGNMENT – 6
6 a) Write a C program to Implement the quick sort.

Code:

#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function to place the pivot element in the correct position
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as the pivot
int i = (low - 1); // Index of the smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // If current element is smaller than the pivot
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // Place pivot in the correct position
return (i + 1);
}
// QuickSort function to recursively sort the subarrays
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partitioning index
// Recursively sort the subarrays
quickSort(arr, low, pi - 1); // Left subarray
quickSort(arr, pi + 1, high); // Right subarray
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

46
// Main function
int main() {
int n;
// User input for array size
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// User input for array elements
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nOriginal array: ");
printArray(arr, n);
// Sorting the array using quicksort
quickSort(arr, 0, n - 1);
// Display the sorted array
printf("\nSorted array: ");
printArray(arr, n);
return 0;
}

Output:

Enter the number of elements: 6

Enter 6 elements: 98
56
23
67
11
89

Original array: 98 56 23 67 11 89

Sorted array: 11 23 56 67 89 98

47
b) Write a C program to sort the numbers in merge sort method.

Code:

// C program for the implementation of merge sort

#include <stdio.h>
#include <stdlib.h>
// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int leftArr[n1], rightArr[n2];
// Copy data to temporary arrays
for (i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
}
else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// Copy the remaining elements of leftArr[], if any
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;

48
}
// Copy the remaining elements of rightArr[], if any
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
// The subarray to be sorted is in the index range [left-right]
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Calculate the midpoint
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Sorting arr using mergesort
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);

return 0;
}

Output:5 6 7 11 12 13

49
c. Write a C program to sort the given numbers through heap sort
method.

Code:

// C Program for HeapSort

#include <stdio.h>
// Heapify function
void heapify(int arr[], int n, int i)
{
int temp, maximum, left_index, right_index;
// currently assuming i postion to
// be holding the largest value
maximum = i;
// right child index
right_index = 2 * i + 2;
// left child index
left_index = 2 * i + 1;
// if left index value is grater than the current index
// value
if (left_index < n && arr[left_index] > arr[maximum])
maximum = left_index;
// if right index value is grater than the current index
// value
if (right_index < n && arr[right_index] > arr[maximum])
maximum = right_index;
// checking if we needed swaping the elements or not
if (maximum != i) {
temp = arr[i];
arr[i] = arr[maximum];
arr[maximum] = temp;
heapify(arr, n, maximum);
}
}
// HeapSorting function
void heapsort(int arr[], int n)
{
int i, temp;
// performing heapify on the non leaf nodes so n/2 - 1
// to 0 are the non leaf nodes
for (i = n / 2 - 1; i >= 0; i--) {

50
 heapify(arr, n, i);
}
// the current array is changed to max heap
for (i = n - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
// Driver code
int main()
{
// initializing the array
int arr[] = { 20, 18, 5, 15, 3, 2 };
int n = 6;
// Displaying original array
printf("Original Array : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heapsort(arr, n);
// Displaying sorted array
printf("Array after performing heap sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Output:

Original Array : 20 18 5 15 3 2
Array after performing heap sort: 2 3 5 15 18 20

51
 ASSIGNMENT-7

A) Write a C program to Implement basic tree operations:

insertion, deletion, and traversal (in-order).

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

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

struct Node* createNode(int data) {

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

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

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

struct Node* findMin(struct Node* root) {

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

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

if (root == NULL) return root;
if (key < root->data) root->left = deleteNode(root->left, key);
else if (key > root->data) root->right = deleteNode(root->right,
key);

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

void inOrder(struct Node* root) {

if (root) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}

int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

printf("In-order traversal: ");

inOrder(root);

53
 printf("\nDeleting 20...\n");
root = deleteNode(root, 20);
printf("In-order after deletion: ");
inOrder(root);
return 0;
}

Output:

In-order traversal: 20 30 40 50 60 70 80
Deleting 20...
In-order after deletion: 30 40 50 60 70 80

54
b) Write a C program to Implement basic tree operations: insertion,
deletion, and traversal(pre-order).
Code:

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

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

struct Node* createNode(int data) {

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

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

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

struct Node* findMin(struct Node* root) {

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

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

if (root == NULL) return root;
if (key < root->data) root->left = deleteNode(root->left, key);
else if (key > root->data) root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) {

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

void preOrder(struct Node* root) {

if (root) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}

int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

printf("Pre-order traversal: ");

preOrder(root);

printf("\nDeleting 30...\n");

56
 root = deleteNode(root, 30);
printf("Pre-order after deletion: ");
preOrder(root);

return 0;
}
Output:
Pre-order traversal: 50 30 20 40 70 60 80
Deleting 30...
Pre-order after deletion: 50 40 20 70 60 80

57
c) Write a C program to Implement basic tree operations: insertion,
deletion, and traversal (post-order).

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

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

struct Node* createNode(int data) {

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

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

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

struct Node* findMin(struct Node* root) {

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

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

if (root == NULL) return root;
if (key < root->data) root->left = deleteNode(root->left, key);
else if (key > root->data) root->right = deleteNode(root->right,
key);
else {
if (root->left == NULL) {

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

void postOrder(struct Node* root) {

if (root) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}

int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

printf("Post-order traversal: ");

postOrder(root);

printf("\nDeleting 70...\n");

59
 root = deleteNode(root, 70);
printf("Post-order after deletion: ");
postOrder(root);

return 0;
}
Output:
Post-order traversal: 20 40 30 60 80 70 50
Deleting 70...
Post-order after deletion: 20 40 30 60 80 50

60
 ASSIGNMENT-8
a) Write a C program to implement BFS on a graph using a queue
data structure.
Code:
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

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

void enqueue(int vertex) {

if (rear == SIZE - 1)
return;
if (front == -1)
front = 0;
queue[++rear] = vertex;
}

int dequeue() {
if (front == -1 || front > rear)
return -1;
return queue[front++];
}

int isEmpty() {
return front == -1 || front > rear;
}

void bfs(int adj[SIZE][SIZE], int visited[], int start, int n) {

enqueue(start);
visited[start] = 1;

while (!isEmpty()) {
int vertex = dequeue();
printf("%d ", vertex);
for (int i = 0; i < n; i++) {

61
 if (adj[vertex][i] == 1 && !visited[i]) {
enqueue(i);
visited[i] = 1;
}
}
}
}

int main() {
int n = 5;
int adj[SIZE][SIZE] = {
{0,1,1,0,0},
{1,0,1,1,0},
{1,1,0,1,1},
{0,1,1,0,1},
{0,0,1,1,0}
};
int visited[SIZE] = {0};

printf("BFS traversal starting from node 0:\n");

bfs(adj, visited, 0, n);

return 0;
}
Output:
BFS traversal starting from node 0:
01234

62
b) Write a C program to implement DFS on a graph using a queue
data structure.
Code:
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int stack[SIZE], top = -1;

void push(int vertex) {

if (top == SIZE - 1)
return;
stack[++top] = vertex;
}

int pop() {
: if (top == -1)
return -1;
return stack[top--];
}

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

void dfs(int adj[SIZE][SIZE], int visited[], int start, int n) {

push(start);
while (!isEmpty()) {
int vertex = pop();
if (!visited[vertex]) {
printf("%d ", vertex);
visited[vertex] = 1;
for (int i = n - 1; i >= 0; i--) {
if (adj[vertex][i] == 1 && !visited[i])
push(i);
}

63
 }
}
}

int main() {
int n = 5;
int adj[SIZE][SIZE] = {
{0,1,1,0,0},
{1,0,1,1,0},
{1,1,0,1,1},
{0,1,1,0,1},
{0,0,1,1,0}
};
int visited[SIZE] = {0};

printf("DFS traversal starting from node 0:\n");

dfs(adj, visited, 0, n);

return 0;
}
Output:
DFS traversal starting from node 0:
02431

64
 ASSIGNMENT-9
a) Write a C program to implement Kruskal’s algorithm to find the
Minimum Spanning Tree (MST).
Code:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum number of edges
// Structure to represent an edge
struct Edge {
int src, dest, weight;
};
// Structure to represent a graph
struct Graph {
int V, E;
struct Edge edges[MAX];
};
// Structure to represent a subset for Union-Find
struct Subset {
int parent, rank;
};
// Create a graph
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
return graph;
}
// Find set of an element (uses path compression)
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// Union of two sets (uses union by rank)
void unionSets(struct Subset subsets[], int x, int y) {
int rootX = find(subsets, x);
int rootY = find(subsets, y);

65
if (subsets[rootX].rank < subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}
// Compare function for sorting edges
int compareEdges(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}
// Kruskal’s algorithm
void KruskalMST(struct Graph* graph) {
struct Edge result[MAX];
int e = 0, i = 0;
qsort(graph->edges, graph->E, sizeof(graph->edges[0]),
compareEdges);
struct Subset subsets[MAX];
for (int v = 0; v < graph->V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < graph->V - 1 && i < graph->E) {
struct Edge nextEdge = graph->edges[i++];
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
unionSets(subsets, x, y);
}
}
printf("Minimum Spanning Tree (MST):\n");
for (i = 0; i < e; i++)
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}

66
int main()
{
int V = 4, E = 5;
struct Graph* graph = createGraph(V, E);
graph->edges[0] = (struct Edge){0, 1, 10};
graph->edges[1] = (struct Edge){0, 2, 6};
graph->edges[2] = (struct Edge){0, 3, 5};
graph->edges[3] = (struct Edge){1, 3, 15};
graph->edges[4] = (struct Edge){2, 3, 4};
KruskalMST(graph);
return 0;
}
Output:
Minimum Spanning Tree (MST):
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

67
 9b) Write a C program to implement prime algorithm to find the
Minimum Spanning Tree (MST).
Code:
#include <stdio.h>
#include <limits.h>
#define MAX 100 // Maximum number of vertices
// Find the vertex with the minimum key value
int minKey(int key[], int visited[], int V) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!visited[v] && key[v] < min)
min = key[v], minIndex = v;
return minIndex;
}
// Print the MST
void printMST(int parent[], int graph[MAX][MAX], int V) {
printf("Minimum Spanning Tree (MST):\n");
for (int i = 1; i < V; i++)
printf("%d -- %d == %d\n", parent[i], i, graph[i][parent[i]]);
}
// Prim’s Algorithm
void primMST(int graph[MAX][MAX], int V) {
int parent[MAX]; // Stores MST edges
int key[MAX]; // Stores minimum weights
int visited[MAX] = {0}; // Visited vertices
for (int i = 0; i < V; i++)
key[i] = INT_MAX; // Initialize key values
key[0] = 0; // Start from vertex 0
parent[0] = -1; // First node is always root
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, visited, V);
visited[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && !visited[v] && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph, V);

68
}
int main() {
int V = 5;
int graph[MAX][MAX] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
primMST(graph, V);
return 0;
}
Output:
Minimum Spanning Tree (MST):
0 -- 1 == 2
1 -- 2 == 3
0 -- 3 == 6
1 -- 4 == 5

69
C) Write a C program to implement basic operations on a BST:
insertion, search, and traversal.

Code:
#include <stdio.h>
#include <stdlib.h>
// Structure for a BST Node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert a node into BST
struct Node* insert(struct Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
// Search for a value in BST
struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key) return root;
if (key < root->data) return search(root->left, key);
return search(root->right, key);
}
// In-order Traversal (Left, Root, Right)
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);

70
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("In-order Traversal: ");
inorder(root);
printf("\n");
int key = 40;
struct Node* found = search(root, key);
if (found) printf("Element %d found in BST.\n", key);
else printf("Element %d not found in BST.\n", key);
return 0;
}

Output:
In-order Traversal: 20 30 40 50 60 70 80
Element 40 found in BST.

71