diff options
[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.cpp | 94 |
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; + } +} |
