Data Structures & Algorithms (CS-208-23)

Lab Session-03

Objective: Understand and implement fundamental data structures- Arrays and Linked
Lists, focusing on their operations, implementations, and practical applications.
• Outcomes:
After completion of the lab session, students will be able to:
• Implement static and dynamic arrays
• Create and manipulate single and multi-dimensional arrays
• Understand and implement different types of linked lists
• Perform basic operations on arrays and linked lists
• Apply these data structures to solve practical problems
• Lab Tasks:
• 1. StudentRecordManagementSystem:
Create aprogramthat implements a student recordmanagement systemusing
arrays. Your program should:
• Declare a structure for student records with fields: rollNo (integer), name
(string), marks (array of 3 integers for different subjects)
• Implement functions for:– Adding a new student record– Searching for a student by
roll number– Calculating average marks for each student– Finding the student with
highest total marks
• Handle array resizing when maximum capacity is reached
 Write/copy your code here:
#include <iostream>
#include <string>
using namespace std;
struct Student {
int rollNo;
string name;
int marks[3];
};
class StudentRecordSystem {
private:
Student* students;
int size;
int capacity;
void resizeArray() {
capacity *= 2;
Student* newStudents = new Student[capacity];
for (int i = 0; i < size; i++) {
newStudents[i] = students[i];
}
 delete[] students;
students = newStudents;
}

public:
StudentRecordSystem(int initialCapacity = 5) {
capacity = initialCapacity;
size = 0;
students = new Student[capacity];
}
~StudentRecordSystem() {
delete[] students;
}
void addStudent(int rollNo, string name, int marks[]) {
if (size == capacity) {
resizeArray();
}
students[size].rollNo = rollNo;
students[size].name = name;
for (int i = 0; i < 3; i++) {
students[size].marks[i] = marks[i];
}
size++;
}
void searchStudent(int rollNo) {
for (int i = 0; i < size; i++) {
if (students[i].rollNo == rollNo) {
cout << "Student Found: " << students[i].name << "\n";
cout << "Marks: " << students[i].marks[0] << ", "
<< students[i].marks[1] << ", " << students[i].marks[2] << "\n";
 return;
}}
cout << "Student with Roll No " << rollNo << " not found.\n";
}
void calculateAverageMarks() {
for (int i = 0; i < size; i++) {
double avg = (students[i].marks[0] + students[i].marks[1] + students[i].marks[2]) / 3.0;
cout << "Student: " << students[i].name << " - Average Marks: " << avg << "\n";
}}
void findTopStudent() {
if (size == 0) {
cout << "No students in the system.\n";
return;
}
int maxIndex = 0;
int maxMarks = students[0].marks[0] + students[0].marks[1] + students[0].marks[2];
for (int i = 1; i < size; i++) {
int totalMarks = students[i].marks[0] + students[i].marks[1] + students[i].marks[2];
if (totalMarks > maxMarks) {
maxMarks = totalMarks;
maxIndex = i;
}}
cout << "Top Student: " << students[maxIndex].name << " - Total Marks: " << maxMarks << "\
n";
}};
int main() {
StudentRecordSystem system;
int marks1[] = {85, 90, 78};
int marks2[] = {92, 88, 95};
int marks3[] = {78, 82, 84};
int marks4[] = {95, 91, 89};
 int marks5[] = {75, 76, 72};
system.addStudent(1001, "Ali", marks1);
system.addStudent(1002, "Sarah", marks2);
system.addStudent(1003, "Usman", marks3);
system.addStudent(1004, "Ayesha", marks4);
system.addStudent(1005, "Hassan", marks5);
cout << "\n--- Test Operations ---\n";
cout << "\nSearching for student with Roll No 1003:\n";
system.searchStudent(1003);
cout << "\nCalculating Average Marks:\n";
system.calculateAverageMarks();
cout << "\nFinding Top Student:\n";
system.findTopStudent();
int marks6[] = {88, 86, 90};
cout << "\nAdding new student (Zainab) to test array resizing:\n";
system.addStudent(1006, "Zainab", marks6);
system.searchStudent(1006);
return 0;
}
2. Image Processing with 2D Arrays:
Implement a program to simulate basic image processing operations using 2D ar
rays. Your program should:
• Create a 5x5 2D array representing pixel values (0-255) of a grayscale image
• Implement functions for:– Image inversion (255- pixel value)– Horizontal flip (swap
columns)– Vertical flip (swap rows)– 90-degree clockwise rotation
• Display the original and processed arrays in a readable format
 Write/copy your code here:
#include <iostream>
using namespace std;
const int SIZE = 5;
void displayImage(int image[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
cout << image[i][j] << "\t";
}
cout << endl;
}}
void invertImage(int image[SIZE][SIZE], int output[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
output[i][j] = 255 - image[i][j];
}}}
void flipHorizontal(int image[SIZE][SIZE], int output[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
output[i][j] = image[i][SIZE - j - 1];
}}}
void flipVertical(int image[SIZE][SIZE], int output[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
output[i][j] = image[SIZE - i - 1][j];
 }}}
void rotate90Clockwise(int image[SIZE][SIZE], int output[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
output[j][SIZE - i - 1] = image[i][j];
}}}
int main() {
int image[SIZE][SIZE] = {
{50, 100, 150, 100, 50},
{100, 150, 200, 150, 100},
{150, 200, 250, 200, 150},
{100, 150, 200, 150, 100},
{50, 100, 150, 100, 50}
};
int inverted[SIZE][SIZE], flippedH[SIZE][SIZE], flippedV[SIZE][SIZE], rotated[SIZE][SIZE];
invertImage(image, inverted);
flipHorizontal(image, flippedH);
flipVertical(image, flippedV);
rotate90Clockwise(image, rotated);
cout << "Original Image:\n";
displayImage(image);
cout << "\nInverted Image:\n";
displayImage(inverted);
cout << "\nHorizontally Flipped Image:\n";
displayImage(flippedH);
cout << "\nVertically Flipped Image:\n";
displayImage(flippedV);
cout << "\n90-degree Rotated Image:\n";
displayImage(rotated);
return 0;
}
3. To-Do List Manager:
Design a to-do list manager application using a singly linked list. Your program
should:
• Create a node class/structure containing: taskDescription (string), priority
(integer, 1-5 with 1 being highest), isCompleted (boolean)
• Implement functions for:– Adding tasks (insert based on priority)– Marking tasks as
completed– Removing completed tasks– Displaying all tasks with their status
• Sort tasks by priority while displaying
• Handle proper memory management (free allocated memory)

Write/copy your code here:

#include <iostream>
#include <string>
using namespace std;
struct Task {
string description;
int priority;
bool isCompleted;
Task* next;
};
Task* createTask(string desc, int pri) {
 Task* newTask = new Task();
newTask->description = desc;
newTask->priority = pri;
newTask->isCompleted = false;
newTask->next = nullptr;
return newTask;
}
void addTask(Task*& head, string desc, int pri) {
Task* newTask = createTask(desc, pri);
if (!head || pri < head->priority) {
newTask->next = head;
head = newTask;
return;
}
Task* current = head;
while (current->next && current->next->priority <= pri) {
current = current->next;
}
newTask->next = current->next;
current->next = newTask;
}
void markCompleted(Task* head, string desc) {
Task* current = head;
while (current) {
if (current->description == desc) {
current->isCompleted = true;
cout << "Task \"" << desc << "\" marked as completed.\n";
return;
}
current = current->next;
 }
cout << "Task not found.\n";
}
void removeCompleted(Task*& head) {
while (head && head->isCompleted) { if completed
Task* temp = head;
head = head->next;
delete temp;
}
Task* current = head;
while (current && current->next) {
if (current->next->isCompleted) {
Task* temp = current->next;
current->next = temp->next;
delete temp;
} else {
current = current->next;
}}}
void displayTasks(Task* head) {
if (!head) {
cout << "No tasks in the list.\n";
return;
}
cout << "\nTo-Do List:\n";
Task* current = head;
while (current) {
cout << "[Priority: " << current->priority << "] "
<< current->description
<< " - " << (current->isCompleted ? "Completed" : "Pending") << endl;
current = current->next;
 }}
