Summary Files Commits Branches @commit @diff @stats
path: root / Year 2 / Structures and data algorithms / Exam 1 / ex1.cpp
diff options
context:
space:
mode:
Commit884a3cc6d873053b72855107f9f5d95d7ad1706d (patch)
Author
 Syndamia <kamen@syndamia.com>
2022-11-24 20:07:46 +0200
Committer
 Syndamia <kamen@syndamia.com>
2022-11-24 20:07:46 +0200
Files4dddd0d1fa72fcf514f649cbe8054e8ed3709bb4 /Year 2/Structures and data algorithms/Exam 1/ex1.cpp
uni-projects-884a3cc6d873053b72855107f9f5d95d7ad1706d.tar
uni-projects-884a3cc6d873053b72855107f9f5d95d7ad1706d.tar.gz
uni-projects-884a3cc6d873053b72855107f9f5d95d7ad1706d.zip
Parent81f851c6ea7988314812cf7cdb3cc94a6aa5cbf3 (diff)
[SDP/E1] Added work from today's exam
1 files changed, 94 insertions, 0 deletions
-rw-r--r--Year 2/Structures and data algorithms/Exam 1/ex1.cpp94
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 <iostream>
+
+template <typename T>
+struct Node {
+ T value;
+ Node<T>* next;
+
+ Node(T value, Node<T>* next = nullptr) : value(value), next(next) {}
+};
+
+template <typename T, typename U>
+struct Pair {
+ T left;
+ U right;
+
+ Pair(T left, U right) : left(left), right(right) {}
+};
+
+#define PII Pair<int, int>
+#define NPII Node<Pair<int, int>*>
+
+template <typename T>
+void reverseSublist(Node<T>*& list, int start, int end) {
+ Node<T>* prev = nullptr; // element before first in range
+ Node<T>* iter = list; // first element in range
+ while (start > 0) {
+ prev = iter;
+ iter = iter->next;
+ start--;
+ end--;
+ }
+ Node<T>* eter = iter; // last element in range
+ Node<T>* next = nullptr; // element after last in range
+ for (int i = 0; i < end; i++) {
+ eter = eter->next;
+ next = eter->next;
+ }
+
+ prev->next = eter;
+ Node<T>* last;
+ Node<T>* 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 <typename T>
+void reverseSublists(Node<T>*& list, NPII* intervals) {
+ while (intervals != nullptr) {
+ reverseSublist(list, intervals->value->left, intervals->value->right);
+ intervals = intervals->next;
+ }
+}
+
+template <typename T>
+void print(Node<T>* 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<int>* list = new Node<int>(11, new Node<int>(4, new Node<int>(3, new Node<int>(7, new Node<int>(13, new Node<int>(4, new Node<int>(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<int>* temp1 = nullptr;
+ while (list != nullptr) {
+ temp1 = list->next;
+ delete list;
+ list = temp1;
+ }
+}