Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 1 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

University of Management & Technology

Iqbal Campus, Sialkot
Fall 2024 (3rd Semester)
Student Name: SYED SHAHZIL ABBAS ID: 23018020020
Course Title: Data Structures Lab Program: BSCS-A-B18
Resource Person: Ms Jaweria Jalil Activity: Lab Manuals

DATA STRUCTURES & ALGORITHMS IN C++

LAB MANUALS By Syed Shahzil Abbas

Contents
Lab 1- Stack Data Structure.........................................................................................................................5
Task 1.1-Implement stack with the following functions: 1-push() 2-pop() 3-Traversal() 4-search()
5-sort() 6-MinVal() 7-MaxVal()............................................................................................................5
Task 1.2-A function that will find all duplicate values and their indexes in Stack................................10
Task-1.3-InputStack & SortedStack.......................................................................................................11
Task 1.4- Real-life Applications of Stack...............................................................................................13
1-Delimiter Checker.........................................................................................................................13
2-Web browser history navigator.....................................................................................................14
3-Undo in Text Editor........................................................................................................................18
Lab 2-Conversion of Infix Expression to Prefix & Postfix Expression using Stack....................................21
Task 2.1,2 A Generic Code for above procedure...................................................................................21

Page 2 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 2.3- Adding Some additional Operators.......................................................................................28

Lab 3-Queue Data Structure.....................................................................................................................35
Task 3.1-Simple Queue using Array......................................................................................................35
Task 3.2-Simple Queue using Array & Proper Memory Utilization......................................................37
Task 3.3-Circular Queue using Array.....................................................................................................40
Task 3.4-Simple Queue using Array that automatically sorts its element...........................................43
Task 3.5-Applications of Circular Queue...............................................................................................46
1-Traffic Light Signals.........................................................................................................................46
2-Round Table Video Conferencing...................................................................................................48
3-Managing Buffers...........................................................................................................................51
Lab 4- Linked-list DS (Single & Circular)....................................................................................................54
Task 4.1 Implementations of 10 functionalities (given in QP) in Single & Circular Link lists...............54
Task 4.1.1 -Single Linked-list.............................................................................................................54
Task 4.1.2 Circular Linked list............................................................................................................60
Task 4.2- Real-Life Applications of Single/y Linked-list.........................................................................67
Polynomial Arithmetic......................................................................................................................67
Shahzil CMD for Managing Directories.............................................................................................70
Task 4.3- Real-Life Applications of Circular Linked-list.........................................................................75
Token Ring Network (STRN)..............................................................................................................75
...........................................................................................................................................................80
Online Ludo by Shahzil (SOL)............................................................................................................80
Lab 5-Linked-list DS (Doubly Link list).......................................................................................................88
Task 5.1- Implementation of 10 Functionalities in Doubly linked-list (SDL & CDL)..............................88
Task 5.1.1- SDL...................................................................................................................................88
Task 5.1.2-CDL...................................................................................................................................97
Lab 6- Searching & Sorting......................................................................................................................102
Task 6.1-C++ Code for Linear Searching..............................................................................................102
Task 6.2-C++ Code for Binary Searching..............................................................................................102
Task 6.3-C++ code for Bubble Sort......................................................................................................103
Task 6.4-C++ code for Handling Duplicate values in Linear Search....................................................104
Task 6.5-Binary Search with Bubble Sort............................................................................................105
Task 6.6- Reverse Bubble Sort.............................................................................................................106
Task 6.7,8- Real-Time Scenario............................................................................................................107

Page 3 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Lab 7- Stack & Queue using Linked-list...................................................................................................110

Task 7.1- Stack using link list...............................................................................................................110
Task 7.2-Queue using link list..............................................................................................................113
Task 7.3- Real-Time Scenarios.............................................................................................................117
Ordering System..............................................................................................................................117
Priority Task Manager.....................................................................................................................120

Page 4 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

STACK DATA STRUCTURE

`LAB 1
DATED=: 31/10/24

Lab 1- Stack Data Structure

Task 1.1-Implement stack with the following functions: 1-push() 2-
pop() 3-Traversal() 4-search() 5-sort() 6-MinVal() 7-MaxVal()
Respective Code:
1- #include<iostream>
2- -#include<cstdlib>
3- using namespace std;
4- class Stack{
5- public:
6- int top,size;
7- int *arr;
8- Stack() {
9- top=-1;
10- cout<<"\n Enter Size of Stack: ";
11- cin>>size;
12- arr=new int[size];
13- }
14- bool isempty(){
15- if(top==-1)
16- return true;
17- else
18- return false;
19- }
20- bool isfull(){
21- if(top==(size-1))
22- return true;
23- else
24- return false;
25- }
26- void push(int val){
27- if(!isfull()){
28- top+=1;
29- cout<<"\n Value Pushed Successfully! ";
30- arr[top]=val;}
31- else
32- cout<<"\n Stack is in Overflow state "; }
33- void pop(){

Page 5 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

34- if(!isempty()){
35- cout<<"\n Value Poped Successfully! ";
36- arr[top]=0;
37- top-=1;}
38- else
39- cout<<"\n Stack is in Underflow State";}
40- int count(){
41-
42- return (top+1);
43- }
44- void display(){
45- if(top==-1)
46- cout<<"\n No Element on Stack";
47- else{
48- cout<<"Elements on Stack";
49- for(int i=top;i>=0;i--)
50- cout<<"\n "<<arr[i];
51- }
52- }
53-
54- void search(int val){
55- int loc=-1;
56- for(int i=0;i<=top;i++){
57- if(arr[i]==val){
58- loc=i;
59- break;
60- }
61- }
62- if(loc>-1)
63- cout<<"\n The value "<<val<<" found at position: "<<loc;
64- else
65- cout<<"\n The value "<<val<<" You are trying to search does not
exist";
66- }
67- void Sort(){
68- int ch;
69- if(count()<=2)
70- cout<<"\n Sorting Operation can only be perform if elements are atleat 2 in the
Stack";
71- else{
72- cout<<"\n In which way you want to sort the Stack:\n Ascending Order(1) \n
Descending Order (2)";
73- cout<<"\n\n Enter Your Choice: ";
74- cin>>ch;
75- if(ch==1){
76- for(int i=top;i>=0;i--) {

Page 6 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

77- for(int j=top;j>=0;j--){

78- if(arr[j]>arr[i])
79- swap(arr[j],arr[i]);
80- }
81- }
82- cout<<"\n Stack Sorted in Ascending Order Successfully! ";
83- cout<<endl;
84- display();
85- }
86- else if(ch==2){
87- for(int i=top;i>=0;i--) {
88- for(int j=top;j>=0;j--){
89- if(arr[j]<arr[i])
90- swap(arr[j],arr[i]);
91- }
92- }
93- cout<<"\n Stack Sorted in Descending Order Successfully! ";
94- cout<<endl;
95- display();
96- }
97- else
98- cout<<"\n Invalid Choice";
99- }
100- }
101- void MinV(){
102- int min,pos;
103- if(top==0){
104- cout<<"\n Stack is Empty Yet or having only one element ";
105- }
106- else{
107- min=arr[top];
108- for(int i=(top-1);i>-1;i--){
109- if(min>arr[i]){
110- min=arr[i];
111- pos=i;
112- }
113- }
114- cout<<"\n Smallest value in Stack is: "<<min<<" at index:
"<<pos;
115- }
116- }
117- void MaxV(){
118- int max,pos;
119- if(top==0){
120- cout<<"\n Stack is Empty Yet or having only one element ";
121- }

Page 7 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

122- else{
123- max=arr[top];
124- for(int i=(top-1);i>-1;i--){
125- if(max<arr[i]){
126- max=arr[i];
127- pos=i;
128- }
129- }
130- cout<<"\n Largest value in Stack is: "<<max<<" at index:
"<<pos;
131- }
132- }
133- };
134- int main(){
135- Stack s1;
136- int choice=0;
137- int val=0;
138- do{
139- cout<<"\n Wellcome to Stack: ";
140- cout<<"\n\n 0- Exit ";
141- cout<<"\n 1- Push ";
142- cout<<"\n 2- Pop ";
143- cout<<"\n 3- Display ";
144- cout<<"\n 4- Search ";
145- cout<<"\n 5- Sort ";
146- cout<<"\n 6- Find Minimum Value ";
147- cout<<"\n 7- Find Maximum Value ";
148- cout<<"\n 8- Clear Screen ";
149- cout<<"\n\n ENTER YOUR CHOICE: ";
150- cin>>choice;
151- switch(choice){
152- case 1:{
153- cout<<"\n Enter a value: ";
154- cin>>val;
155- s1.push(val);
156- break;
157- }
158- case 2:{
159- s1.pop();
160- break;
161- }
162- case 3:{
163- s1.display();
164- break;
165- }
166- case 4:{

Page 8 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

167- cout<<"\n Enter a Values to be searched in a Stack: (Remember

that the index starts from 0): ";
168- cin>>val;
169- s1.search(val);
170- break;
171- }
172- case 5:{
173- s1.Sort();
174- break;
175- }
176- case 6:{
177- s1.MinV();
178- break;
179- }
180- case 7:{
181- s1.MaxV();
182- break;
183- }
184- case 8:{
185- system("cls");
186- break;
187- }
188- default:
189- cout<<"\n Wrong Selection of Option ";
190- }
191- }while(choice!=0);
192- return 0;
193- }
Output Observed:

Page 9 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 10 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 1.2-A function that will find all duplicate values and their
indexes in Stack
Respective Code:
1- void duplicate() {
2- if (top <= 0) {
3- cout << "\n Duplicate function requires at least two elements in the stack.";
4- } else {
5- cout << "\n Element\tRepetition\tIndexes";
6-
7- for (int i = 0; i <= top; i++) {
8- int element = arr[i];
9- int count = 0;
10- string indexes = "";
11-
12- // I am counting occurrences of arr[i] and record indexes
13- for (int j = 0; j <= top; j++) {
14- if (arr[j] == element) {
15- count++;
16- indexes += to_string(j) + " ";
17- }
18- }
19-
20- // I want to display only duplicates once
21- if (count > 1&& element !=-1) {
22- cout << "\n " << element << "\t\t" << count << "\t\t" << indexes;
23-
24- // I mark the duplicates as processed to avoid reprinting
25- for (int k = 0; k <= top; k++) {
26- if (arr[k] == element)
27- arr[k] = -1; // Use -1 as a marker; ensure -1 isn't a valid stack value
28- }
29- }
30- }
31- }
32- }
Output Observed:

Page 11 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task-1.3-InputStack & SortedStack

Respective Code:
1- #include<iostream>
2- #include<stack>
3- using namespace std;
4- int main(){
5- stack <int> InputStack,SortedStack;
6- int size,i;
7- cout<<"\n How many elements you want to insert on the InputStack? ";
8- cin>>size;
9- int st[size];
10- for(i=0;i<size;i++){
11- cout<<"\n Enter Element "<<i+1<<": ";
12- cin>>st[i];
13- }
14- for(i=0;i<size;i++)
15- InputStack.push(st[i]);
16-
17- //I have To arrange the array in descending order in this way when I pushed these
elements to sorted stack they will appear as in ascending order
18- for(i=0;i<size;i++){
19- for(int j=0;j<size;j++){
20- if(st[i]>st[j])
21- swap(st[i],st[j]);
22- }
23- }
24- //Pushing elements to the sorted stack
25- for(i=0;i<size;i++)
26- SortedStack.push(st[i]);
27-
28- cout<<"\n InputStack";
29- while(!InputStack.empty()){
30- cout<<"\n "<<InputStack.top();
31- InputStack.pop();
32- }
33- cout<<"\n\n Sorted Stack: ";
34- while(!SortedStack.empty()){
35- cout<<"\n "<<SortedStack.top();
36- SortedStack.pop();
37- }
38- return 0;
39- }
Output Observed:

Page 12 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 1.4- Real-life Applications of Stack

1-Delimiter Checker
Respective Code:
1- #include<iostream>
2- #include<string>
3- #include<stack>
4- using namespace std;
5- bool valid(string s){
6- int l=s.size();
7- stack <char> S;
8- for(int i=0;i<l;i++){
9- if(s[i]=='('||s[i]=='['||s[i]=='{')
10- S.push(s[i]);
11- else if(!S.empty() && s[i]==')'){
12- if(S.top()=='(')
13- S.pop();
14- else
15- return false;
16- }
17- else if(!S.empty() && s[i]==']'){
18- if(S.top()=='[')

Page 13 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

19- S.pop();
20- else
21- return false;
22- }
23- else if(!S.empty() && s[i]=='}'){
24- if(S.top()=='{')
25- S.pop();
26- else
27- return false;
28- }
29- }
30- if(S.empty())
31- return true;
32- else
33- return false;
34- }
35- int main(){
36- string str;
37- cout<<"\n Enter Any String: ";
38- cin>>str;
39- if(valid(str))
40- cout<<"\n It is Valid string with balanced parenthesis";
41- else
42- cout<<"\n It is not Valid String";
43- return 0;
44- }
Output Observed:

2-Web browser history navigator

Respective Code:
1- #include <iostream>
2- #include <stack>

Page 14 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

3- #include <string>
4- using namespace std;
5-
6- class WBHM { // Web browser history management
7- stack<int> s1; // Stack to store history of screens
8- string S[4]; // Array to store user inputs
9-
10- public:
11- WBHM(){
12- for(int i=0;i<4;i++)
13- S[i]=" ";
14- }
15- void screen1() {
16- system("cls");
17- cout << "\n WELCOME TO REGISTRATION PLATFORM ";
18- if(S[0]!=" ")
19- cout<<"\n Previous Entered Info: "<<S[0];
20- cout << "\n\n Enter Your Full Name: ";
21- string s;
22- cin.ignore(); // Ignore newline from previous input
23- getline(cin, s);
24- S[0] = s;
25- navigator(1);
26- }
27-
28- void screen2() {
29- system("cls");
30- if(S[1]!=" ")
31- cout<<"\n Previous Entered Info: "<<S[1];
32- cout << "\n Enter Your CNIC No: ";
33- string cnic;
34- cin >> cnic;
35- S[1] = cnic;
36- navigator(2);
37- }
38-
39- void screen3() {
40- system("cls");
41- if(S[2]!=" ")
42- cout<<"\n Previous Entered Info: "<<S[2];
43- cout << "\n Are you interested in freelancing? ";
44- string fre;
45- cin >> fre;
46- S[2] = fre;
47- navigator(3);
48- }

Page 15 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

49-
50- void screen4() {
51- system("cls");
52- if(S[3]!=" ")
53- cout<<"\n Previous Entered Info: "<<S[3];
54- cout << "\n Enter Your Country Name: ";
55- cin.ignore(); // Ignore newline from previous input
56- string co;
57- getline(cin, co);
58- S[3] = co;
59- navigator(4);
60- }
61-
62- void screen5() {
63- system("cls");
64- cout << "\n YOUR DATA REPORT: ";
65- cout << "\n\n Full Name: " << S[0];
66- cout << "\n\n CNIC: " << S[1];
67- cout << "\n\n Interested in Freelancing: " << S[2];
68- cout << "\n\n Country: " << S[3];
69- navigator(5);
70- }
71-
72- void Move(int l) {
73- // Navigates to the specified screen based on the integer 'l'
74- switch (l) {
75- case 1: screen1(); break;
76- case 2: screen2(); break;
77- case 3: screen3(); break;
78- case 4: screen4(); break;
79- case 5: screen5(); break;
80- default: cout << "\nInvalid Screen"; break;
81- }
82- }
83-
84- void navigator(int cl) { // Current location
85- // Display options for navigation
86- cout << "\n\n SELECT AN OPTION: ";
87- if (cl < 5) {
88- cout << "\n 1-Next ";
89- }
90- if (!s1.empty()) {
91- cout << "\n 2-Back ";
92- }
93-
94- int ch;

Page 16 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

95- cout << "\n Enter Here: ";

96- cin >> ch;
97-
98- // Implementing forward and backward navigation
99- if (ch == 1 && cl < 5) {
100- s1.push(cl); // Push current screen to stack
101- Move(cl + 1); // Move to the next screen
102- } else if (ch == 2 && !s1.empty()) {
103- int previous = s1.top(); // Get the last screen
104- s1.pop(); // Remove it from stack
105- Move(previous); // Move to the previous screen
106- } else {
107- cout << "\nInvalid choice. Try again.\n";
108- navigator(cl); // Retry for valid input
109- }
110- }
111- };
112-
113- int main() {
114- WBHM w1;
115- w1.screen1(); // Start from the first screen
116- return 0;
117- }
Output Observed:

Page 17 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

3-Undo in Text Editor

Respective Code:
1- #include <iostream>
2- #include <stack>
3- #include <string>
4- using namespace std;
5-
6- int main() {
7- string s1 = " ";
8- int ch = 0;
9- string word;
10- stack<string> history; // Stack to store words for undo
11- stack<int> actions; // Stack to store actions for undo (1 = add, 2 = delete)
12-
13- do {
14- cout << "\n Your Note: " << s1;
15- cout << "\n\n 0-Exit";
16- cout << "\n 1-Add Word?";
17- cout << "\n 2-Delete Word?";
18- cout << "\n 3-Undo?";
19- cout << "\n\n Enter from 1-3: ";
20- cin >> ch;
21- actions.push(ch);
22- if (ch == 1) {
23- cout << "\n Enter a Word: ";
24- cin >> word;
25- s1 += word + " ";
26- history.push(word); // I Store word in history for potential undo
27- }
28- else if (ch == 2) {
29- if (!history.empty()) {
30- word = history.top(); // Get the last added word
31- size_t pos = s1.rfind(word); // Find the position of the word at the end of the
string
32-
33- if (pos !=string::npos) // Avoiding errors
34- s1.erase(pos, word.length() + 1); // Erase the word and the trailing space
35- else
36- cout << "\n Error: Word not found at the end.\n";
37- } else {
38- cout << "\n Error: No words to delete.\n";
39- }
40- }
41- else if (ch == 3) {
42- if (!actions.empty()) {
43- actions.pop(); // Remove the most recent action (Undo)

Page 18 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

44- if (!actions.empty()) {
45- int lastAction = actions.top();
46- actions.pop(); // Pop the second recent action to use
47-
48- if (lastAction == 1) { // Undo an addition
49- word = history.top();
50- size_t pos = s1.rfind(word);
51- if (pos !=string::npos) {
52- s1.erase(pos, word.length() + 1); // Erase the added word
53- history.pop();
54- }
55- } else if (lastAction == 2) {
56- word = history.top();
57- s1 += word + " "; // Re-add the word at the end
58- }
59- } else {
60- cout << "\n Error: No previous action to undo.\n";
61- }
62- } else {
63- cout << "\n Error: No actions to undo.\n";
64- }
65- }
66- } while (ch != 0);
67- return 0;
68- }
Output Observed:

Page 19 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 20 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

CONVERSION OF INFIX EXPRESSION

`LAB 2
DATED: 31/10/24

Lab 2-Conversion of Infix Expression to Prefix &

Postfix Expression using Stack.
Task 2.1,2 A Generic Code for above procedure
Respective Code:

1. #include <iostream>
2. #include <stack>
3. #include <cstring>
4. #include <cstdlib>
5. using namespace std;
6. class INFIX{
7. stack<char> s1;
8. public:
9. int prec(char c) {
10. if (c == '+' || c == '-')
11. return 1;
12. else if (c == '*' || c == '/')
13. return 2;
14. else if (c == '^')
15. return 3;
16. else
17. return 0;
18. }
19. bool balanced_p(char *c){
20. stack <char> checker;
21. for(int i=0;c[i]!=NULL;i++){
22. if(c[i]=='('||c[i]=='{'||c[i]=='}'||c[i]=='['||c[i]==']')
23. checker.push(c[i]);
24. else if(c[i]==')')
25. checker.pop();
26. }
27. if(checker.empty())
28. return true;
29. else
30. return false;
31. }
32. void InF_PoF(char *c) {
33. int j=0;

Page 21 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

34. char exp[100];

35. cout << "\n\n Processing\tStack\t\tExpression";
36. cout << "\n --------------------------------------";
37.
38. for (int i = 0; c[i] != '\0'; i++) {
39. cout << "\n " << c[i];
40.
41. if (c[i] == '+' || c[i] == '*' || c[i] == '-' || c[i] == '/' || c[i] == '^') {
42. while (!s1.empty() && prec(c[i]) <= prec(s1.top())) {
43. exp[j++] = s1.top();
44. s1.pop();
45. }
46. s1.push(c[i]);
47. }
48. else if (c[i] == '(') {
49. s1.push(c[i]);
50. }
51. else if (c[i] == ')') {
52. while (!s1.empty() && s1.top() != '(') {
53. exp[j++] = s1.top();
54. s1.pop();
55. }
56. s1.pop(); // Pop the '(' from the stack
57. }
58. else if (isalnum(c[i])) {
59. exp[j++] = c[i];
60. }
61.
62. // Display current stack and expression
63. cout << "\t\t";
64. stack<char> tempStack = s1;
65. stack<char> revStack;
66. while (!tempStack.empty()) {
67. revStack.push(tempStack.top());
68. tempStack.pop();
69. }
70. while (!revStack.empty()) {
71. cout << revStack.top();
72. revStack.pop();
73. }
74.
75. cout << "\t\t";
76. for (int k = 0; k < j; k++) {
77. cout << exp[k];

Page 22 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

78. }
79. }
80.
81. // Pop all remaining operators from the stack
82. while (!s1.empty()) {
83. exp[j++] = s1.top();
84. s1.pop();
85. }
86.
87. // Display the final postfix expression
88. exp[j] = '\0';
89. cout << "\n\nPostfix Expression: " << exp << endl;
90. }
91.
92. void InF_PrF(char *c) {
93. stack<char> reverse;
94. int len = strlen(c);
95. for (int i = 0; i < len; ++i)
96. reverse.push(c[i]);
97.
98. cout << "\n\n Step 1 - Reversed Expression: ";
99. int i = 0;
100. while (!reverse.empty()) {
101. if (reverse.top() == '(')
102. c[i] = ')';
103. else if (reverse.top() == ')')
104. c[i] = '(';
105. else
106. c[i] = reverse.top();
107.
108. cout << c[i];
109. reverse.pop();
110. i++;
111. }
112. c[i] = '\0'; // Null-terminate the reversed expression
113.
114. cout << "\n\n Step2 Performing Postfix Conversion: ";
115. char exp[100];
116. int j = 0;
117.
118. cout << "\n\n Processing\tStack\t\tExpression";
119. cout << "\n --------------------------------------";
120.
121. for (int i = 0; c[i] != '\0'; i++) {

Page 23 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

122. cout << "\n " << c[i];

123.
124. if (c[i] == '+' || c[i] == '*' || c[i] == '-' || c[i] == '/' || c[i] == '^') {
125. while (!s1.empty() && prec(c[i]) <= prec(s1.top())) {
126. exp[j++] = s1.top();
127. s1.pop();
128. }
129. s1.push(c[i]);
130. }
131. else if (c[i] == '(') {
132. s1.push(c[i]);
133. }
134. else if (c[i] == ')') {
135. while (!s1.empty() && s1.top() != '(') {
136. exp[j++] = s1.top();
137. s1.pop();
138. }
139. s1.pop(); // Pop the '(' from the stack
140. }
141. else if (isalnum(c[i])) {
142. exp[j++] = c[i];
143. }
144.
145. // Display current stack and expression
146. cout << "\t\t";
147. stack<char> tempStack = s1;
148. stack<char> revStack;
149. while (!tempStack.empty()) {
150. revStack.push(tempStack.top());
151. tempStack.pop();
152. }
153. while (!revStack.empty()) {
154. cout << revStack.top();
155. revStack.pop();
156. }
157.
158. cout << "\t\t";
159. for (int k = 0; k < j; k++) {
160. cout << exp[k];
161. }
162. }
163.
164. // Pop all remaining operators from the stack
165. while (!s1.empty()) {

Page 24 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

166. exp[j++] = s1.top();

167. s1.pop();
168. }
169.
170. exp[j] = '\0';
171. cout << "\n\n Step 3 - Reversing Postfix Expression for Prefix";
172. cout << "\n Final Prefix Expression: ";
173. for (int i = j - 1; i >= 0; i--) {
174. cout << exp[i];
175. }
176. cout << endl;
177. }
178.
179. };
180.
181.
182. int main() {
183. INFIX I;
184. int choice=0;
185. char infix[100];
186. do{
187. cout<<"\n WELCOME TO STACK FOR CONVERTING INFIX EXPRESSION
TO:";
188. cout<<"\n\n 0-Nothing (Exit)";
189. cout<<"\n 1-PostFix";
190. cout<<"\n 2-PreFix";
191. cout<<"\n RULES: 1-Balance your prenthesis \'()\'";
192. cout<<"\n 2-Don't Use any other braces other than prenthesis";
193. cout<<"\n\n Whats Your Choice? ";
194. cin>>choice;
195. if(choice==1){
196. system("cls");
197. cout<<"\n Enter Your Infix Expression: ";
198. cin>>infix;
199. if(I.balanced_p(infix))
200. I.InF_PoF(infix);
201. else
202. cout<<"\n Sorry! Your Expression is not Valid According to Rules
Provided";
203. }
204. else if(choice==2){
205. system("cls");
206. cout<<"\n Enter Your Infix Expression: ";
207. cin>>infix;

Page 25 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

208. if(I.balanced_p(infix))
209. I.InF_PrF(infix);
210. else
211. cout<<"\n Sorry! Your Expression is not Valid According to Rules
Provided";
212. }
213. else
214. cout<<"\n Wrong Choice";
215. }while(choice!=0);
216. return 0;
217. }
Output Observed:

Page 26 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 27 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 2.3- Adding Some additional Operators

Respective Code:
1. #include <iostream>
2. #include <stack>
3. #include <cstring>
4. using namespace std;
5.
6. class INFIX {
7. stack<string> s1; // Use string stack to handle multi-char operators
8.
9. public:
10. int prec(char c) {
11. if (c == '<' || c == '>')
12. return 1;
13. else if (c == '+' || c == '-')
14. return 2;
15. else if (c == '*' || c == '/' || c == '%')
16. return 3;
17. else if (c == '^' || c == '!')
18. return 4;
19. else
20. return 0;
21. }
22.
23. bool balanced_p(char *c) {
24. stack<char> checker;
25. for (int i = 0; c[i] != '\0'; i++) {
26. if (c[i] == '(')
27. checker.push(c[i]);
28. else if (c[i] == ')') {
29. if (checker.empty() || checker.top() != '(')
30. return false;
31. checker.pop();
32. }
33. }
34. return checker.empty();
35. }
36.
37. void InF_PoF(char *c) {
38. int j = 0;
39. string exp[100];
40. cout << "\n\n Processing\tStack\t\tExpression";
41. cout << "\n --------------------------------------";
42.
43. for (int i = 0; c[i] != '\0'; i++) {
44. string token(1, c[i]); // Convert character to string for easier handling
Page 28 of 125 Lab Manuals
 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

45.
46. // Handle multi-character operators like <=, >=
47. if (c[i] == '<' && c[i + 1] == '=') {
48. token = "<=";
49. i++;
50. } else if (c[i] == '>' && c[i + 1] == '=') {
51. token = ">=";
52. i++;
53. }
54.
55. cout << "\n " << token;
56.
57. if (token == "+" || token == "-" || token == "*" || token == "/" || token == "^" ||
token == "%" || token == "<" || token == ">" || token == "<=" || token == ">=") {
58. while (!s1.empty() && prec(s1.top()[0]) >= prec(token[0])) {
59. exp[j++] = s1.top();
60. s1.pop();
61. }
62. s1.push(token);
63. } else if (c[i] == '(') {
64. s1.push("(");
65. } else if (c[i] == ')') {
66. while (!s1.empty() && s1.top() != "(") {
67. exp[j++] = s1.top();
68. s1.pop();
69. }
70. s1.pop(); // Pop the '(' from the stack
71. } else if (isalnum(c[i])) {
72. exp[j++] = token;
73. }
74.
75. // Display current stack and expression
76. cout << "\t\t";
77. stack<string> tempStack = s1;
78. stack<string> revStack;
79. while (!tempStack.empty()) {
80. revStack.push(tempStack.top());
81. tempStack.pop();
82. }
83. while (!revStack.empty()) {
84. cout << revStack.top();
85. revStack.pop();
86. }
87.
88. cout << "\t\t";
89. for (int k = 0; k < j; k++) {

Page 29 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

90. cout << exp[k];

91. }
92. }
93.
94. // Pop all remaining operators from the stack
95. while (!s1.empty()) {
96. exp[j++] = s1.top();
97. s1.pop();
98. }
99.
100. // Display the final postfix expression
101. cout << "\n\nPostfix Expression: ";
102. for (int k = 0; k < j; k++) {
103. cout << exp[k];
104. }
105. cout << endl;
106. }
107.
108. void InF_PrF(char *c) {
109. stack<char> reverse;
110. int len = strlen(c);
111. for (int i = 0; i < len; ++i)
112. reverse.push(c[i]);
113.
114. cout << "\n\n Step 1 - Reversed Expression: ";
115. int i = 0;
116. while (!reverse.empty()) {
117. if (reverse.top() == '(')
118. c[i] = ')';
119. else if (reverse.top() == ')')
120. c[i] = '(';
121. else
122. c[i] = reverse.top();
123.
124. cout << c[i];
125. reverse.pop();
126. i++;
127. }
128. c[i] = '\0'; // Null-terminate the reversed expression
129.
130. cout << "\n\n Step 2 Performing Postfix Conversion: ";
131. char exp[100];
132. int j = 0;
133.
134. cout << "\n\n Processing\tStack\t\tExpression";
135. cout << "\n --------------------------------------";

Page 30 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

136.
137. for (int i = 0; c[i] != '\0'; i++) {
138. cout << "\n " << c[i];
139.
140. if (c[i] == '+' || c[i] == '*' || c[i] == '-' || c[i] == '/' || c[i] == '^') {
141. while (!s1.empty() && prec(c[i]) <= prec(s1.top()[0])) {
142. exp[j++] = s1.top()[0];
143. s1.pop();
144. }
145. s1.push(string(1, c[i]));
146. } else if (c[i] == '(') {
147. s1.push("(");
148. } else if (c[i] == ')') {
149. while (!s1.empty() && s1.top() != "(") {
150. exp[j++] = s1.top()[0];
151. s1.pop();
152. }
153. s1.pop(); // Pop the '(' from the stack
154. } else if (isalnum(c[i])) {
155. exp[j++] = c[i];
156. }
157.
158. // Display current stack and expression
159. cout << "\t\t";
160. stack<string> tempStack = s1;
161. stack<string> revStack;
162. while (!tempStack.empty()) {
163. revStack.push(tempStack.top());
164. tempStack.pop();
165. }
166. while (!revStack.empty()) {
167. cout << revStack.top();
168. revStack.pop();
169. }
170.
171. cout << "\t\t";
172. for (int k = 0; k < j; k++) {
173. cout << exp[k];
174. }
175. }
176.
177. // Pop all remaining operators from the stack
178. while (!s1.empty()) {
179. exp[j++] = s1.top()[0];
180. s1.pop();
181. }

Page 31 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

182.
183. cout << "\n\n Step 3 - Reversing Postfix Expression for Prefix";
184. cout << "\n Final Prefix Expression: ";
185. for (int i = j - 1; i >= 0; i--) {
186. cout << exp[i];
187. }
188. cout << endl;
189. }
190. };
191.
192. int main() {
193. INFIX I;
194. int choice = 0;
195. char infix[100];
196. do {
197. cout << "\n WELCOME TO STACK FOR CONVERTING INFIX
EXPRESSION TO:";
198. cout << "\n\n 0-Nothing (Exit)";
199. cout << "\n 1-PostFix";
200. cout << "\n 2-PreFix";
201. cout << "\n RULES: 1-Balance your parentheses '()'";
202. cout << "\n 2-Don't Use any other braces other than parentheses";
203. cout << "\n\n What's Your Choice? ";
204. cin >> choice;
205. if (choice == 1) {
206. system("cls");
207. cout << "\n Enter Your Infix Expression: ";
208. cin >> infix;
209. if (I.balanced_p(infix))
210. I.InF_PoF(infix);
211. else
212. cout << "\n Sorry! Your Expression is not Valid According to Rules
Provided";
213. } else if (choice == 2) {
214. system("cls");
215. cout << "\n Enter Your Infix Expression: ";
216. cin >> infix;
217. if (I.balanced_p(infix))
218. I.InF_PrF(infix);
219. else
220. cout << "\n Sorry! Your Expression is not Valid According to Rules
Provided";
221. } else if (choice != 0) {
222. cout << "\n Wrong Choice";
223. }
224. } while (choice != 0);

Page 32 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

225. return 0;
226. }
Output Observed:

Page 33 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 34 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Queue Data Structure

`LAB 3
-
DATED: 07/11/24

Lab 3-Queue Data Structure

Task 3.1-Simple Queue using Array
Respective Code:
1. #include<iostream>
2. using namespace std;
3. int arr[20];
4. class queue{
5. int fr,rear;
6. public:
7. int element;
8. queue(){
9. fr=rear=-1;
10. element=0;
11. }
12. void enque(int val){
13. if(rear==19){
14. cout<<"\n Queue is full";
15. }
16. else {
17. if(fr==-1&&rear==-1){
18. fr=rear=0;
19. arr[fr]=val;
20. }
21. else{
22. arr[++rear]=val;
23. }
24. ++element;
25. } cout<<"\n Value is successfully enqued";
26. }
27. void deque(){
28. if(fr==-1&&rear==-1){
29. cout<<"\n Queue is empty, no value to be dequed";
30. }
31. else{
32. arr[fr]=0;
33. for(int i=fr;i<=rear;i++)
34. arr[i]=arr[i+1];
35. rear--;
36. --element;
37. cout<<"\n Value dequed Successfully ";

Page 35 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

38. }
39. }
40. void display(){
41. system("cls");
42. cout<<"\n Elements of Queue are: ";
43. for(int i=fr;i<=rear;i++)
44. cout<<"\n "<<arr[i];
45. }
46.
47. };
48. int main(){
49. queue q;
50. int ch,val;
51. do{
52. cout<<"\n Chose any function to be performed on Queue: ";
53. cout<<"\n\t0-Exit ";
54. cout<<"\n\t1-Enque ";
55. cout<<"\n\t2-Deque ";
56. cout<<"\n\t3-Current Elements ";
57. cout<<"\n\t4-Display Queue ";
58. cout<<"\n Enter Here from 0-4: ";
59. cin>>ch;
60. if(ch==1){
61. cout<<"\n Enter a value: ";
62. cin>>val;
63. q.enque(val);
64. }
65. else if(ch==2)
66. q.deque();
67. else if(ch==3)
68. cout<<"\n There are "<<q.element<<" elements in Queue out of 20";
69. else if(ch==4)
70. q.display();
71. else
72. cout<<"\n Invalid Choice";
73. }while(ch!=0);
74.
75. return 0;
76. }
Output Observed:

Page 36 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 3.2-Simple Queue using Array & Proper Memory

Utilization
Respective Code:
77. #include<iostream>
78. using namespace std;
79. int arr[20];

Page 37 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

80. class queue{

81. int fr,rear;
82. public:
83. int element;
84. queue(){
85. fr=rear=-1;
86. element=0;
87. }
88. void enque(int val){
89. if(rear==19){
90. cout<<"\n Queue is full";
91. }
92. else {
93. if(fr==-1&&rear==-1){
94. fr=rear=0;
95. arr[fr]=val;
96. }
97. else{
98. arr[++rear]=val;
99. }
100. ++element;
101. } cout<<"\n Value is successfully enqued";
102. }
103. void deque(){
104. if(fr==-1&&rear==-1){
105. cout<<"\n Queue is empty, no value to be dequed";
106. }
107. else{
108. arr[fr]=0;
109. for(int i=fr;i<=rear;i++)
110. arr[i]=arr[i+1];
111. rear--;
112. --element;
113. cout<<"\n Value dequed Successfully ";
114. }
115. }
116. void display(){
117. system("cls");
118. cout<<"\n Elements of Queue are: ";
119. for(int i=fr;i<=rear;i++)
120. cout<<"\n "<<arr[i];
121. }
122.
123. };
124. int main(){
125. queue q;

Page 38 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

126. int ch,val;

127. do{
128. cout<<"\n Chose any function to be performed on Queue: ";
129. cout<<"\n\t0-Exit ";
130. cout<<"\n\t1-Enque ";
131. cout<<"\n\t2-Deque ";
132. cout<<"\n\t3-Current Elements ";
133. cout<<"\n\t4-Display Queue ";
134. cout<<"\n Enter Here from 0-4: ";
135. cin>>ch;
136. if(ch==1){
137. cout<<"\n Enter a value: ";
138. cin>>val;
139. q.enque(val);
140. }
141. else if(ch==2)
142. q.deque();
143. else if(ch==3)
144. cout<<"\n There are "<<q.element<<" elements in Queue out of 20";
145. else if(ch==4)
146. q.display();
147. else
148. cout<<"\n Invalid Choice";
149. }while(ch!=0);
150.
151. return 0;
152. }
Output Observed:

Page 39 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 3.3-Circular Queue using Array

Respective Code:
1. #include<iostream>
2. using namespace std;
3. int arr[20];
4. class queue{

Page 40 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

5. int fr,rear;
6. public:
7. int element;
8. queue(){
9. fr=rear=-1;
10. element=0;
11. }
12. void enque(int val){
13. if(element==20){
14. cout<<"\n Queue is full";
15. }
16. else {
17. if(fr==-1&&rear==-1){
18. fr=rear=0;
19. arr[fr]=val;
20. }
21. else{
22. rear+=1%20;
23. arr[rear]=val;
24. }
25. ++element;
26. } cout<<"\n Value is successfully enqued";
27. }
28. void deque(){
29. if(element==0){
30. cout<<"\n Queue is empty, no value to be dequed";
31. }
32. else{
33. fr+=1%20;
34. --element;
35. cout<<"\n Value dequed Successfully ";
36. }
37. }
38. void display(){
39. system("cls");
40. cout<<"\n Elements of Queue are: ";
41. for(int i=fr;i<=rear;i++)
42. cout<<"\n "<<arr[i];
43. }
44.
45. };
46. int main(){
47. queue q;
48. int ch,val;
49. do{
50. cout<<"\n Chose any function to be performed on Queue: ";

Page 41 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

51. cout<<"\n\t0-Exit ";

52. cout<<"\n\t1-Enque ";
53. cout<<"\n\t2-Deque ";
54. cout<<"\n\t3-Current Elements ";
55. cout<<"\n\t4-Display Queue ";
56. cout<<"\n Enter Here from 0-4: ";
57. cin>>ch;
58. if(ch==1){
59. cout<<"\n Enter a value: ";
60. cin>>val;
61. q.enque(val);
62. }
63. else if(ch==2)
64. q.deque();
65. else if(ch==3)
66. cout<<"\n There are "<<q.element<<" elements in Queue out of 20";
67. else if(ch==4)
68. q.display();
69. else
70. cout<<"\n Invalid Choice";
71. }while(ch!=0);
72.
73. return 0;
74. }
Output Observed:

Page 42 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 3.4-Simple Queue using Array that automatically sorts its

element.
Respective Code:
1. #include<iostream>
2. using namespace std;
3. const int size=5;

Page 43 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

4. int arr[size];
5. class queue{
6. int fr,rear;
7. public:
8. int element;
9. queue(){
10. fr=rear=-1;
11. element=0;
12. }
13. void enque(int val){
14. if(rear==(size-1)){
15. cout<<"\n Queue is full";
16. }
17. else {
18. if(fr==-1&&rear==-1){
19. fr=rear=0;
20. arr[fr]=val;
21. }
22. else{
23. arr[++rear]=val;
24. }
25. ++element;
26. cout<<"\n Value is successfully enqued";
27. // Automatically sorts queue elements
28. if(element>=2){
29. for(int i=fr;i<=rear;i++){
30. for(int j=fr;j<=rear;j++){
31. if(arr[i]<arr[j])
32. swap(arr[i],arr[j]);
33. }
34.
35. }
36. }
37.
38. }
39.
40. }
41. void deque(){
42. if(fr==-1&&rear==-1){
43. cout<<"\n Queue is empty, no value to be dequed";
44. }
45. else{
46. arr[fr]=0;
47. for(int i=fr;i<=rear;i++)
48. arr[i]=arr[i+1];
49. rear--;

Page 44 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

50. --element;
51. cout<<"\n Value dequed Successfully ";
52. }
53. }
54. void display(){
55. system("cls");
56. cout<<"\n Elements of Queue are: ";
57. for(int i=fr;i<=rear;i++)
58. cout<<"\n "<<arr[i];
59. }
60.
61. };
62. int main(){
63. queue q;
64. int ch,val;
65. do{
66. cout<<"\n Chose any function to be performed on Queue: ";
67. cout<<"\n\t0-Exit ";
68. cout<<"\n\t1-Enque ";
69. cout<<"\n\t2-Deque ";
70. cout<<"\n\t3-Current Elements ";
71. cout<<"\n\t4-Display Queue ";
72. cout<<"\n Enter Here from 0-4: ";
73. cin>>ch;
74. if(ch==1){
75. cout<<"\n Enter a value: ";
76. cin>>val;
77. q.enque(val);
78. }
79. else if(ch==2)
80. q.deque();
81. else if(ch==3)
82. cout<<"\n There are "<<q.element<<" elements in Queue out of 20";
83. else if(ch==4)
84. q.display();
85. else
86. cout<<"\n Invalid Choice";
87. }while(ch!=0);
88.
89. return 0;
90. }
Output Observed:

Page 45 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 3.5-Applications of Circular Queue

1-Traffic Light Signals
Respective Code:
1. #include <iostream>
2. #include <thread>
3. #include <chrono>
4.
5. using namespace std;
6. const int size = 3; // For three lights: red, yellow, and green
7.
8. class Traffic_L { // Circular queue class for traffic light system
9. string Lights[size];
10. int front, rear, element;
11.
12. public:
13. Traffic_L() {
14. front = rear = -1;
15. element = 0;
16. }
17.
18. void enque(const string &s1) {
19. if (element == size) {
20. cout << "\nQueue is full";
21. } else {
22. if (front == -1 && rear == -1) {
23. front = rear = 0;
24. } else {
25. rear = (rear + 1) % size;
26. }
27. Lights[rear] = s1;
28. ++element;
29. }

Page 46 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

30. }
31.
32. string deque() {
33. if (element == 0) {
34. cout << "\nQueue is empty, no value to be dequeued";
35. return "";
36. } else {
37. int i = front;
38. front = (front + 1) % size;
39. --element;
40. return Lights[i];
41. }
42. }
43.
44. void setColor(const string &color) {
45. if (color == "Red") {
46. cout << "\033[41m"; // Red background
47. } else if (color == "Yellow") {
48. cout << "\033[43m"; // Yellow background
49. } else if (color == "Green") {
50. cout << "\033[42m"; // Green background
51. }
52. cout << "\033[30m"; // Set text color to black for visibility
53. }
54.
55. void resetColor() {
56. cout << "\033[0m"; // Reset to default color
57. }
58.
59. void TR_CTRL() { // Traffic light setup control
60. int time = 3; // 3 seconds
61. enque("Red");
62. enque("Yellow");
63. enque("Green");
64.
65. while (true) {
66. system("cls");
67. cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\t\t\t\t\t\t\t\tTRAFFIC LIGHT SIGNALS";
68. string L = deque();
69.
70. setColor(L); // I Set the background color based on the light
71. cout << "\n\n\n\t\t\t\t\t\t\t\tCURRENT LIGHT: " << L << endl;
72. this_thread::sleep_for(chrono::seconds(time));
73. resetColor(); // Reset color after each light display
74. enque(L);
75. }

Page 47 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

76. }
77. };
78.
79. int main() {
80. Traffic_L T;
81. T.TR_CTRL();
82.
83. return 0;
84. }
Output Observed:

2-Round Table Video Conferencing

Respective Code:
1. #include <iostream>
2. #include <string>
3. #include <iomanip> // For formatting
4. using namespace std;
5.
6. const int SIZE = 4;
7.
8. class RDVC {
9. string calls[SIZE];
10. int front, rear, NoOfCalls;
11.
12. public:
13. RDVC() {
14. front = rear = -1;
15. NoOfCalls = 0;
16. }
17.
18. // Add a new person to the conference
19. void enqueue(string newCall) {
20. if (NoOfCalls == SIZE) {
21. cout << "\nRound Table is Full! Wait until someone leaves.\n";
22. } else {
23. if (front == -1) front = rear = 0;
24. else rear = (rear + 1) % SIZE;
25.

Page 48 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

26. calls[rear] = newCall;

27. ++NoOfCalls;
28. cout << "\n" << newCall << " has joined the conference.\n";
29. }
30. }
31.
32. // Remove the person who has been on the call the longest
33. void dequeue() {
34. if (NoOfCalls == 0) {
35. cout << "\nNo one to remove!\n";
36. } else {
37. cout << "\n" << calls[front] << " has left the conference.\n";
38. calls[front] = ""; // Clear the name
39. front = (front + 1) % SIZE;
40. --NoOfCalls;
41. }
42. }
43.
44. // Display the call slots in a circular layout with colors
45. void draw() {
46. cout << "\n\t\t\t ROUND TABLE VIDEO CONFERENCE\n";
47. cout << "\nMeeting Status: " << (NoOfCalls > 0 ? "Active" : "No Call Active
Yet") << "\n";
48.
49. for (int i = 0; i < SIZE; ++i) {
50. // Positioning each slot
51. if (i == 0) cout << "\n\t\t\t\t ";
52. else if (i == 1) cout << "\n\n\t\t\t ";
53. else if (i == 3) cout << "\n\n\t\t\t\t ";
54.
55. // Determine color based on whether the slot is empty or filled
56. cout << (calls[i].empty() ? "\033[44;37m" : "\033[42;37m")
57. << setw(15) << (calls[i].empty() ? "Empty Slot" : calls[i]) << "\033[0m";
58.
59. // Space between slots on the middle line
60. if (i == 1) cout << " ";
61. }
62. cout << "\n"; // End of circular layout
63. }
64. // Simulate adding/removing participants and displaying the conference
65. void simulate() {
66. int choice = 0;
67. do {
68. system("cls"); // Clear screen
69. draw();
70.

Page 49 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

71. cout << "\nOptions:";

72. cout << "\n\t\033[32m1 - Add Person\033[0m"; // Green color for Add Person
73. if (NoOfCalls != 0) cout << "\n\t\033[31m2 - " << calls[front] << " is done.
Remove them?\033[0m"; // Red color for Remove Person
74. cout << "\n\t\033[34m0 - Exit\033[0m"; // Blue color for Exit
75. cout << "\nChoice: ";
76. cin >> choice;
77.
78. switch (choice) {
79. case 1: {
80. if (NoOfCalls < SIZE) {
81. string name;
82. cout << "Enter the name of the person joining: ";
83. cin >> ws; // Clear any leading whitespace
84. getline(cin, name);
85. enqueue(name);
86. }
87. break;
88. }
89. case 2:
90. if (NoOfCalls != 0) dequeue();
91. else cout<<"\n In Valid Choice";
92. break;
93. case 0:
94. cout << "\nExiting conference.\n";
95. break;
96. default:
97. cout << "\nInvalid choice. Try again.\n";
98. }
99.
100. } while (choice != 0);
101. }
102. };
103.
104. int main() {
105. RDVC r1;
106. r1.simulate();
107. return 0;
108. }
Output Observed:

Page 50 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

3-Managing Buffers
Respective Code:
1. #include <iostream>
2. #include <iomanip>
3. using namespace std;
4.
5. // ASCII color codes for different buffer statuses
6. void setColor(int color) {
7. cout << "\033[1;" << color << "m";
8. }
9.
10. void resetColor() {
11. cout << "\033[0m";
12. }
13.
14. // CircularQueue class with fixed size and visual display
15. class CircularQueue {
16. private:
17. int buffer[9]; // Fixed-size buffer of 9 elements
18. int front; // Points to the front of the queue
19. int rear; // Points to the rear of the queue
20. int count; // Current number of elements in the queue
21.
22. public:
23. CircularQueue() : front(-1), rear(-1), count(0) {
24. // Initialize buffer with dummy values (e.g., -1 for empty slots)
25. for (int i = 0; i < 9; ++i) {
26. buffer[i] = -1;
27. }
28. }
29.
30. // Function to check if the buffer is empty
31. bool isEmpty() const {
32. return count == 0;
33. }
34.
35. // Function to check if the buffer is full
36. bool isFull() const {
37. return count == 9;
Page 51 of 125 Lab Manuals
 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

38. }
39.
40. // Function to add data to the buffer
41. void addData(int data) {
42. if (isFull()) {
43. cout << "Buffer is Full. Cannot add more data.\n";
44. } else {
45. rear = (rear + 1) % 9;
46. buffer[rear] = data;
47. count++;
48.
49. if (front == -1) {
50. front = 0;
51. }
52. displayBuffer();
53. }
54. }
55.
56. // Function to remove data from the buffer
57. void removeData() {
58. if (isEmpty()) {
59. cout << "Buffer is Empty. Cannot remove data.\n";
60. } else {
61. buffer[front] = -1; // Set removed spot to empty (-1)
62. front = (front + 1) % 9;
63. count--;
64.
65. if (isEmpty()) {
66. front = rear = -1;
67. }
68. displayBuffer();
69. }
70. }
71.
72. // Function to display buffer as a 3x3 grid with background colors
73. void displayBuffer() const {
74. cout << "\n\t\t\tBuffer Status:\n";
75.
76. for (int row = 0; row < 3; ++row) {
77. cout << "\t\t\t"; // Center-align each row
78. for (int col = 0; col < 3; ++col) {
79. int index = row * 3 + col;
80. if (buffer[index] == -1) {
81. setColor(44); // Blue background for empty slots
82. cout << "[ ] ";
83. } else {

Page 52 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

84. setColor(42); // Green background for filled slots

85. cout << "[" << setw(3) << buffer[index] << "] ";
86. }
87. resetColor();
88. }
89. cout << endl;
90. }
91. }
92. };
93.
94. int main() {
95. CircularQueue queue;
96.
97. while (true) {
98. cout << "\n\tChoose an operation:\n";
99. cout << "\t\t1. Add data to buffer\n";
100. cout << "\t\t2. Remove data from buffer\n";
101. cout << "\t\t3. Exit\n";
102. cout << "\n Enter from 1-3 Here: ";
103. int choice;
104. cin >> choice;
105. system("cls");
106. if (choice == 1) {
107. int data;
108. cout << "Enter data to add to buffer: ";
109. cin >> data;
110. queue.addData(data);
111. } else if (choice == 2) {
112. queue.removeData();
113. } else if (choice == 3) {
114. break;
115. } else {
116. cout << "Invalid choice. Try again.\n";
117. }
118. }
119.
120. return 0;
121. }
Output Observed:

Page 53 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Linked-list Data Structure

`LAB 4
-
DATED: 14/11/24

Lab 4- Linked-list DS (Single & Circular)

Task 4.1 Implementations of 10 functionalities (given in QP) in
Single & Circular Link lists.
Task 4.1.1 -Single Linked-list
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. class Node {
5. public:
6. int data;
7. Node* next;
8. Node(int a) : data(a), next(nullptr) {}
9. };
10.
11. class L_LIST {
12. public:
13. Node* head, * tail;
14. int size;
15.
16. L_LIST() : head(nullptr), tail(nullptr), size(0) {}
17.
18. // I use this to add a node with a specific value to the end of the list
19. void add(int val) {
20. Node* newnode = new Node(val);
21. if (head == nullptr) {
22. head = tail = newnode;
23. } else {
24. tail->next = newnode;
25. tail = newnode;
26. }
27. size++;
28. }
29.
30. // I use this to remove the first node that contains a specific value
31. void remove(int val) {
32. if (head == nullptr) {
33. cout << "List is empty.\n";
34. return;

Page 54 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

35. }
36.
37. Node* temp = head;
38. Node* prev = nullptr;
39.
40. while (temp != nullptr && temp->data != val) {
41. prev = temp;
42. temp = temp->next;
43. }
44.
45. if (temp == nullptr) {
46. cout << "Value not found in the list.\n";
47. return;
48. }
49.
50. if (temp == head) {
51. head = head->next;
52. } else {
53. prev->next = temp->next;
54. }
55.
56. if (temp == tail) {
57. tail = prev;
58. }
59.
60. delete temp;
61. size--;
62. cout << "Value " << val << " removed from the list.\n";
63. }
64.
65. // I use this to display all elements in the list
66. void display() {
67. cout << "Linked list Elements: ";
68. Node* check = head;
69. while (check != nullptr) {
70. cout << check->data << " -> ";
71. check = check->next;
72. }
73. cout << "NULL\n";
74. }
75.
76. // I use this to find the index of the first occurrence of a specific value
77. int searchByValue(int val) {
78. Node* temp = head;
79. int index = 0;
80.

Page 55 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

81. while (temp != nullptr) {

82. if (temp->data == val) {
83. return index;
84. }
85. temp = temp->next;
86. index++;
87. }
88.
89. return -1; // Value not found
90. }
91.
92. // I use this to retrieve the value at a specific index
93. int searchByIndex(int index) {
94. if (index < 0 || index >= size) {
95. cout << "Index out of bounds.\n";
96. return -1;
97. }
98.
99. Node* temp = head;
100. for (int i = 0; i < index; i++) {
101. temp = temp->next;
102. }
103.
104. return temp->data;
105. }
106.
107. // I use this to get the next node from the current node
108. Node* nextNode(Node* current) {
109. if (current == nullptr) {
110. cout << "Current node is null.\n";
111. return nullptr;
112. }
113. return current->next;
114. }
115.
116. // I use this to copy the entire linked list into a new one
117. L_LIST copyList() {
118. L_LIST newList;
119. Node* temp = head;
120.
121. while (temp != nullptr) {
122. newList.add(temp->data);
123. temp = temp->next;
124. }
125.
126. return newList;

Page 56 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

127. }
128.
129. // I use this to find and print duplicates in the list
130. void findDuplicateNodes() {
131. Node* outer = head;
132. int indexOuter = 0;
133. bool found = false;
134.
135. while (outer != nullptr) {
136. Node* inner = outer->next;
137. int indexInner = indexOuter + 1;
138.
139. while (inner != nullptr) {
140. if (outer->data == inner->data) {
141. cout << "Duplicate value " << outer->data << " found at index " <<
indexInner << ".\n";
142. found = true;
143. }
144. inner = inner->next;
145. indexInner++;
146. }
147.
148. outer = outer->next;
149. indexOuter++;
150. }
151.
152. if (!found) {
153. cout << "No duplicate values found.\n";
154. }
155. }
156.
157. // I use this to insert a node at a specific index
158. void updateList(int index, int val) {
159. if (index < 0 || index > size) {
160. cout << "Index out of bounds.\n";
161. return;
162. }
163.
164. Node* newnode = new Node(val);
165.
166. if (index == 0) {
167. newnode->next = head;
168. head = newnode;
169. if (tail == nullptr) {
170. tail = newnode;
171. }

Page 57 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

172. } else {
173. Node* temp = head;
174. for (int i = 0; i < index - 1; i++) {
175. temp = temp->next;
176. }
177.
178. newnode->next = temp->next;
179. temp->next = newnode;
180.
181. if (newnode->next == nullptr) {
182. tail = newnode;
183. }
184. }
185.
186. size++;
187. }
188. };
189.
190. int main() {
191. L_LIST l1;
192. l1.add(1); // I use this to add 1 to the list
193. l1.add(4); // I use this to add 4 to the list
194. l1.add(3); // I use this to add 3 to the list
195.
196. l1.display(); // I use this to display the list
197. l1.remove(4); // I use this to remove 4 from the list
198. l1.display(); // I use this to display the list after removing
199.
200. cout << "Search value 3 found at index: " << l1.searchByValue(3) << "\n"; //
I use this to search value 3
201. cout << "Value at index 1: " << l1.searchByIndex(1) << "\n"; // I use this to
get value at index 1
202.
203. L_LIST l2 = l1.copyList(); // I use this to create a copy of the list
204. l2.display(); // I use this to display the copied list
205.
206. l1.add(5); // I use this to add 5 to the list
207. l1.add(1); // I use this to add 1 to the list (duplicate)
208. l1.findDuplicateNodes(); // I use this to find duplicates
209.
210. l1.updateList(1, 10); // I use this to insert 10 at index 1
211. l1.display(); // I use this to display the updated list
212.
213. return 0;
214. }
Output Observed:

Page 58 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 4.1.2 Circular Linked list

Respective Code:
Page 59 of 125 Lab Manuals
 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

1. #include <iostream>
2. using namespace std;
3.
4. class Node {
5. public:
6. int data;
7. Node* next;
8. Node(int a) : data(a), next(nullptr) {}
9. };
10.
11. class CIRCULAR_LIST {
12. public:
13. Node* head, * tail;
14. int size;
15.
16. CIRCULAR_LIST() : head(nullptr), tail(nullptr), size(0) {}
17.
18. // I use this to add a node with a specific value to the end of the circular list
19. void add(int val) {
20. Node* newnode = new Node(val);
21. if (head == nullptr) {
22. head = tail = newnode;
23. tail->next = head; // Circular link
24. } else {
25. tail->next = newnode;
26. tail = newnode;
27. tail->next = head; // Maintain circular link
28. }
29. size++;
30. }
31.
32. // I use this to remove the first node that contains a specific value
33. void remove(int val) {
34. if (head == nullptr) {
35. cout << "List is empty.\n";
36. return;
37. }
38.
39. Node* temp = head;
40. Node* prev = tail;
41. bool found = false;
42.
43. do {
44. if (temp->data == val) {
45. found = true;
46. break;

Page 60 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

47. }
48. prev = temp;
49. temp = temp->next;
50. } while (temp != head);
51.
52. if (!found) {
53. cout << "Value not found in the list.\n";
54. return;
55. }
56.
57. if (temp == head) {
58. head = head->next;
59. tail->next = head;
60. } else {
61. prev->next = temp->next;
62. }
63.
64. if (temp == tail) {
65. tail = prev;
66. }
67.
68. delete temp;
69. size--;
70. if (size == 0) {
71. head = tail = nullptr; // Reset list
72. }
73. cout << "Value " << val << " removed from the list.\n";
74. }
75.
76. // I use this to display all elements in the circular list
77. void display() {
78. if (head == nullptr) {
79. cout << "List is empty.\n";
80. return;
81. }
82. cout << "Circular Linked List Elements: ";
83. Node* temp = head;
84. do {
85. cout << temp->data << " -> ";
86. temp = temp->next;
87. } while (temp != head);
88. cout << "(back to head)\n";
89. }
90.
91. // I use this to find the index of the first occurrence of a specific value
92. int searchByValue(int val) {

Page 61 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

93. Node* temp = head;

94. int index = 0;
95.
96. do {
97. if (temp->data == val) {
98. return index;
99. }
100. temp = temp->next;
101. index++;
102. } while (temp != head);
103.
104. return -1; // Value not found
105. }
106.
107. // I use this to retrieve the value at a specific index
108. int searchByIndex(int index) {
109. if (index < 0 || index >= size) {
110. cout << "Index out of bounds.\n";
111. return -1;
112. }
113.
114. Node* temp = head;
115. for (int i = 0; i < index; i++) {
116. temp = temp->next;
117. }
118.
119. return temp->data;
120. }
121.
122. // I use this to get the next node from the current node
123. Node* nextNode(Node* current) {
124. if (current == nullptr) {
125. cout << "Current node is null.\n";
126. return nullptr;
127. }
128. return current->next;
129. }
130.
131. // I use this to copy the entire circular linked list into a new one
132. CIRCULAR_LIST copyList() {
133. CIRCULAR_LIST newList;
134. Node* temp = head;
135.
136. do {
137. newList.add(temp->data);
138. temp = temp->next;

Page 62 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

139. } while (temp != head);

140.
141. return newList;
142. }
143.
144. // I use this to find and print duplicates in the circular list
145. void findDuplicateNodes() {
146. if (head == nullptr) {
147. cout << "List is empty.\n";
148. return;
149. }
150.
151. Node* outer = head;
152. int indexOuter = 0;
153. bool found = false;
154.
155. do {
156. Node* inner = outer->next;
157. int indexInner = indexOuter + 1;
158.
159. while (inner != head) {
160. if (outer->data == inner->data) {
161. cout << "Duplicate value " << outer->data << " found at index " <<
indexInner << ".\n";
162. found = true;
163. }
164. inner = inner->next;
165. indexInner++;
166. }
167.
168. outer = outer->next;
169. indexOuter++;
170. } while (outer != head);
171.
172. if (!found) {
173. cout << "No duplicate values found.\n";
174. }
175. }
176.
177. // I use this to insert a node at a specific index in the circular list
178. void updateList(int index, int val) {
179. if (index < 0 || index > size) {
180. cout << "Index out of bounds.\n";
181. return;
182. }
183.

Page 63 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

184. Node* newnode = new Node(val);

185.
186. if (index == 0) {
187. if (head == nullptr) {
188. head = tail = newnode;
189. tail->next = head; // Circular link
190. } else {
191. newnode->next = head;
192. head = newnode;
193. tail->next = head; // Maintain circular link
194. }
195. } else {
196. Node* temp = head;
197. for (int i = 0; i < index - 1; i++) {
198. temp = temp->next;
199. }
200.
201. newnode->next = temp->next;
202. temp->next = newnode;
203.
204. if (temp == tail) {
205. tail = newnode;
206. }
207. }
208.
209. size++;
210. }
211. };
212.
213. int main() {
214. CIRCULAR_LIST l1;
215. l1.add(1); // I use this to add 1 to the list
216. l1.add(4); // I use this to add 4 to the list
217. l1.add(3); // I use this to add 3 to the list
218.
219. l1.display(); // I use this to display the list
220. l1.remove(4); // I use this to remove 4 from the list
221. l1.display(); // I use this to display the list after removing
222.
223. cout << "Search value 3 found at index: " << l1.searchByValue(3) << "\n"; //
I use this to search value 3
224. cout << "Value at index 1: " << l1.searchByIndex(1) << "\n"; // I use this to
get value at index 1
225.
226. CIRCULAR_LIST l2 = l1.copyList(); // I use this to create a copy of the list
227. l2.display(); // I use this to display the copied list

Page 64 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

228.
229. l1.add(5); // I use this to add 5 to the list
230. l1.add(1); // I use this to add 1 to the list (duplicate)
231. l1.findDuplicateNodes(); // I use this to find duplicates
232.
233. l1.updateList(1, 10); // I use this to insert 10 at index 1
234. l1.display(); // I use this to display the updated list
235.
236. return 0;
237. }
Output Observed:

Page 65 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 66 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 4.2- Real-Life Applications of Single/y Linked-list

Polynomial Arithmetic
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. // Node for singly linked list
5. class Node {
6. public:
7. int coefficient; // Coefficient of the term
8. int exponent; // Exponent of the term
9. Node* next; // Pointer to the next node
10.
11. Node(int coeff, int exp) : coefficient(coeff), exponent(exp), next(nullptr) {}
12. };
13.
14. // Singly linked list class for polynomial representation
15. class Polynomial {
16. private:
17. Node* head;
18.
19. public:
20. Polynomial() {
21. head=nullptr;
22. }
23.
24. // Add a new term to the polynomial
25. void addTerm(int coefficient, int exponent) {
26. Node* newNode = new Node(coefficient, exponent);
27.
28. // If the list is empty or the new term has a higher exponent
29. if (!head || exponent > head->exponent) {
30. newNode->next = head;
31. head = newNode;
32. } else {
33. Node* current = head;
34. Node* previous = nullptr;
35.
36. // Traverse to the correct position
37. while (current && current->exponent >= exponent) {
38. previous = current;
39. current = current->next;
40. }
41.
42. // Insert the new term

Page 67 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

43. if (previous->exponent == exponent) {

44. // Combine terms with the same exponent
45. previous->coefficient += coefficient;
46. } else {
47. newNode->next = current;
48. previous->next = newNode;
49. }
50. }
51. }
52.
53. // Display the polynomial
54. void display() {
55. if (!head) {
56. cout << "\n Nothing entered properly" << endl;
57. return;
58. }
59.
60. Node* current = head;
61. while (current) {
62. cout << current->coefficient << "x^" << current->exponent;
63. if (current->next) cout << " + ";
64. current = current->next;
65. }
66. cout << endl;
67. }
68.
69. // Add two polynomials
70. static Polynomial addPolynomials(Polynomial& p1, Polynomial& p2) {
71. Polynomial result;
72. Node* t1 = p1.head;
73. Node* t2 = p2.head;
74.
75. // Traverse both polynomials
76. while (t1 && t2) {
77. if (t1->exponent > t2->exponent) {
78. result.addTerm(t1->coefficient, t1->exponent);
79. t1 = t1->next;
80. } else if (t1->exponent < t2->exponent) {
81. result.addTerm(t2->coefficient, t2->exponent);
82. t2 = t2->next;
83. } else {
84. // Combine terms with the same exponent
85. result.addTerm(t1->coefficient + t2->coefficient, t1->exponent);
86. t1 = t1->next;
87. t2 = t2->next;
88. }

Page 68 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

89. }
90.
91. // Add remaining terms
92. while (t1) {
93. result.addTerm(t1->coefficient, t1->exponent);
94. t1 = t1->next;
95. }
96.
97. while (t2) {
98. result.addTerm(t2->coefficient, t2->exponent);
99. t2 = t2->next;
100. }
101.
102. return result;
103. }
104. };
105.
106. int main() {
107. Polynomial poly1, poly2, result;
108. cout<<"\n\t WELCOME TO POLY-SUM.Singly@linkedlist.com\
Shahzil_Develper ";
109. int terms, coefficient, exponent;
110.
111. // Input for first polynomial
112. cout << "\n Enter the number of terms in the first polynomial: ";
113. cin >> terms;
114. for (int i = 0; i < terms; ++i) {
115. cout << "\n Enter coefficient and exponent for term " << i + 1 << ": ";
116. cin >> coefficient >> exponent;
117. poly1.addTerm(coefficient, exponent);
118. }
119.
120. // Input for second polynomial
121. cout << " Enter the number of terms in the second polynomial: ";
122. cin >> terms;
123. for (int i = 0; i < terms; ++i) {
124. cout << "Enter coefficient and exponent for term " << i + 1 << ": ";
125. cin >> coefficient >> exponent;
126. poly2.addTerm(coefficient, exponent);
127. }
128.
129. // Display the polynomials
130. cout << "\n First Polynomial: ";
131. poly1.display();
132.
133. cout << "\n Second Polynomial: ";

Page 69 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

134. poly2.display();
135.
136. // Add the two polynomials
137. result = Polynomial::addPolynomials(poly1, poly2);
138.
139. // Display the result
140. cout << "\n Resultant Polynomial (Sum): ";
141. result.display();
142.
143. return 0;
144. }
Output Observed:

Shahzil CMD for Managing Directories

Respective Code:
1. #include<iostream>
2. #include<iomanip>
3. #include<cstdlib>
4. using namespace std;
5.
6. class Folder {
7. public:
8. Folder* next, *sub;
9. string name;
10.
11. Folder(string n) {
12. name = n;
13. next = sub = NULL;
14. }
15. };

Page 70 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

16.
17. class Folder_System {
18. public:
19. Folder* start, *end;
20.
21. Folder_System() {
22. start = end = NULL;
23. }
24.
25. // Create folder function with duplication check for both folders and subfolders
26. void create(string n) {
27. // Check for duplicate folder names
28. Folder* check = start;
29. while (check != NULL) {
30. if (check->name == n || (check->sub != NULL && check->sub->name == n)) {
31. cout << "\n. Folder with the name '" << n << "' already exists!";
32. return;
33. }
34. check = check->next;
35. }
36.
37. // Create and add the new folder
38. Folder* newfolder = new Folder(n);
39. if (start == NULL) {
40. start = newfolder;
41. end = start;
42. } else {
43. end->next = newfolder; // Fixing the linkage
44. end = newfolder;
45. }
46.
47. cout << "\n. Folder '" << n << "' added successfully!";
48. }
49.
50. // Delete folder or subfolder function
51. void Delete(string n) {
52. Folder* check = start;
53. Folder* prev = NULL;
54.
55. // Case 1: Folder is at the start
56. if (check != NULL && check->name == n) {
57. start = check->next;
58. delete check;
59. cout << "\n. Folder '" << n << "' deleted successfully!";
60. return;
61. }

Page 71 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

62.
63. // Traverse the list to find the folder or subfolder
64. while (check != NULL) {
65. // If main folder matches
66. if (check->name == n) {
67. if (prev != NULL) prev->next = check->next;
68. else start = check->next; // Update start if needed
69. delete check;
70. cout << "\n. Folder '" << n << "' deleted successfully!";
71. return;
72. }
73.
74. // If subfolder matches
75. if (check->sub != NULL && check->sub->name == n) {
76. delete check->sub;
77. check->sub = NULL;
78. cout << "\n. Subfolder '" << n << "' deleted successfully!";
79. return;
80. }
81.
82. prev = check;
83. check = check->next;
84. }
85.
86. // If folder or subfolder not found
87. cout << "\n. No folder or subfolder found with the name '" << n << "'!";
88. }
89.
90. // Add subfolder function
91. void add_sub(string f, string n) {
92. Folder* check = start;
93.
94. // Traverse the list to find the main folder
95. while (check != NULL && check->name != f) {
96. check = check->next;
97. }
98.
99. if (check == NULL) {
100. cout << "\n. Main folder not found.";
101. return;
102. }
103.
104. // Check for duplicate subfolder name
105. if (check->sub != NULL) {
106. cout << "\n Shahzil_CMD Version 1.0 Does\'nt manage more than 1
subfolder within main folder";

Page 72 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

107. } else {
108. Folder* newfolder = new Folder(n);
109. check->sub = newfolder;
110. cout << "\n Subfolder '" << n << "' added successfully in main
folder '" << f << "'.";
111. }
112. }
113.
114. // Display folders and subfolders with proper alignment
115. void display() {
116. cout << "\n. Shahzil_CMD:C<drive>: Folders Info";
117. if (start == NULL) {
118. cout << "\n. Empty";
119. return;
120. }
121.
122. Folder* check = start;
123. cout << left << setw(15) << "\n. Folder" << setw(20) << "Subfolder";
124. cout << "\n. --------------------------------";
125.
126. while (check != NULL) {
127. cout << left << "\n. " << setw(15) << check->name
128. << (check->sub == NULL ? "No Subfolder" : check->sub->name);
129. check = check->next;
130. }
131. }
132.
133. // Clear screen function
134. void clear() {
135. system("cls");
136. }
137.
138. // Display instruction function
139. void INS() {
140. cout << "\n. Functionality\t\tCommand";
141. cout << "\n. Create new folder\tnew<folder_name>";
142. cout << "\n. Create new subfolder\
tnew_sub<main_folderName,subfolder_name>";
143. cout << "\n. Delete folder/subfolder del<folder_name>";
144. cout << "\n. Display folders\tdisplay";
145. cout << "\n. Clear screen\t\tclear";
146. }
147. };
148.
149. int main() {
150. Folder_System fs;

Page 73 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

151. string command;

152. while (true) {
153. cout << "\n Shahzil_CMD:C<drive>: Write ins/exit/command >> ";
154. getline(cin, command);
155.
156. if (command == "exit") {
157. break;
158. } else if (command == "ins") {
159. fs.INS();
160. } else if (command.substr(0, 4) == "new<") {
161. string folderName = command.substr(4, command.size() - 5); // Extract
folder name
162. fs.create(folderName);
163. } else if (command.substr(0, 8) == "new_sub<") {
164. size_t commaPos = command.find(',');
165. if (commaPos != string::npos) {
166. string mainFolder = command.substr(8, commaPos - 8);
167. string subFolder = command.substr(commaPos + 1, command.size() -
commaPos - 2);
168. fs.add_sub(mainFolder, subFolder);
169. } else {
170. cout << "\n Invalid command format for subfolder creation!";
171. }
172. } else if (command.substr(0, 4) == "del<") {
173. string folderName = command.substr(4, command.size() - 5);
174. fs.Delete(folderName);
175. } else if (command == "display") {
176. fs.display();
177. } else if (command == "clear") {
178. fs.clear();
179. } else {
180. cout << "\n Invalid command!";
181. }
182. cout << endl;
183. }
184. return 0;
185. }
Output Observed:

Page 74 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 4.3- Real-Life Applications of Circular Linked-list

Token Ring Network (STRN)
Respective Code:
1. #include <iostream>
2. #include <iomanip>
3. using namespace std;
4.
5. class Device {
6. public:
7. string message, state;
8. Device* next;
9. int id;
10.
11. Device(int ID) {
12. id = ID;
13. state = "Active";
14. next = NULL;
15. message = "";
16. }
17. };
18.
19. class TokenRing {
20. public:
21. Device* head, * tail;
22. int count;
23. bool tokenBusy;
24.
25. TokenRing() {
26. head = tail = NULL;
27. count = 0;
28. tokenBusy = false;
29. }
30.
31. void add(int ID) {
32. if (count == 4) {
33. cout << "\n Only 4 devices are supported.\n";
34. return;
35. }
36. if (findDevice(ID)) {
37. cout << "\n Device with ID " << ID << " already exists.\n";
38. return;
39. }
40. Device* newDevice = new Device(ID);
41. if (!head) {

Page 75 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

42. head = tail = newDevice;

43. tail->next = head; // Circular connection
44. } else {
45. tail->next = newDevice;
46. tail = newDevice;
47. tail->next = head;
48. }
49. count++;
50. cout << "\n Device with ID " << ID << " added successfully.\n";
51. }
52.
53. void deleteDevice(int ID) {
54. if (!head) {
55. cout << "\n No devices to delete.\n";
56. return;
57. }
58.
59. Device* temp = head;
60. Device* prev = NULL;
61.
62. do {
63. if (temp->id == ID) {
64. if (temp == head && temp == tail) {
65. head = tail = NULL;
66. } else if (temp == head) {
67. head = head->next;
68. tail->next = head;
69. } else if (temp == tail) {
70. tail = prev;
71. tail->next = head;
72. } else {
73. prev->next = temp->next;
74. }
75. delete temp;
76. count--;
77. cout << "\n Device with ID " << ID << " deleted successfully.\n";
78. return;
79. }
80. prev = temp;
81. temp = temp->next;
82. } while (temp != head);
83.
84. cout << "\n Device with ID " << ID << " not found.\n";
85. }
86.
87. void sendMessage() {

Page 76 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

88. if (tokenBusy) {
89. cout << "\n Token is busy. Please wait for the acknowledgment.";
90. return;
91. }
92. if (count == 0) {
93. cout << "\n No devices in the network to send a message.";
94. return;
95. }
96.
97. int senderID, receiverID;
98. cout << "\n Enter sender's device ID: ";
99. cin >> senderID;
100. cout << "\n Enter receiver's device ID: ";
101. cin >> receiverID;
102.
103. Device* sender = findDevice(senderID);
104. Device* receiver = findDevice(receiverID);
105.
106. if (!sender || !receiver) {
107. cout << "\n Invalid device IDs.\n";
108. return;
109. }
110.
111. string msg;
112. cout << "\n Enter the message: ";
113. cin.ignore();
114. getline(cin, msg);
115.
116. receiver->message = msg;
117. tokenBusy = true;
118. cout << "\n Message sent successfully from Device " << senderID << " to
Device " << receiverID << ".\n";
119. }
120.
121. void acknowledgeMessage() {
122. if (!tokenBusy) {
123. cout << "\n Token is already free.\n";
124. return;
125. }
126.
127. cout << "\n Acknowledgment received. Token is now free.\n";
128. tokenBusy = false;
129. }
130.
131. void display() {
132. cout << "\n\tTOKEN RING NETWORK SYSTEM By Syed Shahzil:\n";

Page 77 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

133.
134. // Pattern for the layout
135. string emptySlot = "\033[47m\033[30m Unknown Device \033[0m"; // Grey
background
136. string activeSlotTemplate = "\033[42m\033[30m ID: %d | Active \
033[0m"; // Green background
137.
138. // Initialize the layout with empty slots
139. string slots[4] = {emptySlot, emptySlot, emptySlot, emptySlot};
140.
141. // Populate allocated slots
142. Device* temp = head;
143. if (temp) {
144. int i = 0;
145. do {
146. char activeSlot[50];
147. snprintf(activeSlot, sizeof(activeSlot), activeSlotTemplate.c_str(), temp-
>id);
148. slots[i++] = string(activeSlot);
149. temp = temp->next;
150. } while (temp != head && i < 4);
151. }
152.
153. // Print the layout (matching the picture's pattern)
154. cout << "\n\t\t\t" << slots[0] << "\n";
155. cout << "\n\t" << slots[1] << "\t\t\t" << slots[2] << "\n";
156. cout << "\n\t\t\t" << slots[3] << "\n\n";
157. }
158. Device* findDevice(int ID) {
159. if (!head) return NULL;
160. Device* temp = head;
161. do {
162. if (temp->id == ID) return temp;
163. temp = temp->next;
164. } while (temp != head);
165. return NULL;
166. }
167. };
168.
169. int main() {
170. TokenRing network;
171. int choice, id;
172.
173. while (true) {
174. network.display();
175. cout << "\n --- Token Ring Network Simulation ---\n";

Page 78 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

176. cout << " 1. Add Device\n";

177. cout << " 2. Delete Device\n";
178. cout << " 3. Send Message\n";
179. cout << " 4. Acknowledge Message\n";
180. cout << " 5. Exit\n";
181. cout << " Enter your choice: ";
182. cin >> choice;
183. system("cls");
184. switch (choice) {
185. case 1:
186. cout << "\n Enter device ID to add: ";
187. cin >> id;
188. network.add(id);
189. break;
190. case 2:
191. cout << "\n Enter device ID to delete: ";
192. cin >> id;
193. network.deleteDevice(id);
194. break;
195. case 3:
196. network.sendMessage();
197. break;
198. case 4:
199. network.acknowledgeMessage();
200. break;
201. case 5:
202. cout << " Exiting...\n";
203. return 0;
204. default:
205. cout << " Invalid choice. Please try again.\n";
206. }
207. }
208.
209. return 0;
210. }
Output Observed:

Page 79 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Online Ludo by Shahzil (SOL)

Respective Code:
1. #include <iostream>
2. #include <conio.h>
3. #include <iomanip>
4. using namespace std;
5.
6. class User {
7. public:
8. string Name;
9. User* next;
10. int id;
11.
12. User(int ID, string name) {
13. id = ID;

Page 80 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

14. next = NULL;

15. Name = name;
16. }
17. };
18.
19. class OnlineLudo {
20. public:
21. User* head, * tail;
22. int count;
23.
24. OnlineLudo() {
25. head = tail = NULL;
26. count = 0;
27. }
28.
29. User* Search(int ID) {
30. if (head == NULL)
31. return NULL;
32. else {
33. User* check = head;
34. do {
35. if (check->id == ID)
36. return check;
37. check = check->next;
38. } while (check != head);
39. return NULL;
40. }
41. }
42.
43. void add(int ID, string name) {
44. if (count == 4) {
45. cout << "\n Only 4 Players are supported.\n";
46. return;
47. }
48. if (Search(ID)) {
49. cout << "\n Player with ID \'" << ID << "\' already exists.\n";
50. return;
51. }
52. User* newUser = new User(ID, name);
53. if (!head) {
54. head = tail = newUser;
55. tail->next = head; // Circular connection
56. } else {
57. tail->next = newUser;
58. tail = newUser;
59. tail->next = head;

Page 81 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

60. }
61. count++;
62. cout << "\n Welcome " << name << "! You are successfully added.\n";
63. }
64.
65. void deleteUser(int ID) {
66. if (!head) {
67. cout << "\n No Player to delete.\n";
68. return;
69. }
70.
71. User* temp = head;
72. User* prev = NULL;
73.
74. do {
75. if (temp->id == ID) {
76. if (temp == head && temp == tail) {
77. head = tail = NULL;
78. } else if (temp == head) {
79. head = head->next;
80. tail->next = head;
81. } else if (temp == tail) {
82. tail = prev;
83. tail->next = head;
84. } else {
85. prev->next = temp->next;
86. }
87. delete temp;
88. count--;
89. cout << "\n Player with ID " << ID << " deleted successfully.\n";
90. return;
91. }
92. prev = temp;
93. temp = temp->next;
94. } while (temp != head);
95.
96. cout << "\n Player with ID " << ID << " not found.\n";
97. }
98.
99. void Display(User* CrU) {
100. if (!CrU) {
101. cout << "\n No current user to display.\n";
102. return;
103. }
104.
105. string NAMES[count]; // Use count for active players

Page 82 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

106. int IDS[count]; // Use count for active player IDs

107. User* tmp = head;
108.
109. // Populate NAMES and IDS arrays
110. for (int i = 0; i < count; i++) {
111. NAMES[i] = tmp->Name;
112. IDS[i] = tmp->id;
113. tmp = tmp->next;
114. }
115.
116. if (IDS[0] == CrU->id) { // First condition for index 0
117. cout << "\n\n\n\t\tONLINE LUDO By Syed Shahzil Abaas Naqvi\n";
118. cout << "\n\n\n\t\t" << setw(15) << NAMES[1] << " \
033[41m \033[42m \033[0m";
119. cout << "\n\t\t" << setw(15) << "ID: " << IDS[1] << "\033[41m
\033[42m \033[0m\t\t" << (count >= 3 ? NAMES[2] : "No Player");
120. cout << "\n\t\t\t\t\033[41m \033[42m \033[0m\t\t"
<< (count >= 3 ? "ID: " + to_string(IDS[2]) : " ");
121. cout << "\n\t\t\t\t\033[41m \033[42m \033[0m";
122. cout << "\n\t\t\t\t\033[44m \033[43m \033[0m";
123. cout << "\n\t\t" << setw(15) << NAMES[0] << " \033[44m \
033[43m \033[0m\t\t" << (count >= 4 ? NAMES[3] : "No Player");
124. cout << "\n\t\t" << setw(15) << "ID: " << IDS[0] << "\033[44m
\033[43m \033[0m" << (count >= 4 ? "ID: " + to_string(IDS[3]) : " ");
125. cout << "\n\t\t\t\t\033[44m \033[43m \033[0m";
126. }
127.
128. if (IDS[1] == CrU->id) { // Second condition for index 1
129. cout << "\n\n\n\t\tONLINE LUDO By Syed Shahzil Abaas Naqvi\n";
130. cout << "\n\n\n\t\t" << setw(15) << NAMES[0] << " \
033[44m \033[42m \033[0m";
131. cout << "\n\t\t" << setw(15) << "ID: " << IDS[0] << "\033[44m
\033[42m \033[0m\t\t" << (count >= 3 ? NAMES[2] : "No Player");
132. cout << "\n\t\t\t\t\033[44m \033[42m \033[0m\t\t"
<< (count >= 3 ? "ID: " + to_string(IDS[2]) : " ");
133. cout << "\n\t\t\t\t\033[44m \033[42m \033[0m";
134. cout << "\n\t\t\t\t\033[41m \033[43m \033[0m";
135. cout << "\n\t\t" << setw(15) << NAMES[1] << " \033[41m \
033[43m \033[0m\t\t" << (count >= 4 ? NAMES[3] : "No Player");
136. cout << "\n\t\t" << setw(15) << "ID: " << IDS[1] << "\033[41m
\033[43m \033[0m" << (count >= 4 ? "ID: " + to_string(IDS[3]) : " ");
137. cout << "\n\t\t\t\t\033[41m \033[43m \033[0m";
138. }
139.
140. if (count >= 3 && IDS[2] == CrU->id) { // Third condition for index 2
141. cout << "\n\n\n\t\tONLINE LUDO By Syed Shahzil Abaas Naqvi\n";

Page 83 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

142. cout << "\n\n\n\t\t" << setw(15) << NAMES[0] << " \
033[44m \033[41m \033[0m";
143. cout << "\n\t\t" << setw(15) << "ID: " << IDS[0] << "\033[44m
\033[41m \033[0m\t\t" << (count >= 2 ? NAMES[1] : "No Player");
144. cout << "\n\t\t\t\t\033[44m \033[41m \033[0m\t\t"
<< "ID: " << IDS[1];
145. cout << "\n\t\t\t\t\033[44m \033[41m \033[0m";
146. cout << "\n\t\t\t\t\033[42m \033[43m \033[0m";
147. cout << "\n\t\t" << setw(15) << NAMES[2] << " \033[42m \
033[43m \033[0m\t\t" << (count >= 4 ? NAMES[3] : "No Player");
148. cout << "\n\t\t" << setw(15) << "ID: " << IDS[2] << "\033[42m
\033[43m \033[0m" << (count >= 4 ? "ID: " + to_string(IDS[3]) : " ");
149. cout << "\n\t\t\t\t\033[42m \033[43m \033[0m";
150. }
151.
152. if (count >= 4 && IDS[3] == CrU->id) { // Fourth condition for index 3
153. cout << "\n\n\n\t\tONLINE LUDO By Syed Shahzil Abaas Naqvi\n";
154. cout << "\n\n\n\t\t" << setw(15) << NAMES[0] << " \
033[44m \033[41m \033[0m";
155. cout << "\n\t\t" << setw(15) << "ID: " << IDS[0] << "\033[44m
\033[41m \033[0m\t\t" << (count >= 2 ? NAMES[1] : "No Player");
156. cout << "\n\t\t\t\t\033[44m \033[41m \033[0m\t\t"
<< "ID: " << IDS[1];
157. cout << "\n\t\t\t\t\033[44m \033[41m \033[0m";
158. cout << "\n\t\t\t\t\033[43m \033[42m \033[0m";
159. cout << "\n\t\t" << setw(15) << NAMES[3] << " \033[43m \
033[42m \033[0m\t\t" <<(count>=4? NAMES[2]:"No Player");
160. cout << "\n\t\t" << setw(15) << "ID: " << IDS[3] << "\033[43m
\033[42m \033[0m";(count>=4? "ID: "+ to_string(IDS[2]):" ");
161. cout << "\n\t\t\t\t\033[43m \033[42m \033[0m";
162. }
163. }
164. void PlayGame() {
165. if (count < 2) {
166. cout << "\n At least 2 players are required to play.\n";
167. return;
168. }
169.
170. // Wait for user input to start
171. cout << "\n\n Game over! Thanks for playing.\n";
172. User* tmp=head;
173. for(int i=0;i<=20;i++){
174. system("cls");
175.
176. Display(tmp);
177. cout << "\n\n "<<tmp->Name<<"! PRESS ANY KEY

Page 84 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

TO MOVEON....";
178. // cin.ignore();
179. getch();
180. tmp=tmp->next;
181. }
182. }
183. };
184.
185. int main() {
186. OnlineLudo OL;
187. int choice;
188.
189. do {
190. cout << "\n\n MENU:";
191. cout << "\n 1. Add User";
192. cout << "\n 2. Remove User";
193. cout << "\n 3. Play Game";
194. cout << "\n 4. Exit";
195. cout << "\n\n Enter your choice: ";
196. cin >> choice;
197. system("cls"); // Clear screen for a clean display
198. switch (choice) {
199. case 1: {
200. int id;
201. string name;
202. cout << "\n Enter Player ID: ";
203. cin >> id;
204. cout << " Enter Player Name: ";
205. cin >> name;
206. OL.add(id, name);
207. break;
208. }
209. case 2: {
210. int id;
211. cout << "\n Enter Player ID to Remove: ";
212. cin >> id;
213. OL.deleteUser(id);
214. break;
215. }
216. case 3:
217. OL.PlayGame();
218. break;
219. case 4:
220. cout << "\n Exiting the game. Goodbye!\n";
221. break;
222. default:

Page 85 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

223. cout << "\n Invalid choice. Please try again.\n";

224. }
225. } while (choice != 4);
226.
227. return 0;
228. }
Output Observed:

Page 86 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 87 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Linked-list Data Structure =

`LAB 5
-
DATED: 21/11/24

Lab 5-Linked-list DS (Doubly Link list)

Task 5.1- Implementation of 10 Functionalities in Doubly
linked-list (SDL & CDL)
Task 5.1.1- SDL
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. class Node {
5. public:
6. int data;
7. Node* next;
8. Node* prev;
9. Node(int a) : data(a), next(nullptr), prev(nullptr) {}
10. };
11.
12. class DOUBLY_LIST {
13. public:
14. Node* head, * tail;
15. int size;
16.
17. DOUBLY_LIST() : head(nullptr), tail(nullptr), size(0) {}
18.
19. // I use this to add a node with a specific value to the end of the list
20. void add(int val) {
21. Node* newnode = new Node(val);
22. if (head == nullptr) {
23. head = tail = newnode;
24. } else {
25. tail->next = newnode;
26. newnode->prev = tail;
27. tail = newnode;
28. }
29. size++;
30. }
31.
32. // I use this to remove the node using FIFO
33. void remove() {

Page 88 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

34. if (head == nullptr) {

35. cout << "List is empty.\n";
36. return;
37. }
38. Node* temp = head;
39. head = head->next;
40. if (head != nullptr) {
41. head->prev = nullptr;
42. } else {
43. tail = nullptr;
44. }
45. cout << "Removed value: " << temp->data << "\n";
46. delete temp;
47. size--;
48. }
49.
50. // I use this to display all elements in the doubly linked list
51. void display() {
52. Node* temp = head;
53. cout << "Doubly Linked List: ";
54. while (temp != nullptr) {
55. cout << temp->data << " <-> ";
56. temp = temp->next;
57. }
58. cout << "NULL\n";
59. }
60.
61. // I use this to retrieve the value at a specific index
62. int searchByIndex(int index) {
63. if (index < 0 || index >= size) {
64. cout << "Index out of bounds.\n";
65. return -1;
66. }
67. Node* temp = head;
68. for (int i = 0; i < index; i++) {
69. temp = temp->next;
70. }
71. return temp->data;
72. }
73.
74. // I use this to move back to the previous node from the current node
75. Node* backNode(Node* current) {
76. if (current == nullptr || current->prev == nullptr) {
77. cout << "Cannot move back.\n";
78. return nullptr;
79. }

Page 89 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

80. return current->prev;

81. }
82.
83. // I use this to insert a node at a specific index
84. void updateList(int index, int val) {
85. if (index < 0 || index > size) {
86. cout << "Index out of bounds.\n";
87. return;
88. }
89. Node* newnode = new Node(val);
90. if (index == 0) {
91. newnode->next = head;
92. if (head != nullptr) {
93. head->prev = newnode;
94. }
95. head = newnode;
96. if (tail == nullptr) {
97. tail = newnode;
98. }
99. } else {
100. Node* temp = head;
101. for (int i = 0; i < index - 1; i++) {
102. temp = temp->next;
103. }
104. newnode->next = temp->next;
105. newnode->prev = temp;
106. if (temp->next != nullptr) {
107. temp->next->prev = newnode;
108. } else {
109. tail = newnode;
110. }
111. temp->next = newnode;
112. }
113. size++;
114. }
115. };
116.
117. void performDoublyLinkedListOperations() {
118. DOUBLY_LIST list;
119. int choice, value, index;
120. do {
121. cout << "\nDoubly Linked List Operations:\n";
122. cout << "1. Add\n2. Remove\n3. Display\n4. Search by Index\n5. Back
Node\n6. Update List\n0. Exit\n";
123. cout << "Enter your choice: ";
124. cin >> choice;

Page 90 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

125. switch (choice) {

126. case 1:
127. cout << "Enter value to add: ";
128. cin >> value;
129. list.add(value);
130. break;
131. case 2:
132. list.remove();
133. break;
134. case 3:
135. list.display();
136. break;
137. case 4:
138. cout << "Enter index to search: ";
139. cin >> index;
140. cout << "Value at index " << index << ": " << list.searchByIndex(index)
<< "\n";
141. break;
142. case 5: {
143. Node* current = list.tail; // Start from tail
144. Node* previous = list.backNode(current);
145. if (previous != nullptr) {
146. cout << "Previous Node: " << previous->data << "\n";
147. }
148. break;
149. }
150. case 6:
151. cout << "Enter index and value to update: ";
152. cin >> index >> value;
153. list.updateList(index, value);
154. break;
155. }
156. } while (choice != 0);
157. }
158.
159. ---
160.
161. ### Program 2: Doubly Circular Linked List
162.
163. ```cpp
164. class DOUBLY_CIRCULAR_LIST {
165. public:
166. Node* head;
167. int size;
168.
169. DOUBLY_CIRCULAR_LIST() : head(nullptr), size(0) {}

Page 91 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

170.
171. // I use this to add a node with a specific value to the end of the circular list
172. void add(int val) {
173. Node* newnode = new Node(val);
174. if (head == nullptr) {
175. head = newnode;
176. newnode->next = newnode->prev = head;
177. } else {
178. Node* tail = head->prev;
179. tail->next = newnode;
180. newnode->prev = tail;
181. newnode->next = head;
182. head->prev = newnode;
183. }
184. size++;
185. }
186.
187. // I use this to remove a node in FIFO
188. void remove() {
189. if (head == nullptr) {
190. cout << "List is empty.\n";
191. return;
192. }
193.
194. Node* temp = head;
195.
196. if (head->next == head) { // Only one node in the list
197. head = nullptr;
198. } else {
199. Node* tail = head->prev;
200. head = head->next;
201. head->prev = tail;
202. tail->next = head;
203. }
204.
205. cout << "Removed value: " << temp->data << "\n";
206. delete temp;
207. size--;
208. }
209.
210. // I use this to display all elements dynamically in the circular list
211. void display() {
212. if (head == nullptr) {
213. cout << "List is empty.\n";
214. return;
215. }

Page 92 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

216.
217. Node* temp = head;
218. cout << "Doubly Circular Linked List: ";
219. do {
220. cout << temp->data << " <-> ";
221. temp = temp->next;
222. } while (temp != head);
223. cout << "(back to head)\n";
224. }
225.
226. // I use this to retrieve the value at a specific index
227. int searchByIndex(int index) {
228. if (index < 0 || index >= size) {
229. cout << "Index out of bounds.\n";
230. return -1;
231. }
232.
233. Node* temp = head;
234. for (int i = 0; i < index; i++) {
235. temp = temp->next;
236. }
237.
238. return temp->data;
239. }
240.
241. // I use this to move back to the previous node from the current node
242. Node* backNode(Node* current) {
243. if (current == nullptr || current->prev == nullptr) {
244. cout << "Cannot move back.\n";
245. return nullptr;
246. }
247. return current->prev;
248. }
249.
250. // I use this to insert a node at a specific index
251. void updateList(int index, int val) {
252. if (index < 0 || index > size) {
253. cout << "Index out of bounds.\n";
254. return;
255. }
256.
257. Node* newnode = new Node(val);
258.
259. if (index == 0) {
260. if (head == nullptr) {
261. head = newnode;

Page 93 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

262. newnode->next = newnode->prev = head;

263. } else {
264. Node* tail = head->prev;
265. newnode->next = head;
266. newnode->prev = tail;
267. tail->next = newnode;
268. head->prev = newnode;
269. head = newnode;
270. }
271. } else {
272. Node* temp = head;
273. for (int i = 0; i < index - 1; i++) {
274. temp = temp->next;
275. }
276. newnode->next = temp->next;
277. newnode->prev = temp;
278. temp->next->prev = newnode;
279. temp->next = newnode;
280. }
281. size++;
282. }
283. };
284.
285. void performDoublyCircularLinkedListOperations() {
286. DOUBLY_CIRCULAR_LIST list;
287. int choice, value, index;
288. do {
289. cout << "\nDoubly Circular Linked List Operations:\n";
290. cout << "1. Add\n2. Remove\n3. Display\n4. Search by Index\n5. Back
Node\n6. Update List\n0. Exit\n";
291. cout << "Enter your choice: ";
292. cin >> choice;
293. switch (choice) {
294. case 1:
295. cout << "Enter value to add: ";
296. cin >> value;
297. list.add(value);
298. break;
299. case 2:
300. list.remove();
301. break;
302. case 3:
303. list.display();
304. break;
305. case 4:
306. cout << "Enter index to search: ";

Page 94 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

307. cin >> index;

308. cout << "Value at index " << index << ": " << list.searchByIndex(index)
<< "\n";
309. break;
310. case 5: {
311. Node* current = list.head; // Start from head
312. if (current != nullptr) {
313. Node* previous = list.backNode(current);
314. if (previous != nullptr) {
315. cout << "Previous Node: " << previous->data << "\n";
316. }
317. }
318. break;
319. }
320. case 6:
321. cout << "Enter index and value to update: ";
322. cin >> index >> value;
323. list.updateList(index, value);
324. break;
325. }
326. } while (choice != 0);
327. }
328.
329. int main() {
330. int listType;
331. cout << "Choose List Type:\n1. Doubly Linked List\n2. Doubly Circular
Linked List\n";
332. cout << "Enter your choice: ";
333. cin >> listType;
334.
335. if (listType == 1) {
336. performDoublyLinkedListOperations();
337. } else if (listType == 2) {
338. performDoublyCircularLinkedListOperations();
339. } else {
340. cout << "Invalid choice.\n";
341. }
342.
343. return 0;
344. }
Output Observed:

Page 95 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 5.1.2-CDL
Respective Code:
Page 96 of 125 Lab Manuals
 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

1. #include <iostream>
2. using namespace std;
3.
4. class Node {
5. public:
6. int data;
7. Node* next;
8. Node* prev;
9. Node(int a) : data(a), next(nullptr), prev(nullptr) {}
10. };
11.
12. class DOUBLY_CIRCULAR_LIST {
13. public:
14. Node* head;
15. int size;
16.
17. DOUBLY_CIRCULAR_LIST() : head(nullptr), size(0) {}
18.
19. // I use this to add a node with a specific value to the end of the circular list
20. void add(int val) {
21. Node* newnode = new Node(val);
22. if (head == nullptr) {
23. head = newnode;
24. newnode->next = newnode->prev = head;
25. } else {
26. Node* tail = head->prev;
27. tail->next = newnode;
28. newnode->prev = tail;
29. newnode->next = head;
30. head->prev = newnode;
31. }
32. size++;
33. }
34.
35. // I use this to remove the node using FIFO
36. void remove() {
37. if (head == nullptr) {
38. cout << "List is empty.\n";
39. return;
40. }
41.
42. Node* temp = head;
43.
44. if (head->next == head) { // Only one node in the list
45. head = nullptr;
46. } else {

Page 97 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

47. Node* tail = head->prev;

48. head = head->next;
49. head->prev = tail;
50. tail->next = head;
51. }
52.
53. cout << "Removed value: " << temp->data << "\n";
54. delete temp;
55. size--;
56. }
57.
58. // I use this to display all elements dynamically in the circular list
59. void display() {
60. if (head == nullptr) {
61. cout << "List is empty.\n";
62. return;
63. }
64.
65. Node* temp = head;
66. cout << "Doubly Circular Linked List: ";
67. do {
68. cout << temp->data << " <-> ";
69. temp = temp->next;
70. } while (temp != head);
71. cout << "(back to head)\n";
72. }
73.
74. // I use this to retrieve the value at a specific index
75. int searchByIndex(int index) {
76. if (index < 0 || index >= size) {
77. cout << "Index out of bounds.\n";
78. return -1;
79. }
80.
81. Node* temp = head;
82. for (int i = 0; i < index; i++) {
83. temp = temp->next;
84. }
85.
86. return temp->data;
87. }
88.
89. // I use this to move back to the previous node from the current node
90. Node* backNode(Node* current) {
91. if (current == nullptr || current->prev == nullptr) {
92. cout << "Cannot move back.\n";

Page 98 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

93. return nullptr;

94. }
95. return current->prev;
96. }
97.
98. // I use this to insert a node at a specific index
99. void updateList(int index, int val) {
100. if (index < 0 || index > size) {
101. cout << "Index out of bounds.\n";
102. return;
103. }
104.
105. Node* newnode = new Node(val);
106.
107. if (index == 0) {
108. if (head == nullptr) {
109. head = newnode;
110. newnode->next = newnode->prev = head;
111. } else {
112. Node* tail = head->prev;
113. newnode->next = head;
114. newnode->prev = tail;
115. tail->next = newnode;
116. head->prev = newnode;
117. head = newnode;
118. }
119. } else {
120. Node* temp = head;
121. for (int i = 0; i < index - 1; i++) {
122. temp = temp->next;
123. }
124. newnode->next = temp->next;
125. newnode->prev = temp;
126. temp->next->prev = newnode;
127. temp->next = newnode;
128. }
129. size++;
130. }
131. };
132.
133. void performDoublyCircularLinkedListOperations() {
134. DOUBLY_CIRCULAR_LIST list;
135. int choice, value, index;
136. do {
137. cout << "\nDoubly Circular Linked List Operations:\n";
138. cout << "1. Add\n2. Remove\n3. Display\n4. Search by Index\n5. Back

Page 99 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Node\n6. Update List\n0. Exit\n";

139. cout << "Enter your choice: ";
140. cin >> choice;
141. switch (choice) {
142. case 1:
143. cout << "Enter value to add: ";
144. cin >> value;
145. list.add(value);
146. break;
147. case 2:
148. list.remove();
149. break;
150. case 3:
151. list.display();
152. break;
153. case 4:
154. cout << "Enter index to search: ";
155. cin >> index;
156. cout << "Value at index " << index << ": " << list.searchByIndex(index)
<< "\n";
157. break;
158. case 5: {
159. Node* current = list.head; // Start from head
160. if (current != nullptr) {
161. Node* previous = list.backNode(current);
162. if (previous != nullptr) {
163. cout << "Previous Node: " << previous->data << "\n";
164. }
165. }
166. break;
167. }
168. case 6:
169. cout << "Enter index and value to update: ";
170. cin >> index >> value;
171. list.updateList(index, value);
172. break;
173. }
174. } while (choice != 0);
175. }
176.
177. int main() {
178. performDoublyCircularLinkedListOperations();
179. return 0;
180. }
Output Observed:

Page 100 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Searching & Sorting

`LAB 6

Page 101 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

DATED=: 19/12/24

Lab 6- Searching & Sorting

Task 6.1-C++ Code for Linear Searching
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void linearSearch(int arr[], int size, int key) {
5. bool found = false;
6. for (int i = 0; i < size; i++) {
7. if (arr[i] == key) {
8. cout << "\n Key found at index " << i << endl;
9. found = true;
10. break;
11. }
12. }
13. if (!found)
14. cout << "\n Key not found!" << endl;
15. }
16.
17. int main() {
18. cout<<"\n Syed Shahzil-- DSA Lab M6 ";
19. int arr[] = {5, 3, 8, 6, 2};
20. int key=6;
21. linearSearch(arr, 5, key);
22. return 0;
23. }
Output Observed:

Task 6.2-C++ Code for Binary Searching

Respective Code:
1. #include <iostream>
2. using namespace std;

Page 102 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

3.
4. void binarySearch(int arr[], int size, int key) {
5. int low = 0, high = size - 1;
6. while (low <= high) {
7. int mid = (low + high) / 2;
8. if (arr[mid] == key) {
9. cout << "\n Key found at index " << mid << endl;
10. return;
11. }
12. if (arr[mid] < key)
13. low = mid + 1;
14. else
15. high = mid - 1;
16. }
17. cout << "\n Key not found!" << endl;
18. }
19.
20. int main() {
21. cout<<"\n Syed Shahzil-- DSA Lab M6 ";
22.
23. int arr[] = {2, 3, 5, 6, 8}; // Must be sorted
24. int key=8;
25. binarySearch(arr, 5, key);
26. return 0;
27. }
Output Observed:

Task 6.3-C++ code for Bubble Sort

Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void bubbleSort(int arr[], int size) {
5. for (int i = 0; i < size - 1; i++) {
6. for (int j = 0; j < size - i - 1; j++) {
7. if (arr[j] > arr[j + 1]) {
8. swap(arr[j],arr[j+1]);
9. }
10. }
11. }

Page 103 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

12. }
13.
14. int main() {
15. cout<<"\n Syed Shahzil-- DSA Lab M6 ";
16. int arr[] = {5, 3, 8, 6, 2};
17. int size = 5;
18. cout << "\n Before Sorted array: ";
19. for (int i = 0; i < size; i++) {
20. cout << arr[i] << " ";
21. }
22. bubbleSort(arr, size);
23. cout << "\n Sorted array: ";
24. for (int i = 0; i < size; i++) {
25. cout << arr[i] << " ";
26. }
27.
28.
29. return 0;
30. }
Output Observed:

Task 6.4-C++ code for Handling Duplicate values in Linear

Search
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void findDuplicates(int arr[], int size) {
5. for (int i = 0; i < size; i++) {
6. int count = 1;
7. for (int j = i + 1; j < size; j++) {
8. if (arr[i] == arr[j]) {
9. count++;
10. arr[j] = -1; // Mark duplicate
11. }
12. }
13. if (arr[i] != -1 && count > 1) {
14. cout << "\n Value " << arr[i] << " appears " << count << " times." << endl;

Page 104 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

15. }
16. }
17. }
18.
19. int main() {
20. cout<<"\n Syed Shahzil-- DSA Lab M6 ";
21.
22. int arr[] = {5, 3, 5, 6, 2, 3,17,11,17,11,11};
23. findDuplicates(arr, 11);
24. return 0;
25. }
Output Observed:

Task 6.5-Binary Search with Bubble Sort

Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void bubbleSort(int arr[], int size) {
5. for (int i = 0; i < size - 1; i++) {
6. for (int j = 0; j < size - i - 1; j++) {
7. if (arr[j] > arr[j + 1]) {
8. int temp = arr[j];
9. arr[j] = arr[j + 1];
10. arr[j + 1] = temp;
11. }
12. }
13. }
14. }
15.
16. void binarySearch(int arr[], int size, int key) {
17. int low = 0, high = size - 1;
18. while (low <= high) {
19. int mid = (low + high) / 2;

Page 105 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

20. if (arr[mid] == key) {

21. cout << "Key found at index " << mid << endl;
22. return;
23. }
24. if (arr[mid] < key)
25. low = mid + 1;
26. else
27. high = mid - 1;
28. }
29. cout << "Key not found!" << endl;
30. }
31.
32. int main() {
33. int arr[] = {5, 3, 8, 6, 2};
34. int size = 5;
35. bubbleSort(arr, size);
36.
37. int key;
38. cout << "Enter key to search: ";
39. cin >> key;
40. binarySearch(arr, size, key);
41.
42. return 0;
43. }
Output Observed:

Task 6.6- Reverse Bubble Sort

Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void bubbleSortDescending(char arr[], int size) {
5. for (int i = 0; i < size - 1; i++) {
6. for (int j = 0; j < size - i - 1; j++) {
7. if (arr[j] < arr[j + 1]) {
8. char temp = arr[j];
9. arr[j] = arr[j + 1];
10. arr[j + 1] = temp;
11. }
12. }
13. }
14. }
15.
16. int main() {

Page 106 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

17. char name[] = {'S', 'h', 'a', 'h', 'z', 'i', 'l'};
18. int size = sizeof(name) / sizeof(name[0]);
19.
20. bubbleSortDescending(name, size);
21. cout << "\n Name in descending order: ";
22. for (int i = 0; i < size; i++) {
23. cout << name[i] << " ";
24. }
25.
26. return 0;
27. }
Output Observed:

Task 6.7,8- Real-Time Scenario

Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void bubbleSort(double prices[], int size) {
5. for (int i = 0; i < size - 1; i++) {
6. for (int j = 0; j < size - i - 1; j++) {
7. if (prices[j] > prices[j + 1]) {
8. swap(prices[j],prices[j+1]);
9. }
10. }
11. }
12. }
13.
14. void linearSearch(double prices[], int size, double target) {
15. bool found = false;
16. for (int i = 0; i < size; i++) {
17. if (prices[i] == target) {
18. cout << "\n Price " << target << " found at index " << i << "." << endl;
19. found = true;
20. break;
21. }
22. }
23. if (!found)
24. cout << "\n Price " << target << " not found." << endl;
25. }

Page 107 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

26.
27. void binarySearch(double prices[], int size, double minRange, double maxRange) {
28. int low = 0, high = size - 1;
29. cout << "\n Prices within range " << minRange << " to " << maxRange << ": ";
30. while (low <= high) {
31. int mid = (low + high) / 2;
32. if (prices[mid] >= minRange && prices[mid] <= maxRange) {
33. cout << prices[mid] << " ";
34. }
35. if (prices[mid] < minRange)
36. low = mid + 1;
37. else if (prices[mid] > maxRange)
38. high = mid - 1;
39. else
40. break;
41. }
42. cout << endl;
43. }
44.
45. int main() {
46. int size;
47. cout<<"\n Syed Shahzil-23018020020";
48. cout<<"\n How many prices you want to eneter?";
49. cin>>size;
50. double prices[size];
51.
52. for(int i=0;i<size;i++){
53. cout<<"\n Enter price "<<i+1<<" : ";
54. cin>>prices[i];
55. }
56.
57. // Sort prices for binary search
58. bubbleSort(prices, size);
59.
60. double target;
61. cout << "\n Enter a price to search: ";
62. cin >> target;
63. linearSearch(prices, size, target);
64.
65. double minRange, maxRange;
66. cout << "\n Enter the price range (min and max): ";
67. cin >> minRange >> maxRange;
68. binarySearch(prices, size, minRange, maxRange);
69.
70. cout << "Prices sorted in ascending order: ";
71. for (int i = 0; i < size; i++) {

Page 108 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

72. cout << prices[i] << " ";

73. }
74. cout << endl;
75.
76. return 0;
77. }
Output Observed:

Respective Code:
28.
Output Observed:

Page 109 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Stack & Queue using Linked-list

`LAB 7
DATED=: 26/12/24

Lab 7- Stack & Queue using Linked-list

Task 7.1- Stack using link list
Respective Code:
1. #include<iostream>
2. using namespace std;
3. class Node{
4. public:
5. int data;
6. Node* next;
7. Node(int d){
8. data=d;
9. next=NULL;
10. }
11. };
12.
13. class Stack{
14. Node* top;
15. int size;
16. public:
17. Stack(){
18. top=NULL;
19. size=0;
20. }
21. void push(int val){
22. Node* newNode=new Node(val);
23. if(top==NULL){
24. top=newNode;
25. }
26. else{
27. newNode->next=top;
28. top=newNode;
29. }
30. cout<<"\n Value pushed on to stack";
31. ++size;
32. }
33. void display(){
34. if(top==NULL){

Page 110 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

35. cout<<"\n Stack is empty";

36. }
37. else{
38. Node* tmp=top;
39. cout<<"\n Values in Stack: ";
40. while(tmp!=NULL){
41. cout<<"\n "<<tmp->data;
42. tmp=tmp->next;
43. }
44. }
45. }
46. void pop(){
47. if(size==0)
48. cout<<"\n Stack is in underflow state";
49. else{
50. Node* c=top;
51. top=top->next;
52. cout<<"\n Value "<<c->data<<" poped successfully.";
53. delete c;
54. --size;
55. }
56. }
57. void peak(){
58. if(size==0){
59. cout<<"\n Stack is empty";
60. }
61. else{
62. int mid=size/2;
63. cout<<"\n First Value= "<<top->data;
64. Node* tmp=top;
65. Node* MID;
66. int i=1;
67. while(tmp->next!=NULL){
68. tmp=tmp->next;
69. if(i==mid){
70. MID=tmp;
71. }
72. ++i;
73. }
74. cout<<"\n Last value= "<<tmp->data;
75. cout<<"\n Middle value= "<<MID->data;
76. }
77. }
78. void SEARCH(int val){
79. if(top==NULL)
80. cout<<"\n Stack is empty.";

Page 111 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

81. else{
82. Node* c=top;
83. int i=1;
84. while(c->data!=val){
85. c=c->next;
86. ++i;
87. }
88. if(c->data==val)
89. cout<<"\n Value "<<c->data<<" found succeffully at index:
"<<i<<" (index starts from 1)";
90. else
91. cout<<"\n Value "<<val<<" not found";
92. }
93. }
94. void CLEAR(){
95. if(top==NULL)
96. cout<<"\n Stack is already cleared";
97. else{
98. Node* c=top;
99. while(top!=NULL){
100. c=top;
101. top=top->next;
102. delete c;
103. }
104. cout<<"\n Stack cleared successfully...";
105. }
106. }
107. void AVOID_DUP_PUSH(int val){
108. if(top==NULL)
109. cout<<"\n Stack is empty";
110. else{
111. Node* c=top;
112. while(c->data!=val){
113. c=c->next;
114. }
115. if(c->data==val){
116. cout<<"\n This value already exists";
117. }
118. else
119. push(val);
120. }
121. }
122. };
123. int main(){
124. Stack s;
125. cout<<"\n Syed Shahzil Abbas Naqvi- 23018020020\n\n";

Page 112 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

126. s.push(11);
127. s.push(8);
128. s.push(3);
129. s.display();
130. s.display();
131. s.pop();
132. s.SEARCH(8);
133. s.peak();
134. s.AVOID_DUP_PUSH(11);
135. s.CLEAR();
136. s.display();
137. return 0;
138. }
Output Observed:

Task 7.2-Queue using link list

Respective Code:
1. #include<iostream>
2. using namespace std;
3. class Node{
4. public:
5. int data;

Page 113 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

6. Node* next;
7. Node(int d){
8. data=d;
9. next=NULL;
10. }
11. };
12.
13. class Queue{
14. Node* fr,*re;
15. int size;
16. public:
17. Queue(){
18. fr=re=NULL;
19. size=0;
20. }
21. void enque(int val){
22. Node* newNode=new Node(val);
23. if(fr==NULL){
24. fr=re=newNode;
25. }
26. else{
27. re->next=newNode;
28. re=newNode;
29. }
30. cout<<"\n Value: "<<val<<" enqued in Queue";
31. ++size;
32. }
33. void display(){
34. if(fr==NULL){
35. cout<<"\n Queue is empty";
36. }
37. else{
38. Node* tmp=fr;
39. cout<<"\n Values in Queue: ";
40. while(tmp!=NULL){
41. cout<<" "<<tmp->data;
42. tmp=tmp->next;
43. }
44. }
45. }
46. void deque(){
47. if(size==0)
48. cout<<"\n Queue is in underflow state";
49. else{
50. Node* c=fr;
51. fr=fr->next;

Page 114 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

52. cout<<"\n Value "<<c->data<<" dequed successfully.";

53. delete c;
54. --size;
55. }
56. }
57. void peak(){
58. if(size==0){
59. cout<<"\n Stack is empty";
60. }
61. else{
62. int mid=size/2;
63. cout<<"\n First Value= "<<fr->data;
64. Node* tmp=fr;
65. Node* MID;
66. int i=1;
67. while(tmp->next!=NULL){
68. tmp=tmp->next;
69. if(i==mid){
70. MID=tmp;
71. break;
72. }
73. ++i;
74. }
75. cout<<"\n Last value= "<<re->data;
76. cout<<"\n Middle value= "<<MID->data;
77. }
78. }
79. void SEARCH(int val){
80. if(fr==NULL)
81. cout<<"\n Queue is empty.";
82. else{
83. Node* c=fr;
84. int i=1;
85. while(c->data!=val){
86. c=c->next;
87. ++i;
88. }
89. if(c->data==val)
90. cout<<"\n Value "<<c->data<<" found succeffully at index:
"<<i<<" (index starts from 1)";
91. else
92. cout<<"\n Value "<<val<<" not found";
93. }
94. }
95. void CLEAR(){
96. if(fr==NULL)

Page 115 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

97. cout<<"\n Stack is already cleared";

98. else{
99. Node* c=fr;
100. while(fr!=NULL){
101. c=fr;
102. fr=fr->next;
103. delete c;
104. }
105. delete re;
106. cout<<"\n Stack cleared successfully...";
107. }
108. }
109. void AVOID_DUP_ENQUE(int val){
110. if(fr==NULL)
111. cout<<"\n Queue is empty";
112. else{
113. Node* c=fr;
114. while(c->data!=val){
115. c=c->next;
116. }
117. if(c->data==val){
118. cout<<"\n This value already exists";
119. }
120. else
121. enque(val);
122. }
123. }
124. };
125. int main(){
126. cout<<"\n Syed Shahzil Abbas Naqvi- 23018020020\n DS(Lab)-
Manual 7 Q2\n\n";
127. Queue Q;
128. Q.enque(11);
129. Q.enque(20);
130. Q.enque(40);
131. Q.enque(60);
132. Q.enque(35);
133. Q.display();
134. Q.AVOID_DUP_ENQUE(20);
135. Q.deque();
136. Q.peak();
137. Q.deque();
138. Q.SEARCH(11);
139. Q.CLEAR();
140. Q.deque();
141. return 0;

Page 116 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

142. }
Output Observed:

Task 7.3- Real-Time Scenarios

Ordering System
Respective Code:
1. #include<iostream>
2. using namespace std;
3. class Order{
4. public:
5. int OrderNo;
6. string OrderName;
7. Order* next;
8. Order(string O,int On){
9. OrderName=O;
10. OrderNo=On;
11. next=NULL;
12. }
13. };
14.
15. class Ordering_System{
16. Order* fr,*re;
17. int size;
18. public:

Page 117 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

19. Ordering_System(){
20. fr=re=NULL;
21. size=0;
22. }
23. void Take_Order(string Ord){
24. Order* newOrd=new Order(Ord,size+1);
25. if(fr==NULL){
26. fr=re=newOrd;
27. }
28. else{
29. re->next=newOrd;
30. re=newOrd;
31. }
32. cout<<"\n Order has been taken successfully: "<<endl<<" Order
Name: "<<newOrd->OrderName<<" Order Number #00"<<newOrd->OrderNo;
33. ++size;
34. }
35. void display_pending_orders(){
36. if(fr==NULL){
37. cout<<"\n No pending order";
38. }
39. else{
40. Order* tmp=fr;
41. cout<<"\n Orders pending: ";
42. cout<<"\n Order No #\tOrder Name";
43. while(tmp!=NULL){
44. cout<<"\n "<<tmp->OrderNo<<"\t\t"<<tmp->OrderName;
45. tmp=tmp->next;
46. }
47. }
48. }
49. void Complete_Last_Order(){
50. if(size==0)
51. cout<<"\n No last order found to complete ";
52. else{
53. Order* c=fr;
54. fr=fr->next;
55. cout<<"\n Order # "<<c->OrderNo<<" ("<<c->OrderName<<") has
completed successfully.";
56. delete c;
57. --size;
58. }
59. }
60.
61. };
62. int main(){

Page 118 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

63. cout<<"\n Syed Shahzil Abbas Naqvi- 23018020020\n DS(Lab)-Manual 7

Q3(A)\n\n";
64. Ordering_System O;
65. O.Take_Order("Chicken Soup");
66. O.Take_Order("Fried Rice");
67. O.Take_Order("Pizza");
68. O.Take_Order("Karachi Baryani");
69. O.Take_Order("Tikka with Tadori Roti");
70. O.display_pending_orders();
71. O.Complete_Last_Order();
72. O.Complete_Last_Order();
73. O.display_pending_orders();
74.
75.
76.
77. return 0;
78. }
Output Observed:

Page 119 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Priority Task Manager

Respective Code:
1. #include<iostream>
2. using namespace std;
3.
4. class Task {
5. public:
6. string TaskName;
7. char Priority;
8. Task* next;
9.

Page 120 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

10. Task(string T, char P) {

11. TaskName = T;
12. Priority = P;
13. next = NULL;
14. }
15. };
16.
17. class Task_Manager {
18. Task* highFront, * highRear; // Queue for high-priority tasks
19. Task* lowTop; // Stack for low-priority tasks
20. int highSize, lowSize;
21.
22. void Take_HP_Task(string taskName) {
23. Task* newTask = new Task(taskName, 'H');
24. if (highFront == NULL) {
25. highFront = highRear = newTask;
26. } else {
27. highRear->next = newTask;
28. highRear = newTask;
29. }
30. cout << "\n High-priority task (" << taskName << ") has been added.\n";
31. ++highSize;
32. }
33.
34. void Take_LP_Task(string taskName) {
35. Task* newTask = new Task(taskName, 'L');
36. newTask->next = lowTop;
37. lowTop = newTask;
38. cout << "\n Low-priority task (" << taskName << ") has been added.\n";
39. ++lowSize;
40. }
41.
42. void Complete_HP_Task() {
43. if (highSize == 0) {
44. cout << "\n No high-priority tasks to complete.\n";
45. } else {
46. Task* temp = highFront;
47. highFront = highFront->next;
48. cout << "\n High-priority task (" << temp->TaskName << ") completed.\n";
49. delete temp;
50. --highSize;
51. if (highFront == NULL) highRear = NULL; // Reset queue if empty
52. }
53. }
54.
55. void Complete_LP_Task() {

Page 121 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

56. if (lowSize == 0) {
57. cout << "\n No low-priority tasks to complete.\n";
58. } else {
59. Task* temp = lowTop;
60. lowTop = lowTop->next;
61. cout << "\n Low-priority task (" << temp->TaskName << ") completed.\n";
62. delete temp;
63. --lowSize;
64. }
65. }
66.
67. public:
68. Task_Manager() {
69. highFront = highRear = lowTop = NULL;
70. highSize = lowSize = 0;
71. }
72.
73. void Take_Task(string taskName, char priority) {
74. if (priority == 'H' || priority == 'h') {
75. Take_HP_Task(taskName);
76. } else if (priority == 'L' || priority == 'l') {
77. Take_LP_Task(taskName);
78. } else {
79. cout << "\n Invalid priority. Use 'H' for high or 'L' for low.\n";
80. }
81. }
82.
83. void Complete_Task() {
84. if (highSize > 0) {
85. Complete_HP_Task();
86. } else if (lowSize > 0) {
87. Complete_LP_Task();
88. } else {
89. cout << "\n No tasks to complete.\n";
90. }
91. }
92.
93. void display_pending_Tasks() {
94. Task* temp;
95.
96. cout << "\n High-Priority Tasks:\n";
97. if (highFront == NULL) {
98. cout << " No tasks pending.\n";
99. } else {
100. temp = highFront;
101. while (temp != NULL) {

Page 122 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

102. cout << " Task: " << temp->TaskName << "\n";
103. temp = temp->next;
104. }
105. }
106.
107. cout << "\n Low-Priority Tasks:\n";
108. if (lowTop == NULL) {
109. cout << " No tasks pending.\n";
110. } else {
111. temp = lowTop;
112. while (temp != NULL) {
113. cout << " Task: " << temp->TaskName << "\n";
114. temp = temp->next;
115. }
116. }
117. }
118. };
119.
120. int main() {
121. Task_Manager manager;
122. cout << "\n Task Manager by Syed Shahzil:\n";
123.
124.
125. manager.Take_Task("Complete DS Manual", 'H');
126. manager.Take_Task("Research work", 'H');
127. manager.Take_Task("Web surfing", 'L');
128. manager.Take_Task("Screening", 'L');
129.
130. cout << "\n Pending Tasks:";
131. manager.display_pending_Tasks();
132.
133. cout << "\n\n Completing tasks:\n";
134. manager.Complete_Task(); // Completes high-priority task
135. manager.Complete_Task(); // Completes another high-priority task
136. manager.Complete_Task(); // Moves to low-priority task
137. manager.Complete_Task(); // Completes low-priority task
138. manager.Complete_Task(); // No tasks left
139.
140. cout << "\n Final Pending Tasks:";
141. manager.display_pending_Tasks();
142.
143. return 0;
144. }
Output Observed:

Page 123 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 124 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Binary Search Trees

`LAB 8
DATED=: 2/1/25

Lab 8- Binary Search Trees

Task 8.1- Implementing BST with different functionalities
Respective Code:
1. #include<iostream>
2. using namespace std;
3. class Node{
4. public:
5. int data;
6. Node* left,*right;
7. Node(int d){
8. data=d;
9. left=right=NULL;
10. }
11. };
12. class Tree{
13. public:
14. Node* root;
15. int count,space;
16. Tree(){
17. root=NULL;
18. count=0;
19. space=5;
20. }
21. void INSERT(Node* r,int d){
22. Node* newNode=new Node(d);
23. if(root==NULL){
24. root=newNode;
25. ++count;
26. }
27. if(r==NULL){
28. r=root;
29. }
30. else if(newNode->data<r->data){
31. if(r->left==NULL){
32. r->left=newNode;
33. ++count;
34. }

Page 125 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

35. else{
36. INSERT(r->left,newNode->data);
37. }
38. }
39. else if(newNode->data>r->data){
40. if(r->right==NULL){
41. r->right=newNode;
42. ++count;
43. }
44. else{
45. INSERT(r->right,newNode->data);
46. }
47. }
48. else{
49. cout<<"\n The value "<<d<<" already exists in the tree";
50. return;
51. }
52. }
53.
54. Node* SEARCH(Node* Root, int val){
55. if(Root->data==val)
56. return Root;
57. else if(val<Root->data)
58. return SEARCH(Root->left,val);
59. else if(val>Root->data)
60. return SEARCH(Root->right,val);
61. else
62. return NULL;
63. }
64.
65. Node* MINV(Node* r){
66. while(r->left!=NULL)
67. r=r->left;
68. return r;
69. }
70.
71.
72. Node* DEL(Node* r,int val){
73. if(r==NULL) return NULL; //Tree is Empty
74. if(val < r->data) r->left=DEL(r->left,val);
75. else if(val > r->data) r->right=DEL(r->right,val);
76. else {
77. if(r->left==NULL) {
78. Node* tmp=r->right;
79. delete r;
80. return tmp;

Page 126 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

81. }
82. else if(r->right==NULL) {
83. Node* tmp=r->left;
84. delete r;
85. return tmp;
86. }
87. else {
88. Node* tmp=MINV(r->right);
89. r->data=tmp->data;
90. r->right=DEL(r->right,r->data);
91. }
92. return r;
93. }
94. }
95. void preorder(Node* Root){
96. if(Root==NULL)
97. return;
98. else{
99. cout<<"\n "<<Root->data;
100. preorder(Root->left);
101. preorder(Root->right);
102. }
103. }
104. void inorder(Node* Root){
105. if(Root==NULL)
106. return;
107. else{
108. inorder(Root->left);
109. cout<<"\n "<<Root->data;
110. inorder(Root->right);
111. }
112. }
113. void postorder(Node* Root){
114. if(Root==NULL)
115. return;
116. else{
117. postorder(Root->left);
118. postorder(Root->right);
119. cout<<"\n "<<Root->data;
120. }
121. }
122. void PRINT2D(Node* r,int sp){
123. if(r==NULL)
124. return;
125. sp+=space;
126. PRINT2D(r->right,sp);

Page 127 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

127. cout<<endl;
128. for(int i=space;i<sp;i++)
129. cout<<" ";
130. cout<<r->data<<endl;
131. PRINT2D(r->left,sp);
132. }
133. void update(int cv,int nw){// Current value, New value
134. Node* s=SEARCH(root,cv);
135. if(s==NULL){
136. cout<<"\n Current Node with val "<<cv<<" not found to be
replaced with "<<nw;
137. }
138. else{
139. root=DEL(root,s->data);
140. INSERT(root,nw);
141. cout<<"\n Current Node with val "<<cv<<" successfully replaced
with new value: "<<nw;
142. }
143. }
144. };
145.
146. int main(){
147. cout<<"\n Syed Shahzil Abbas --- 23018020020\n";
148.
149. Tree t;
150. t.INSERT(t.root,13);
151. t.INSERT(t.root,53);
152. t.INSERT(t.root,43);
153. t.INSERT(t.root,23);
154. t.INSERT(t.root,3);
155. t.INSERT(t.root,5);
156. t.INSERT(t.root,5);
157.
158.
159. cout<<endl<<" Tree Structure:- ";
160. t.PRINT2D(t.root,5);
161. t.update(3,17);
162.
163. cout<<endl<<"\n Tree Structure:- ";
164. t.PRINT2D(t.root,5);
165.
166. t.root=t.DEL(t.root,13);
167. cout<<endl<<"\n Tree Structure:- ";
168. t.PRINT2D(t.root,5);
169.
170. cout<<"\n ";

Page 128 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

171. return 0;
172. }
Output Observed:

Task 8.2- AI-WildGuess by Syed Shahzil- An application of BST

Respective Code:
1. #include<iostream>
2. #include<string>
3. using namespace std;
4.
5. class Animal {

Page 129 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

6. public:
7. string keyword;
8. string description;
9. Animal* left;
10. Animal* right;
11.
12. Animal(string k, string d) {
13. keyword = k;
14. description = d;
15. left = right = NULL;
16. }
17. };
18.
19. class KEYWORDS_SEARCH {
20. public:
21. Animal* root;
22.
23. KEYWORDS_SEARCH() {
24. root = NULL;
25. }
26.
27. void INSERT(string k, string d) {
28. root = insertHelper(root, k, d);
29. }
30.
31. Animal* SEARCH(string k) {
32. return searchHelper(root, k);
33. }
34.
35. void PRINT2D() {
36. print2DHelper(root, 0);
37. }
38.
39. private:
40. Animal* insertHelper(Animal* node, string k, string d) {
41. if (node == NULL) {
42. return new Animal(k, d);
43. }
44.
45. if (k < node->keyword) {
46. node->left = insertHelper(node->left, k, d);
47. } else if (k > node->keyword) {
48. node->right = insertHelper(node->right, k, d);
49. }
50.
51. return node;

Page 130 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

52. }
53.
54. Animal* searchHelper(Animal* node, string k) {
55. if (node == NULL || node->keyword == k) {
56. return node;
57. }
58.
59. if (k < node->keyword) {
60. return searchHelper(node->left, k);
61. } else {
62. return searchHelper(node->right, k);
63. }
64. }
65.
66. void print2DHelper(Animal* node, int space) {
67. if (node == NULL) return;
68.
69. space += 5;
70. print2DHelper(node->right, space);
71.
72. cout << endl;
73. for (int i = 5; i < space; i++) cout << " ";
74. cout << node->keyword << endl;
75.
76. print2DHelper(node->left, space);
77. }
78. };
79.
80. int main() {
81. KEYWORDS_SEARCH WS;
82.
83. // Insert animal descriptions with keywords
84. WS.INSERT("roar", "It sounds like you're describing a lion, famous for its roar.");
85. WS.INSERT("eatrat", "A cat is known for eating rats. Am I right?");
86. WS.INSERT("tusk", "I think it may be an elephant with large tusks and a heavy
body.");
87. WS.INSERT("jump", "If you're describing an animal that jumps high, it's probably a
kangaroo.");
88. WS.INSERT("king", "A lion is known as the king of the jungle. Am I right?");
89. WS.INSERT("tail", "The tail is a characteristic feature of many animals, like dogs
and horses.");
90. WS.INSERT("whiskers", "Whiskers are often found on cats and some other animals
for sensing.");
91. WS.INSERT("feathers", "Feathers are a distinct feature of birds.");
92. WS.INSERT("hooves", "Hooves are characteristic of animals like horses, cows, and
deer.");

Page 131 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

93. WS.INSERT("mane", "A lion's mane is a prominent feature that makes it stand
out.");
94. WS.INSERT("claws", "Claws are found in many animals like cats and tigers.");
95. WS.INSERT("snout", "A snout is found on animals like pigs and anteaters.");
96. WS.INSERT("shell", "The shell is a notable feature of tortoises and some other
reptiles.");
97. WS.INSERT("wings", "Wings are essential for birds and bats to fly.");
98. WS.INSERT("antlers", "Antlers are typically found on male deer and other related
species.");
99. WS.INSERT("fangs", "Fangs are sharp teeth found in animals like snakes and
tigers.");
100. WS.INSERT("scales", "Scales cover the body of animals like fish and
reptiles.");
101. WS.INSERT("paws", "Paws are a common feature of animals like cats and
dogs.");
102. WS.INSERT("tailfin", "A tailfin helps fish steer while swimming.");
103. WS.INSERT("beak", "A beak is commonly found in birds, adapted for eating
food.");
104.
105. // Chatbot functionality
106. string userInput;
107. cout << "\n Syed Shahzil Abbas --- 23018020020\n";
108. cout << "\n\n WildGuess AI\n";
109.
110. while(userInput!="exit"){
111. cout << " Describe an animal with one word: ";
112. cin >> userInput;
113. Animal* result = WS.SEARCH(userInput);
114. if (result != NULL) {
115. cout <<"\t"<< result->description << endl;
116. } else {
117. cout << "\n Sorry, I couldn't identify the animal based on your input.
Give me one more chance please";
118. }
119. }
120. return 0;
121. }
Output Observed:

Page 132 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 8.3-Video Recommendation System

Respective Code:
1. #include<iostream>
2. #include<string>
3. using namespace std;
4.
5. class Video {
6. public:
7. string Title;
8. string Category;
9. float Duration; // Duration of the video in minutes
10. Video* left;
11. Video* right;
12.
13. Video(string t, string c, float d) {
14. Title = t;
15. Category = c;
16. Duration = d;
17. left = right = NULL;
18. }
19. };
20.
21. class VideoRecommendationSystem {
22. public:
23. Video* root;
24.
25. VideoRecommendationSystem() {
26. root = NULL;
27. }
28.
29. // Insert a new video into the tree
30. void insert(Video* &node, string title, string category, float duration) {
31. if (node == NULL) {
32. node = new Video(title, category, duration);
33. return;
34. }

Page 133 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

35.
36. if (title < node->Title) {
37. insert(node->left, title, category, duration);
38. } else if (title > node->Title) {
39. insert(node->right, title, category, duration);
40. } else {
41. cout << "Video with title '" << title << "' already exists!" << endl;
42. }
43. }
44.
45. void addVideo(string title, string category, float duration) {
46. insert(root, title, category, duration);
47. }
48.
49. // Recommend videos based on category and duration range
50. void recommend(Video* node, string category, float durationRange) {
51. if (node == NULL) return;
52.
53. // Check if the category matches and duration is within range
54. if (node->Category == category && abs(node->Duration - durationRange) <=
5.0) {
55. cout << "Recommended Video: " << node->Title << " (" << node->Category
<< ", "
56. << node->Duration << " mins)" << endl;
57. }
58.
59. // Traverse the left and right subtrees
60. recommend(node->left, category, durationRange);
61. recommend(node->right, category, durationRange);
62. }
63.
64. void recommendVideo(string category, float durationRange) {
65. recommend(root, category, durationRange);
66. }
67. };
68.
69. int main() {
70. VideoRecommendationSystem vrs;
71. cout<<"\n Syed Shahzil--------23018020020";
72. // Sample videos
73. vrs.addVideo("Learning C++", "Education", 15.0);
74. vrs.addVideo("Top 10 Movies", "Entertainment", 10.0);
75. vrs.addVideo("Workout Routine", "Fitness", 20.0);
76. vrs.addVideo("Cooking Pasta", "Food", 12.0);
77.
78. int choice;

Page 134 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

79. string category;

80. float durationRange;
81.
82. do {
83. cout << "\n --- Video Recommendation System ---\n";
84. cout << " 1. Add Video\n";
85. cout << " 2. Get Recommendation\n";
86. cout << " 3. Exit\n";
87. cout << "\n Enter your choice: ";
88. cin >> choice;
89.
90. switch (choice) {
91. case 1: {
92. string title;
93. cout << "\n Enter Title: ";
94. cin.ignore(); // To ignore leftover newline from previous input
95. getline(cin, title);
96. cout << "\n Enter Category: ";
97. getline(cin, category);
98. cout << "\n Enter Duration (mins): ";
99. cin >> durationRange;
100. vrs.addVideo(title, category, durationRange);
101. cout << "\n Video added successfully!\n";
102. break;
103. }
104. case 2: {
105. cout << "\n Enter Category: ";
106. cin.ignore();
107. getline(cin, category);
108. cout << "\n Enter Approximate Duration (mins): ";
109. cin >> durationRange;
110. cout << "\n Finding Recommendation...\n";
111. vrs.recommendVideo(category, durationRange);
112. break;
113. }
114. case 3:
115. cout << "\n Thank you for using the system!\n";
116. break;
117. default:
118. cout << "\n Invalid choice. Try again.\n";
119. }
120. } while (choice != 3);
121.
122. return 0;
123. }

Page 135 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 136 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 137 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Inefficient Sorting Algorithms

`LAB 9
DATED=: 9/1/25

Lab 9- Inefficient Sorting Algorithms

Task 9.1- Bubble, Selection & Insertion Sort using Arrays
Respective Code:
1. #include <iostream>
2. using namespace std;
3.
4. void display(int arr[], int size) {
5. for (int i = 0; i < size; i++) {
6. cout << arr[i] << " ";
7. }
8. cout << endl;
9. }
10.
11. void insertionSort(int arr[], int size) {
12. int i, j, key;
13. for (i = 1; i < size; i++) {
14. key = arr[i];
15. j = i - 1;
16.
17. while (j >= 0 && arr[j] > key) {
18. arr[j + 1] = arr[j];
19. j = j - 1;
20. }
21. arr[j + 1] = key;
22. }
23. cout << "\n After Sorting with Insertion Sort:\n";
24. display(arr, size);
25. }
26.
27. void bubbleSort(int arr[], int size) {
28. for (int i = 0; i < size - 1; i++) {
29. for (int j = 0; j < size - i - 1; j++) {
30. if (arr[j] > arr[j + 1]) {
31. // Swap arr[j] and arr[j+1]
32. swap(arr[j],arr[j+1]);
33. }
34. }

Page 138 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

35. }
36. cout << "\n After Sorting with Bubble Sort:\n";
37. display(arr, size);
38. }
39.
40. void selectionSort(int arr[], int size) {
41. for (int i = 0; i < size - 1; i++) {
42. int minIndex = i;
43.
44. for (int j = i + 1; j < size; j++) {
45. if (arr[j] < arr[minIndex]) {
46. minIndex = j;
47. }
48. }
49.
50. if (minIndex != i) {
51. swap(arr[i],arr[minIndex]);
52. }
53. }
54. cout << "\n After Sorting with Selection Sort:\n";
55. display(arr, size);
56. }
57.
58. int main() {
59. cout<<"\n Syed Shahzil-CS(A)-020-DSAL-M9T9.1";
60. cout<<endl<<endl;
61. int size;
62. cout << "\n How many values do you want to enter? ";
63. cin >> size;
64.
65. int arr[size];
66. cout << "\n Enter values from 1-" <<size<<" with spaces bellow:- \n ";
67.
68. for (int i = 0; i < size; i++) {
69. cin >> arr[i];
70. }
71.
72. cout << "\nBefore Sorting:\n";
73. display(arr, size);
74. cout<<"\n Which Sorting Technique you want to use? ";
75. cout<<"\n\t1-Bubble Sort";
76. cout<<"\n\t2-Selection Sort";
77. cout<<"\n\t3-Insertion Sort";
78. cout<<"\n Enter from 1-3 here:- ";
79. int ch;cin>>ch;
80.

Page 139 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

81. if(ch==1)
82. bubbleSort(arr, size);
83. else if(ch==2)
84. selectionSort(arr, size);
85. else if(ch==3)
86. insertionSort(arr, size);
87. else
88. cout<<"\n You entered wrong choice. Tata Bye bye...";
89. return 0;
90. }
Output Ob-served:

Task 9.2- Bubble, Selection & Insertion Sort using Linked-list

Respective Code:
1. #include<iostream>
2. using namespace std;
3. class Node{
4. public:
5. int data;
6. Node* next;
7. Node(int a){
8. data=a;

Page 140 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

9. next=NULL;
10. }
11. };
12. class L_LIST{
13. public:
14. Node* head,*tail;
15. int size;
16. L_LIST(){
17. head=tail=NULL;
18. size=0;
19. }
20. void add(int val){
21. Node* newnode =new Node(val);
22. if(head==NULL){
23. head=newnode;
24. tail=head;
25. size++;
26. }
27. else{
28. tail->next=newnode;
29. tail=newnode;
30. size++;
31. }
32. }
33. void display(){
34. cout<<"\n Linked list Elements: ";
35. Node* check=head;
36. while(check!=NULL){
37. cout<<endl<<check->data;
38. check=check->next;
39. }
40. cout<<"\n NULL";
41. }
42. Node* SEARCH(int index){
43. if(head==NULL || index>=size )
44. return NULL;
45. else{
46. Node* tmp=head;
47. for(int i=0;i<size;i++){
48. if(i==index){
49. return tmp;
50. break;
51. }
52.
53. tmp=tmp->next;
54. }

Page 141 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

55. }
56. }
57. };
58. void bubbleSort(L_LIST &l){
59. for(int i=0;i<l.size-1;i++){
60. for(int j=0;j<l.size-i-1;j++){
61. Node* t1=l.SEARCH(j);
62. Node* t2=l.SEARCH(j+1);
63. if(t1->data>t2->data){
64. swap(t1->data,t2->data);
65. }
66. }
67. }
68. l.display();
69. }
70. void selectionSort(L_LIST &l) {
71. for (int i = 0; i < l.size - 1; i++) {
72. int minIndex = i;
73. for (int j = i + 1; j < l.size; j++) {
74. Node* t1=l.SEARCH(j);
75. Node* t2=l.SEARCH(minIndex);
76.
77. if (t1->data < t2->data) {
78. minIndex = j;
79. }
80. }
81.
82. if (minIndex != i) {
83. Node* t1=l.SEARCH(i);
84. Node* t2=l.SEARCH(minIndex);
85. swap(t1->data,t2->data);
86. }
87. }
88. cout << "\n After Sorting with Selection Sort:\n";
89. l.display();
90. }
91. void insertionSort(L_LIST &l) {
92. if (l.head == NULL || l.head->next == NULL) return;
93.
94. Node* sorted = NULL; // Start with an empty sorted list
95. Node* current = l.head; // Current node to be inserted
96.
97. while (current != NULL) {
98. Node* next = current->next; // Store the next node
99. if (sorted == NULL || sorted->data >= current->data) {
100. // Insert at the beginning or before the head of the sorted list

Page 142 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

101. current->next = sorted;

102. sorted = current;
103. } else {
104. // Find the correct position in the sorted list
105. Node* temp = sorted;
106. while (temp->next != NULL && temp->next->data < current->data) {
107. temp = temp->next;
108. }
109. // Insert current node after temp
110. current->next = temp->next;
111. temp->next = current;
112. }
113. current = next; // Move to the next node
114. }
115.
116. l.head = sorted; // Update head to point to the sorted list
117. cout << "\n After Sorting with Insertion Sort:\n";
118. l.display();
119. }
120. int main(){
121. L_LIST l1;
122. cout<<"\n Syed Shahzil Abbas-CS(A)-020-DSAL-M9.T9.2";
123. cout<<"\n How many values you want to enter? ";
124. int size;cin>>size;
125. cout<<"\n Enter values with spaces: ";
126.
127. for(int i=0;i<size;i++){
128. int val;cin>>val;
129. l1.add(val);
130. }
131.
132. l1.display();
133. cout<<"\n Which Sorting Technique you want to use? ";
134. cout<<"\n\t1-Bubble Sort";
135. cout<<"\n\t2-Selection Sort";
136. cout<<"\n\t3-Insertion Sort";
137. cout<<"\n Enter from 1-3 here:- ";
138. int ch;cin>>ch;
139.
140. if(ch==1)
141. bubbleSort(l1);
142. else if(ch==2)
143. selectionSort(l1);
144. else if(ch==3)
145. insertionSort(l1);
146. else

Page 143 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

147. cout<<"\n You entered wrong choice. Tata Bye bye...";

148.
149. return 0;
150. }
Output Ob-served:

Page 144 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Task 9.3- Applications of Sorting Algorithms

Leader-Board for Players – Bubble Sort
Respective Code:
1. #include <iostream>
2. #include <string>
3. #include <iomanip>
4.
5. using namespace std;
6.
7. // Player class to store individual player data
8. class Player {
9. public:
10. string name;
11. int score;
12. Player* next;
13.
14. Player(string n, int s) {
15. name = n;
16. score = s;
17. next = NULL;
18. }
19. };
20.
21. // Linked list class to manage the leaderboard
22. class L_LIST {
23. public:
24. Player* head;
25. Player* tail;
26. int size;
27.
28. L_LIST() {
29. head = tail = NULL;
30. size = 0;
31. }
32.
33. // Add a new player to the list
34. void add(string name, int score) {
35. Player* newPlayer = new Player(name, score);
36. if (head == NULL) {
37. head = tail = newPlayer;
38. } else {
39. tail->next = newPlayer;
40. tail = newPlayer;
41. }
42. size++;

Page 145 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

43. }
44.
45. // Display the leaderboard
46. void display() {
47. cout << "\n Leaderboard:";
48. cout << "\n Name\t\tScores";
49.
50. Player* current = head;
51. while (current != NULL) {
52. cout << "\n"<<" " <<setw(15)<< current->name << setw(6) << current-
>score;
53. current = current->next;
54. }
55. cout << "\n __________________________________\n";
56. }
57.
58. // Get a player at a specific index
59. Player* getPlayerAt(int index) {
60. if (index >= size || head == NULL) return NULL;
61.
62. Player* current = head;
63. for (int i = 0; i < index; i++) {
64. current = current->next;
65. }
66. return current;
67. }
68. };
69.
70. // Bubble sort to sort the leaderboard by score
71. void bubbleSort(L_LIST& l) {
72. for (int i = 0; i < l.size - 1; i++) {
73. for (int j = 0; j < l.size - i - 1; j++) {
74. Player* p1 = l.getPlayerAt(j);
75. Player* p2 = l.getPlayerAt(j + 1);
76. if (p1->score < p2->score) { // Sorting in descending order
77. swap(p1->name, p2->name);
78. swap(p1->score, p2->score);
79. }
80. }
81. }
82. cout << "\n Leaderboard sorted by scores in descending order:\n";
83. l.display();
84. }
85.
86. int main() {
87. L_LIST leaderboard;

Page 146 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

88.
89. cout << "\n Welcome to the Player Leaderboard! Developed by Syed Shahzil\n";
90. cout << "\n Enter the number of players: ";
91. int numPlayers;
92. cin >> numPlayers;
93.
94. for (int i = 0; i < numPlayers; i++) {
95. cout << "\n Enter name and score for player " << (i + 1) << ": ";
96. string name;int score; cin >> name >> score;
97. leaderboard.add(name, score);
98. }
99.
100. cout << "\n Initial Leaderboard:";
101. leaderboard.display();
102.
103. cout << "\n Sorting the leaderboard...\n";
104. bubbleSort(leaderboard);
105.
106. return 0;
107. }
108.
109. //Bubble sorting is very efficient algorithm in sorting the leaderboard as it is
small data set and do not require any complexity
Output Ob-served:

Page 147 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 148 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Managing Parcels for Shipping – Selection Sort

Respective Code:
1. #include <iostream>
2. #include <string>
3. #include <iomanip>
4.
5. using namespace std;
6.
7. // Parcel class to store individual parcel data
8. class Parcel {
9. public:
10. string name;
11. double weight;
12. Parcel* next;
13.
14. Parcel(string n, double w) {
15. name = n;
16. weight = w;
17. next = NULL;
18. }
19. };
20.
21. // Linked list class to manage the parcel shipping system
22. class ParcelList {
23. public:
24. Parcel* head;
25. Parcel* tail;
26. int size;
27.
28. ParcelList() {
29. head = tail = NULL;
30. size = 0;
31. }
32.
33. // Add a new parcel to the list
34. void add(string name, double weight) {
35. Parcel* newParcel = new Parcel(name, weight);
36. if (head == NULL) {
37. head = tail = newParcel;
38. } else {
39. tail->next = newParcel;
40. tail = newParcel;
41. }
42. size++;
43. }
44.

Page 149 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

45. // Display the parcel list

46. void display() {
47. cout << "\n Parcel Shipping List:";
48. cout << "\n Name\t\tWeight (kg)";
49. Parcel* current = head;
50. while (current != NULL) {
51. cout << "\n " << setw(15) << current->name << setw(10) << current-
>weight;
52. current = current->next;
53. }
54. cout << "\n __________________________________\n";
55. }
56.
57. // Get a parcel at a specific index
58. Parcel* getParcelAt(int index) {
59. if (index >= size || head == NULL) return NULL;
60.
61. Parcel* current = head;
62. for (int i = 0; i < index; i++) {
63. current = current->next;
64. }
65. return current;
66. }
67. };
68.
69. // Selection sort to sort parcels by weight in ascending order
70. void selectionSort(ParcelList& list) {
71. for (int i = 0; i < list.size - 1; i++) {
72. int minIndex = i;
73. for (int j = i + 1; j < list.size; j++) {
74. Parcel* p1 = list.getParcelAt(minIndex);
75. Parcel* p2 = list.getParcelAt(j);
76. if (p2->weight < p1->weight) {
77. minIndex = j;
78. }
79. }
80. // Swap parcels at index i and minIndex
81. Parcel* p1 = list.getParcelAt(i);
82. Parcel* p2 = list.getParcelAt(minIndex);
83. swap(p1->name, p2->name);
84. swap(p1->weight, p2->weight);
85. }
86. cout << "\n Parcels sorted by weight in ascending order:\n";
87. list.display();
88. }
89.

Page 150 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

90. int main() {

91. ParcelList shippingList;
92.
93. cout << "\n Welcome to the Parcel Shipping Management System! Developed by
Syed Shahzil\n";
94. cout << "\n Enter the number of parcels to be shipped: ";
95. int numParcels;
96. cin >> numParcels;
97.
98. for (int i = 0; i < numParcels; i++) {
99. cout << "\n Enter name and weight (in kg) for parcel " << (i + 1) << ": ";
100. string name; double weight; cin >> name >> weight;
101. shippingList.add(name, weight);
102. }
103.
104. cout << "\n Initial Parcel List:";
105. shippingList.display();
106.
107. cout << "\n Sorting the parcels by weight...\n";
108. selectionSort(shippingList);
109.
110. return 0;
111. }
112. // Selection sort is very efficient in this case. Imagine a shipping system where
different parcels are to be placed, In such case, the lighter parcel will place first and
then others to make the shipping management system more convenient.
Output Ob-served:

Page 151 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Books Placement – Insertion Sort

Respective Code:
1. #include <iostream>
2. #include <string>
3. #include <iomanip>
4.
5. using namespace std;
6.
7. // Book class to store individual book data
8. class Book {
9. public:
10. string name;
11. int releaseYear;

Page 152 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

12. Book* next;

13.
14. Book(string n, int y) {
15. name = n;
16. releaseYear = y;
17. next = NULL;
18. }
19. };
20.
21. // Linked list class to manage the bookshelf
22. class BookList {
23. public:
24. Book* head;
25. Book* tail;
26. int size;
27.
28. BookList() {
29. head = tail = NULL;
30. size = 0;
31. }
32.
33. // Add a new book to the list
34. void add(string name, int releaseYear) {
35. Book* newBook = new Book(name, releaseYear);
36. if (head == NULL) {
37. head = tail = newBook;
38. } else {
39. tail->next = newBook;
40. tail = newBook;
41. }
42. size++;
43. }
44.
45. // Display the book list
46. void display() {
47. cout << "\n Bookshelf:";
48. cout << "\n Name\t\tRelease Year";
49. Book* current = head;
50. while (current != NULL) {
51. cout << "\n " << setw(20) << current->name << setw(15) << current-
>releaseYear;
52. current = current->next;
53. }
54. cout << "\n __________________________________\n";
55. }
56.

Page 153 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

57. // Get a book at a specific index

58. Book* getBookAt(int index) {
59. if (index >= size || head == NULL) return NULL;
60.
61. Book* current = head;
62. for (int i = 0; i < index; i++) {
63. current = current->next;
64. }
65. return current;
66. }
67. };
68.
69. // Insertion sort to sort books by release year in ascending order
70. void insertionSort(BookList& list) {
71. for (int i = 1; i < list.size; i++) {
72. Book* key = list.getBookAt(i);
73. int keyYear = key->releaseYear;
74. string keyName = key->name;
75.
76. int j = i - 1;
77. while (j >= 0) {
78. Book* current = list.getBookAt(j);
79. if (current->releaseYear > keyYear) {
80. Book* next = list.getBookAt(j + 1);
81. next->name = current->name;
82. next->releaseYear = current->releaseYear;
83. } else {
84. break;
85. }
86. j--;
87. }
88. Book* target = list.getBookAt(j + 1);
89. target->name = keyName;
90. target->releaseYear = keyYear;
91. }
92. cout << "\n Books sorted by release year in ascending order:\n";
93. list.display();
94. }
95.
96. int main() {
97. BookList bookshelf;
98.
99. cout << "\n Welcome to the Book Management System! Developed by Syed
Shahzil\n";
100. cout << "\n Enter the number of books: ";
101. int numBooks;

Page 154 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

102. cin >> numBooks;

103.
104. for (int i = 0; i < numBooks; i++) {
105. cout << "\n Enter name and release year for book " << (i + 1) << ": ";
106. string name; int year; cin >> name >> year;
107. bookshelf.add(name, year);
108. }
109.
110. cout << "\n Initial Bookshelf:";
111. bookshelf.display();
112.
113. cout << "\n Sorting the books by release year...\n";
114. insertionSort(bookshelf);
115.
116. return 0;
117. }
118. // Insertion salt is very efficient in this case. Imagine You are placing books on a
shelf based on their release year in ascending order whenever new book arrives it is
inserted in the existing ones using the insertion sort .
119.
Output Ob-served:

Page 155 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Page 156 of 125 Lab Manuals

 Syed shahzil abbas DATA STRUCTURES AND ALGORITHMS

Respective Code:
1.
Output Ob-served:

Page 157 of 125 Lab Manuals