From 5e595c4055876c4169e6eb7a9bcbbe67787e69ce Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 5 Jan 2023 18:28:02 +0200 Subject: [SDP/E2] Added work from exam --- .../Structures and data algorithms/Exam 2/ex2.cpp | 81 ++++++++++++++++++++++ 1 file changed, 81 insertions(+) create mode 100644 Year 2/Structures and data algorithms/Exam 2/ex2.cpp (limited to 'Year 2/Structures and data algorithms/Exam 2/ex2.cpp') diff --git a/Year 2/Structures and data algorithms/Exam 2/ex2.cpp b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp new file mode 100644 index 0000000..cbe6a02 --- /dev/null +++ b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp @@ -0,0 +1,81 @@ +#include + +template +struct DLListElem { + T data; + DLListElem *next, *prev; + DLListElem(const T& data, DLListElem* next = nullptr, DLListElem* prev = nullptr) : data(data), next(next), prev(prev) {} +}; + +template +void freeList(DLListElem* l) { + DLListElem* temp; + while (l != nullptr) { + temp = l; + l = l->next; + delete temp; + } +} + +// A <-> i <-> j <-> D + +template +void swap(DLListElem* i, DLListElem* j) { + if (i == j) return; + if (i->prev != nullptr) i->prev->next = j; + if (j->next != nullptr) j->next->prev = i; + DLListElem* iPrev = i->prev; + i->next = j->next; + i->prev = j; + j->next = i; + j->prev = iPrev; +} +template +void swapNext(DLListElem* i, DLListElem* j) { + if (i == j) return; + if (i->prev != nullptr) i->prev->next = j; + i->next = j->next; + j->next = i; +} + +// O(n^2) time complexity +template +void sortDescending(DLListElem* start, DLListElem* end) { + for (DLListElem* i = end; i != start && i != nullptr; i = i->prev) { + DLListElem* toSwap = i; + for (DLListElem* j = i->prev; j != start && j != nullptr; j = j->prev) { + if (j->data < toSwap->data) toSwap = j; + } + //swap(i, toSwap); + swapNext(i, toSwap); + } + // TODO: update prevs +} + +int main() { + DLListElem* l1 = new DLListElem(1); + DLListElem* l2 = new DLListElem(2); + DLListElem* l3 = new DLListElem(3); + DLListElem* l4 = new DLListElem(4); + DLListElem* l5 = new DLListElem(5); + DLListElem* l6 = new DLListElem(6); + DLListElem* l7 = new DLListElem(7); + DLListElem* l8 = new DLListElem(8); + + // 8 7 2 5 6 1 4 3 + l8->next = l7; + l7->prev = l8; l7->next = l2; + l2->prev = l7; l2->next = l5; + l5->prev = l2; l5->next = l6; + l6->prev = l5; l6->next = l1; + l1->prev = l6; l1->next = l4; + l4->prev = l1; l4->next = l3; + l3->prev = l4; + + sortDescending(l8, l3); + for (DLListElem* i = l8; i != nullptr; i = i->next) + std::cout << i->data << ", "; + std::cout << std::endl; + + freeList(l1); +} -- cgit v1.3.1-26-gb76a