KEMBAR78
Practical File | PDF | Computer Programming | Algorithms And Data Structures
Scribd
Upload
25 views20 pages

Practical File

The document provides implementations of various data structures in C++, including Singly Linked List, Doubly Linked List, Circular Linked List, Stack, Queue, Binary Search Tree (BST), and AVL Tree. Each data structure is defined with methods for insertion, deletion, searching, and displaying elements. The document includes example usage for each data structure in a main function.

Uploaded by

4n9ypsxqmm
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views20 pages

Practical File

The document provides implementations of various data structures in C++, including Singly Linked List, Doubly Linked List, Circular Linked List, Stack, Queue, Binary Search Tree (BST), and AVL Tree. Each data structure is defined with methods for insertion, deletion, searching, and displaying elements. The document includes example usage for each data structure in a main function.

Uploaded by

4n9ypsxqmm
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 20

PRACTICAL FILE

GIRISHA NAGPAL
240773
ECO+CA

### **1. Singly Linked List as an ADT**

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() : head(nullptr) {}

// i. Insert at the beginning


void insertAtBeginning(int x) {
Node* newNode = new Node(x);
newNode->next = head;
head = newNode;
}

// ii. Insert at i-th position


void insertAtPosition(int x, int pos) {
if (pos < 1) {
cout << "Invalid position\n";
return;
}
if (pos == 1) {
insertAtBeginning(x);
return;
}
Node* newNode = new Node(x);
Node* temp = head;
for (int i = 1; i < pos - 1 && temp != nullptr; i++)
temp = temp->next;
if (temp == nullptr) {
cout << "Position out of range\n";
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

// iii. Remove from beginning


void removeFromBeginning() {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}

// iv. Remove from i-th position


void removeFromPosition(int pos) {
if (head == nullptr || pos < 1) {
cout << "Invalid position or empty list\n";
return;
}
if (pos == 1) {
removeFromBeginning();
return;
}
Node* temp = head;
for (int i = 1; i < pos - 1 && temp != nullptr; i++)
temp = temp->next;
if (temp == nullptr || temp->next == nullptr) {
cout << "Position out of range\n";
return;
}
Node* toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
}

// v. Search for an element and return its pointer


Node* search(int x) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == x)
return temp;
temp = temp->next;
}
return nullptr;
}

void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "nullptr\n";
}
};
};

int main() {
SinglyLinkedList list;
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtPosition(15, 2);
list.display();
list.removeFromPosition(2);
list.display();
Node* found = list.search(10);
cout << (found ? "Found 10\n" : "Not found\n");
return 0;
}
```

---

### **2. Doubly Linked List as an ADT**

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
private:
Node* head;
public:
DoublyLinkedList() : head(nullptr) {}
// i. Insert at the beginning
void insertAtBeginning(int x) {
Node* newNode = new Node(x);
if (head == nullptr) {
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}

// ii. Insert at the end


void insertAtEnd(int x) {
Node* newNode = new Node(x);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}

// iii. Remove from the beginning


void removeFromBeginning() {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next;
if (head != nullptr)
head->prev = nullptr;
head->prev = nullptr;
delete temp;
}

// iv. Remove from the end


void removeFromEnd() {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->prev->next = nullptr;
delete temp;
}

void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " <-> ";
temp = temp->next;
}
cout << "nullptr\n";
}
};

int main() {
DoublyLinkedList list;
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtBeginning(5);
list.display();
list.removeFromBeginning();
list.removeFromEnd();
list.display();
return 0;
}
```

---

### **3. Circular Linked List as an ADT**

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() : head(nullptr) {}

// i. Insert an element
void insert(int x) {
Node* newNode = new Node(x);
if (head == nullptr) {
head = newNode;
head->next = head;
return;
}
Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
}

// ii. Remove an element and return its pointer


Node* remove(int x) {
if (head == nullptr)
return nullptr;

Node *temp = head, *prev = nullptr;


do {
if (temp->data == x)
break;
prev = temp;
temp = temp->next;
} while (temp != head);

if (temp->data != x)
return nullptr;

if (temp == head && temp->next == head) {


head = nullptr;
return temp;
}

if (temp == head) {
Node* last = head;
while (last->next != head)
last = last->next;
head = head->next;
last->next = head;
return temp;
}

prev->next = temp->next;
return temp;
}

void display() {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "head\n";
}
};

int main() {
CircularLinkedList list;
list.insert(10);
list.insert(20);
list.insert(30);
list.display();
Node* removed = list.remove(20);
cout << (removed ? "Removed 20\n" : "Not found\n");
list.display();
return 0;
}
```

---
### **4. Stack as an ADT for Prefix/Postfix Expression**

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class Stack {
private:
stack<int> s;
public:
void push(int x) {
s.push(x);
}

int pop() {
if (s.empty()) {
cout << "Stack underflow\n";
return -1;
}
int val = s.top();
s.pop();
return val;
}

bool isEmpty() {
return s.empty();
}

int evaluatePostfix(string exp) {


for (char c : exp) {
if (isdigit(c)) {
push(c - '0');
} else {
int val2 = pop();
int val1 = pop();
switch (c) {
case '+': push(val1 + val2); break;
case '-': push(val1 - val2); break;
case '*': push(val1 * val2); break;
case '/': push(val1 / val2); break;
}
}
}
return pop();
}
};

int main() {
Stack stack;
string postfix = "231*+9-"; // Example: (2 + 3 * 1) - 9
cout << "Postfix evaluation: " << stack.evaluatePostfix(postfix) << "\n";
return 0;
}
```

---

### **5. Queue as an ADT**

#include <iostream>
using namespace std;

class Queue {
private:
static const int MAX = 100;
int arr[MAX];
int front, rear;
public:
Queue() : front(-1), rear(-1) {}
void enqueue(int x) {
if (rear == MAX - 1) {
cout << "Queue overflow\n";
return;
}
if (front == -1)
front = 0;
arr[++rear] = x;
}

int dequeue() {
if (front == -1 || front > rear) {
cout << "Queue underflow\n";
return -1;
}
return arr[front++];
}

void display() {
if (front == -1 || front > rear) {
cout << "Queue is empty\n";
return;
}
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
cout << "\n";
}
};

int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
cout << "Dequeued: " << q.dequeue() << "\n";
q.display();
return 0;
}
```

---

### **6. Binary Search Tree (BST) as an ADT**

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BST {
private:
Node* root;
Node* insertRec(Node* root, int x) {
if (root == nullptr)
return new Node(x);
if (x < root->data)
root->left = insertRec(root->left, x);
else if (x > root->data)
root->right = insertRec(root->right, x);
return root;
}

Node* findMin(Node* root) {


while (root->left != nullptr)
root = root->left;
return root;
}

Node* deleteRec(Node* root, int x) {


if (root == nullptr)
return nullptr;
if (x < root->data)
root->left = deleteRec(root->left, x);
else if (x > root->data)
root->right = deleteRec(root->right, x);
else {
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRec(root->right, temp->data);
}
return root;
}

Node* searchRec(Node* root, int x) {


if (root == nullptr || root->data == x)
return root;
if (x < root->data)
return searchRec(root->left, x);
return searchRec(root->right, x);
}

void preorderRec(Node* root) {


if (root == nullptr)
return;
cout << root->data << " ";
preorderRec(root->left);
preorderRec(root->right);
}

void inorderRec(Node* root) {


if (root == nullptr)
return;
inorderRec(root->left);
cout << root->data << " ";
inorderRec(root->right);
}

void postorderRec(Node* root) {


if (root == nullptr)
return;
postorderRec(root->left);
postorderRec(root->right);
cout << root->data << " ";
}

public:
BST() : root(nullptr) {}

void insert(int x) {
root = insertRec(root, x);
}

void remove(int x) {
root = deleteRec(root, x);
}

Node* search(int x) {
return searchRec(root, x);
}

void preorder() {
preorderRec(root);
cout << "\n";
}

void inorder() {
inorderRec(root);
cout << "\n";
}

void postorder() {
postorderRec(root);
cout << "\n";
}
};

int main() {
BST tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
cout << "Preorder: ";
tree.preorder();
cout << "Inorder: ";
tree.inorder();
cout << "Postorder: ";
tree.postorder();
tree.remove(30);
cout << "After deletion, Inorder: ";
tree.inorder();
return 0;
}
```

---

### **7. AVL Tree Insert and Search**

#include <iostream>
using namespace std;

class Node {
public:
int data, height;
Node* left;
Node* right;
Node(int val) : data(val), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
private:
Node* root;

int height(Node* node) {


return node ? node->height : 0;
}

int balanceFactor(Node* node) {


return node ? height(node->left) - height(node->right) : 0;
}

void updateHeight(Node* node) {


if (node)
node->height = max(height(node->left), height(node->right)) + 1;
}

Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
}

Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}

Node* insertRec(Node* root, int x) {


if (root == nullptr)
return new Node(x);

if (x < root->data)
root->left = insertRec(root->left, x);
else if (x > root->data)
root->right = insertRec(root->right, x);
else
return root;

updateHeight(root);
int balance = balanceFactor(root);

// Left Left
if (balance > 1 && x < root->left->data)
return rightRotate(root);
// Right Right
if (balance < -1 && x > root->right->data)
return leftRotate(root);

// Left Right
if (balance > 1 && x > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Left
if (balance < -1 && x < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

Node* searchRec(Node* root, int x) {


if (root == nullptr || root->data == x)
return root;
if (x < root->data)
return searchRec(root->left, x);
return searchRec(root->right, x);
}

void inorderRec(Node* root) {


if (root == nullptr)
return;
inorderRec(root->left);
cout << root->data << " ";
inorderRec(root->right);
}

public:
AVLTree() : root(nullptr) {}

void insert(int x) {
root = insertRec(root, x);
}

Node* search(int x) {
return searchRec(root, x);
}

void inorder() {
inorderRec(root);
cout << "\n";
}
};

int main() {
AVLTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
cout << "Inorder traversal: ";
tree.inorder();
Node* found = tree.search(25);
cout << (found ? "Found 25\n" : "Not found\n");
return 0;
}

You might also like