SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY SCHOOL OF COMPUTING

SCSB2201 DATA STRUCTURES LAB

EX 1: In a marketplace, there are multiple places that sell pineapple at different size and cost.
Implement a program to find the place that sells quality pineapple with largest size and minimum
cost by getting the size and cost in array.

Implementation of an array to find maximum size and minimum cost

Aim:
To identify the best pineapple for purchase based on the largest size and the lowest cost. It compares
two lists: one representing the sizes of pineapples and the other representing their costs. The program
finds the pineapple with the largest size, and if multiple pineapples share the same size, it selects the
one with the lowest cost.
Algorithm:

Step 1 : Input Validation

 Check if the size of the arrays (sizes and costs) is greater than zero.
 If not, print an error message and return -1 to indicate an error.

Step 2: Initialize Variables

 Initialize best_pineapple_index to 0, assuming the first pineapple is the best.

 Set max_size to the size of the first pineapple and min_cost to the cost of the first
pineapple.

Step 3: Loop through Pineapple Data

 Start a loop from the second element (index 1) and compare each pineapple's size and
cost.
 If a pineapple has a larger size than the current max_size, update the
best_pineapple_index, max_size, and min_cost.
 If the size is the same as the max_size but the cost is lower than the current min_cost,
update the best_pineapple_index and min_cost.

Step 4: Output the Best Pineapple

 After looping through all the pineapples, print the index, size, and cost of the best
pineapple.

Step 5: Return the Result

 Return the index of the best pineapple. If no valid data is found, return -1.
Program:

#include <stdio.h>
int find_best_pineapple(int sizes[], float costs[], int length) {
// Check if sizes and costs arrays have the same length
if (length <= 0) {
printf("Error: Sizes and costs arrays must have the same length and must not be empty.\n");
return -1; // Return -1 to indicate an error
}
int best_pineapple_index = 0;
int max_size = sizes[0];
float min_cost = costs[0];

// Loop through the sizes and costs arrays

for (int i = 1; i < length; i++) {
if (sizes[i] > max_size || (sizes[i] == max_size && costs[i] < min_cost)) {
best_pineapple_index = i;
max_size = sizes[i];
min_cost = costs[i];
}
}
return best_pineapple_index;
}

int main() {
int sizes[] = {5, 8, 7, 6};
float costs[] = {2.5, 3.0, 2.0, 2.2};
int length = sizeof(sizes) / sizeof(sizes[0]); // Determine the length of the arrays
int best_pineapple_index = find_best_pineapple(sizes, costs, length);
if (best_pineapple_index != -1) {
int best_size = sizes[best_pineapple_index];
float best_cost = costs[best_pineapple_index];
 printf("The place that sells the quality pineapple with the largest size (%d) and minimum cost
(%.2f) is at index %d.\n",
best_size, best_cost, best_pineapple_index);
}
return 0;
}

Output:

The place that sells the quality pineapple with the largest size (8) and minimum cost (3.00) is at index
1.

Ex 2:
To use undo operation in a Microsoft Word, the machine needs to remember the list of states and
operations made. To implement this in real time write a detailed program with set of insertion
and deletion operation functions.

Text Editor with Undo Feature Using String Manipulation and Historical Tracking

Aim:

To implement a simple text editor that supports basic operations such as insertions, deletions,
and undoing the most recent changes. By maintaining a history of operations, the editor allows
users to dynamically modify text and revert changes using the undo feature.

Algorithm:
Step 1: Initialization

 Initialize [Link] to an empty string.

 Set editor.history_count to 0 to indicate that no operations have been performed yet.

Step 2: Insert Text Operation

 Create a HistoryItem to store the operation details.

o Set the operation field to "insert".
o Store the current [Link] in the previous_text field.
o Store the inserted_text in the affected_text field.
 Append the inserted_text to the current [Link] using strcat().
 Save the HistoryItem in [Link][editor.history_count].
 Increment editor.history_count.

Step 3: Delete Text Operation

 If num_chars is less than or equal to 0 or greater than the length of [Link], print an error
message.
 Create a HistoryItem to store the operation details.
 o Set the operation field to "delete".
o Store the current [Link] in the previous_text field.
o Store the last num_chars characters of [Link] in the affected_text field.
 Remove the last num_chars characters from [Link] by truncating it (\0).
 Save the HistoryItem in [Link][editor.history_count].
 Increment editor.history_count.

Step 4: Undo Operation

 If editor.history_count is 0 (no operations in history), print a message saying "Nothing to

undo".
 Decrement editor.history_count to get the last operation.
 Retrieve the last operation stored in [Link][editor.history_count].
 If the operation was an "insert":

o Set [Link] to the previous_text stored in the HistoryItem.

 If the operation was a "delete":
o Append the affected_text back to [Link].
 The text is now reverted to its state before the last operation.

Step 5: Display Text

 Print the current content of [Link].

Program:

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

#define MAX_TEXT_LENGTH 1000

#define MAX_HISTORY 100

// Structure to hold the history of operations

typedef struct {
char operation[10]; // Operation type: "insert" or "delete"
char previous_text[MAX_TEXT_LENGTH]; // Text before the operation
char affected_text[MAX_TEXT_LENGTH]; // Text inserted or deleted
} HistoryItem;

// TextEditor structure with text and history

typedef struct {
char text[MAX_TEXT_LENGTH]; // Current text
HistoryItem history[MAX_HISTORY]; // History of operations
int history_count; // Number of operations in history
} TextEditor;

// Function to initialize the text editor

void init(TextEditor *editor) {
editor->text[0] = '\0'; // Initialize text as an empty string
editor->history_count = 0; // Initialize history count to 0
}
// Function to insert text into the editor
void insert_text(TextEditor *editor, const char *inserted_text) {
// Save current text and the inserted text into history
HistoryItem history_item;
strcpy(history_item.operation, "insert");
strcpy(history_item.previous_text, editor->text);
strcpy(history_item.affected_text, inserted_text);

// Add to history
editor->history[editor->history_count++] = history_item;

// Update the current text

strcat(editor->text, inserted_text);
}

// Function to delete text from the editor

void delete_text(TextEditor *editor, int num_chars) {
if (num_chars <= 0 || num_chars > strlen(editor->text)) {
printf("Invalid number of characters to delete.\n");
return;
}

// Save current text and the deleted text into history

HistoryItem history_item;
strcpy(history_item.operation, "delete");
strcpy(history_item.previous_text, editor->text);
strncpy(history_item.affected_text, editor->text + strlen(editor->text) - num_chars, num_chars);
history_item.affected_text[num_chars] = '\0'; // Null-terminate the deleted text

// Add to history
editor->history[editor->history_count++] = history_item;

// Update the current text by removing characters

editor->text[strlen(editor->text) - num_chars] = '\0';
}

// Function to undo the last operation

void undo(TextEditor *editor) {
if (editor->history_count == 0) {
printf("Nothing to undo.\n");
return;
}

// Get the last operation from the history

HistoryItem last_history = editor->history[--editor->history_count];

// Perform undo based on the operation type

if (strcmp(last_history.operation, "insert") == 0) {
strcpy(editor->text, last_history.previous_text);
} else if (strcmp(last_history.operation, "delete") == 0) {
strcat(editor->text, last_history.affected_text);
}
}
// Function to display the current text
void display_text(const TextEditor *editor) {
printf("Current Text: %s\n", editor->text);
}

// Main function to demonstrate the text editor

int main() {
TextEditor editor;
init(&editor);

// Example Usage
insert_text(&editor, "Welcome to ");
display_text(&editor);

insert_text(&editor, "C programming.");

display_text(&editor);

delete_text(&editor, 11);
display_text(&editor);

undo(&editor);
display_text(&editor);

return 0;
}

Output:

Current Text: Welcome to

Current Text: Welcome to C programming.
Current Text: Welcome to C p
Current Text: Welcome to C programming.

Ex 3: To implement a playlist that allows navigation to the next and previous songs, we can use a
doubly linked list in C. This structure enables efficient traversal in both directions and supports
dynamic insertion and deletion of songs.
Dynamic Playlist Management Using Doubly Linked List

Aim:

To implement a dynamic playlist management system in C using a doubly linked list that
supports adding songs, deleting songs, navigating between songs, and displaying the playlist.

Algorithm:
Step 1. Start the program
Step 2. Define Structures: Song Node, Contains the song title and pointers to the next and previous
songs. Playlist: Contains pointers to the head (first song), tail (last song), and current (currently playing
song).
Step 3. Initialize Playlist: Set the head, tail, and current pointers to `NULL`.
Step 4. Add Song: - Create a new song node with the given title.
- If the playlist is empty:
- Set head, tail, and current to the new song.
-Else:
- Append the new song to the end of the list.
- Update the necessary pointers to maintain the doubly linked structure.
Step 5. Delete Song: - Traverse the list to find the song with the given title.
- If found:
- Update the pointers of the adjacent nodes to bypass the node to be deleted.
- Adjust head, tail, and current pointers if necessary.
- Free the memory allocated for the deleted node.
- If not found, indicate that the song is not in the playlist.

Step 6. Play Next Song:

- If the current song has a next song:
- Move the current pointer to the next song.
- Display the title of the new current song.
- Else:
- Indicate that there is no next song available.

Step 7. Play Previous Song: - If the current song has a previous song:
- Move the current pointer to the previous song.
- Display the title of the new current song.
- Else:
- Indicate that there is no previous song available.
Step 8. Display Playlist:
- Traverse the list from the head to the tail.
- Print the title of each song in sequence.
Step 9. Stop the program
Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define the structure for a song node
typedef struct Song {
char title[100];
struct Song *next;
struct Song *prev;
} Song;
// Define the structure for the playlist
typedef struct Playlist {
Song *head;
Song *tail;
Song *current;
} Playlist;
// Function to create a new song node
Song* createSong(const char *title) {
Song *newSong = (Song*)malloc(sizeof(Song));
if (newSong == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
strncpy(newSong->title, title, sizeof(newSong->title) - 1);
newSong->title[sizeof(newSong->title) - 1] = '\0';
newSong->next = NULL;
newSong->prev = NULL;
return newSong;
}
// Function to initialize the playlist
void initPlaylist(Playlist *playlist) {
playlist->head = NULL;
 playlist->tail = NULL;
playlist->current = NULL;
}
// Function to add a song to the playlist
void addSong(Playlist *playlist, const char *title) {
Song *newSong = createSong(title);
if (playlist->head == NULL) {
playlist->head = newSong;
playlist->tail = newSong;
playlist->current = newSong;
} else {
playlist->tail->next = newSong;
newSong->prev = playlist->tail;
playlist->tail = newSong;
}
printf("Added: %s\n", title);
}

// Function to delete a song from the playlist

void deleteSong(Playlist *playlist, const char *title) {
Song *temp = playlist->head;
while (temp != NULL) {
if (strcmp(temp->title, title) == 0) {
if (temp->prev) temp->prev->next = temp->next;
if (temp->next) temp->next->prev = temp->prev;
if (temp == playlist->head) playlist->head = temp->next;
if (temp == playlist->tail) playlist->tail = temp->prev;
if (temp == playlist->current) playlist->current = temp->next ? temp->next : temp->prev;
free(temp);
printf("Deleted: %s\n", title);
return;
}
 temp = temp->next;
}
printf("Song not found: %s\n", title);
}
// Function to play the next song
void playNext(Playlist *playlist) {
if (playlist->current && playlist->current->next) {
playlist->current = playlist->current->next;
printf("Playing next song: %s\n", playlist->current->title);
} else {
printf("No next song available.\n");
}
}
// Function to play the previous song
void playPrevious(Playlist *playlist) {
if (playlist->current && playlist->current->prev) {
playlist->current = playlist->current->prev;
printf("Playing previous song: %s\n", playlist->current->title);
} else {
printf("No previous song available.\n");
}
}
// Function to display the playlist
void displayPlaylist(const Playlist *playlist) {
Song *temp = playlist->head;
printf("Playlist: ");
while (temp != NULL) {
printf("%s -> ", temp->title);
temp = temp->next;
}
printf("NULL\n");
}
// Main function
int main() {
Playlist playlist;
initPlaylist(&playlist);

addSong(&playlist, "Song A");

addSong(&playlist, "Song B");
addSong(&playlist, "Song C");
displayPlaylist(&playlist);

playNext(&playlist);
playNext(&playlist);
playPrevious(&playlist);
deleteSong(&playlist, "Song B");
displayPlaylist(&playlist);
return 0;
}
```
OUTPUT
Added: Song A
Added: Song B
Added: Song C
Playlist: Song A -> Song B -> Song C -> NULL
Playing next song: Song B
Playing next song: Song C
Playing previous song: Song B
Deleted: Song B
Playlist: Song A -> Song C -> NULL
EX.4 : Algorithm and C program implementation for the Towers of Hanoi using the Stack data
structure.

Implementing the Towers of Hanoi Problem Using a Stack

Aim:

To implement the iterative solution for the Towers of Hanoi problem using stack data structures
in C.

Algorithm

1. Start the program

2. Initialize three stacks representing the source, auxiliary, and destination rods.
3. Push disks onto the source stack in descending order (largest at the bottom).
4. Use an iterative approach (instead of recursion) to simulate moving disks between stacks.
5. Follow the rules:
o Only one disk can be moved at a time.
o A larger disk cannot be placed on a smaller disk.
o Use the auxiliary rod as an intermediate step.
6. Use a stack-based iterative simulation to solve the problem.
7. Stop the program

Program

#include <stdio.h>
#include <stdlib.h>
#define MAX 64 // Maximum number of disks

// Structure for Stack

typedef struct {
int top;
int array[MAX];
} Stack;

// Function to initialize a stack

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

// Function to check if the stack is empty

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

// Function to check if the stack is full

int isFull(Stack *s) {
return (s->top == MAX - 1);
}

// Function to push an element onto the stack

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

// Function to pop an element from the stack

int pop(Stack *s) {
if (isEmpty(s)) {
return -1; // Invalid value, means stack underflow
}
return s->array[s->top--];
}

// Function to move a disk from one stack to another

void moveDisk(Stack *src, Stack *dest, char s, char d) {
int disk1 = pop(src);
int disk2 = pop(dest);

if (disk1 == -1) {
push(src, disk2);
printf("Move disk %d from %c to %c\n", disk2, d, s);
} else if (disk2 == -1) {
push(dest, disk1);
printf("Move disk %d from %c to %c\n", disk1, s, d);
} else if (disk1 > disk2) {
push(src, disk1);
push(src, disk2);
printf("Move disk %d from %c to %c\n", disk2, d, s);
} else {
push(dest, disk2);
push(dest, disk1);
printf("Move disk %d from %c to %c\n", disk1, s, d);
}
}

// Function to implement the iterative Towers of Hanoi

void towersOfHanoi(int num_of_disks, Stack *src, Stack *aux, Stack *dest, char S, char A, char D) {
int moves = (1 << num_of_disks) - 1; // Total moves = 2^n - 1
int i;

// Push disks onto the source stack

for (i = num_of_disks; i >= 1; i--) {
push(src, i);
}

// If even number of disks, swap auxiliary and destination pegs

if (num_of_disks % 2 == 0) {
char temp = D;
D = A;
A = temp;
}

// Perform the moves

for (i = 1; i <= moves; i++) {
if (i % 3 == 1)
 moveDisk(src, dest, S, D);
else if (i % 3 == 2)
moveDisk(src, aux, S, A);
else if (i % 3 == 0)
moveDisk(aux, dest, A, D);
}
}

// Driver function
int main() {
int num_of_disks;

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

scanf("%d", &num_of_disks);
Stack src, aux, dest;
initialize(&src);
initialize(&aux);
initialize(&dest);
printf("Solution for %d disks:\n", num_of_disks);
towersOfHanoi(num_of_disks, &src, &aux, &dest, 'A', 'B', 'C');
return 0;
}

Example Output

Enter the number of disks: 3

Solution for 3 disks:
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

EX 5: To manage the queuing system of ticket counter in SKY cinemas implement the queue
data structure with all of its corresponding operations.
Implementation of Queue using Array

Aim:

To implement a queue data structure using an array in C, which supports basic operations such as
enqueue, dequeue, peek, and displaying the queue. The program simulates a ticket counter queue
system where customers are added and served sequentially.

Algorithm:

Step 1: Initialize the Queue

1. Define a structure Queue with an array to store elements and two integer variables front and
rear.
 2. Create a function initQueue(Queue *q) to set front = -1 and rear = -1, indicating an empty
queue.

Step 2: Check if the Queue is Empty

1. Create a function isEmpty(Queue *q).

2. Return true if front == -1 or front > rear.

Step 3: Enqueue an Element

1. Create a function enqueue(Queue *q, char *item).

2. Check if the queue is full (rear == MAX_SIZE - 1). If yes, print "Queue is full" and exit.
3. If front == -1, set front = 0.
4. Increment rear and add the new item to q->items[rear].

Step 4: Dequeue an Element

1. Create a function dequeue(Queue *q).

2. Check if the queue is empty using isEmpty(q). If yes, print "Queue is empty" and return
NULL.
3. Retrieve and return the element at q->front, then increment front.

Step 5: Peek at the Front Element

1. Create a function peek(Queue *q).

2. Check if the queue is empty. If yes, print "Queue is empty" and return NULL.
3. Return the element at q->front.

Step 6: Display the Queue

1. Create a function displayQueue(Queue *q).

2. Check if the queue is empty. If yes, print "Queue is empty".
3. Print elements from front to rear.

Step 7: Implement the Main Function

1. Create an instance of Queue and initialize it.

2. Enqueue three customers (Customer 1, Customer 2, Customer 3).
3. Display the queue.
4. Peek at the front customer and print it.
5. Dequeue a customer and display the updated queue.
6. End the program.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct {
 char items[MAX_SIZE][50]; // Array to store queue elements
int front, rear;
} Queue;

// Function to initialize the queue

void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the queue is empty

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

// Function to add an element to the queue (enqueue)

void enqueue(Queue *q, char *item) {
if (q->rear == MAX_SIZE - 1) {
printf("Queue is full!\n");
return;
}
if (q->front == -1)
q->front = 0;
q->rear++;
strcpy(q->items[q->rear], item);
}

// Function to remove an element from the queue (dequeue)

char* dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return NULL;
 }
return q->items[q->front++];
}

// Function to get the front element of the queue (peek)

char* peek(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return NULL;
}
return q->items[q->front];
}

// Function to print the queue elements

void displayQueue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return;
}
printf("Current Queue: ");
for (int i = q->front; i <= q->rear; i++) {
printf("%s ", q->items[i]);
}
printf("\n");
}
int main() {
Queue ticketQueue;
initQueue(&ticketQueue);
// Enqueue customers
enqueue(&ticketQueue, "Customer 1");
enqueue(&ticketQueue, "Customer 2");
enqueue(&ticketQueue, "Customer 3");
 // Display the queue
displayQueue(&ticketQueue);

// Peek at the next customer

char *nextCustomer = peek(&ticketQueue);
if (nextCustomer)
printf("Next Customer: %s\n", nextCustomer);

// Dequeue the next customer

char *servedCustomer = dequeue(&ticketQueue);
if (servedCustomer)
printf("Serving Customer: %s\n", servedCustomer);
// Display the updated queue
displayQueue(&ticketQueue);
return 0;
}
Output:
Current Queue: Customer 1 Customer 2 Customer 3
Next Customer: Customer 1
Serving Customer: Customer 1
Current Queue: Customer 2 Customer 3

EX 6: To organize a traffic light management system based on number of vehicles on each side,
Implement a circular queue data structure algorithm along with its respective operations.

Implementation of Circular Queue using Array

Aim:

To implement a Circular Queue data structure using an array in C, which supports basic operations
such as enqueue, dequeue, peek, and display. The program simulates a traffic management queue
system where vehicles from different directions are processed in a circular manner.

Algorithm:

Step 1: Initialize the Circular Queue

 1. Define a structure CircularQueue with an array queue[MAX_SIZE] and two integer variables
front and rear.
2. Create a function initQueue(CircularQueue *q) to set front = -1 and rear = -1, indicating an
empty queue.

Step 2: Check if the Queue is Empty

1. Create a function isEmpty(CircularQueue *q).

2. If front == -1, return true; otherwise, return false.

Step 3: Check if the Queue is Full

1. Create a function isFull(CircularQueue *q).

2. If (rear + 1) % MAX_SIZE == front, return true, indicating the queue is full.

Step 4: Enqueue an Element

1. Create a function enqueue(CircularQueue *q, char *item).

2. Check if the queue is full using isFull(q). If true, print "Queue is full" and return.
3. If the queue is empty, set front = 0 and rear = 0.
4. Otherwise, increment rear = (rear + 1) % MAX_SIZE.
5. Store item at queue[rear].

Step 5: Dequeue an Element

1. Create a function dequeue(CircularQueue *q).

2. Check if the queue is empty using isEmpty(q). If true, print "Queue is empty" and return.
3. Retrieve and print queue[front].
4. If front == rear, set both front = -1 and rear = -1.
5. Otherwise, update front = (front + 1) % MAX_SIZE.

Step 6: Peek at the Front Element

1. Create a function peek(CircularQueue *q).

2. If the queue is empty, print "Queue is empty".
3. Otherwise, print queue[front] as the front element.

Step 7: Display the Queue

1. Create a function display(CircularQueue *q).

2. If the queue is empty, print "Queue is empty" and return.
3. Start from front and iterate circularly until rear.
4. Print all elements in the queue.

Step 8: Implement the Main Function

1. Create an instance of CircularQueue and initialize it using initQueue().

2. Enqueue elements representing vehicle data from different directions.
3. Display the queue.
4. Dequeue elements and display the updated queue.
5. Enqueue more elements and display the final queue state.
6. End the program.
Program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 5
typedef struct {
char queue[MAX_SIZE][50];
int front, rear;
} CircularQueue;

// Function to initialize the circular queue

void initQueue(CircularQueue *q) {
q->front = q->rear = -1;
}

// Function to check if the queue is empty

int isEmpty(CircularQueue *q) {
return q->front == -1;
}

// Function to check if the queue is full

int isFull(CircularQueue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}

// Function to enqueue an element

void enqueue(CircularQueue *q, char *item) {
if (isFull(q)) {
printf("Queue is full. Cannot enqueue.\n");
return;
}
if (isEmpty(q)) {
 q->front = q->rear = 0;
} else {
q->rear = (q->rear + 1) % MAX_SIZE;
}
strcpy(q->queue[q->rear], item);
printf("%s enqueued to the queue.\n", item);
}

// Function to dequeue an element

void dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty. Cannot dequeue.\n");
return;
}
printf("%s dequeued from the queue.\n", q->queue[q->front]);
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX_SIZE;
}
}

// Function to peek at the front element

void peek(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
} else {
printf("Front element: %s\n", q->queue[q->front]);
}
}
// Function to display the queue
void display(CircularQueue *q) {
 if (isEmpty(q)) {
printf("Queue is empty.\n");
return;
}
int i = q->front;
printf("Queue: ");
while (1) {
printf("%s ", q->queue[i]);
if (i == q->rear)
break;
i = (i + 1) % MAX_SIZE;
}
printf("\n");
}

int main() {
CircularQueue trafficQueue;
initQueue(&trafficQueue);

// Enqueue elements
enqueue(&trafficQueue, "North: 5 vehicles");
enqueue(&trafficQueue, "East: 3 vehicles");
enqueue(&trafficQueue, "South: 2 vehicles");
enqueue(&trafficQueue, "West: 4 vehicles");
display(&trafficQueue);

// Dequeue elements
dequeue(&trafficQueue);
dequeue(&trafficQueue);
display(&trafficQueue);
// Enqueue more elements
enqueue(&trafficQueue, "North: 1 vehicle");
 enqueue(&trafficQueue, "South: 7 vehicles");
display(&trafficQueue);
return 0;
}

Output:
North: 5 vehicles enqueued to the queue.
East: 3 vehicles enqueued to the queue.
South: 2 vehicles enqueued to the queue.
West: 4 vehicles enqueued to the queue.

Queue: North: 5 vehicles East: 3 vehicles South: 2 vehicles West: 4 vehicles

North: 5 vehicles dequeued from the queue.
East: 3 vehicles dequeued from the queue.

Queue: South: 2 vehicles West: 4 vehicles

North: 1 vehicle enqueued to the queue.
South: 7 vehicles enqueued to the queue.

Queue: South: 2 vehicles West: 4 vehicles North: 1 vehicle South: 7 vehicles

EX 7: BODMAS Conversion and Evaluation

Get a complex expression from the user in human‘s understandable BODMAS format and convert the
same expression into machine readable form.

Evaluating BODMAS Expressions Using Recursive Parsing and Stack

Aim: To design a C program that allows users to input complex mathematical expressions in
human-readable BODMAS format and evaluates the expression to produce a result in machine-
readable form.

Algorithm:

Step 1: Start 1.1 Declare variables: Initialize variables for expression input and result storage. 1.2
Include necessary libraries: Ensure libraries such as stdio.h, stdlib.h, ctype.h, math.h, and string.h are
included.
Step 2: Input: Prompt the user to enter a mathematical expression in BODMAS format. 2.1 Read user
input: Use fgets to capture the user input and store it in a character array.

Step 3: Initialize: Define functions to parse and evaluate the expression. 3.1 Declare function
prototypes: Define prototypes for evaluateExpression, parseExpression, parseTerm, and parseFactor.

Step 4: Evaluate Expression: 4.1 Read the expression string: Assign the user input to a variable to
be processed. 4.2 Call the evaluateExpression function: Pass the expression to the evaluateExpression
function for evaluation.

Step 5: Parse Expression: 5.1 Check for parentheses: - If found, recursively evaluate the inner
expression using parseExpression. - If not found, parse numeric value using strtod.

Step 6: Parse Term: 6.1 Perform multiplication () and division (/) operations*: - Iterate through the
expression, evaluating terms connected by * or /. - Continue parsing until all such operators are
exhausted.

Step 7: Parse Factor: 7.1 Perform addition (+) and subtraction (-) operations: - Iterate through the
expression, evaluating factors connected by + or -. - Continue parsing until all such operators are
exhausted.

Step 8: Display the machine-readable version of the input expression. 8.2 Print the evaluated
result of the expression using printf.

Step 9: Terminate the program.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>

// Function prototypes
double evaluateExpression(char* expression);
double parseExpression(char** expr);

int main() {
char expression[100];
printf("Enter a mathematical expression(BODMAS FORMAT): ");
fgets(expression, 100, stdin);
 double result = evaluateExpression(expression);
printf("Machine-readable expression: %s", expression);
printf("Result: %lf\n", result);
return 0;
}

double evaluateExpression(char* expression) {

char* expr = expression;
return parseExpression(&expr);
}

double parseFactor(char** expr) {

double result;
if (**expr == '(') {
(*expr)++;
result = parseExpression(expr);
(*expr)++;
} else {
char* end;
result = strtod(*expr, &end);
*expr = end;
}
return result;
}
double parseTerm(char** expr) {
double result = parseFactor(expr);
while (**expr == '*' || **expr == '/') {
char op = **expr;
(*expr)++;
double right = parseFactor(expr);
if (op == '*') {
result *= right;
 } else {
result /= right;
}
}
return result;
}

double parseExpression(char** expr) {

double result = parseTerm(expr);
while (**expr == '+' || **expr == '-') {
char op = **expr;
(*expr)++;
double right = parseTerm(expr);
if (op == '+') {
result += right;
} else {
result -= right;
}
}
return result;
}
Output:
Enter a mathematical expression(BODMAS FORMAT): (5+3)*(7-2)/4
Machine-readable expression: (5+3)*(7-2)/4
Result: 10.000000

Ex 8: To sort the contact names in your phone in ascending order based on the first name using
insertion sort algorithm

Sorting Contact Names using Insertion Sort

AIM:
To implement the insertion sort algorithm to sort contact names in ascending order based on the first
name.
ALGORITHM:
Step 1. Start
Step 2. Define an array of contact names.
Step 3. Implement the insertion sort algorithm:
a. Iterate through each element from index 1 to n-1.
b. Store the current element as a key.
c. Compare it with previous elements and shift elements greater than the key.
d. Insert the key at the correct position.
Step 4. Display the sorted contact names.
Step 5. Terminate the program

Program:
#include <stdio.h>
#include <string.h>
#define MAX 5
#define NAME_LENGTH 50
// Function to perform insertion sort on names
void insertionSort(char names[MAX][NAME_LENGTH], int n) {
int i, j;
char key[NAME_LENGTH];
for (i = 1; i < n; i++) {
strcpy(key, names[i]);
j = i - 1;
// Move elements that are greater than key one position ahead
while (j >= 0 && strcmp(names[j], key) > 0) {
strcpy(names[j + 1], names[j]);
j = j - 1;
}
strcpy(names[j + 1], key);
}
}
int main() {
char names[MAX][NAME_LENGTH] = {"Zara", "Arun", "John", "Bala", "Charlie"};
int i;
printf("Original Contact Names:\n");
for (i = 0; i < MAX; i++) {
printf("%s\n", names[i]);
}

// Sorting names using insertion sort

insertionSort(names, MAX);
printf("\nSorted Contact Names:\n");
for (i = 0; i < MAX; i++) {
printf("%s\n", names[i]);
}
return 0;
}

Output:
Original Contact Names:
Zara
Arun
John
Bala
Charlie

Sorted Contact Names:

Arun
Bala
Charlie
John
Zara
Ex 9: To sort the students in the class according to their heights for group photo in descending
using quick sort algorithm.

Sorting Students by Height using Quick Sort

AIM:

To implement the quick sort algorithm to sort student heights in descending order for a group photo.

ALGORITHM:

Step 1. Start

Step 2. Define an array of student heights.

Step 3. Implement the quick sort algorithm:

a. Select a pivot element.

b. Partition the array so that elements greater than the pivot go to the left, and elements smaller go to
the right.

c. Recursively apply quick sort to both partitions.

Step 4. Display the sorted heights.

Step 5. End

Program:

#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

// Partition function for quick sort (descending order)

int partition(int heights[], int low, int high) {

int pivot = heights[high];

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

if (heights[j] >= pivot) { // Change condition for descending order

i++;

swap(&heights[i], &heights[j]);

swap(&heights[i + 1], &heights[high]);

return i + 1;

// Quick sort function

void quickSort(int heights[], int low, int high) {

if (low < high) {

int pi = partition(heights, low, high);

quickSort(heights, low, pi - 1);

quickSort(heights, pi + 1, high);

int main() {

int heights[] = {160, 170, 150, 180, 175};

int n = sizeof(heights) / sizeof(heights[0]);

printf("Original Heights:\n");

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

printf("%d ", heights[i]);

// Sorting heights using quick sort

quickSort(heights, 0, n - 1);
 printf("\n\nSorted Heights in Descending Order:\n");

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

printf("%d ", heights[i]);

return 0;

Output:

Original Heights:

160 170 150 180 175

Sorted Heights in Descending Order:

180 175 170 160 150

Ex 10: To sort the chocolates in the supermarket based on its cost and size in ascending order
using merge sort algorithm.

Sorting Chocolates by Cost and Size using Merge Sort

AIM:

To implement the merge sort algorithm to sort chocolates in ascending order based on cost and size.

ALGORITHM:

Step 1. Start

Step 2. Define an array of chocolates with cost and size.

Step 3. Implement the merge sort algorithm:

a. Divide the array into two halves.

b. Recursively sort both halves.

c. Merge the sorted halves based on cost first; if costs are equal, sort by size.

Step 4. Display the sorted chocolates.

Step 5. End

Program:

#include <stdio.h>

// Structure to represent a chocolate with cost and size

typedef struct {

int cost;

int size;

} Chocolate;

// Function to merge two subarrays

void merge(Chocolate arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

Chocolate L[n1], R[n2];

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

L[i] = arr[left + i];

for (int j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i].cost < R[j].cost || (L[i].cost == R[j].cost && L[i].size < R[j].size)) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

}
 k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

// Merge sort function

void mergeSort(Chocolate arr[], int left, int right) {

if (left < right) {

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

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

int main() {

Chocolate chocolates[] = {{20, 5}, {10, 3}, {15, 4}, {10, 2}, {20, 7}};

int n = sizeof(chocolates) / sizeof(chocolates[0]);

printf("Original Chocolates (Cost, Size):\n");

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

printf("(%d, %d) ", chocolates[i].cost, chocolates[i].size);

// Sorting chocolates using merge sort

mergeSort(chocolates, 0, n - 1);

printf("\n\nSorted Chocolates in Ascending Order (Cost, Size):\n");

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

printf("(%d, %d) ", chocolates[i].cost, chocolates[i].size);

return 0;

Output
Original Chocolates (Cost, Size):
(20, 5) (10, 3) (15, 4) (10, 2) (20, 7)

Sorted Chocolates in Ascending Order (Cost, Size):

(10, 2) (10, 3) (15, 4) (20, 5) (20, 7)

Ex 11: Implement the Linear Search and Binary Search methods in two programmes to discover
any given element inside the provided range of numbers, and compare the results to determine
which algorithm is faster and/or uses less space.
Comparing Linear Search and Binary Search

Aim:
To implement Linear Search and Binary Search algorithms in C to find a given element within a
provided range of numbers and compare their performance in terms of speed and space.

Algorithm:
Linear Search:
Step 1. Start
Step 2. Iterate through each element in the array.
Step 3. If the element matches the target, return its position.
Step 4. If the element is not found, return -1.
Step 5. End

Binary Search (works on sorted arrays):

Step 1. Start
Step 2. Set low = 0 and high = n - 1.
Step 3. Repeat until low is less than or equal to high:
a. Find the middle element.
b. If the middle element matches the target, return its position.
c. If the middle element is greater than the target, search in the left half.
d. If the middle element is smaller than the target, search in the right half.
Step 4. If the element is not found, return -1.
Step 5. End

Program:
#include <stdio.h>
#include <time.h>

// Function for Linear Search

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}

// Function for Binary Search

int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
 int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

int main() {
int n, key;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];

printf("Enter %d sorted elements: ", n);

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

printf("Enter the element to search: ");

scanf("%d", &key);
clock_t start, end;
double time_taken;

// Linear Search Execution Time

start = clock();
int lin_result = linearSearch(arr, n, key);
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
 printf("Linear Search: Element found at index %d, Time Taken: %f seconds\n", lin_result,
time_taken);

// Binary Search Execution Time

start = clock();
int bin_result = binarySearch(arr, 0, n - 1, key);
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Binary Search: Element found at index %d, Time Taken: %f seconds\n", bin_result,
time_taken);

return 0;
}

Output:
Enter the number of elements: 3
Enter 3 sorted elements: 23
21
45
Enter the element to search: 45
Linear Search: Element found at index 2, Time Taken: 0.000001 seconds
Binary Search: Element found at index 2, Time Taken: 0.000000 seconds

Ex 12: To create a program in C that visits every restaurant along the route from Chennai to
Pondicherry using a binary tree.
Binary Tree Program to Display Restaurants along the Route
Aim: To create a binary tree representation of restaurants along the route from Chennai to Pondicherry
and use in-order traversal to visit and display the restaurant names in sorted order.
Algorithm:
Step 1. Start.
Step 2. Define a structure for a tree node with the following attributes: - Restaurant name (a string). -
Pointers to left and right child nodes.
Step 3. Create a function to: - Dynamically allocate memory for a new node. - Initialize the node with
the restaurant name and set its child pointers to NULL.
Step 4. Create a function to insert a restaurant node into the binary tree: - If the tree is empty, make the
new node the root. - If the restaurant name is smaller than the root node's name, insert it into the left
subtree. - Otherwise, insert it into the right subtree.
Step 5. Create an in-order traversal function: - Recursively traverse the left subtree. - Print the current
node's restaurant name. - Recursively traverse the right subtree.
Step 6. In the main function: - Initialize the binary tree by adding restaurant nodes. - Call the in-order
traversal function to visit all restaurants and display their names.
Step 7. Free the allocated memory for the binary tree.
Step 8. End.

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

// Define the structure for a tree node

typedef struct Node {
char restaurantName[50];
struct Node* left;
struct Node* right;
} Node;

// Function to create a new tree node

Node* createNode(const char* name) {
Node* newNode = (Node*)malloc(sizeof(Node));
strcpy(newNode->restaurantName, name);
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into the binary tree

Node* insertNode(Node* root, const char* name) {
if (root == NULL) {
 return createNode(name);
}

// Insert to the left or right based on lexicographical order

if (strcmp(name, root->restaurantName) < 0) {
root->left = insertNode(root->left, name);
} else {
root->right = insertNode(root->right, name);
}
return root;
}

// In-order traversal function

void inOrderTraversal(Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("Visited Restaurant: %s\n", root->restaurantName);
inOrderTraversal(root->right);
}
}
// Free the memory allocated for the tree
void freeTree(Node* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}

int main() {
// Create a binary tree and add restaurants
Node* root = NULL;
 printf("Adding restaurants along the route...\n");
root = insertNode(root, "Saravana Bhavan");
root = insertNode(root, "A2B (Adyar Ananda Bhavan)");
root = insertNode(root, "Murugan Idli Shop");
root = insertNode(root, "Cafe Coffee Day");
root = insertNode(root, "Sangeetha Veg Restaurant");
root = insertNode(root, "Le Pondy Cafe");
root = insertNode(root, "French Delights");
printf("\nVisiting restaurants in order:\n");
inOrderTraversal(root);
// Free the allocated memory for the tree
freeTree(root);
return 0;
}

Output:
Adding restaurants along the route...

Visiting restaurants in order:

Visited Restaurant: A2B (Adyar Ananda Bhavan)
Visited Restaurant: Cafe Coffee Day
Visited Restaurant: French Delights
Visited Restaurant: Le Pondy Cafe
Visited Restaurant: Murugan Idli Shop
Visited Restaurant: Sangeetha Veg Restaurant
Visited Restaurant: Saravana Bhavan

Ex 13: Write a program:

a. To find the nearest restaurants from your location by implementing Breadth First Search traversal
algorithm.
b. Implement the Depth First Search traversal algorithm to find the cycles in any given graph. Finding
Nearest Restaurants Using Breadth-First Search (BFS)
 A. Finding Nearest Restaurants Using Breadth-First Search (BFS)
Aim:

To implement the Breadth-First Search (BFS) traversal algorithm to find and list the nearest
restaurants from a given starting location in a graph.

Algorithm:

Step 1: Start.

Step 2: Represent the locations (restaurants) and their connections as a graph using an adjacency
matrix.

Step 3: Define a queue data structure to help traverse the graph level by level.

Step 4: Initialize the visited array to track visited nodes.

Step 5: Enqueue the starting location (restaurant) and mark it as visited.

Step 6: While the queue is not empty:

Dequeue a node and print it as a visited restaurant.

For each neighbor of the current node:

If it is not visited, mark it as visited and enqueue it.

Step 7: End.

Program:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

// Structure to represent a restaurant

typedef struct Restaurant {

char name[50];

int neighbors[MAX]; // Array to store neighbors' indices

 int neighborCount;

} Restaurant;

// Queue structure for BFS

typedef struct {

int items[MAX];

int front, rear;

} Queue;

// Initialize the queue

void initQueue(Queue* q) {

q->front = -1;

q->rear = -1;

// Check if the queue is empty

int isEmpty(Queue* q) {

return q->front == -1;

// Enqueue an element into the queue

void enqueue(Queue* q, int value) {

if (q->rear == MAX - 1) {

printf("Queue overflow!\n");

return;

}
 if (q->front == -1)

q->front = 0;

q->items[++q->rear] = value;

// Dequeue an element from the queue

int dequeue(Queue* q) {

if (isEmpty(q)) {

printf("Queue underflow!\n");

return -1;

int item = q->items[q->front];

if (q->front == q->rear)

q->front = q->rear = -1; // Reset queue

else

q->front++;

return item;

// BFS function to find the nearest restaurant

void bfsFindNearestRestaurant(Restaurant restaurants[], int start, char target[], int n) {

int visited[MAX] = {0}; // Track visited nodes

int distance[MAX] = {0}; // Store distances

Queue q;

initQueue(&q);
 enqueue(&q, start);

visited[start] = 1;

while (!isEmpty(&q)) {

int current = dequeue(&q);

// Check if the current restaurant is the target

if (strcmp(restaurants[current].name, target) == 0) {

printf("The nearest restaurant to your location is %s. Distance: %d\n",

restaurants[current].name, distance[current]);

return;

// Visit all neighbors

for (int i = 0; i < restaurants[current].neighborCount; i++) {

int neighborIndex = restaurants[current].neighbors[i];

if (!visited[neighborIndex]) {

enqueue(&q, neighborIndex);

visited[neighborIndex] = 1;

distance[neighborIndex] = distance[current] + 1;

printf("No matching restaurant found.\n");

}
int main() {

int n, i, j, connections;

Restaurant restaurants[MAX];

// Get the number of restaurants

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

scanf("%d", &n);

// Input restaurant details

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

printf("Enter the name of restaurant %d: ", i + 1);

scanf("%s", restaurants[i].name);

restaurants[i].neighborCount = 0;

// Input connections between restaurants

printf("\nEnter the connections between restaurants:\n");

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

printf("Enter the number of connections for %s: ", restaurants[i].name);

scanf("%d", &connections);

printf("Enter the indices (1 to %d) of the connected restaurants: ", n);

for (j = 0; j < connections; j++) {

int neighborIndex;

scanf("%d", &neighborIndex);

restaurants[i].neighbors[restaurants[i].neighborCount++] = neighborIndex - 1;

}
 }

// Input the target restaurant

char target[50];

printf("\nEnter the name of the target restaurant: ");

scanf("%s", target);

// Input the starting restaurant index

int startIndex;

printf("Enter the index (1 to %d) of the starting restaurant: ", n);

scanf("%d", &startIndex);

// Find the nearest restaurant

bfsFindNearestRestaurant(restaurants, startIndex - 1, target, n);

return 0;

Input:

Enter the number of restaurants: 4

Enter the name of restaurant 1: RestaurantA

Enter the name of restaurant 2: RestaurantB

Enter the name of restaurant 3: RestaurantC

Enter the name of restaurant 4: RestaurantD

Enter the number of connections for RestaurantA: 2

Enter the indices (1 to 4) of the connected restaurants: 2 3

 Enter the number of connections for RestaurantB: 2

Enter the indices (1 to 4) of the connected restaurants: 1 4

Enter the number of connections for RestaurantC: 2

Enter the indices (1 to 4) of the connected restaurants: 1 4

Enter the number of connections for RestaurantD: 2

Enter the indices (1 to 4) of the connected restaurants: 2 3

Enter the name of the target restaurant: RestaurantD

Enter the index (1 to 4) of the starting restaurant: 1

Output:

The nearest restaurant to your location is RestaurantD. Distance: 2

Ex 13 b: Implement the Depth First Search traversal algorithm to find the cycles in any given
graph

Cycle Detection in an Undirected Graph using Depth First Search (DFS)

Aim

To implement a program in C that uses Depth First Search (DFS) traversal to detect cycles in
any given undirected graph.

Algorithm

Step 1: Start.

Step 2: Initialize a graph using an adjacency matrix to represent the edges between vertices.

Step 3: Input the number of vertices and edges in the graph.

Step 4: Populate the adjacency matrix by taking input for each edge (u, v). Mark adj[u][v] = 1
and adj[v][u] = 1 for undirected edges.

Step 5: Define a visited array to keep track of visited vertices.

Step 6: Implement the recursive function dfsDetectCycle(node, parent, visited):

  Mark the current node as visited.
 For each adjacent node of the current node:
o If the adjacent node is not visited, recursively call dfsDetectCycle for that node.
o If the adjacent node is visited and is not the parent of the current node, a cycle is
detected.
 Return true if a cycle is detected, otherwise false.

Step 7: Define the function hasCycle():

 Iterate through all vertices.

 If a vertex is not visited, start a DFS traversal from it.
 If any DFS traversal detects a cycle, return true.

Step 8: If the function hasCycle() returns true, print "The graph contains a cycle". Otherwise,
print "The graph does not contain a cycle".

Step 9: End.

Program:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 100 // Maximum number of nodes

// Structure to represent a graph node

typedef struct Graph {

int vertices;

int adj[MAX][MAX]; // Adjacency matrix

} Graph;

// Function prototypes

void initializeGraph(Graph *graph, int vertices);

void addEdge(Graph *graph, int u, int v);

bool dfsDetectCycle(Graph *graph, int node, int parent, int *visited);

bool hasCycle(Graph *graph);

int main() {

int vertices, edges;

 int u, v;

// Input the number of vertices and edges

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

scanf("%d", &vertices);

Graph graph;

initializeGraph(&graph, vertices);

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

scanf("%d", &edges);

// Input edges

printf("Enter the edges (u v):\n");

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

scanf("%d %d", &u, &v);

addEdge(&graph, u, v);

// Check for cycles

if (hasCycle(&graph)) {

printf("The graph contains a cycle.\n");

} else {

printf("The graph does not contain a cycle.\n");

return 0;

// Initialize the graph

void initializeGraph(Graph *graph, int vertices) {

 graph->vertices = vertices;

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

for (int j = 0; j < vertices; j++) {

graph->adj[i][j] = 0; // No edges initially

// Add an undirected edge to the graph

void addEdge(Graph *graph, int u, int v) {

graph->adj[u][v] = 1;

graph->adj[v][u] = 1; // Since the graph is undirected

// Recursive DFS function to detect cycles

bool dfsDetectCycle(Graph *graph, int node, int parent, int *visited) {

visited[node] = 1; // Mark the current node as visited

// Explore all neighbors of the current node

for (int i = 0; i < graph->vertices; i++) {

if (graph->adj[node][i]) { // If there is an edge

if (!visited[i]) {

// Recursively call DFS for unvisited neighbors

if (dfsDetectCycle(graph, i, node, visited)) {

return true; // Cycle detected

} else if (i != parent) {
 // If the neighbor is already visited and not the parent, a cycle is detected

return true;

return false;

// Function to check if the graph has a cycle

bool hasCycle(Graph *graph) {

int visited[MAX] = {0}; // Array to keep track of visited nodes

// Perform DFS for every unvisited node

for (int i = 0; i < graph->vertices; i++) {

if (!visited[i]) {

if (dfsDetectCycle(graph, i, -1, visited)) {

return true; // Cycle detected

return false; // No cycle found

Sample Input 1:
Enter the number of vertices in the graph: 4
Enter the number of edges in the graph: 4
Enter the edges (u v):
01
12
23
31
Output:
The graph contains a cycle.

Sample Input 2:
Enter the number of vertices in the graph: 4
Enter the number of edges in the graph: 3
Enter the edges (u v):
01
12
23
Output:
The graph does not contain a cycle.

Ex 14. By applying the minimal spanning tree technique, you can implement an intercom system
to connect all the departments in your college with the least amount of wiring
Implementation of Intercom System Using Kruskal’s Algorithm to Minimize
Wiring Costs

Aim:

To implement an intercom system connecting all departments in a college using Kruskal’s

algorithm for finding the Minimum Spanning Tree (MST), thereby minimizing the total wiring
cost.

Algorithm:

Step 1: Input the Graph:

Read the number of departments (vertices) and connections (edges).

Input the edges with their weights representing the wiring distances.

Step 2: Initialize Structures:

Create an array to store edges of the graph.

 Initialize arrays for parent and rank to manage the disjoint sets.

Step 3: Sort Edges:

Sort all edges in ascending order based on their weights using qsort.

Step 4: Iterate Through Edges:

For each edge in the sorted list:

Find the parent of each department connected by the edge using the find
function.

If the departments are not in the same set (no cycle formed), add the edge
to the MST and union the two sets using the unionSets function.

Step 5: Store Connections:

For each selected edge, update the connection list of both departments.

Step 6: Output the MST:

Print the edges included in the MST along with their weights.

Calculate and display the total wiring cost.

Step 7: Output Intercom Connections:

For each department, list its connected departments based on the MST.

Step 8: End.

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

#define MAX 100

typedef struct Edge {

int department1;
int department2;
int weight;
} Edge;
// Structure to represent the graph
typedef struct Graph {
int vertices;
int edges;
Edge edge[MAX];
} Graph;

// Structure to store connections for each department

typedef struct Department {
int id;
int connected[MAX];
int connectedCount;
} Department;

// Function to find the parent of a node in the disjoint set

int find(int parent[], int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}

// Function to perform union of two subsets

void unionSets(int parent[], int rank[], int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);

if (rank[rootX] < rank[rootY]) {

parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
 parent[rootY] = rootX;
rank[rootX]++;
}
}

// Comparator function for sorting edges by weight

int compareEdges(const void *a, const void *b) {
Edge *edgeA = (Edge *)a;
Edge *edgeB = (Edge *)b;
return edgeA->weight - edgeB->weight;
}

// Kruskal's algorithm to find the Minimum Spanning Tree (MST)

void kruskalMST(Graph *graph, Department departments[]) {
int vertices = graph->vertices;
Edge result[MAX]; // Array to store the resulting MST
int e = 0; // Index for result[]
int i = 0; // Index for sorted edges

// Sort all edges in increasing order of weight

qsort(graph->edge, graph->edges, sizeof(graph->edge[0]), compareEdges);

int parent[MAX], rank[MAX];

// Initialize disjoint set

for (int v = 0; v < vertices; v++) {
parent[v] = v;
rank[v] = 0;
departments[v].id = v;
departments[v].connectedCount = 0;
}
// Pick the smallest edges one by one and add them to the MST
 while (e < vertices - 1 && i < graph->edges) {
Edge nextEdge = graph->edge[i++];

int x = find(parent, nextEdge.department1);

int y = find(parent, nextEdge.department2);

// If it doesn't form a cycle, include it in the result

if (x != y) {
result[e++] = nextEdge;
unionSets(parent, rank, x, y);

// Add connections for the departments

departments[nextEdge.department1].connected[departments[nextEdge.department1].connectedCount
++] = nextEdge.department2;

departments[nextEdge.department2].connected[departments[nextEdge.department2].connectedCount
++] = nextEdge.department1;
}
}

// Print the resulting MST

printf("The Minimal Spanning Tree (MST) is:\n");
int totalWeight = 0;
for (i = 0; i < e; i++) {
printf("Department %d -- Department %d == %d\n",
result[i].department1, result[i].department2, result[i].weight);
totalWeight += result[i].weight;
}
printf("Total wiring cost: %d\n", totalWeight);

// Print the intercom connections

printf("\nIntercom connections:\n");
for (i = 0; i < vertices; i++) {
 printf("%d is connected to: ", departments[i].id);
for (int j = 0; j < departments[i].connectedCount; j++) {
printf("%d", departments[i].connected[j]);
if (j < departments[i].connectedCount - 1) {
printf(", ");
}
}
printf("\n");
}
}

int main() {
Graph graph;
printf("Enter the number of departments: ");
scanf("%d", &[Link]);

printf("Enter the number of wiring connections: ");

scanf("%d", &[Link]);

for (int i = 0; i < [Link]; i++) {

printf("Enter connection (department1 department2 weight): ");
scanf("%d %d %d", &[Link][i].department1, &[Link][i].department2,
&[Link][i].weight);
}

Department departments[MAX];
kruskalMST(&graph, departments);

return 0;
}

Output:
Enter the number of departments: 4
Enter the number of wiring connections: 5
Enter connection (department1 department2 weight): 0 1 2
Enter connection (department1 department2 weight): 0 2 1
Enter connection (department1 department2 weight): 1 2 3
Enter connection (department1 department2 weight): 1 3 4
Enter connection (department1 department2 weight): 2 3 5
The Minimal Spanning Tree (MST) is:
Department 0 -- Department 2 == 1
Department 0 -- Department 1 == 2
Department 1 -- Department 3 == 4
Total wiring cost: 7

Intercom connections:
0 is connected to: 2, 1
1 is connected to: 0, 3
2 is connected to: 0
3 is connected to: 1

Ex 15. Implement any shortest path algorithm to discover the shortest route between
Chennai and Hyderabad.
Dijkstra’s Algorithm Implementation for Finding the Shortest Path Between Cities

Aim:

To implement Dijkstra’s Shortest Path Algorithm in C to calculate the shortest distance

between two cities based on user-provided inputs, such as cities, roads, and distances.

Algorithm:

Step 1: Input the number of cities and roads

o Prompt the user to input the total number of cities.
o Prompt the user to input the number of roads and their respective details
(connected cities and distances).

Step 2: Initialize the graph

o Use structures to represent cities as nodes and roads as weighted edges.
o Store the edges in an adjacency list.
Step 3: Add nodes and edges
o Add city names as nodes to the graph.
o For each road, add bidirectional edges between the cities with the given
distance.

Step 4: Prepare the data for Dijkstra's algorithm

o Initialize the distances of all cities to infinity (INF), except the starting city,
which is set to 0.
o Create a priority queue to process the cities based on their current shortest
distance.

Step 5: Run Dijkstra's algorithm

o Pop the city with the shortest distance from the priority queue.
o Update the distances to its neighbors if a shorter path is found through the
current city.
o Repeat until all reachable cities are processed.

Step 6: Output the result

o Check the distance to the destination city.
o If a path exists, print the shortest distance; otherwise, indicate that no path
exists.

Step 7: End of Program

o Free dynamically allocated memory (if applicable) and terminate the program.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 99999
#define MAX 100

// Structure for edges

typedef struct Edge {
int to;
int weight;
struct Edge* next;
} Edge;

// Structure for graph nodes

typedef struct Node {
 char name[50];
Edge* edges;
} Node;

Node graph[MAX];
int node_count = 0;

// Structure for the priority queue

typedef struct PriorityQueue {
int node;
int distance;
} PriorityQueue;

PriorityQueue pq[MAX];
int pq_size = 0;

// Add a city (node) to the graph

void add_node(const char* name) {
strcpy(graph[node_count].name, name);
graph[node_count].edges = NULL;
node_count++;
}

// Add a road (edge) to the graph

void add_edge(const char* from, const char* to, int weight) {
int from_idx = -1, to_idx = -1;

// Find indices of the cities

for (int i = 0; i < node_count; i++) {
if (strcmp(graph[i].name, from) == 0) from_idx = i;
if (strcmp(graph[i].name, to) == 0) to_idx = i;
}
 if (from_idx == -1 || to_idx == -1) {
printf("Error: City not found!\n");
return;
}

// Add edge from "from" to "to"

Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->to = to_idx;
edge->weight = weight;
edge->next = graph[from_idx].edges;
graph[from_idx].edges = edge;

// Add edge from "to" to "from" (undirected graph)

edge = (Edge*)malloc(sizeof(Edge));
edge->to = from_idx;
edge->weight = weight;
edge->next = graph[to_idx].edges;
graph[to_idx].edges = edge;
}

// Priority queue functions

void pq_push(int node, int distance) {
pq[pq_size].node = node;
pq[pq_size].distance = distance;
pq_size++;

for (int i = pq_size - 1; i > 0; i--) {

if (pq[i].distance < pq[i - 1].distance) {
PriorityQueue temp = pq[i];
pq[i] = pq[i - 1];
pq[i - 1] = temp;
 } else {
break;
}
}
}

PriorityQueue pq_pop() {
PriorityQueue top = pq[0];
for (int i = 0; i < pq_size - 1; i++) {
pq[i] = pq[i + 1];
}
pq_size--;
return top;
}

int pq_empty() {
return pq_size == 0;
}

// Dijkstra's algorithm
void dijkstra(const char* start_city, const char* end_city) {
int distances[MAX];
int visited[MAX] = {0};
int start_idx = -1, end_idx = -1;

// Find indices of the start and end cities

for (int i = 0; i < node_count; i++) {
if (strcmp(graph[i].name, start_city) == 0) start_idx = i;
if (strcmp(graph[i].name, end_city) == 0) end_idx = i;
}

if (start_idx == -1 || end_idx == -1) {

 printf("Error: City not found!\n");
return;
}

// Initialize distances
for (int i = 0; i < node_count; i++) {
distances[i] = INF;
}
distances[start_idx] = 0;

// Add start node to the priority queue

pq_push(start_idx, 0);

while (!pq_empty()) {
PriorityQueue current = pq_pop();
int current_node = [Link];

if (visited[current_node]) continue;
visited[current_node] = 1;

Edge* edge = graph[current_node].edges;

while (edge) {
int neighbor = edge->to;
int weight = edge->weight;

if (!visited[neighbor] && distances[current_node] + weight < distances[neighbor]) {

distances[neighbor] = distances[current_node] + weight;
pq_push(neighbor, distances[neighbor]);
}

edge = edge->next;
}
 }

// Print the shortest distance

if (distances[end_idx] != INF) {
printf("\nThe shortest distance from %s to %s is: %d\n", start_city, end_city, distances[end_idx]);
} else {
printf("\nNo path exists from %s to %s.\n", start_city, end_city);
}
}

int main() {
int choice, weight;
char city1[50], city2[50], start_city[50], end_city[50];

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

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

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

printf("Enter city %d name: ", i + 1);
scanf("%s", city1);
add_node(city1);
}

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

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

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

printf("Enter road %d (city1 city2 distance): ", i + 1);
scanf("%s %s %d", city1, city2, &weight);
add_edge(city1, city2, weight);
 }

printf("Enter the starting city: ");

scanf("%s", start_city);

printf("Enter the destination city: ");

scanf("%s", end_city);

dijkstra(start_city, end_city);

return 0;
}

Output:
Enter the number of cities: 4
Enter city 1 name: chennai
Enter city 2 name: hyderabad
Enter city 3 name: bangalore
Enter city 4 name: mumbai
Enter the number of roads: 5
Enter road 1 (city1 city2 distance): chennai hyderabad 900
Enter road 2 (city1 city2 distance): chennai bangalore 350
Enter road 3 (city1 city2 distance): hyderabad bangalore 500
Enter road 4 (city1 city2 distance): hyderabad mumbai 700
Enter road 5 (city1 city2 distance): bangalore mumbai 800
Enter the starting city: chennai
Enter the destination city: hyderabad

The shortest distance from chennai to hyderabad is: 850