ASSIGNMENT 1(MS Teams)

MALHAAR PRANAVKUMAR BAROT

23BIT0049

Question 1: Write a program to get and display student details (regno, name, cgpa and
grade ) using queue (linked list)

Code:

#include<iostream>
using namespace std;
class node{
public:
string redg_no;
string name;
float cgpa;
char grade;
node* next;
public:
node(string s1,string s2,float f1,char c1){
redg_no = s1;
name = s2;
cgpa = f1;
grade = c1;
next = NULL;

}
};
class que{
public:
node* top;
node* end;
int size;
public:
que(){
top=NULL;
end=NULL;
size=0;
}
void enque(string rd,string nm,float cg,char grd){
if(top==NULL && end==NULL){
node* temp = new node(rd,nm,cg,grd);
end = temp;
top = temp;
size++;
}
else{
node* temp = new node(rd,nm,cg,grd);
 top->next = temp;
top = temp;
size++;
}
}
void deque(){
if(end==NULL){
cout<<"\nThe queue is underflow\n";
}
else{
node* temp = end;
end = end->next;
delete(temp);
size--;
cout<<"Dequeue sucessful"<<endl;
}
}
void print_que(){
if(end==NULL){
cout<<"\nThe queue is empty\n";
}
else{
node* temp = end;
while(temp!=top){
cout<<"\n";
cout<<temp->redg_no<<"\t"<<temp->name<<"\t"<<temp-
>cgpa<<"\t"<<temp->grade<<endl;
temp = temp->next;
}
cout<<"\n";
cout<<temp->redg_no<<"\t"<<temp->name<<"\t"<<temp-
>cgpa<<"\t"<<temp->grade<<endl;
cout<<"\n";
}
}
};
int main(){
que q1;
int i=-1;
while(i!=4){
cout<<"1.Enqueue\n2.Dequeue\n3.Print data\n4.Exit\n";
cin>>i;
switch(i){
case 1:{
string sr;
string sn;
float cgp;
char gr;
cout<<"\nEnter the Redg No: ";
cin>>sr;
cout<<"\nEnter name: ";
 cin>>sn;
cout<<"\nEnter the CGPA: ";
cin>>cgp;
cout<<"\nEnter the grade: ";
cin>>gr;
q1.enque(sr,sn,cgp,gr);
break;
}
case 2:
q1.deque();
break;
case 3:
q1.print_que();
break;
case 4:
cout<<"Thank You!"<<endl;
break;
}
}
return 0;
}
Output:
Question 2: Write a program to implement insertion and deletion of node in a specific
position using circularly singly linked list.

Code:

#include<iostream>
#include<vector>
using namespace std;
class node{
public:
int data;
node* next;
public:
node(int data1,node* next1){
data = data1;
next = next1;
}
node(int data1){
data = data1;
next = NULL;
}
};
node* arr_to_ll(vector<int>arr){
node* head = new node(arr[0]);
node* mover = head;
for(int i=1;i<arr.size();i++){
node* temp = new node(arr[i]);
mover -> next = temp;
mover = temp;
}
mover->next = head;
return head;
}
node* insert_at_kth(node* head,int num,int pos){
if(head==NULL){
return new node(num);
}
else{
if(head->next==NULL && pos!=1){
return head;
}
else{
if(pos==1){
node* ins = new node(num);
node* temp = head;
while(temp->next!=head){
temp = temp->next;
}
temp->next = ins;
ins->next = head;
 return ins;
}
else{
int i=1;
node* temp =head;
while(i<pos-1){
temp = temp->next;
i++;
}
node* ins = new node(num);
ins->next = temp->next;
temp->next = ins;
return head;
}
}
}
}
node* del_kth(node* head,int pos){
if(head==NULL || (head->next && pos==1)){
return NULL;
}
if(head->next==NULL && pos!=1){
return head;
}
else{
int i=1;
node* temp = head;
while(i<pos-1){
temp = temp->next;
i++;
}
node* val = temp->next->next;
delete(temp->next);
temp->next = val;
return head;
}
}
void print_cll(node* head){
cout<<"\n";
if(head==NULL){
cout<<"";
}
else if(head->next==NULL){
cout<<head->data;
}
else{
node* temp = head;
while(temp->next!=head){
cout<<temp->data<<"\t";
temp = temp->next;
}
 cout<<temp->data;
}
cout<<"\n";
}
int main(){
vector<int>ip;
int cnt;
cout<<"Enter the number of element array ";
cin>>cnt;
for(int i=0;i<cnt;i++){
int temp;
cout<<"\nEnter the element: ";
cin>>temp;
ip.push_back(temp);
}
node* head;
node* head_n;
int i=-1;
while(i!=5){
cout<<"\n1.Creat an circular linked list from array\n2.Insert at any
position\n3.Delete from any position\n4.Print LL\n5.End"<<endl;
cin>>i;
switch(i){
case 1:
head = arr_to_ll(ip);
head_n = head;
break;
case 2:
int nm;
int ps;
cout<<"\nEnter the number to be inserted: ";
cin>>nm;
cout<<"\nEnter the position at which number be inserted: ";
cin>>ps;
head_n = insert_at_kth(head,nm,ps);
break;
case 3:
int po_del;
cout<<"\nEnter the position of number to be deleted: ";
cin>>po_del;
head_n = del_kth(head,po_del);
break;
case 4:
print_cll(head_n);
break;
case 5:
cout<<"\nThank You!"<<endl;
break;
}
}
return 0;
}

