DSA LAB PROGRAMES

1. Develop a Program in C for the following: a) Declare a calendar as an

array of 7 elements (A dynamically Created array) to represent 7 days
of a week. Each Element of the array is a structure having three fields.
The first field is the name of the Day (A dynamically allocated String),
The second field is the date of the Day (A integer), the third field is the
description of the activity for a particular day (A dynamically
allocated String). b) Write functions create(), read() and display(); to
create the calendar, to read the data from the keyboard and to print
weeks activity details report on screen.
Code:
#include <stdio.h>
#include <stdlib.h>

struct Day {
char* name; // Day name
int date; // Date
char* activity; // Activity description
};

struct Day* calendar[7];

void create() {
for (int i = 0; i < 7; i++) {
calendar[i] = (struct Day*)malloc(sizeof(struct Day));
calendar[i]->name = (char*)malloc(20);
calendar[i]->activity = (char*)malloc(100);
printf("Enter day name: ");
scanf("%s", calendar[i]->name);
printf("Enter date: ");
scanf("%d", &calendar[i]->date);
printf("Enter activity: ");
scanf(" %[^\n]", calendar[i]->activity);
 printf("\n");
}
}

void read() {
printf("\nReading Calendar:\n");
for (int i = 0; i < 7; i++) {
printf("Day %d\n", i + 1);
printf("Day name: %s\n", calendar[i]->name);
printf("Date: %d\n", calendar[i]->date);
printf("Activity: %s\n\n", calendar[i]->activity);
}
}

void display() {
printf("\nWeekly Activity Details:\n");
for (int i = 0; i < 7; i++) {
printf("Day %d: %s - %d, Activity: %s\n", i + 1, calendar[i]->name,
calendar[i]->date, calendar[i]->activity);
}
}

int main() {
printf("Creating Calendar:\n");
create();

read();

printf("Displaying Calendar:\n");
display();

// Free memory
for (int i = 0; i < 7; i++) {
free(calendar[i]->name);
free(calendar[i]->activity);
 free(calendar[i]);
}

return 0;
}

2. Develop a Program in C for the following operations on Strings. a.

Read a main String (STR), a Pattern String (PAT) and a Replace String
(REP) b. Perform Pattern Matching Operation: Find and Replace all
occurrences of PAT in STR with REP if PAT exists in STR. Report
suitable messages in case PAT does not exist in STR Support the
program with functions for each of the above operations. Don't use
Built-in functions.
Code:
#include<stdio.h>
#include<string.h>

char str[50], pat[20], rep[20], ans[50];

int c=0, m=0, i=0, j=0, k, flag=0;

void stringmatch() {
while(str[c] !='\0') {
if(str[m] == pat[i]) {
i++;
m++;
if(pat[i] == '\0') {
flag = 1;
for(k = 0; rep[k] != '\0'; k++, j++) {
 ans[j] = rep[k];
}
i = 0;
c = m;
}
} else {
ans[j] = str[c];
j++;
c++;
m = c;
i = 0;
}
}
ans[j] = '\0';
}

int main() {
printf("\nEnter the main string: ");
gets(str); // Use of gets() is unsafe, consider using fgets() for safety.
printf("\nEnter the pattern string: ");
gets(pat);
printf("\nEnter the replace string: ");
gets(rep);

stringmatch();
 if(flag == 1) {
printf("\nResultant string is: %s", ans);
} else {
printf("\nPattern string is not found");
}

return 0;
}
3. Develop a menu driven Program in C for the following operations on
STACK of Integers (Array Implementation of Stack with maximum size
MAX) a. Push an Element on to Stack b. Pop an Element from Stack c.
Demonstrate how Stack can be used to check Palindrome d.
Demonstrate Overflow and Underflow situations on Stack e. Display
the status of Stack f. Exit Support the program with appropriate
functions for each of the above operations.
Code:
#include <stdio.h>
#define MAX 5
int stack[MAX], top = -1;
void push(int element);
int pop();
void checkPalindrome();
void display();

int main() {
int choice, element;
 while (1) {
// Display menu
printf("\n~~~~~~Menu~~~~~~ :\n");
printf("1. Push an Element to Stack\n2. Pop an Element from
Stack\n3. Palindrome demo\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter an element to be pushed: ");
scanf("%d", &element);
push(element);
break;
case 2:
element = pop();
if (element != -1) printf("Popped element: %d\n", element);
break;
case 3:
checkPalindrome();
break;
case 4:
display();
break;
case 5:
 return 0;
default:
printf("Invalid choice. Try again.\n");
}
}
}

// Push operation
void push(int element) {
if (top == MAX - 1)
printf("Stack is full, can't push %d\n", element); // Stack full check
else
stack[++top] = element;
}

// Pop operation
int pop() {
if (top == -1) {
printf("Stack is empty, can't pop.\n"); // Stack empty check
return -1; // Return -1 if empty
}
return stack[top--];
}

// Check palindrome using stack

void checkPalindrome() {
if (top == -1) {
printf("Stack is empty, cannot check for palindrome.\n");
return;
}

// Using two pointers approach to check for palindrome

int i = 0, j = top;
while (i < j) {
if (stack[i] != stack[j]) {
printf("It is not a palindrome number\n");
return; // If mismatch is found, it's not a palindrome
}
i++;
j--;
}

printf("It is a palindrome number\n");

}

// Display stack content

void display() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
 printf("Stack content are:\n");
for (int i = top; i >= 0; i--) {
printf("| %d |\n", stack[i]);
}
}
}
4. Develop a Program in C for converting an Infix Expression to Postfix
Expression. Program should support for both parenthesized and free
parenthesized expressions with the operators: +, -, *, /, %
(Remainder), ^ (Power) and alphanumeric operands.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

char stack[MAX];
int top = -1;

// Function to push an operator to the stack

void push(char c) {
stack[++top] = c;
}

// Function to pop an operator from the stack

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

// Function to check operator precedence

int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/' || c == '%') return 2;
if (c == '+' || c == '-') return 1;
return -1;
}

// Function to convert infix to postfix

void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char symbol;

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

if (isalnum(symbol)) { // If operand, add it to postfix
postfix[j++] = symbol;
} else if (symbol == '(') { // If '(', push it to stack
push(symbol);
} else if (symbol == ')') { // If ')', pop until '('
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
 pop(); // Remove '('
} else { // If operator
while (top != -1 && precedence(stack[top]) >= precedence(symbol)) {
postfix[j++] = pop();
}
push(symbol);
}
}

while (top != -1) { // Pop remaining operators from stack

postfix[j++] = pop();
}
postfix[j] = '\0'; // Null-terminate the postfix expression
}

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

printf("Enter infix expression: ");

fgets(infix, MAX, stdin);
infixToPostfix(infix, postfix);

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

return 0;
}
5. Develop a Program in C for the following Stack Applications a.
Evaluation of Suffix expression with single digit operands and
operators: +, -, *, /, %, ^ b. Solving Tower of Hanoi problem with n
disks
Code:
a) #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>

int top = -1, s[20];

void push(int item) {

s[++top] = item;
}

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

int main() {
char postfix[90], symb;
int op1, op2, res;

printf("\nEnter a valid postfix expression:\n");

scanf("%s", postfix);

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

symb = postfix[i];

// If the symbol is a digit, push the integer value onto the stack
if (isdigit(symb)) {
push(symb - '0'); // Converts char to int
}
else {
// Pop two operands from the stack
op2 = pop();
op1 = pop();

// Perform the operation based on the current symbol

switch (symb) {
case '+': push(op1 + op2); break;
case '-': push(op1 - op2); break;
case '*': push(op1 * op2); break;
case '/': push(op1 / op2); break;
case '%': push(op1 % op2); break;
case '$': // Treat both '^' and '$' as exponentiation
case '^': push((int)pow(op1, op2)); break;
default: push(0); break;
}
 }
}

// The final result will be the only item left on the stack
res = pop();
printf("\nResult = %d\n", res);

return 0;
}
b) #include <stdio.h>

int moves = 0; // Move counter

void towerOfHanoi(int n, char src, char tgt, char aux) {

if (n == 1) {
printf("Move disk 1 from %c to %c\n", src, tgt);
moves++;
return;
}
towerOfHanoi(n - 1, src, aux, tgt);
printf("Move disk %d from %c to %c\n", n, src, tgt);
moves++;
towerOfHanoi(n - 1, aux, tgt, src);
}
int main() {
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
towerOfHanoi(n, 'A', 'C', 'B');
printf("Total number of moves: %d\n", moves);
return 0;
}
6. Develop a menu driven Program in C for the following operations on
Circular QUEUE of Characters (Array Implementation of Queue with
maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit Support the program with appropriate functions for each of the
above operations
code:
#include <stdio.h>

#define SIZE 5

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

// Check if the queue is full

int isFull() {
 return (rear + 1) % SIZE == front;
}

// Check if the queue is empty

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

// Insert an element
void enQueue(int element) {
if (isFull())
printf("\nQueue is full cannot push!!\n");
else {
rear = (rear + 1) % SIZE;
if (front == -1) front = 0; // If the queue is empty, initialize front
items[rear] = element;
printf("\nInserted -> %d\n", element);
}
}

// Remove an element
int deQueue() {
if (isEmpty()) {
printf("\nQueue is empty cannot pop!!\n");
return -1;
 }
int element = items[front];
if (front == rear) front = rear = -1; // Reset if queue becomes empty
else front = (front + 1) % SIZE;
printf("\nDeleted element -> %d\n", element);
return element;
}

// Display the queue with front, items, and rear

void display() {
if (isEmpty()) {
printf("\nQueue is empty\n");
return;
}

// Display front, items and rear

printf("\nFront -> %d\n", front);
printf("Items -> ");

int i = front;
while (i != rear) {
printf("%d ", items[i]);
i = (i + 1) % SIZE; // Circular increment
}
printf("%d ", items[rear]); // Print the rear element
 printf("\nRear -> %d\n", rear);
}

int main() {
int choice, x;
do {
printf("\n1: Insert\n2: Delete\n3: Display\n0: Exit\nEnter choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
printf("Enter element: ");
scanf("%d", &x);
enQueue(x);
break;
case 2:
deQueue();
break;
case 3:
display();
break;
case 0:
printf("\nExiting.\n");
break;
 default:
printf("\nInvalid choice\n");
}
} while (choice != 0);
return 0;
}
7. Develop a menu driven Program in C for the following operations on
Singly Linked List (SLL) of Student Data with the fields: USN, Name,
Programme, Sem, PhNo
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit
code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Student {

char usn[15], name[30], prog[30], phno[15];
int sem;
struct Student *next;
} Student;

Student *head = NULL;

void createSLL() {
int n;
printf("Enter number of students to create the list: ");
scanf("%d", &n);

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

Student *newNode = (Student *)malloc(sizeof(Student));
printf("Enter USN, Name, Programme, Sem, PhNo for Student %d: \n",
i+1);
scanf("%s %s %s %d %s", newNode->usn, newNode->name,
newNode->prog, &newNode->sem, newNode->phno);
newNode->next = head;
head = newNode;
}
// Display the list after creation
}

void display() {
if (!head) {
printf("The list is empty.\n");
return;
}
Student *temp = head;
int count = 0;
while (temp) {
 printf("USN: %s, Name: %s, Programme: %s, Sem: %d, PhNo:
%s\n",temp->usn, temp->name, temp->prog, temp->sem, temp->phno);
temp = temp->next;
count++;
}
printf("Total Students: %d\n", count);
}

void insertEnd() {
Student *newNode = (Student *)malloc(sizeof(Student));
printf("Enter USN, Name, Programme, Sem, PhNo: \n");
scanf("%s %s %s %d %s", newNode->usn, newNode->name, newNode-
>prog, &newNode->sem, newNode->phno);
newNode->next = NULL;
if (!head) head = newNode;
else {
Student *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
}
}

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

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

int main() {
int choice;
do {
printf("\n1. Create SLL of students Nodes\n2. Display\n3. Insert
End\n4. Delete Front\n5. Delete End\n6. Exit\nEnter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: createSLL(); break;
 case 2: display(); break;
case 3: insertEnd(); break;
case 4: deleteFront(); break;
case 5: deleteEnd(); break;
}
} while (choice != 6);
return 0;
}
8. Develop a menu driven Program in C for the following operations on
Doubly Linked List (DLL) of Employee Data with the fields: SSN, Name,
Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit
code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Employee {

char ssn[15], name[50], dept[30], designation[30], phone[15];
float salary;
struct Employee *prev, *next;
} Employee;

Employee *head = NULL;

// Function to create a new employee node

Employee* createNode() {
Employee *newNode = (Employee *)malloc(sizeof(Employee));
printf("Enter the ssn, Name, Department, Designation, Salary, PhoneNo
of the employee:\n");
scanf("%s %s %s %s %f %s", newNode->ssn, newNode->name,
newNode->dept, newNode->designation, &newNode->salary, newNode-
>phone);
newNode->prev = newNode->next = NULL;
return newNode;
}

// Create a Doubly Linked List (DLL) of employees

void createDLL() {
int n;
printf("Enter the number of Employees: ");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
Employee *newNode = createNode();
if (!head) head = newNode;
else {
Employee *temp = head;
 while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
}
}

// Insert an employee at the end of the DLL

void insertEnd() {
Employee *newNode = createNode();
if (!head) head = newNode;
else {
Employee *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
}

// Display the DLL of employees

void displayDLL() {
Employee *temp = head;
int count = 0;
if (!temp) {
printf("List is empty\n");
 return;
}
while (temp) {
printf("SSN: %s, Name: %s, Dept: %s, Designation: %s, Salary: %.2f,
Phone: %s\n",
temp->ssn, temp->name, temp->dept, temp->designation, temp-
>salary, temp->phone);
temp = temp->next;
count++;
}
printf("Total Employees: %d\n", count);
}

// Delete an employee from the end of the DLL

void deleteEnd() {
if (!head) {
printf("List is empty\n");
} else if (!head->next) { // Only one node
free(head);
head = NULL;
} else {
Employee *temp = head;
while (temp->next) temp = temp->next;
temp->prev->next = NULL;
free(temp);
}
}

// Insert an employee at the front of the DLL

void insertFront() {
Employee *newNode = createNode();
if (!head) {
head = newNode;
} else {
head->prev = newNode;
newNode->next = head;
head = newNode;
}
}

// Delete an employee from the front of the DLL

void deleteFront() {
if (!head) {
printf("List is empty\n");
} else if (!head->next) { // Only one node
free(head);
head = NULL;
} else {
Employee *temp = head;
head = head->next;
head->prev = NULL;
 free(temp);
}
}

// Double Ended Queue (DEQ) Demo

void deqdemo() {
int ch;
while (1) {
printf("\nDemo Double Ended Queue Operation\n");
printf("1: InsertQueueFront\n2: DeleteQueueFront\n3:
InsertQueueRear\n4: DeleteQueueRear\n5: Display Status\n6: Exit\n");
scanf("%d", &ch);

switch (ch) {
case 1:
insertFront();
break;
case 2:
deleteFront();
break;
case 3:
insertEnd();
break;
case 4:
deleteEnd();
 break;
case 5:
displayDLL();
break;
case 6:
return;
default:
printf("Invalid choice! Exiting demo.\n");
return;
}
}
}

// Menu to choose options

void menu() {
int choice;
do {
printf("\n1: Create DLL of Employee Nodes\n");
printf("2: Display Status\n");
printf("3: Insert At End\n");
printf("4: Delete At End\n");
printf("5: Insert At Front\n");
printf("6: Delete At Front\n");
printf("7: Double Ended Queue Demo using DLL\n");
printf("8: Exit\n");
 printf("Please enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: createDLL(); break;
case 2: displayDLL(); break;
case 3: insertEnd(); break;
case 4: deleteEnd(); break;
case 5: insertFront(); break;
case 6: deleteFront(); break;
case 7: deqdemo(); break;
case 8: printf("Exiting...\n"); break;
default: printf("Invalid choice!\n");
}
} while (choice != 8);
}

int main() {
menu();
return 0;
}
9. Develop a Program in C for the following operationson Singly Circular
Linked List (SCLL) with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-
4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store
the result in POLYSUM(x,y,z) Support the program with appropriate
functions for each of the above operations
code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct node {
int coef, xexp, yexp, zexp;
struct node* link;
};

typedef struct node* NODE;

NODE getnode() {
NODE x = (NODE)malloc(sizeof(struct node));
if (!x) exit(1);
return x;
}

NODE attach(NODE head, int coef, int xexp, int yexp, int zexp) {
NODE temp = getnode();
temp->coef = coef;
temp->xexp = xexp;
temp->yexp = yexp;
 temp->zexp = zexp;
NODE cur = head;
while (cur->link != head) cur = cur->link;
cur->link = temp;
temp->link = head;
return head;
}

NODE read_poly(NODE head) {

int n, coef, xexp, yexp, zexp;
printf("Enter number of terms: ");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
printf("Term %d: Coef = ", i + 1);
scanf("%d", &coef);
printf("Enter Pow(x), Pow(y), Pow(z): ");
scanf("%d %d %d", &xexp, &yexp, &zexp);
head = attach(head, coef, xexp, yexp, zexp);
}
return head;
}

void display(NODE head) {

NODE temp = head->link;
while (temp != head) {
 printf("%dx^%dy^%dz^%d", temp->coef, temp->xexp, temp->yexp,
temp->zexp);
if (temp->link != head) printf(" + ");
temp = temp->link;
}
printf("\n");
}

int evaluate(NODE head) {

int x, y, z, sum = 0;
printf("Enter values for x, y, z: ");
scanf("%d %d %d", &x, &y, &z);
NODE poly = head->link;
while (poly != head) {
sum += poly->coef * pow(x, poly->xexp) * pow(y, poly->yexp) * pow(z,
poly->zexp);
poly = poly->link;
}
return sum;
}

NODE poly_sum(NODE head1, NODE head2) {

NODE a = head1->link, b = head2->link, head3 = getnode();
head3->link = head3;
while (a != head1 || b != head2) {
 if (a == head1 || (b != head2 && (b->xexp < a->xexp || (b->xexp == a->xexp
&& (b->yexp < a->yexp || (b->yexp == a->yexp && b->zexp < a->zexp)))))) {
head3 = attach(head3, b->coef, b->xexp, b->yexp, b->zexp);
b = b->link;
} else if (b == head2 || (a != head1 && (a->xexp < b->xexp || (a->xexp ==
b->xexp && (a->yexp < b->yexp || (a->yexp == b->yexp && a->zexp < b-
>zexp)))))) {
head3 = attach(head3, a->coef, a->xexp, a->yexp, a->zexp);
a = a->link;
} else {
head3 = attach(head3, a->coef + b->coef, a->xexp, a->yexp, a->zexp);
a = a->link;
b = b->link;
}
}
return head3;
}

int main() {
NODE head1 = getnode(), head2 = getnode(), head3 = getnode();
head1->link = head1; head2->link = head2; head3->link = head3;

int ch;
while (1) {
printf("\n~~~Menu~~~\n1. Represent and Evaluate a Polynomial\n2.
Find the sum of two polynomials\nEnter your choice: ");
 scanf("%d", &ch);

if (ch == 1) {
printf("\nPolynomial evaluation\n");
head1 = read_poly(head1);
printf("Polynomial: "); display(head1);
printf("Result: %d\n", evaluate(head1));
}
else if (ch == 2) {
printf("\nEnter POLY1(x, y, z):\n");
head1 = read_poly(head1);
printf("POLY1: "); display(head1);

printf("\nEnter POLY2(x, y, z):\n");

head2 = read_poly(head2);
printf("POLY2: "); display(head2);

head3 = poly_sum(head1, head2);

printf("Polynomial sum: "); display(head3);
} else {
break;
}
}
return 0;
}
10. Develop a menu driven Program in C for the following operations on
Binary Search Tree (BST) of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate
message
d. Exit
code: #include <stdio.h>
#include <stdlib.h>

// Define structure for the node

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

typedef struct node* NODE;

// Function to create a new node

NODE createNode(int data) {
NODE newNode = (NODE)malloc(sizeof(struct node));
if (!newNode) {
printf("Memory allocation error!\n");
return NULL;
}
 newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a node into the BST

NODE insert(NODE root, int data) {
if (root == NULL) return createNode(data);

if (data < root->data)

root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);

return root;
}

// Inorder traversal: Left, Root, Right

void inorder(NODE root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Preorder traversal: Root, Left, Right
void preorder(NODE root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

// Postorder traversal: Left, Right, Root

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

// Function to search for a key in the BST

NODE search(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);
}

// Main function
int main() {
NODE root = NULL;
int choice, key, n, i;

do {
// Display menu options
printf("\n~~~~BST MENU~~~~\n");
printf("1. Create a BST\n");
printf("2. Search\n");
printf("3. BST Traversals:\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: // Create BST
printf("Enter the number of elements: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Enter The value: ");
scanf("%d", &key);
 root = insert(root, key);
}
break;

case 2: // Search
printf("Enter the value to search: ");
scanf("%d", &key);
NODE found = search(root, key);
if (found != NULL) {
printf("Element %d found in the BST.\n", key);
} else {
printf("Element %d not found in the BST.\n", key);
}
break;

case 3: // Traversals
printf("The Preorder display: ");
preorder(root);
printf("\nThe Inorder display: ");
inorder(root);
printf("\nThe Postorder display: ");
postorder(root);
printf("\n");
break;
 case 4: // Exit
printf("Exiting program.\n");
break;

default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 4);

return 0;
}
11. Develop a Program in C for the following operations on Graph(G) of
Cities a. Create a Graph of N cities using Adjacency Matrix. b. Print all the
nodes reachable from a given starting node in a digraph using DFS/BFS
method
Code:
#include <stdio.h>
#include <stdlib.h>

#define MAX 20

int graph[MAX][MAX], visited[MAX];

void BFS(int start, int n) {

int queue[MAX], front = 0, rear = 0;
visited[start] = 1;
 queue[rear++] = start;

printf("Nodes reachable from starting vertex %d are: ", start + 1);

while (front < rear) {
int v = queue[front++];
printf("%d ", v + 1);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
printf("\n");
}

void DFS(int v, int n) {

visited[v] = 1;
printf("%d ", v + 1);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) DFS(i, n);
}
}

void resetVisited(int n) {
 for (int i = 0; i < n; i++) visited[i] = 0;
}

int main() {
int n, start, choice;

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

scanf("%d", &n);

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

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);

printf("\nEnter the starting vertex: ");

scanf("%d", &start);
start--;

while (1) {
printf("\n==>1. BFS: Print all nodes reachable from a given starting
node\n");
printf("==>2. DFS: Print all nodes reachable from a given starting
node\n");
printf("==>3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
 switch (choice) {
case 1:
resetVisited(n);
BFS(start, n);
for (int i = 0; i < n; i++) if (!visited[i]) printf("The vertex that is not
reachable is %d\n", i + 1);
break;
case 2:
resetVisited(n);
printf("Nodes reachable from starting vertex %d are: ", start + 1);
DFS(start, n);
printf("\n");
break;
case 3:
exit(0);
default:
printf("Invalid choice.\n");
}
}

return 0;
}
12. Given a File of N employee records with a set K of Keys (4-digit) which
uniquely determine the records in file F. Assume that file F is maintained in
memory by a Hash Table (HT) of m memory locations with L as the set of
memory addresses (2-digit) of locations in HT. Let the keys in K and
addresses in L are Integers. Develop a Program in C that uses Hash
function H: K →L as H(K)=K mod m (remainder method), and implement
hashing technique to map a given key K to the address space L. Resolve the
collision (if any) using linear probing.
Code:
#include <stdio.h>
#include <stdlib.h>

#define MAX 10 // Size of the hash table

// Hash Table array

int hashTable[MAX];

// Hash function (remainder method)

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

// Function to insert a key into the hash table using linear probing
void insert(int key, int m) {
int index = hashFunction(key, m);
int originalIndex = index;

// Linear probing to resolve collisions

while (hashTable[index] != -1) {
 index = (index + 1) % m;
if (index == originalIndex) {
printf("Hash Table is full\n");
return;
}
}
hashTable[index] = key;
}

// Function to display the hash table contents

void display(int m) {
printf("\nHash Table contents are:\n");
for (int i = 0; i < m; i++) {
printf("T[%d] --> %d\n", i, hashTable[i]);
}
}

int main() {
int n, key, m;

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

for (int i = 0; i < MAX; i++) {
hashTable[i] = -1;
}
 // Take the number of employee records and table size as input
printf("Enter the number of employee records (N): ");
scanf("%d", &n);
printf("Enter the two digit memory locations (m) for hash table: ");
scanf("%d", &m);

// Take the key values for N employee records and insert into hash table
printf("Enter the four digit key values (K) for %d Employee Records:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &key);
insert(key, m);
}

// Display the hash table contents

display(m);

return 0;
}

11) alter
#include <stdio.h>
#include <stdlib.h>

#define MAX 20
int graph[MAX][MAX], visited[MAX];

void BFS(int start, int n) {

int queue[MAX], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;

printf("BFS: Nodes reachable from starting vertex %d: ", start + 1);
while (front < rear) {
int v = queue[front++];
printf("%d ", v + 1);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
printf("\n");
}

void DFS(int v, int n) {

visited[v] = 1;
printf("%d ", v + 1);
for (int i = 0; i < n; i++) {
 if (graph[v][i] && !visited[i]) DFS(i, n);
}
}

void resetVisited(int n) {
for (int i = 0; i < n; i++) visited[i] = 0;
}

int main() {
int n, start, choice;

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

scanf("%d", &n);

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

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

printf("Enter the starting vertex: ");

scanf("%d", &start);
start--;
 while (1) {
printf("\n1. BFS\n2. DFS\n3. Exit\nEnter choice: ");
scanf("%d", &choice);

resetVisited(n);
switch (choice) {
case 1:
BFS(start, n);
break;
case 2:
printf("DFS: Nodes reachable from starting vertex %d: ", start + 1);
DFS(start, n);
printf("\n");
break;
case 3:
exit(0);
default:
printf("Invalid choice\n");
}
}

return 0;
}