From 2b22b0eb65d20f590f67ce21efe6ef71840f31f5 Mon Sep 17 00:00:00 2001 From: lonkaars Date: Tue, 14 Feb 2023 23:25:13 +0100 Subject: week 3 deel 2 --- algo1w3/IntDoubleLink.cpp | 19 +++++ algo1w3/IntDoubleLink.h | 22 ++++++ algo1w3/IntDoubleLinkedList.cpp | 167 ++++++++++++++++++++++++++++++++++++++++ algo1w3/IntDoubleLinkedList.h | 47 +++++++++++ algo1w3/main.cpp | 90 ++++++++-------------- algo1w3/makefile | 1 + 6 files changed, 288 insertions(+), 58 deletions(-) create mode 100644 algo1w3/IntDoubleLink.cpp create mode 100644 algo1w3/IntDoubleLink.h create mode 100644 algo1w3/IntDoubleLinkedList.cpp create mode 100644 algo1w3/IntDoubleLinkedList.h (limited to 'algo1w3') diff --git a/algo1w3/IntDoubleLink.cpp b/algo1w3/IntDoubleLink.cpp new file mode 100644 index 0000000..fb7d7a3 --- /dev/null +++ b/algo1w3/IntDoubleLink.cpp @@ -0,0 +1,19 @@ +#include "IntDoubleLink.h" + +IntDoubleLink::IntDoubleLink() { } +IntDoubleLink::~IntDoubleLink() { } + +IntDoubleLink::IntDoubleLink(int value, IntDoubleLink* prev, IntDoubleLink* next) { + this->value = value; + this->prev = prev; + this->next = next; +} + +IntDoubleLink* IntDoubleLink::getPrev() { + return this->prev; +} + +IntDoubleLink* IntDoubleLink::getNext() { + return this->next; +} + diff --git a/algo1w3/IntDoubleLink.h b/algo1w3/IntDoubleLink.h new file mode 100644 index 0000000..e3cb385 --- /dev/null +++ b/algo1w3/IntDoubleLink.h @@ -0,0 +1,22 @@ +#pragma once +class IntDoubleLink { +private: + IntDoubleLink(); + IntDoubleLink(int, IntDoubleLink*, IntDoubleLink*); + +public: + virtual ~IntDoubleLink(); + +public: + virtual IntDoubleLink *getPrev(); + virtual IntDoubleLink *getNext(); + +private: + int value = 0; + IntDoubleLink* next = nullptr; + IntDoubleLink* prev = nullptr; + +private: + friend class IntDoubleLinkedList; +}; + diff --git a/algo1w3/IntDoubleLinkedList.cpp b/algo1w3/IntDoubleLinkedList.cpp new file mode 100644 index 0000000..4f993a6 --- /dev/null +++ b/algo1w3/IntDoubleLinkedList.cpp @@ -0,0 +1,167 @@ +#include +#include "IntDoubleLinkedList.h" +#include "IntDoubleLink.h" + +IntDoubleLinkedList::IntDoubleLinkedList() { } +IntDoubleLinkedList::~IntDoubleLinkedList() { } + +void IntDoubleLinkedList::initFirstElement(int value) { + this->head = new IntDoubleLink(value, nullptr, nullptr); + this->tail = this->head; +} + +void IntDoubleLinkedList::insertAtStart(int value) { + this->size++; + if (this->size == 1) return initFirstElement(value); + + // this->tail->prev is used as the new instance holder + this->tail->prev = new IntDoubleLink(value, nullptr, this->tail); + this->tail->prev->next = this->tail; // yes + this->tail = this->tail->prev; +} + +void IntDoubleLinkedList::insertAtEnd(int value) { + this->size++; + if (this->size == 1) return initFirstElement(value); + + this->head->next = new IntDoubleLink(value, this->head, nullptr); + this->head->next->prev = this->head; + this->head = this->head->next; +} + +bool IntDoubleLinkedList::removeAtStart() { + // can't remove anything from an empty list + if (this->tail == nullptr) return false; + + // clear list if last element remaining is deleted + if (this->tail->next == nullptr) { + head = tail = nullptr; + size = 0; + return true; + } + + // delete and shift + IntDoubleLink* node = this->tail; + this->tail = this->tail->next; + delete node; + size--; + + return true; +} + +bool IntDoubleLinkedList::removeAtEnd() { + // can't remove anything from an empty list + if (this->head == nullptr) return false; + + // clear list if last element remaining is deleted + if (this->head->prev == nullptr) { + head = tail = nullptr; + size = 0; + return true; + } + + // delete and shift + IntDoubleLink* node = this->head; + this->head = this->head->prev; + delete node; + size--; + + return true; +} + +IntDoubleLink* IntDoubleLinkedList::getHead() { return this->head; } +IntDoubleLink* IntDoubleLinkedList::getTail() { return this->tail; } + +int IntDoubleLinkedList::_indexOf(IntDoubleLink* s) { + int i = 0; + IntDoubleLink* c = tail; + while (c != nullptr) { + if (c == s) return i; + i++; + c = c->next; + } + + return -1; +} + +void IntDoubleLinkedList::rapidBubbleSort() { + // waarom moet hier v ook een pointer sterretje staan!? + IntDoubleLink *outer, *inner; + bool sorted; + for (outer = tail; outer != head; outer = outer->next) { + sorted = true; // check if array was modified during inner loop + for (inner = head->prev; inner != outer->prev; inner = inner->prev) { + // printf("inner [%d, %d]\n", _indexOf(inner), _indexOf(inner->next)); + if (inner->value >= inner->next->value) { + std::swap(inner->value, inner->next->value); + sorted = false; + } + } + // printf("outer %d: ", _indexOf(outer)); // indexOf printing for loop debugging + // showAll(); + if (sorted) break; // break if nothing changed (already sorted) + } +} + +/* + * metingen van de duur van het sorteren... + * + * aantal waarden: duur in us: + * 1000 4718 + * 2000 19976 + * 5000 131068 + * 10000 547875 + * ... + */ + +/* + * gemeten snelheid van dit algoritme: O(n^2) + * onderbouwing: + * + * aan de structuur van de zoekfunctie is niets veranderd, er zijn nog steeds + * twee for-lussen waar het aantal iteraties recht evenredig is met de + * arraygrotte. mijn zoekfunctie gebruikt geen getAt of setAt, dus er worden + * geen extra 'factoren' van n toegevoegd + */ + +/* + * Vergelijking met bubblesort van week 3 deel 1 + * + * hij draait wel een ordergrootte sneller dan in deel 1 :^) + */ + +void IntDoubleLinkedList::insertAction(int code) { + while (head != actionCursor) + if (!removeAtEnd()) break; + insertAtEnd(code); + actionCursor = head; +} + +int IntDoubleLinkedList::undo() { + if (actionCursor->prev != nullptr) + actionCursor = actionCursor->prev; + return actionCursor->value; +} + +int IntDoubleLinkedList::redo() { + if (actionCursor->next != nullptr) + actionCursor = actionCursor->next; + return actionCursor->value; +} + +int IntDoubleLinkedList::getCurrentAction() { + return actionCursor->value; +} + +void IntDoubleLinkedList::showAll() { + std::cout << "["; + IntDoubleLink* node = this->tail; + while (node != nullptr) { + if (node == actionCursor) std::cout << "{"; // curly braces for highlighting actionCursor + std::cout << node->value; + if (node == actionCursor) std::cout << "}"; + node = node->next; + if (node != nullptr) std::cout << ", "; + } + std::cout << "]" << std::endl; +} diff --git a/algo1w3/IntDoubleLinkedList.h b/algo1w3/IntDoubleLinkedList.h new file mode 100644 index 0000000..e48f254 --- /dev/null +++ b/algo1w3/IntDoubleLinkedList.h @@ -0,0 +1,47 @@ +#pragma once + +#include + +class IntDoubleLink; + +class IntDoubleLinkedList { +public: + IntDoubleLinkedList(); + virtual ~IntDoubleLinkedList(); + +public: + virtual void insertAtStart(int); + virtual void insertAtEnd(int); + + virtual bool removeAtStart(); + virtual bool removeAtEnd(); + + virtual void initFirstElement(int); + +public: + virtual IntDoubleLink *getHead(); + virtual IntDoubleLink *getTail(); + +public: // voor vraag 1 + virtual void rapidBubbleSort(); + +public: // voor vraag 2 + virtual void insertAction(int code); + virtual int undo(); + virtual int redo(); + virtual int getCurrentAction(); +private: + IntDoubleLink* actionCursor = nullptr; + +public: // alleen voor het gemak + virtual void showAll(); + +private: + size_t size = 0; + IntDoubleLink* head = nullptr; + IntDoubleLink* tail = nullptr; + +private: + virtual int _indexOf(IntDoubleLink*); +}; + diff --git a/algo1w3/main.cpp b/algo1w3/main.cpp index 38a88b1..8f89afa 100644 --- a/algo1w3/main.cpp +++ b/algo1w3/main.cpp @@ -1,83 +1,57 @@ -// Week3Deel1.cpp : Defines the entry point for the console application. -// - -#include "NAWLinkedList.h" -#include "IntLinkedList.h" - -#include "NAW.h" -#include "NAWLink.h" +#include "IntDoubleLinkedList.h" +#include +#include #include #include -#include -void testNAWLinkedList(); -void testintLinkedList(); +void testVraag1(); +void testVraag2(); int main() { - testNAWLinkedList(); - testintLinkedList(); + testVraag1(); + testVraag2(); return 0; } -void testNAWLinkedList() { - NAWLinkedList linkedList; - NAWLink *link1, *link2; - - for (int n = 0; n < 20; n++) { - std::stringstream naam, adres, plaats; +void testVraag1() { + const int SIZE = 20; + IntDoubleLinkedList linkedList; + std::chrono::steady_clock::time_point start, end; - naam << "avans " << n + 1; - adres << "onderwijsboulevard " << n + 1; - plaats << "den bosch " << n + 1; + std::srand(unsigned(time(nullptr))); - linkedList.addToStart({ naam.str(), adres.str(), plaats.str() }); + for (int n = 0; n < SIZE; n++) { + if ((n&1) == 0) + linkedList.insertAtStart(std::rand()); + else + linkedList.insertAtEnd(std::rand()); } - linkedList.showAll(); - - std::stringstream naam, adres, plaats; - - naam << "avans " << 7; - adres << "onderwijsboulevard " << 7; - plaats << "den bosch " << 7; + start = std::chrono::steady_clock::now(); + linkedList.rapidBubbleSort();// for (int n=0; n<(1<<25); n++); + end = std::chrono::steady_clock::now(); - link1 = linkedList.search({ naam.str(), adres.str(), plaats.str() }); - link2 = linkedList.removeFirst({ naam.str(), adres.str(), plaats.str() }); + std::cout << "duration = " << std::chrono::duration_cast(end - start).count() << " us" << std::endl; - std::cout << link1 << " =?= " << link2 << std::endl; + linkedList.showAll(); } -void testintLinkedList() { - IntLinkedList linkedList; - std::chrono::steady_clock::time_point start, end; - - for (int n = 20; n > 0; n--) { - if ((n & 1) == 0) - linkedList.addToStart(n+10); - else - linkedList.addToStart(n); - } - - std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl; - std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl; +void testVraag2() { + IntDoubleLinkedList linkedList; - linkedList.setAt( 7, 8); - linkedList.setAt(37, 38); + for (int n = 0; n < 20; n++) + linkedList.insertAction(n); - std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl; - std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl; + for (int n = 0; n < 10; n++) + std::cout << linkedList.undo() << std::endl; - std::cout << linkedList.length1() << " =?= " << linkedList.length2() << std::endl; + for (int n = 0; n < 5; n++) + std::cout << linkedList.redo() << std::endl; - linkedList.showAll(); - - start = std::chrono::steady_clock::now(); - linkedList.bubbleSort(); for (int n=0; n<(1<<25); n++); - end = std::chrono::steady_clock::now(); - - std::cout << "duration = " << std::chrono::duration_cast(end - start).count() << " us" << std::endl; + linkedList.insertAction(100); + std::cout << " ----- " << std::endl; linkedList.showAll(); } diff --git a/algo1w3/makefile b/algo1w3/makefile index c414a31..a1f8d29 100644 --- a/algo1w3/makefile +++ b/algo1w3/makefile @@ -5,6 +5,7 @@ RM = rm -f TARGET = main OUTPUT_ZIP = Huiswerk_2180996.zip +CFLAGS += -g LFLAGS += -lstdc++ SRCS += $(wildcard *.cpp) -- cgit v1.2.3