void deleteAllTasks(Task*& head) {
while (head) {
Task* temp = head;
head = head->next;
delete temp;
}}
int main() {
Task* taskList = nullptr;
addTask(taskList, "Complete lab assignment", 2);
addTask(taskList, "Prepare for quiz", 1);
addTask(taskList, "Read chapter 4", 3);
addTask(taskList, "Submit project proposal", 1);
addTask(taskList, "Meet group members", 4);
addTask(taskList, "Research paper review", 3);
displayTasks(taskList);
markCompleted(taskList, "Prepare for quiz");
markCompleted(taskList, "Read chapter 4");
removeCompleted(taskList);
addTask(taskList, "Study for midterm", 1);
displayTasks(taskList);
deleteAllTasks(taskList);

return 0;
}
4. Music Playlist Application:
Create a music playlist implementation using a doubly linked list. Your program
should:
• Define a node class/structure for songs with: title (string), artist (string),
duration (float)
• Implement functions for
:– Adding songs to beginning or end of playlist
– Removing a song by title
– Navigating forward and backward through playlist–
Searching for a song by title
– Displaying the current playlist
• Maintain proper memory management for nodes
 Write/copy your code here:
#include <iostream>
#include <string>
using namespace std;
struct Song {
string title;
string artist;
float duration;
Song* prev;
Song* next;
};
Song* createSong(string title, string artist, float duration) {
Song* newSong = new Song();
newSong->title = title;
newSong->artist = artist;
newSong->duration = duration;
 newSong->prev = nullptr;
newSong->next = nullptr;
return newSong;
}
void addSongEnd(Song*& head, Song*& tail, string title, string artist, float duration) {
Song* newSong = createSong(title, artist, duration);
if (!head) {
head = tail = newSong;
return;
}
tail->next = newSong;
newSong->prev = tail;
tail = newSong;
}
void addSongBeginning(Song*& head, Song*& tail, string title, string artist, float duration) {
Song* newSong = createSong(title, artist, duration);
if (!head) {
head = tail = newSong;
return;
}
newSong->next = head;
head->prev = newSong;
head = newSong;
}
void removeSong(Song*& head, Song*& tail, string title) {
Song* current = head;
while (current) {
if (current->title == title) {
if (current == head) {
head = head->next;
 if (head) head->prev = nullptr;
} else if (current == tail) {
tail = tail->prev;
if (tail) tail->next = nullptr;
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current;
cout << "Removed song: " << title << endl;
return;
}
current = current->next;
}
cout << "Song not found: " << title << endl;
}
void displayPlaylistForward(Song* head) {
if (!head) {
cout << "Playlist is empty.\n";
return;
}
cout << "\nPlaylist (Forward Order):\n";
Song* current = head;
while (current) {
cout << "\"" << current->title << "\" by " << current->artist << " (" << current->duration <<
min)\n";
current = current->next;
}}
void displayPlaylistBackward(Song* tail) {
if (!tail) {
cout << "Playlist is empty.\n";
 return;
}
cout << "\nPlaylist (Backward Order):\n";
Song* current = tail;
while (current) {
cout << "\"" << current->title << "\" by " << current->artist << " (" << current->duration <<
min)\n";
current = current->prev;
}}
void searchSong(Song* head, string title) {
Song* current = head;
while (current) {
if (current->title == title) {
cout << "Song found: \"" << current->title << "\" by " << current->artist << " (" << current-
>duration << " min)\n";
return;
}
current = current->next;
}
cout << "Song not found: " << title << endl;
}
void navigateForward(Song*& current, int steps) {
while (current && steps--) {
current = current->next;
}
if (current)
cout << "Now playing: \"" << current->title << "\" by " << current->artist << endl;
else
cout << "Reached end of playlist.\n";
}
void navigateBackward(Song*& current, int steps) {
 while (current && steps--) {
current = current->prev;
}
if (current)
cout << "Now playing: \"" << current->title << "\" by " << current->artist << endl;
else
cout << "Reached start of playlist.\n";
}
void deleteAllSongs(Song*& head) {
while (head) {
Song* temp = head;
head = head->next;
delete temp;
}}
int main() {
Song* head = nullptr;
Song* tail = nullptr;
Song* current = nullptr;
addSongEnd(head, tail, "Shape of You", "Ed Sheeran", 3.54);
addSongEnd(head, tail, "Despacito", "Luis Fonsi", 4.12);
addSongEnd(head, tail, "Blank Space", "Taylor Swift", 3.40);
addSongEnd(head, tail, "See You Again", "Wiz Khalifa", 3.58);
addSongEnd(head, tail, "Uptown Funk", "Mark Ronson", 4.30);
displayPlaylistForward(head);
current = head;
navigateForward(current, 2);
navigateBackward(current, 1);
searchSong(head, "Blank Space");
addSongBeginning(head, tail, "Believer", "Imagine Dragons", 3.24);
addSongEnd(head, tail, "Faded", "Alan Walker", 3.32);
 removeSong(head, tail, "Despacito");
displayPlaylistForward(head);
displayPlaylistBackward(tail);
deleteAllSongs(head);
return 0;
}

5. Round-Robin Process Scheduler:

Develop a simplified round-robin process scheduler using a circular linked list. Your
program should:
• Create a process node structure with: processID (integer), burstTime (inte
ger), remainingTime (integer)
• Implement functions for:– Adding processes to the scheduler– Executing processes
with a fixed time quantum– Removing completed processes– Calculating waiting time
and turnaround time for each process
• Maintain circular linked list structure
• Handle the case when all processes are completed

Write/copy your code here:

#include <iostream>
using namespace std;
struct Process {
int processID;
int burstTime;
int remainingTime;
Process* next;
};
Process* createProcess(int processID, int burstTime) {
Process* newProcess = new Process();
 newProcess->processID = processID;
newProcess->burstTime = burstTime;
newProcess->remainingTime = burstTime;
newProcess->next = nullptr;
return newProcess;
}
void addProcess(Process*& head, int processID, int burstTime) {
Process* newProcess = createProcess(processID, burstTime);
if (!head) {
head = newProcess;
head->next = head;
} else {
Process* temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newProcess;
newProcess->next = head;
}}
void executeProcesses(Process*& head, int timeQuantum) {
if (!head) {
cout << "No processes to execute.\n";
return;
}
int time = 0, completed = 0;
int totalProcesses = 0;
Process* temp = head;
do {
totalProcesses++;
temp = temp->next;
} while (temp != head);
int waitingTime[totalProcesses] = {0}, turnaroundTime[totalProcesses] = {0};
 Process* current = head;
while (completed < totalProcesses) {
if (current->remainingTime > 0) {
int execTime = min(timeQuantum, current->remainingTime);
cout << "Executing Process " << current->processID << " for " << execTime << " units.\n";
current->remainingTime -= execTime;
time += execTime;
if (current->remainingTime == 0) {
completed++;
turnaroundTime[current->processID - 1] = time;
waitingTime[current->processID - 1] = turnaroundTime[current->processID - 1] - current-
>burstTime;
cout << "Process " << current->processID << " completed at time " << time << ".\n";
}}
current = current->next;
}
cout << "\nFinal Process Statistics:\n";
int totalWaitingTime = 0, totalTurnaroundTime = 0;
for (int i = 0; i < totalProcesses; i++) {
cout << "Process " << (i + 1) << " -> Waiting Time: " << waitingTime[i]
<< ", Turnaround Time: " << turnaroundTime[i] << "\n";
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
}
cout << "\nAverage Waiting Time: " << (float)totalWaitingTime / totalProcesses << "\n";
cout << "Average Turnaround Time: " << (float)totalTurnaroundTime / totalProcesses << "\n";
}
void deleteAllProcesses(Process*& head) {
if (!head) return;

Process* temp = head;

 Process* nextProcess;
do {
nextProcess = temp->next;
delete temp;
temp = nextProcess;
} while (temp != head);

head = nullptr;
}
int main() {
Process* head = nullptr;
int timeQuantum = 2;
addProcess(head, 1, 8);
addProcess(head, 2, 4);
addProcess(head, 3, 9);
addProcess(head, 4, 5);
executeProcesses(head, timeQuantum);
deleteAllProcesses(head);
return 0;
}
Write your answer here by hand: