[go: up one dir, main page]
Scribd
Upload
16 views8 pages

data structure task

The document contains multiple C++ programming tasks, including implementations for linked lists to separate positive and negative numbers, delete duplicates in a doubly linked list, convert prefix expressions to infix and postfix, and a priority queue. Each task includes relevant code snippets demonstrating the required functionality. The main function for each task showcases the execution of the implemented methods.

Uploaded by

mustafadarweish136
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
16 views8 pages

data structure task

The document contains multiple C++ programming tasks, including implementations for linked lists to separate positive and negative numbers, delete duplicates in a doubly linked list, convert prefix expressions to infix and postfix, and a priority queue. Each task includes relevant code snippets demonstrating the required functionality. The main function for each task showcases the execution of the implemented methods.

Uploaded by

mustafadarweish136
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/ 8

Name : Mustafa Bakri Muhammed

code : 231335
group : 9

Task : linked list for positive and negative numbers


#include <iostream>
using namespace std;

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

void insert(Node *&head, int val)


{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
}
else
{
Node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
}
}

void pos_or_neg(Node *main, Node *&positive, Node *&negative)


{
Node *curr = main;
while (curr != nullptr)
{
if (curr->data >= 0)
{
insert(positive, curr->data);
}
else
{
insert(negative, curr->data);
}
curr = curr->next;
}
}

void display(Node *head)


{
Node *curr = head;
while (curr != nullptr)
{
cout << curr->data;
if (curr->next != nullptr)
{
cout << " -> ";
}
curr = curr->next;
}
cout << endl;
}

int main()
{
Node *main = nullptr;
insert(main, 5);
insert(main, -3);
insert(main, 10);
insert(main, -7);
insert(main, 2);
insert(main, -1);

cout << "main Linked List: ";


display(main);

Node *positive = nullptr;


Node *negative = nullptr;

pos_or_neg(main, positive, negative);

cout << "Positive Linked List: ";


display(positive);

cout << "Negative Linked List: ";


display(negative);
return 0;
}

Task: linked list to delete duplicate numbers


#include <iostream>
using namespace std;

template<typename T>
class Node {
public:
T data;
Node* next;
Node* prev;
Node(T val) {
this->data = val;
this->next = nullptr;
this->prev = nullptr;
}
};

template<typename T>
class DoublyLinkedList {
Node<T>* head;
Node<T>* last;
public:
DoublyLinkedList() {
head = last = nullptr;
}

void push_back(T val) {


Node<T>* newNode = new Node<T>(val);
if (head == nullptr) {
head = last = newNode;
return;
}
newNode->prev = last;
last->next = newNode;
last = newNode;
}

void deleteByValue(T val) {


if (head == nullptr) return;

Node<T>* curr = head;


while (curr != nullptr) {
if (curr->data == val) {
if (curr == head) {
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
last = nullptr;
}
} else if (curr == last) {
last = last->prev;
last->next = nullptr;
} else {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
}
Node<T>* temp = curr;
curr = curr->next;
delete temp;
} else {
curr = curr->next;
}
}
}

void display() {
if (head == nullptr) return;
Node<T>* curr = head;

cout << curr->data;


while ((curr = curr->next) != nullptr) {
cout << " -> " << curr->data;
}
cout << '\n';
}

void deleteDuplicates() {
if (head == nullptr) return;

Node<T>* curr = head;


while (curr != nullptr) {
Node<T>* runner = curr->next;
while (runner != nullptr) {
if (runner->data == curr->data) {
Node<T>* temp = runner;
runner = runner->next;

if (temp == last) {
// If the node to delete is the last node
last = last->prev;
last->next = nullptr;
} else {
// If the node to delete is in the middle
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
delete temp;
} else {
runner = runner->next;
}
}
curr = curr->next;
}
}
};

int main() {
DoublyLinkedList<int> lst;

lst.push_back(5);
lst.push_back(3);
lst.push_back(5);
lst.push_back(2);
lst.push_back(3);
lst.push_back(1);
cout << "Original Linked List: ";
lst.display();

lst.deleteDuplicates();

cout << "Linked List after deleting duplicates: ";


lst.display();

return 0;
}

Task : prefix to infix and postfix


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

string prefix_infix(string str) {


stack<string> infix;

for (int i = str.length() - 1; i >= 0; i--) {


if (isalnum(str[i])) {
string s(1, str[i]);
infix.push(s);
}

else {
string op(1, str[i]);
string right = infix.top(); infix.pop();
string left = infix.top(); infix.pop();
string s = "(" + left + op + right + ")";
infix.push(s);
}
}
return infix.top();
}

string prefix_postfix(string str) {


stack<string> postfix;

for (int i = str.length() - 1; i >= 0; i--) {


if (isalnum(str[i])) {
string s(1, str[i]);
postfix.push(s);
} else {
string op(1, str[i]);
string left = postfix.top(); postfix.pop();
string right = postfix.top(); postfix.pop();
string s = left + right + op;
postfix.push(s);
}
}
return postfix.top();
}

int main() {
cout << prefix_infix("*+AB-CD") << endl;
cout << prefix_postfix("*+AB-CD") << endl;
return 0;
}

Task: priority queue


#include <iostream>
using namespace std;

class Node {
public:
string Data;
int priority;
Node* next;
Node(string d, int p) {
Data = d;
priority = p;
next = nullptr;
}
};

class PriorityQueue {
Node* head;
int size;

public:
PriorityQueue() {
head = nullptr;
size = 0;
}

~PriorityQueue() {
clear();
}

void clear() {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
size = 0;
}

bool empty() {
return head == nullptr;
}
int Size() {
return size;
}

void display() {
if (empty()) {
cout << "Queue is empty.\n" << endl;
}
Node* temp = head;
while (temp != nullptr) {
cout << "[" << temp->Data << "," << temp->priority << "]";
temp = temp->next;
}
cout << endl;
}

void push(string d, int p) {


Node* newnode = new Node(d, p);
if (empty() || head->priority > p) {
newnode->next = head;
head = newnode;
} else {
Node* temp = head;
while (temp->next != nullptr && temp->next->priority <= p) {
temp = temp->next;
}
newnode->next = temp->next;
temp->next = newnode;
}
size++;
}

string pop() {
if (empty()) {
cout << "empty queue\n";
return "";
} else {
Node* temp = head;
head = head->next;
string ret = temp->Data;
delete temp;
size--;
return ret;
}
}

string top() {
return head->Data;
}
};
int main() {
PriorityQueue pq;
pq.push("ABC", 2);
pq.push("XYZ", 1);
pq.push("PQR", 1);
pq.push("RTZ", 3);
pq.push("CBZ", 2);
pq.push("QQQ", 3);
pq.push("XXX", 4);
pq.push("RRR", 1);
pq.display();

return 0;
}

You might also like