From 884a3cc6d873053b72855107f9f5d95d7ad1706d Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 24 Nov 2022 20:07:46 +0200 Subject: [SDP/E1] Added work from today's exam --- .../Structures and data algorithms/Exam 1/ex1.cpp | 94 ++++++++++++++++++++++ .../Structures and data algorithms/Exam 1/ex2.cpp | 56 +++++++++++++ .../Structures and data algorithms/Exam 1/ex3.cpp | 55 +++++++++++++ 3 files changed, 205 insertions(+) create mode 100644 Year 2/Structures and data algorithms/Exam 1/ex1.cpp create mode 100644 Year 2/Structures and data algorithms/Exam 1/ex2.cpp create mode 100644 Year 2/Structures and data algorithms/Exam 1/ex3.cpp diff --git a/Year 2/Structures and data algorithms/Exam 1/ex1.cpp b/Year 2/Structures and data algorithms/Exam 1/ex1.cpp new file mode 100644 index 0000000..f309dcb --- /dev/null +++ b/Year 2/Structures and data algorithms/Exam 1/ex1.cpp @@ -0,0 +1,94 @@ +#include + +template +struct Node { + T value; + Node* next; + + Node(T value, Node* next = nullptr) : value(value), next(next) {} +}; + +template +struct Pair { + T left; + U right; + + Pair(T left, U right) : left(left), right(right) {} +}; + +#define PII Pair +#define NPII Node*> + +template +void reverseSublist(Node*& list, int start, int end) { + Node* prev = nullptr; // element before first in range + Node* iter = list; // first element in range + while (start > 0) { + prev = iter; + iter = iter->next; + start--; + end--; + } + Node* eter = iter; // last element in range + Node* next = nullptr; // element after last in range + for (int i = 0; i < end; i++) { + eter = eter->next; + next = eter->next; + } + + prev->next = eter; + Node* last; + Node* prevLast; + while (end > 0) { + prevLast = iter; + last = iter->next; + for (int i = 1; i < end; i++) { + prevLast = prevLast->next; + last = last->next; + } + last->next = prevLast; + end--; + } + prevLast->next = next; +} + +template +void reverseSublists(Node*& list, NPII* intervals) { + while (intervals != nullptr) { + reverseSublist(list, intervals->value->left, intervals->value->right); + intervals = intervals->next; + } +} + +template +void print(Node* list) { + while (list != nullptr) { + std::cout << list->value << " "; + list = list->next; + } + std::cout << std::endl; +} + +int main() { + NPII* intervals = new NPII(new PII(1, 3), new NPII(new PII(2, 5), new NPII(new PII(5, 6)))); + Node* list = new Node(11, new Node(4, new Node(3, new Node(7, new Node(13, new Node(4, new Node(5))))))); + + print(list); + reverseSublists(list, intervals); + print(list); + + NPII* temp = nullptr; + while (intervals != nullptr) { + delete intervals->value; + temp = intervals->next; + delete intervals; + intervals = temp; + } + + Node* temp1 = nullptr; + while (list != nullptr) { + temp1 = list->next; + delete list; + list = temp1; + } +} diff --git a/Year 2/Structures and data algorithms/Exam 1/ex2.cpp b/Year 2/Structures and data algorithms/Exam 1/ex2.cpp new file mode 100644 index 0000000..99128d0 --- /dev/null +++ b/Year 2/Structures and data algorithms/Exam 1/ex2.cpp @@ -0,0 +1,56 @@ +#include + +template +struct Node { + T value; + Node* next; + + Node(T value, Node* next = nullptr) : value(value), next(next) {} +}; + + +bool makeTotal(Node* head) { + int len = 0; + for (Node* i = head; i != nullptr; i = i->next) + len++; + if (len < 3) return false; + + Node* prev = head; + Node* next = head->next->next; + head = head->next; + bool balanced = true; + while (next != nullptr) { + if (prev->value + next->value != head->value) { + balanced = false; + break; + } + + prev = prev->next; + head = head->next; + next = next->next; + } + + if (!balanced) { + prev->next = next; + delete head; + makeTotal(prev); + } + return balanced; +} + +int main() { + // Node* list = new Node(1, new Node(-4, new Node(-5, new Node(-1, new Node(4))))); + Node* list = new Node(10, new Node(-5, new Node(-5, new Node(-15, new Node(2))))); + + std::cout << makeTotal(list) << std::endl; + for (Node* i = list; i != nullptr; i = i->next) + std::cout << i->value << " "; + std::cout << std::endl; + + Node* tmp = nullptr; + while (list != nullptr) { + tmp = list->next; + delete list; + list = tmp; + } +} diff --git a/Year 2/Structures and data algorithms/Exam 1/ex3.cpp b/Year 2/Structures and data algorithms/Exam 1/ex3.cpp new file mode 100644 index 0000000..d1f0a31 --- /dev/null +++ b/Year 2/Structures and data algorithms/Exam 1/ex3.cpp @@ -0,0 +1,55 @@ +#include +#include +#include +#include + +bool readAndDelete(std::stack& st, std::string& word) { + std::queue backlog; + int index = 0; + while (!st.empty()) { + if (st.top() == word[index]) + index++; + else + backlog.push(st.top()); + st.pop(); + } + + while (!backlog.empty()) { + st.push(backlog.front()); + backlog.pop(); + } + + return index == word.length(); +} + +void printStack(std::stack& st) { + // Знам че принтирането е в обратен ред, бързам! + while (!st.empty()) { + std::cout << st.top() << std::endl; + st.pop(); + } + std::cout << std::endl; +} + +int main() { + std::string word1 = "mom"; + std::stack st1; + st1.push('m'); + st1.push('o'); + st1.push('o'); + st1.push('f'); + st1.push('m'); + std::cout << readAndDelete(st1, word1) << std::endl; + printStack(st1); + + + std::string word2 = "car"; + std::stack st2; + st2.push('y'); + st2.push('a'); + st2.push('d'); + st2.push('c'); + st2.push('c'); + std::cout << readAndDelete(st2, word2) << std::endl; + printStack(st2); +} -- cgit v1.3.1-26-gb76a