Output:
Name: Malhaar Pranavkumar Barot
Redg No: 23BIT0049
DSA Theory DA-Part 2

Code 1:
#include<iostream>
#include<stack>
using namespace std;
class que{
stack <int> stk1;
stack <int> stk2;
public:
void enqueue(int n){
stk1.push(n);
}
void dequeue(){
if(stk1.empty()){
cout<<"The queue is in uunderflow";
}
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
cout<<"The popped elemen is: "<<stk2.top()<<endl;
stk2.pop();
while(!stk2.empty()){
stk1.push(stk2.top());
stk2.pop();
}
}
void print(){
cout<<"\n";
if(stk1.empty()){
cout<<"Queue is empty"<<endl;
}
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
while(!stk2.empty()){
stk1.push(stk2.top());
cout<<stk2.top()<<"\t";
stk2.pop();
}
cout<<"\n";
}
};
int main(){
que q1;
int i=0;
while(i!=4){
 cout<<"1.To Enqueue\n2.To dequeue\n3.To print que"<<endl;
cin>>i;
switch(i){
case 1:
int t;
cout<<"\nEnter the number of elements to insert: ";
cin>>t;
for(int i=0;i<t;i++){
int temp;
cout<<"\nEnter the element: ";
cin>>temp;
q1.enqueue(temp);
}
break;
case 2:
q1.dequeue();
break;
case 3:
q1.print();
break;
}
}
}
Output:
Code 2:
#include<iostream>
using namespace std;
class node{
public:
int data;
node* both;
public:
node(){
data = 0;
both = NULL;
}
node(int data1){
data = data1;
both = NULL;
}
};
node* head=nullptr;
node* mover=nullptr;
void creat_ll(){
node* prev=nullptr;
int i=0;
cout<<"\nEnter the number of elements: ";
cin>>i;
for(int j=0;j<i;j++){
int ip;
cout<<"Enter the number: ";
cin>>ip;
node* temp = new node(ip);
if(head==NULL){
head = temp;
mover = head;
}
else{
mover->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev)
^ reinterpret_cast<uintptr_t>(temp));
temp->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(mover)^reinterpret_cast<uintptr
_t>(nullptr));
prev = mover;
mover = temp;
}
}
}
void print_ll(){
cout<<"\n";
node* prev=nullptr;
node* temp = head;
while(temp!=NULL){
cout<<temp->data<<"\t";
 node* next = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev) ^
reinterpret_cast<uintptr_t>(temp->both));
prev = temp;
temp = next;
}
cout<<"\n";
}
void insertion_at_kth(int num,int pos){
if(pos==1){
node* ins = new node(num);
ins->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(head)^reinterpret_cast<uintptr_
t>(nullptr));
if (head != nullptr) {
head->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(ins) ^
reinterpret_cast<uintptr_t>(head->both));
}
head = ins;
}
else{
int cnt=0;
node* prev = nullptr;
node* temp = head;
while(temp!=NULL){
cnt++;
if(cnt==pos-1){
break;
}
node* next = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev) ^
reinterpret_cast<uintptr_t>(temp->both));
prev = temp;
temp = next;
}
node* next = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev) ^
reinterpret_cast<uintptr_t>(temp->both));
if(next==NULL){
node* ins = new node(num);
temp->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev) ^
reinterpret_cast<uintptr_t>(ins));
ins->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(temp)^reinterpret_cast<uintptr_
t>(nullptr));
}
else{
node* nnext = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(temp) ^
reinterpret_cast<uintptr_t>(next->both));
node* ins = new node(num);
temp->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev) ^
reinterpret_cast<uintptr_t>(ins));
 ins->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(temp)^reinterpret_cast<uintptr_
t>(next));
next->both
=reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(ins)^reinterpret_cast<uintptr_
t>(nnext));
}
}
}
void deletion_at_kth(int pos){
node* prev = nullptr;
if(pos==1){
node* temp = head;
node* next = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(head-
>both) ^ reinterpret_cast<uintptr_t>(nullptr));
head = next;
if (head != nullptr) {
node* next_next =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(head->both) ^
reinterpret_cast<uintptr_t>(temp));
head->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(next_next) ^
reinterpret_cast<uintptr_t>(nullptr));
}
cout<<"\nThe deleted element is: "<<temp->data<<endl;
delete temp;
}
else{
int cnt=0;
node* temp = head;
while(temp!=NULL){
cnt++;
if(cnt==pos-1){
break;
}
node* next = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev)
^ reinterpret_cast<uintptr_t>(temp->both));
prev = temp;
temp = next;
}
node* next_node = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev)
^ reinterpret_cast<uintptr_t>(temp->both));
if((next_node->both)==temp){
temp->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev)
^ reinterpret_cast<uintptr_t>(nullptr));
cout<<"\nThe deleted element is: "<<next_node->data<<endl;
delete(next_node);
}
else{
 node* next_next_node =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(temp) ^
reinterpret_cast<uintptr_t>(next_node->both));
temp->both = reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(prev)
^ reinterpret_cast<uintptr_t>(next_next_node));
node* next_next_next_node =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(next_node) ^
reinterpret_cast<uintptr_t>(next_next_node->both));
next_next_node->both =
reinterpret_cast<node*>(reinterpret_cast<uintptr_t>(temp) ^
reinterpret_cast<uintptr_t>(next_next_next_node));
cout<<"\nThe deleted element is: "<<next_node->data<<endl;
delete(next_node);
}
}

}
int main(){
int i=0;
while(i!=5){
cout<<"1.To creat base linked list\n2.To insert at a given position\n3.To
delete at a postion\n4.Print LL\n5.End"<<endl;
cin>>i;
switch(i){
case 1:
creat_ll();
break;
case 2:
int p;
int n;
cout<<"Enter the element: ";
cin>>n;
cout<<"Enter the position: ";
cin>>p;
insertion_at_kth(n,p);
break;
case 3:
int ip;
cout<<"Enter the postion: ";
cin>>ip;
deletion_at_kth(ip);
break;
case 4:
print_ll();
break;
case 5:
break;
}
}
return 0;
}
Output:
Code 3:
#include<iostream>
using namespace std;
class node{
public:
int data;
node* next;
public:
node(int data1){
data = data1;
next = NULL;
}
};
node* head;
node* prev_node;
void ins_ll(node* head,int num){
if(head==nullptr){
node* ins = new node(num);
prev_node->next = ins;
return;
}
prev_node = head;
ins_ll(head->next,num);
}
void creat_ll(){
int n;
cout<<"Enter the number of elements: ";
cin>>n;
for(int i=0;i<n;i++){
int temp;
cout<<"Enter the element: ";
cin>>temp;
if(head==NULL){
node* ins = new node(temp);
head = ins;
}
else{
ins_ll(head,temp);
}
}
}
void print_ll(node* head){
if(head==nullptr){
return;
}
cout<<head->data<<"\t";
print_ll(head->next);
}
node* pvr_node=NULL;
void del_ll(node* head){
if(head->next==NULL){
 pvr_node->next = NULL;
cout<<"The deleted node is: "<<head->data<<endl;
delete(head);
return;
}
pvr_node = head;
del_ll(head->next);
}
int main(){
int c=0;
while(c!=4){
cout<<"1.To creat and add elements to linked list\n2.To delete a
node\n3.Print\n4.End\n";
cin>>c;
switch(c){
case 1:
creat_ll();
break;
case 2:
del_ll(head);
break;
case 3:
cout<<"\n";
print_ll(head);
cout<<"\n";
break;
case 4:
break;

}
}
return 0;
}
Output:
MALHAAR PRANAVKUMAR BAROT
23BIT0049
DSA THEORY DA – PART3

1.BUBBLE SORT
#include<iostream>
using namespace std;
class node{
public:
int data;
node* next;
public:
node(int i1){
data = i1;
next=NULL;
}
};
node* head=NULL;
node* mover = NULL;
int n;
void take_input(){
cout<<"Enter the number of input: ";
cin>>n;
for(int i=1;i<=n;i++){
int x;
cout<<"Enter the entry "<<i<<": ";
cin>>x;
if(head==NULL){
node* temp = new node(x);
head = temp;
mover = head;
}
else{
node* temp = new node(x);
mover->next = temp;
mover = temp;
}
}
}
void print_ll(){
node* temp = head;
while(temp!=NULL){
cout<<temp->data<<"\t";
temp = temp->next;
}
}
void bubble_sort(){
for(int i=0;i<n-1;i++){
int cnt=0;
node* j = head;
node* k = head->next;
 while(j!=NULL && k!=NULL){
if((k->data)<=(j->data)){
swap((k->data),(j->data));
cnt++;
}
j = j->next;
k = k->next;
}
if(cnt==0){
break;
}
}
}
int main(){
take_input();
cout<<"\nUnsorted Input: ";
print_ll();
bubble_sort();
cout<<"\nBubble Sorted Oputut: ";
print_ll();
}
OP:

2.INSERTION SORT
#include <iostream>
using namespace std;
class node {
public:
int data;
node* next;
node(int i1) {
data = i1;
next = nullptr;
}
};
node* head = nullptr;
void take_input() {
int n;
cout << "Enter the number of inputs: ";
 cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cout << "Enter the entry " << i << ": ";
cin >> x;
if (head == nullptr) {
head = new node(x);
} else {
node* temp = new node(x);
node* mover = head;
while (mover->next != nullptr) {
mover = mover->next;
}
mover->next = temp;
}
}
}
void print_ll() {
node* temp = head;
while (temp != nullptr) {
cout << temp->data << "\t";
temp = temp->next;
}
cout << endl;
}
void insertion_sort() {
if (head == nullptr) return;

node* sorted = nullptr;

node* current = head;
while (current != nullptr) {
node* next = current->next;
if (sorted == nullptr || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
}
else {
node* temp = sorted;
while (temp->next != nullptr && temp->next->data < current->data) {
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
current = next;
}
head = sorted;
}
int main() {
take_input();
cout << "\nUnsorted Input: ";
 print_ll();
insertion_sort();
cout << "\nInsertion Sorted Output: ";
print_ll();
return 0;
}
OP:

3.SELECTION SORT
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
Node* head = nullptr;
Node* mover = nullptr;
int n;
void take_input() {
cout << "Enter the number of inputs: ";
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cout << "Enter entry " << i << ": ";
cin >> x;
Node* temp = new Node(x);
if (head == nullptr) {
head = temp;
mover = head;
} else {
mover->next = temp;
 mover = temp;
}
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void selectionSort() {
if (head == nullptr) {
cout << "Empty list" << endl;
return;
}
Node* temp = head;
while (temp != nullptr) {
Node* minNode = temp;
Node* temp1 = temp->next;
while (temp1 != nullptr) {
if (temp1->data < minNode->data) {
minNode = temp1;
}
temp1 = temp1->next;
}
if (minNode != temp) {
int swap = temp->data;
temp->data = minNode->data;
minNode->data = swap;
}
temp = temp->next;
}
}
int main() {
take_input();
cout << "\nOriginal list:\n";
display();
selectionSort();
cout << "\nSorted list:\n";
display();
return 0;
}

OP:
4.MERGE SORT
#include<iostream>
using namespace std;
class node{
public:
int data;
node* next;
node(int data1){
data = data1;
next = NULL;
}
};
node* find_mid(node* h){
node* s=h;
node* f = h->next;
while(f!=NULL && f->next!=NULL){
s = s->next;
f = f->next->next;
}
return s;
}
node* merge(node* h1,node* h2){
if(h1==NULL) return h2;
else if(h2==NULL) return h1;
else{
node* h3 = new node(-1);
node* t=h3;
while(h1!=NULL && h2!=NULL){
if(h1->data<h2->data){
t->next = h1;
t = h1;
h1 = h1->next;
}
 else{
t->next = h2;
t=h2;
h2 = h2->next;
}
}
if(h1!=NULL){
t->next = h1;
}
else if(h2!=NULL){
t->next = h2;
}
return h3->next;
}
}
node* mergeSort(node* hd){
if(hd==NULL || hd->next==NULL){
return hd;
}
node* mid = find_mid(hd);
node* left = hd;
node* right = mid->next;
mid->next = NULL;
node* left_sorted = mergeSort(left);
node* right_sorted = mergeSort(right);
node* final = merge(left_sorted,right_sorted);

return final;
}
node* head1=NULL;
node* head2=NULL;
node* mover1=NULL;
node* mover2=NULL;
void creat_ll1(){
int arr[5]={1,13,7,6,5};
head1 = new node(arr[0]);
mover1 = head1;
for(int i=1;i<5;i++){
node* temp = new node(arr[i]);
mover1->next = temp;
mover1 = temp;
}
}
void print_ll(node* h){
node* temp = h;
while(temp!=NULL){
cout<<temp->data<<"\t";
temp = temp->next;
}
}
int main(){
 creat_ll1();
print_ll(head1);
cout<<"\n";
node* head3 = mergeSort(head1);
print_ll(head3);
}
OP:

5.BINARY SEARCH
#include <iostream>
using namespace std;
class node {
public:
int data;
node* next;
node(int i1) {
data = i1;
next = nullptr;
}
};
node* head = nullptr;
int n;
void take_input() {
cout << "Enter the number of input: ";
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cout << "Enter the entry " << i << ": ";
cin >> x;
if (head == nullptr) {
head = new node(x);
} else {
node* temp = new node(x);
node* mover = head;
while (mover->next != nullptr) {
mover = mover->next;
}
mover->next = temp;
}
}
}
void print_ll() {
node* temp = head;
while (temp != nullptr) {
 cout << temp->data << "\t";
temp = temp->next;
}
cout << endl;
}
void bubble_sort() {
for (int i = 0; i < n - 1; i++) {
int cnt = 0;
node* j = head;
node* k = head->next;
while (j != nullptr && k != nullptr) {
if (k->data <= j->data) {
swap(k->data, j->data);
cnt++;
}
j = j->next;
k = k->next;
}
if (cnt == 0) {
break;
}
}
}
node* find_mid() {
node* slow = head;
node* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
int binarySearch(int inp, node* hd) {
if (hd == nullptr) return -1;
node* mid = find_mid();
if (mid == nullptr) return -1;
if (inp > mid->data) {
node* rightHead = mid->next;
return binarySearch(inp, rightHead);
}
else if (inp < mid->data) {
node* leftHead = head;
node* current = head;
while (current != mid) {
if (current->next == mid) {
current->next = nullptr;
break;
}
current = current->next;
}
return binarySearch(inp, leftHead);
 } else {
return mid->data;
}
}

int main() {
take_input();
cout << "\nUnsorted Input: ";
print_ll();
bubble_sort();
cout << "\nBubble Sorted Output: ";
print_ll();
int s_num;
cout << "\nEnter the number to be searched: ";
cin >> s_num;
int op = binarySearch(s_num, head);
if (op == -1) {
cout << "The given input number not found" << endl;
} else {
cout << "The given input number found" << endl;
}
return 0;
}

OP: