VIJAYA VITTALA INSTITUTE OF TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

BANGALORE

SUBJECT NAME: -DATA STRUCTURE MANUAL

SUBJECT CODE: BCL305

2022 scheme

Created By
Mr. Aayush Poudel.
Programs:

Program 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.

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

// Structure to represent a day of the week

struct Day {
char *name;
int date;
char *activity;
};

// Function to create a day

struct Day* createDay(char *name, int date, char *activity) {

struct Day *day = (struct Day*)malloc(sizeof(struct Day));
day->name = strdup(name);
day->date = date;
day->activity = strdup(activity);
return day;
}

// Function to display a single day

void displayDay(struct Day *day)

{
printf("Day %s (%d): %s\n", day->name, day->date, day->activity);
}
// main

int main() {
int numDays = 7;
struct Day *calendar[numDays];
printf("Enter the details for the calendar:\n");

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

char name[20];
int date;
char activity[100];
 printf("Enter the name of the day: ");
scanf("%s", name);
printf("Enter the date: ");
scanf("%d", &date);
printf("Enter the activity for the day: ");
scanf(" %[^\n]", activity);

calendar[i] = createDay(name, date, activity);

}

printf("Displaying the Calendar\n");

printf("Week's Activity Details:\n");

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

displayDay(calendar[i]);
}

// Free dynamically allocated memory

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

free(calendar[i]->name);
free(calendar[i]->activity);
free(calendar[i]);
}

return 0;
}

Sample output:

Enter the details for the calendar:

Enter the name of the day: Monday.

Enter the date: 1.
Enter the activity for the day: Work and meetings.

Enter the name of the day: Tuesday.

Enter the date: 2.
Enter the activity for the day: Gym and shopping.

Enter the name of the day: Wednesday.

Enter the date: 3.
Enter the activity for the day: Movie night.

Enter the name of the day: Thursday.

Enter the date: 4.
Enter the activity for the day: Dinner with friends.

Enter the name of the day: Friday.

Enter the date: 5.
Enter the activity for the day: Beach Day.

Enter the name of the day: Saturday.

Enter the date: 6.
Enter the activity for the day: Hiking.
Enter the name of the day: Sunday.
Enter the date: 7.
Enter the activity for the day: Relaxation.

Displaying the Calendar

Week's Activity Details:
Day Monday (1): Work and meetings
Day Tuesday (2): Gym and shopping
Day Wednesday (3): Movie night
Day Thursday (4): Dinner with friends
Day Friday (5): Beach Day
Day Saturday (6): Hiking
Day Sunday (7): Relaxation
Program 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.

#include <stdio.h>

// Function to read a string from the user

void readString(char *str, const char *prompt)
{
printf("%s: ", prompt);
scanf(" %[^\n]", str);
}

// Function to perform pattern matching and replacement

void findAndReplace(char *str, const char *pat, const char *rep)
{
char result[1000]; // Assuming a maximum length for the result string
int strLen = 0;
while (str[strLen] != '\0') {
strLen++;
}
int patLen = 0;
while (pat[patLen] != '\0') {
patLen++;
}
int repLen = 0;
while (rep[repLen] != '\0') {
repLen++;
}
int i = 0, k = 0;
int patternfound = 0; // Variable to track if the pattern was found

while (i < strLen)

{
int match = 1; // Assume a match
for (int j = 0; j < patLen; j++) {
if (str[i + j] != pat[j]) {
match = 0; // Not a match
break;
}
}

if (match) {
// Pattern found, copy the replacement
patternfound = 1; // Set patternfound to 1
for (int r = 0; r < repLen; r++) {
result[k] = rep[r];
 k++;
}
i += patLen;
} else {
// No pattern match, copy the original character
result[k] = str[i];
i++;
k++;
}
}

result[k] = '\0'; // Null-terminate the result string

if (!patternfound)
{
printf("Pattern not found in the main string. No replacements were made.\n");
}
else {
// Copy the result back to the original string
for (i = 0; i <= k; i++) {
str[i] = result[i];
}
}
}
//main
int main()
{
char mainStr[1000];
char pattern[100];
char replacement[100];

// Read the main string, pattern, and replacement from the user
readString(mainStr, "Enter the main string");
readString(pattern, "Enter the pattern to search for");
readString(replacement, "Enter the replacement string");

// Perform pattern matching and replacement

findAndReplace(mainStr, pattern, replacement);

printf("Modified String: %s\n", mainStr);

return 0;
}

Sample output 1:
Enter the main string: This is a test sentence with test pattern.
Enter the pattern to search for: test.
Enter the replacement string: sample.

Modified String: This is a sample sentence with sample pattern.

Sample output 2:
Enter the main string: This is a test sentence with a pattern.
Enter the pattern to search for: sample.
Enter the replacement string: pattern.
Pattern not found in the main string. No replacements were made.
Modified String: This is a test sentence with a pattern.
Program 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

#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int st[MAX], top = -1, status = 0, count;
void push(int st[], int val);
int pop(int st[]);
int peek(int st[]);
void display(int st[]);
void palindrome(int st[]);

void main()
{
int val, option;
do {
printf("\nMenu");
printf("\n1.PUSH");
printf("\n2.POP");
printf("\n3.PEEK");
printf("\n4.DISPLAY");
printf("\n5.PALINDROME");
printf("\nEXIT");
printf("\nenter your option");
scanf("%d", &option);
switch (option)
{
case 1:
printf("\nenter number to push");
scanf("%d", &val);
push(st, val);
display(st);
break;
case 2:
val = pop(st);
if (val != -1)
printf("\ndeleted value %d", val);
display(st);
break;
case 3:
val = peek(st);
if (val != -1)
printf("top of stack:%d", val);
break;
case 4:
display(st);
break;
case 5:
palindrome(st);
break;
case 6:
exit(0);
break;
}
}
while (option != 6);
return;
}
void push(int st[], int val)
{
if (top == MAX - 1)
{
printf("\nSTACK OVERFLOW");
}
else
{
top++;
st[top] = val;
status++;
}
}
int pop(int st[])
{
int val;
if (top == -1)
{
printf("\nSTOCK UNDERFLOW");
return -1;
}
else
{
val = st[top];
top--;
status--;
return val;
}
}
void display(int st[])
{
int front,rear, i = front;
if (front == -1 && rear == -1)
printf("\nStack Overflow");
else
{
printf("\nthe stack contents are");
for (i = top; i >= 0; i--)
printf("\n%d", st[i]);
printf("\n");
}
}
int peek(int st[])
{
if (top == -1)
{
printf("\nStack Overflow");
return -1;
}
else
return (st[top]);
}
void palindrome(int st[])
{
int i, temp;
temp = status;
for (i = 0; i < temp; i++)
{
if (st[i] == pop(st))
count++;
}
if (temp == count)
printf("\nstack contents are palindrome");
else
printf("\nstack contents are not palindrome");

Sample OUTPUT:
Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option1
enter number to push10
the stack contents are
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option1
enter number to push20
the stack contents are
20
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option1
enter number to push30
the stack contents are
30
20
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option2
deleted value 30
the stack contents are
20
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option3
top of stack:20
Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option1
enter number to push20
the stack contents are
20
20
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option1
enter number to push10
the stack contents are
10
20
20
10

Menu
1.PUSH
2.POP
3.PEEK
4.DISPLAY
5.PALINDROME
EXIT
enter your option5
stack contents are palindrome
Program 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.

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

#define MAX_STACK_SIZE 100

#define MAX_OUTPUT_SIZE 100

// Structure for the stack

struct Stack {
char items[MAX_STACK_SIZE];
int top;
};

// Function to initialize the stack

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

// Function to push an element onto the stack

void push(struct Stack* stack, char item) {
if (stack->top < MAX_STACK_SIZE - 1) {
stack->items[++stack->top] = item;
} else {
printf("Stack overflow\n");
exit(1);
}
}

// Function to pop an element from the stack

char pop(struct Stack* stack) {
if (stack->top >= 0) {
return stack->items[stack->top--];
} else {
printf("Stack underflow\n");
exit(1);
}
}

// Function to check if the stack is empty

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

// Function to get the precedence of an operator

int getPrecedence(char operator) {
switch (operator) {
case '^':
 return 3;
case '*':
case '/':
case '%':
return 2;
case '+':
case '-':
return 1;
default:
return 0;
}
}

// Function to convert infix expression to postfix expression

void infixToPostfix(const char* infix, char* postfix) {
struct Stack operatorStack;
initialize(&operatorStack);

int infixLen = strlen(infix);

int postfixIdx = 0;

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

char currentChar = infix[i];

if ((currentChar >= 'a' && currentChar <= 'z') || (currentChar >= '0' && currentChar <= '9')) {
postfix[postfixIdx++] = currentChar;
} else if (currentChar == '(') {
push(&operatorStack, currentChar);
} else if (currentChar == ')') {
while (!isEmpty(&operatorStack) && operatorStack.items[operatorStack.top] != '(') {
postfix[postfixIdx++] = pop(&operatorStack);
}
if (!isEmpty(&operatorStack) && operatorStack.items[operatorStack.top] == '(') {
pop(&operatorStack);
}
} else {
while(!
isEmpty(&operatorStack)&&getPrecedence(currentChar)<=getPrecedence(operatorStack.items[ope
ratorStack.top]))
{
postfix[postfixIdx++] = pop(&operatorStack);
}
push(&operatorStack, currentChar);
}
}

while (!isEmpty(&operatorStack)) {
postfix[postfixIdx++] = pop(&operatorStack);
}

postfix[postfixIdx] = '\0';
}
//main
int main() {
char infixExpression[100];
char postfixExpression[MAX_OUTPUT_SIZE];
 printf("Enter an infix expression: ");
scanf("%s", infixExpression);

infixToPostfix(infixExpression, postfixExpression);
printf("Postfix expression: %s\n", postfixExpression);

return 0;
}

Sample output

Enter an infix expression: (a+b)*(c-d)/e^f

Postfix expression: ab+cd-ef^*/

Program 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

a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %,

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

// Structure for the stack

struct Stack {
int top;
int items[100];
};

// Function to initialize the stack

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

// Function to push an element onto the stack

void push(struct Stack* stack, int item) {
if (stack->top < 99) {
stack->items[++stack->top] = item;
} else {
printf("Stack overflow\n");
exit(1);
}
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (stack->top >= 0) {
return stack->items[stack->top--];
} else {
printf("Stack underflow\n");
exit(1);
}
}

// Function to evaluate a postfix expression

int evaluatePostfix(const char* postfix) {
struct Stack operandStack;
initialize(&operandStack);

int i = 0;
while (postfix[i] != '\0') {
char currentChar = postfix[i];
 if (isdigit(currentChar)) {
push(&operandStack, currentChar - '0');
} else {
int operand2 = pop(&operandStack);
int operand1 = pop(&operandStack);

switch (currentChar) {
case '+':
push(&operandStack, operand1 + operand2);
break;
case '-':
push(&operandStack, operand1 - operand2);
break;
case '*':
push(&operandStack, operand1 * operand2);
break;
case '/':
push(&operandStack, operand1 / operand2);
break;
case '%':
push(&operandStack, operand1 % operand2);
break;
}
}

i++;
}

return pop(&operandStack);
}
//main
int main() {
char postfixExpression[100];

printf("Enter a postfix expression: ");

scanf("%s", postfixExpression);

int result = evaluatePostfix(postfixExpression);

printf("Result: %d\n", result);

return 0;
}

Sample output :

Enter a postfix expression: 23*5+

Result: 11
 B. Solving Tower of Hanoi problem with n disks

#include <stdio.h>

// Function to solve the Tower of Hanoi problem

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);
}
//main
int main() {
int n;

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

scanf("%d", &n);

towerOfHanoi(n, 'A', 'B', 'C');

return 0;
}

Sample output

Enter the number of disks: 3

Move disk 1 from A to C

Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Program 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.

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

#define MAX 5 // Maximum size of the circular queue

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

// Function to check if the circular queue is full

int isFull() {
return ((front == 0 && rear == MAX - 1) || (front == rear + 1));
}

// Function to check if the circular queue is empty

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

// Function to insert an element into the circular queue

void insertElement(char element) {
if (isFull()) {
printf("Queue is full (Overflow)!\n");
} else {
if (front == -1) {
front = 0;
}
rear = (rear + 1) % MAX;
queue[rear] = element;
printf("Element '%c' inserted into the queue.\n", element);
}
}

// Function to delete an element from the circular queue

void deleteElement() {
if (isEmpty()) {
printf("Queue is empty (Underflow)!\n");
} else {
printf("Element '%c' deleted from the queue.\n", queue[front]);
 if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % MAX;
}
}
}

// Function to display the circular queue

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

printf("Circular Queue: ");

int i = front;
while (1) {
printf("%c ", queue[i]);
if (i == rear) {
break;
}
i = (i + 1) % MAX;
}
printf("\n");
}
//main
int main()
{
int choice;
char element;
while (1)
{
printf("\nCircular Queue Menu:\n");
printf("1. Insert Element\n");
printf("2. Delete Element\n");
printf("3. Demonstrate Overflow and Underflow\n");
printf("4. Display Queue\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the element to insert: ");
scanf(" %c", &element);
insertElement(element);
break;
case 2:
deleteElement();
break;
case 3:
if (isFull()) {
printf("Queue is full (Overflow)!\n");
} else if (isEmpty()) {
printf("Queue is empty (Underflow)!\n");
 } else {
printf("Queue is neither empty nor full.\n");
}
break;
case 4:
displayQueue();
break;
case 5:
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

Sample output

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 1
Enter the element to insert: A
Element 'A' inserted into the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 1
Enter the element to insert: B
Element 'B' inserted into the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 4
Circular Queue: A B

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 2
Element 'A' deleted from the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 4
Circular Queue: B

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 3
Queue is neither empty nor full.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 1
Enter the element to insert: C
Element 'C' inserted into the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 1
Enter the element to insert: D
Element 'D' inserted into the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 1
Enter the element to insert: E
Element 'E' inserted into the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
 5. Exit
Enter your choice: 1
Enter the element to insert: F
Queue is full (Overflow)!

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 4
Circular Queue: B C D E

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 2
Element 'B' deleted from the queue.

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 4
Circular Queue: C D E

Circular Queue Menu:

1. Insert Element
2. Delete Element
3. Demonstrate Overflow and Underflow
4. Display Queue
5. Exit
Enter your choice: 5
Program 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

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

// Define the structure for student data

struct Student {
char usn[20];
char name[50];
char programme[20];
int sem;
char phNo[15];
struct Student* next;
};

// Global pointer for the head of the linked list

struct Student* head = NULL;

// Function to create a new student node

struct Student* createStudent() {
struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student));

if (newStudent == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}

printf("Enter USN: ");

scanf("%s", newStudent->usn);
printf("Enter Name: ");
scanf(" %s", newStudent->name);
printf("Enter Programme: ");
scanf(" %s", newStudent->programme);
printf("Enter Semester: ");
scanf("%d", &newStudent->sem);
printf("Enter Phone Number: ");
scanf("%s", newStudent->phNo);

newStudent->next = NULL;
return newStudent;
}

// Function to insert a student at the front of the list (front insertion)

void insertFront() {
struct Student* newStudent = createStudent();
newStudent->next = head;
head = newStudent;
printf("Student inserted at the front of the list.\n");
}

// Function to display the linked list and count the number of nodes
void displayAndCount() {
struct Student* current = head;
int count = 0;

if (current == NULL) {
printf("The list is empty.\n");
return;
}

printf("Student List:\n");
while (current != NULL)
{
printf("USN: %s\nName: %s\nProgramme: %s\nSemester: %d\nPhone Number: %s\n\n",
current->usn, current->name, current->programme, current->sem, current->phNo);
current = current->next;
count++;
}

printf("Total number of students: %d\n", count);

}

// Function to insert a student at the end of the list

void insertEnd() {
struct Student* newStudent = createStudent();
newStudent->next = NULL;

if (head == NULL) {
head = newStudent;
} else {
struct Student* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newStudent;
}

printf("Student inserted at the end of the list.\n");

}

// Function to delete a student from the front of the list

void deleteFront() {
if (head == NULL) {
printf("The list is empty. Nothing to delete.\n");
return;
}
 struct Student* temp = head;
head = head->next;
free(temp);
printf("Student deleted from the front of the list.\n");
}

// Function to delete a student from the end of the list

void deleteEnd() {
if (head == NULL) {
printf("The list is empty. Nothing to delete.\n");
return;
}

if (head->next == NULL) {
free(head);
head = NULL;
printf("Student deleted from the end of the list.\n");
return;
}

struct Student* current = head;

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

free(current->next);
current->next = NULL;
printf("Student deleted from the end of the list.\n");
}

// Function to free the memory and exit the program

void exitProgram() {
struct Student* current = head;
while (current != NULL) {
struct Student* temp = current;
current = current->next;
free(temp);
}
exit(0);
}

int main() {
int choice;

while (1) {
printf("\nStudent Data Menu:\n");
printf("1. Create a student list by using front insertion\n");
printf("2. Display the list and count the number of students\n");
printf("3. Insert a student at the end of the list\n");
printf("4. Delete a student from the front of the list\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
 case 1:
insertFront();
break;
case 2:
displayAndCount();
break;
case 3:
insertEnd();
break;
case 4:
deleteFront();
break;
case 5:
exitProgram();
break;
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

Sample output

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 1
Enter USN: 1234
Enter Name: Alice
Enter Programme: Engineering
Enter Semester: 3
Enter Phone Number: 123-456-7890
Student inserted at the front of the list.

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 1
Enter USN: 5678
Enter Name: Bob
Enter Programme: Computer Science
Enter Semester: 5
Enter Phone Number: 987-654-3210
Student inserted at the front of the list.

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 2
Student List:
USN: 5678
Name: Bob
Programme: Computer Science
Semester: 5
Phone Number: 987-654-3210

USN: 1234
Name: Alice
Programme: Engineering
Semester: 3
Phone Number: 123-456-7890

Total number of students: 2

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 3
Enter USN: 9876
Enter Name: Carol
Enter Programme: Business
Enter Semester: 4
Enter Phone Number: 555-555-5555
Student inserted at the end of the list.

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 4
Student deleted from the front of the list.

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 2
Student List:
USN: 1234
Name: Alice
Programme: Engineering
Semester: 3
Phone Number: 123-456-7890
 USN: 9876
Name: Carol
Programme: Business
Semester: 4
Phone Number: 555-555-5555

Total number of students: 2

Student Data Menu:

1. Create a student list by using front insertion
2. Display the list and count the number of students
3. Insert a student at the end of the list
4. Delete a student from the front of the list
5. Exit
Enter your choice: 5
Program 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

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

// Define the structure for employee data

struct Employee {
char ssn[20];
char name[50];
char dept[30];
char designation[30];
float sal;
char phNo[15];
struct Employee* next;
struct Employee* prev;
};

// Global pointers for the head and tail of the doubly linked list
struct Employee* head = NULL;
struct Employee* tail = NULL;

// Function to create a new employee node

struct Employee* createEmployee() {
struct Employee* newEmployee = (struct Employee*)malloc(sizeof(struct Employee));

if (newEmployee == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}

printf("Enter SSN: ");

scanf("%s", newEmployee->ssn);
printf("Enter Name: ");
scanf(" %s", newEmployee->name);
printf("Enter Department: ");
scanf(" %s", newEmployee->dept);
printf("Enter Designation: ");
scanf(" %s", newEmployee->designation);
printf("Enter Salary: ");
scanf("%f", &newEmployee->sal);
 printf("Enter Phone Number: ");
scanf("%s", newEmployee->phNo);

newEmployee->next = NULL;
newEmployee->prev = NULL;
return newEmployee;
}

// Function to insert an employee at the end of the DLL

void insertEnd() {
struct Employee* newEmployee = createEmployee();

if (head == NULL) {
head = tail = newEmployee;
} else {
tail->next = newEmployee;
newEmployee->prev = tail;
tail = newEmployee;
}
printf("Employee inserted at the end of the list.\n");
}

// Function to display the doubly linked list and count the number of nodes
void displayAndCount() {
struct Employee* current = head;
int count = 0;

if (current == NULL) {
printf("The list is empty.\n");
return;
}

printf("Employee List:\n");
while (current != NULL) {
printf("SSN: %s\nName: %s\nDepartment: %s\nDesignation: %s\nSalary: %.2f\nPhone
Number: %s\n\n", current->ssn, current->name, current->dept, current->designation, current->sal,
current->phNo);
current = current->next;
count++;
}

printf("Total number of employees: %d\n", count);

}

// Function to insert an employee at the front of the DLL

void insertFront() {
struct Employee* newEmployee = createEmployee();

if (head == NULL) {
head = tail = newEmployee;
} else {
newEmployee->next = head;
head->prev = newEmployee;
 head = newEmployee;
}
printf("Employee inserted at the front of the list.\n");
}

// Function to delete an employee from the end of the DLL

void deleteEnd() {
if (head == NULL) {
printf("The list is empty. Nothing to delete.\n");
return;
}

if (head == tail) {
free(head);
head = tail = NULL;
} else {
struct Employee* temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
}
printf("Employee deleted from the end of the list.\n");
}

// Function to delete an employee from the front of the DLL

void deleteFront() {
if (head == NULL) {
printf("The list is empty. Nothing to delete.\n");
return;
}

if (head == tail) {
free(head);
head = tail = NULL;
} else {
struct Employee* temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
printf("Employee deleted from the front of the list.\n");
}

// Function to demonstrate using the DLL as a double-ended queue

void dequeueDemo() {
int choice;
while (1) {
printf("\nDouble-Ended Queue Menu:\n");
printf("1. Insert an employee at the front\n");
printf("2. Insert an employee at the end\n");
printf("3. Delete an employee from the front\n");
printf("4. Delete an employee from the end\n");
printf("5. Back to the main menu\n");
 printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
insertFront();
break;
case 2:
insertEnd();
break;
case 3:
deleteFront();
break;
case 4:
deleteEnd();
break;
case 5:
return;
default:
printf("Invalid choice. Please try again.\n");
}
}
}

// Function to free the memory and exit the program

void exitProgram() {
struct Employee* current = head;
while (current != NULL) {
struct Employee* temp = current;
current = current->next;
free(temp);
}
exit(0);
}
//main
int main()
{
int choice;
while (1)
{
printf("\nEmployee Data Menu:\n");
printf("1. Create a DLL of employees by using end insertion\n");
printf("2. Display the list and count the number of employees\n");
printf("3. Insert an employee at the end of the list\n");
printf("4. Insert an employee at the front of the list\n");
printf("5. Demonstrate using the DLL as a double-ended queue\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
insertEnd();
 break;
case 2:
displayAndCount();
break;
case 3:
insertEnd();
break;
case 4:
insertFront();
break;
case 5:
dequeueDemo();
break;
case 6:
exitProgram();
break;
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

Sample output

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 1
Enter SSN: 12345
Enter Name: John Doe
Enter Department: IT
Enter Designation: Engineer
Enter Salary: 60000
Enter Phone Number: 555-123-4567
Employee inserted at the end of the list.

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 1
Enter SSN: 54321
Enter Name: Jane Smith
Enter Department: HR
Enter Designation: Manager
Enter Salary: 75000
Enter Phone Number: 555-987-6543
Employee inserted at the end of the list.

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 2
Employee List:
SSN: 12345
Name: John Doe
Department: IT
Designation: Engineer
Salary: 60000.00
Phone Number: 555-123-4567

SSN: 54321
Name: Jane Smith
Department: HR
Designation: Manager
Salary: 75000.00
Phone Number: 555-987-6543

Total number of employees: 2

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 3
Enter SSN: 67890
Enter Name: Mark Johnson
Enter Department: Finance
Enter Designation: Accountant
Enter Salary: 55000
Enter Phone Number: 555-222-3333
Employee inserted at the end of the list.

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 4
Enter SSN: 98765
Enter Name: Sarah Lee
Enter Department: Sales
Enter Designation: Sales Representative
Enter Salary: 48000
Enter Phone Number: 555-789-1234
Employee inserted at the front of the list.

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 5

Double-Ended Queue Menu:

1. Insert an employee at the front
2. Insert an employee at the end
3. Delete an employee from the front
4. Delete an employee from the end
5. Back to the main menu
Enter your choice: 1
Enter SSN: 11111
Enter Name: Tom Brown
Enter Department: Marketing
Enter Designation: Marketing Coordinator
Enter Salary: 50000
Enter Phone Number: 555-111-2222
Employee inserted at the front of the list.

Double-Ended Queue Menu:

1. Insert an employee at the front
2. Insert an employee at the end
3. Delete an employee from the front
4. Delete an employee from the end
5. Back to the main menu
Enter your choice: 2
Enter SSN: 22222
Enter Name: Lisa White
Enter Department: Research
Enter Designation: Research Scientist
Enter Salary: 65000
Enter Phone Number: 555-222-3333
Employee inserted at the end of the list.

Double-Ended Queue Menu:

1. Insert an employee at the front
2. Insert an employee at the end
3. Delete an employee from the front
4. Delete an employee from the end
5. Back to the main menu
Enter your choice: 3
Employee deleted from the front of the list.

Double-Ended Queue Menu:

1. Insert an employee at the front
2. Insert an employee at the end
3. Delete an employee from the front
 4. Delete an employee from the end
5. Back to the main menu
Enter your choice: 4
Employee deleted from the end of the list.

Double-Ended Queue Menu:

1. Insert an employee at the front
2. Insert an employee at the end
3. Delete an employee from the front
4. Delete an employee from the end
5. Back to the main menu
Enter your choice: 5

Employee Data Menu:

1. Create a DLL of employees by using end insertion
2. Display the list and count the number of employees
3. Insert an employee at the end of the list
4. Insert an employee at the front of the list
5. Demonstrate using the DLL as a double-ended queue
6. Exit
Enter your choice: 6
Program 9

9. Develop a Program in C for the following operations on Singly Circular Linked List (SCLL) with
header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x' yz+2xy5z-2xyz'
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

A
Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x' yz+2xy5z-2xyz'

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

// Structure to represent a term in a polynomial

struct Term {
int coefficient;
int exponent_x;
int exponent_y;
int exponent_z;
struct Term* next;
};

// Structure for the header node of the polynomial

struct Header {
int num_terms;
struct Term* link;
};

// Function to create a term with given coefficients and exponents

struct Term* createTerm(int coeff, int exp_x, int exp_y, int exp_z) {
struct Term* term = (struct Term*)malloc(sizeof(struct Term));
term->coefficient = coeff;
term->exponent_x = exp_x;
term->exponent_y = exp_y;
term->exponent_z = exp_z;
term->next = NULL;
return term;
}

// Function to insert a term into a polynomial

void insertTerm(struct Header* polynomial, struct Term* term) {
struct Term* current = polynomial->link;

if (current == NULL) {
// The polynomial is empty, so insert the term as the first term
polynomial->link = term;
term->next = term;
polynomial->num_terms++;
} else {
// Find the appropriate position for insertion
 while (current->next != polynomial->link) {
current = current->next;
}

// Insert the term at the end and update the circular link
current->next = term;
term->next = polynomial->link;
polynomial->num_terms++;
}
}
// Function to display a polynomial
void displayPolynomial(struct Header* polynomial, const char* variable) {
if (polynomial->num_terms == 0) {
printf("The polynomial is empty.\n");
return;
}

printf("Polynomial P(%s) = ", variable);

struct Term* current = polynomial->link;
do {
if (current->coefficient > 0) {
printf("+");
}
printf("%d", current->coefficient);

if (current->exponent_x > 0) {
printf("%c^%d", variable[0], current->exponent_x);
}
if (current->exponent_y > 0) {
printf("%c^%d", variable[1], current->exponent_y);
}
if (current->exponent_z > 0) {
printf("%c^%d", variable[2], current->exponent_z);
}

current = current->next;
} while (current != polynomial->link);

printf("\n");
}
// Function to evaluate a polynomial for given values of x, y, and z
int evaluatePolynomial(struct Header* polynomial, int x, int y, int z) {
int result = 0;
struct Term* current = polynomial->link;
do {
int termValue = current->coefficient * pow(x, current->exponent_x) * pow(y, current-
>exponent_y) * pow(z, current->exponent_z);
result += termValue;
current = current->next;
} while (current != polynomial->link);

return result;
}
//main
int main() {
struct Header polynomial;
 polynomial.num_terms = 0;
polynomial.link = NULL;

// Create terms for the polynomial P(x, y, z)

struct Term* term1 = createTerm(6, 2, 2, 1);
struct Term* term2 = createTerm(-4, 1, 0, 5);
struct Term* term3 = createTerm(3, 1, 1, 1);
struct Term* term4 = createTerm(2, 1, 5, 1);
struct Term* term5 = createTerm(-2, 1, 1, 1);

// Insert terms into the polynomial

insertTerm(&polynomial, term1);
insertTerm(&polynomial, term2);
insertTerm(&polynomial, term3);
insertTerm(&polynomial, term4);
insertTerm(&polynomial, term5);

// Display the polynomial

displayPolynomial(&polynomial, "xyz");

// Evaluate the polynomial for x=2, y=3, z=4

int x = 2, y = 3, z = 4;
int result = evaluatePolynomial(&polynomial, x, y, z);

printf("Value of P(%d, %d, %d) = %d\n", x, y, z, result);

return 0;
}

Sample output

Polynomial P(xyz) = +6x^2y^2z-4yz^5+3xyz+2xy^5z-2xyz

Value of P(2, 3, 4) = -104
Program 9 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)

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

// ... (previously defined structures and functions)

// main
int main() {
struct Header poly1, poly2, polySum;
poly1.num_terms = 0;
poly2.num_terms = 0;
polySum.num_terms = 0;
poly1.link = poly2.link = polySum.link = NULL;

// Create terms for the polynomial POLY1(x, y, z)

struct Term* term1a = createTerm(3, 2, 2, 1);
struct Term* term1b = createTerm(2, 1, 5, 1);
struct Term* term1c = createTerm(-2, 1, 1, 1);

// Create terms for the polynomial POLY2(x, y, z)

struct Term* term2a = createTerm(6, 2, 2, 1);
struct Term* term2b = createTerm(-4, 1, 0, 5);
struct Term* term2c = createTerm(3, 1, 1, 1);

// Insert terms into POLY1 and POLY2

insertTerm(&poly1, term1a);
insertTerm(&poly1, term1b);
insertTerm(&poly1, term1c);

insertTerm(&poly2, term2a);
insertTerm(&poly2, term2b);
insertTerm(&poly2, term2c);

// Display POLY1 and POLY2

printf("Polynomial POLY1(xyz) = ");
displayPolynomial(&poly1, "xyz");

printf("Polynomial POLY2(xyz) = ");

displayPolynomial(&poly2, "xyz");

// Add POLY1 and POLY2 and store the result in POLYSUM

addPolynomials(&poly1, &poly2, &polySum);

// Display the result in POLYSUM

printf("\nSum of POLY1 and POLY2:\n");
printf("Resultant Polynomial POLYSUM(xyz) = ");
displayPolynomial(&polySum, "xyz");
 return 0;
}

Sample output

Polynomial POLY1(xyz) = +3x^2y^2z+2xy^5z-2xyz

Polynomial POLY2(xyz) = +6x^2y^2z-4yz^5+3xyz

Sum of POLY1 and POLY2:

Resultant Polynomial POLYSUM(xyz) = +9x^2y^2z-4yz^5+3xyz+2xy^5z
Program 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

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

// Structure for a binary tree node

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

// Function to create a new tree node

struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a new node into the BST

struct TreeNode* insert(struct TreeNode* 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;
}

// Function to perform an in-order traversal of the BST

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

// Function to perform a pre-order traversal of the BST

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

// Function to perform a post-order traversal of the BST

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

// Function to search for a key in the BST

struct TreeNode* search(struct TreeNode* root, int key) {
if (root == NULL || root->data == key) {
return root;
}

if (key < root->data) {

return search(root->left, key);
} else {
return search(root->right, key);
}
}

// Function to check if the key exists in the BST

int keyExists(struct TreeNode* root, int key) {
struct TreeNode* result = search(root, key);
return (result != NULL);
}

// Function to display the appropriate message for search

void displaySearchResult(int key, int exists) {
if (exists) {
printf("%d found in the BST.\n", key);
} else {
printf("%d not found in the BST.\n", key);
}
}

// Function to free the memory and exit the program

void exitProgram(struct TreeNode* root) {
if (root != NULL) {
exitProgram(root->left);
exitProgram(root->right);
free(root);
}
exit(0);
}
//main
int main() {
struct TreeNode* root = NULL;

int choice;
int key;
int exists;

// Create the initial BST with the given elements

int elements[] = {6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2};
int numElements = sizeof(elements) / sizeof(elements[0]);

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

root = insert(root, elements[i]);
}

while (1) {
printf("\nBinary Search Tree Menu:\n");
printf("1. In-order Traversal\n");
printf("2. Pre-order Traversal\n");
printf("3. Post-order Traversal\n");
printf("4. Search for an Element\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("In-order Traversal: ");
inorderTraversal(root);
printf("\n");
break;
case 2:
printf("Pre-order Traversal: ");
preorderTraversal(root);
printf("\n");
break;
case 3:
printf("Post-order Traversal: ");
postorderTraversal(root);
printf("\n");
break;
case 4:
printf("Enter the element to search: ");
scanf("%d", &key);
exists = keyExists(root, key);
displaySearchResult(key, exists);
break;
case 5:
exitProgram(root);
break;
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

Sample output

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
5. Exit
Enter your choice: 1
In-order Traversal: 2 5 6 7 8 9 14 15 24

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
5. Exit
Enter your choice: 2
Pre-order Traversal: 6 5 2 9 8 7 15 14 24

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
5. Exit
Enter your choice: 3
Post-order Traversal: 2 5 7 8 14 24 15 9 6

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
5. Exit
Enter your choice: 4
Enter the element to search: 8
8 found in the BST.

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
5. Exit
Enter your choice: 4
Enter the element to search: 3
3 not found in the BST.

Binary Search Tree Menu:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
4. Search for an Element
 5. Exit
Enter your choice: 5

Program 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

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

// Define the maximum number of cities (you can adjust this as needed)
#define MAX_CITIES 100

// Define the adjacency matrix for the graph

int graph[MAX_CITIES][MAX_CITIES];

// Define an array to keep track of visited cities

bool visited[MAX_CITIES];

// Initialize the graph and visited array

void initializeGraph(int n) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = 0;
}
visited[i] = false;
}
}

// Function to add an edge between two cities

void addEdge(int city1, int city2) {
graph[city1][city2] = 1;
}

// Depth-First Search (DFS) traversal of the graph

void dfs(int city, int n) {
visited[city] = true;
printf("City %d is reachable.\n", city);

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

if (graph[city][i] == 1 && !visited[i]) {
dfs(i, n);
}
}
}

// Breadth-First Search (BFS) traversal of the graph

void bfs(int start, int n) {
visited[start] = true;

int queue[MAX_CITIES];
int front = 0, rear = 0;
 queue[rear++] = start;

printf("Cities reachable from City %d using BFS:\n", start);

while (front < rear) {

int city = queue[front++];
printf("City %d is reachable.\n", city);

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

if (graph[city][i] == 1 && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
}
//main
int main() {
int n, i, city1, city2, startCity;

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

scanf("%d", &n);

initializeGraph(n);

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

int numEdges;
scanf("%d", &numEdges);

printf("Enter the edges (City1 to City2):\n");

for (i = 0; i < numEdges; i++) {
scanf("%d %d", &city1, &city2);
addEdge(city1, city2);
}

printf("Enter the starting city for traversal: ");

scanf("%d", &startCity);

printf("Cities reachable from City %d using DFS:\n", startCity);

dfs(startCity, n);

// Reset visited array

for (i = 0; i < n; i++) {
visited[i] = false;
}

bfs(startCity, n);

return 0;
}

Sample output

Enter the number of cities: 5

Enter the number of edges: 6
Enter the edges (City1 to City2):
01
12
23
34
14
03
Enter the starting city for traversal: 0
Cities reachable from City 0 using DFS:
City 0 is reachable.
City 1 is reachable.
City 2 is reachable.
City 3 is reachable.
City 4 is reachable.
Cities reachable from City 0 using BFS:
City 0 is reachable.
City 1 is reachable.
City 3 is reachable.
City 2 is reachable.
City 4 is reachable.
Program 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.

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

#define MAX_EMPLOYEES 100 // Maximum number of employee records

#define MAX_MEMORY_LOCATIONS 50 // Maximum number of memory locations in the
hash table

// Structure for an employee record

struct Employee {
int key; // 4-digit key
char name[50];
// Add other employee fields here
};

// Structure for a memory location in the hash table

struct MemoryLocation {
int key;
int address;
};

// Hash table (array of memory locations)

struct MemoryLocation hashTable[MAX_MEMORY_LOCATIONS];

// Function to initialize the hash table

void initializeHashTable(int m) {
for (int i = 0; i < m; i++) {
hashTable[i].key = -1;
hashTable[i].address = -1;
}
}

// Hash function: H(K) = K mod m

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

// Function to insert an employee record into the hash table using linear probing
void insertEmployee(struct Employee employee, int m) {
int key = employee.key;
int address = hash(key, m);

while (hashTable[address].key != -1) {

address = (address + 1) % m; // Linear probing
 }

hashTable[address].key = key;
hashTable[address].address = address;

printf("Employee with key %d inserted at memory location %d\n", key, address);

}

// Function to search for an employee record in the hash table

int searchEmployee(int key, int m) {
int address = hash(key, m);

while (hashTable[address].key != key) {

if (hashTable[address].key == -1) {
return -1; // Employee not found
}
address = (address + 1) % m; // Linear probing
}

return address; // Return the memory address of the employee

}
// main
int main() {
int m; // Number of memory locations in the hash table
int n; // Number of employee records
int key;
struct Employee employees[MAX_EMPLOYEES];

printf("Enter the number of memory locations in the hash table (m): ");
scanf("%d", &m);

printf("Enter the number of employee records (n): ");

scanf("%d", &n);

initializeHashTable(m);

printf("Enter employee records:\n");

for (int i = 0; i < n; i++) {
printf("Employee %d:\n", i + 1);
printf("Enter the 4-digit key: ");
scanf("%d", &employees[i].key);
// Add other employee fields here
insertEmployee(employees[i], m);
}

printf("Enter the key to search for: ");

scanf("%d", &key);

int address = searchEmployee(key, m);

if (address != -1) {
printf("Employee with key %d found at memory location %d\n", key, address);
} else {
printf("Employee with key %d not found in the hash table\n", key);
}

return 0;
}

Sample output

Enter the number of memory locations in the hash table (m): 10

Enter the number of employee records (n): 4
Enter employee records:
Employee 1:
Enter the 4-digit key: 1234
Employee with key 1234 inserted at memory location 4
Employee 2:
Enter the 4-digit key: 5678
Employee with key 5678 inserted at memory location 8
Employee 3:
Enter the 4-digit key: 9012
Employee with key 9012 inserted at memory location 2
Employee 4:
Enter the 4-digit key: 3456
Employee with key 3456 inserted at memory location 6
Enter the key to search for: 5678
Employee with key 5678 found at memory location 8