summaryrefslogtreecommitdiff
path: root/algo1w3
diff options
context:
space:
mode:
Diffstat (limited to 'algo1w3')
-rw-r--r--algo1w3/IntLink.cpp11
-rw-r--r--algo1w3/IntLink.h16
-rw-r--r--algo1w3/IntLinkedList.cpp111
-rw-r--r--algo1w3/IntLinkedList.h30
-rw-r--r--algo1w3/NAW.cpp42
-rw-r--r--algo1w3/NAW.h36
-rw-r--r--algo1w3/NAWLink.cpp13
-rw-r--r--algo1w3/NAWLink.h19
-rw-r--r--algo1w3/NAWLinkedList.cpp61
-rw-r--r--algo1w3/NAWLinkedList.h26
-rw-r--r--algo1w3/main.cpp83
-rw-r--r--algo1w3/makefile37
12 files changed, 485 insertions, 0 deletions
diff --git a/algo1w3/IntLink.cpp b/algo1w3/IntLink.cpp
new file mode 100644
index 0000000..a54d449
--- /dev/null
+++ b/algo1w3/IntLink.cpp
@@ -0,0 +1,11 @@
+
+#include "IntLink.h"
+
+IntLink::IntLink() { }
+
+IntLink::IntLink(int value, IntLink* next) {
+ this->value = value;
+ this->next = next;
+}
+
+IntLink::~IntLink() { }
diff --git a/algo1w3/IntLink.h b/algo1w3/IntLink.h
new file mode 100644
index 0000000..ce8c916
--- /dev/null
+++ b/algo1w3/IntLink.h
@@ -0,0 +1,16 @@
+#pragma once
+
+class IntLink {
+public:
+ IntLink();
+ IntLink(int, IntLink*);
+ virtual ~IntLink();
+
+private:
+ IntLink* next = nullptr;
+ int value = 0;
+
+private:
+ friend class IntLinkedList;
+};
+
diff --git a/algo1w3/IntLinkedList.cpp b/algo1w3/IntLinkedList.cpp
new file mode 100644
index 0000000..ce63a6d
--- /dev/null
+++ b/algo1w3/IntLinkedList.cpp
@@ -0,0 +1,111 @@
+#include <iostream>
+
+#include "IntLinkedList.h"
+#include "IntLink.h"
+
+IntLinkedList::IntLinkedList() { }
+
+IntLinkedList::~IntLinkedList() {
+ IntLink* node = this->next;
+ while (node != nullptr) {
+ IntLink* next = node->next;
+ delete node;
+ node = next;
+ }
+}
+
+IntLink* IntLinkedList::getAt(int index) const {
+ if (this->size == 0) return nullptr;
+ IntLink* out = this->next;
+ for (size_t i = 0; i < this->size; i++) {
+ if (out == nullptr) return nullptr;
+ if (i > 0) out = out->next;
+ if (i == index) return out;
+ }
+ return nullptr;
+}
+
+bool IntLinkedList::setAt(int index, int value) {
+ IntLink* node = getAt(index);
+ if (node == nullptr) return false;
+ node->value = value;
+ return true;
+}
+
+int IntLinkedList::length1() const {
+ size_t accu = 0;
+ IntLink* node = this->next;
+ while (node != nullptr) {
+ accu++;
+ node = node->next;
+ }
+ return accu;
+}
+
+int IntLinkedList::length2() const {
+ return this->size;
+}
+
+void IntLinkedList::bubbleSort() {
+ int outer, inner;
+ bool sorted;
+ for (outer = 0; outer < this->size - 2; outer++) {
+ sorted = true; // check if array was modified during inner loop
+ for (inner = this->size - 2; inner >= outer; inner--) {
+ IntLink* inner_node = getAt(inner);
+ if (inner_node->value >= inner_node->next->value) {
+ std::swap(inner_node->value, inner_node->next->value);
+ sorted = false;
+ }
+ }
+ printf("outer %d: ", outer);
+ showAll();
+ if (sorted) break; // break if nothing changed (already sorted)
+ }
+}
+
+/*
+ * geschatte snelheid van dit algoritme: O(n^3)
+ *
+ * onderbouwing:
+ *
+ * bubble sort is O(n^2), de getAt functie is O(n). getAt wordt afhankelijk van
+ * de grootte van de array een aantal keer uitgevoerd, n^2 * n == n^3 -> O(n^3)
+ */
+
+ /*
+ * metingen van de duur van het sorteren...
+ *
+ * aantal waarden: duur in us:
+ * 1000 114410
+ * 2000 275901
+ * 5000 1443233
+ * 10000 5585394
+ * ...
+ */
+
+/*
+ * gemeten snelheid van dit algoritme: O(n^3)
+ * onderbouwing:
+ *
+ * ik heb google spreadsheets gebruikt om de metingen om te zetten naar een
+ * grafiek, en vervolgens een automatische trendlijn te laten maken. bij een
+ * exponentiele lijn is er nog wat afwijking van de metingen, terwijl er bij de
+ * kwadratische lijn geen afwijking is.
+ */
+
+void IntLinkedList::addToStart(int value) {
+ this->next = new IntLink(value, this->next);
+ this->size++;
+}
+
+void IntLinkedList::showAll() const {
+ std::cout << "[";
+ IntLink* node = this->next;
+ while (node != nullptr) {
+ std::cout << node->value;
+ node = node->next;
+ if (node != nullptr) std::cout << ", ";
+ }
+ std::cout << "]" << std::endl;
+}
diff --git a/algo1w3/IntLinkedList.h b/algo1w3/IntLinkedList.h
new file mode 100644
index 0000000..996b5d9
--- /dev/null
+++ b/algo1w3/IntLinkedList.h
@@ -0,0 +1,30 @@
+#pragma once
+
+#include <stdlib.h>
+
+class IntLink;
+
+class IntLinkedList {
+public:
+ IntLinkedList();
+ virtual ~IntLinkedList();
+
+public: // vraag 3
+ virtual IntLink* getAt(int) const;
+ virtual bool setAt(int, int);
+
+ virtual int length1() const;
+ virtual int length2() const;
+
+public: // vraag 4
+ virtual void bubbleSort();
+
+public: // niet gevraagd wel handig... (zie vraag 1)
+ virtual void addToStart(int);
+ virtual void showAll() const;
+
+private:
+ size_t size = 0;
+ IntLink* next = nullptr;
+};
+
diff --git a/algo1w3/NAW.cpp b/algo1w3/NAW.cpp
new file mode 100644
index 0000000..907ad21
--- /dev/null
+++ b/algo1w3/NAW.cpp
@@ -0,0 +1,42 @@
+#include "NAW.h"
+#include <iostream>
+
+NAW::NAW() { }
+
+NAW::NAW(const std::string& naam, const std::string& adres, const std::string& woonplaats) {
+ setNaam(naam);
+ setAdres(adres);
+ setPlaats(woonplaats);
+}
+
+NAW::~NAW() { }
+
+int NAW::compareTo(const NAW& other) const {
+ int c;
+ c = getPlaats().compare(other.getPlaats());
+ if (c != 0) return c;
+ c = getNaam().compare(other.getNaam());
+ if (c != 0) return c;
+ c = getAdres().compare(other.getAdres());
+ return c;
+}
+
+const std::string& NAW::getNaam() const { return _naam; }
+const std::string& NAW::getAdres() const { return _adres; }
+const std::string& NAW::getPlaats() const { return _woonplaats; }
+
+void NAW::setNaam(const std::string& naam) { _naam = naam; }
+void NAW::setAdres(const std::string& adres) { _adres = adres; }
+void NAW::setPlaats(const std::string& woonplaats) { _woonplaats = woonplaats; }
+
+bool NAW::heeftNaam(const std::string& naam) const { return getNaam().compare(naam) == 0; }
+bool NAW::heeftAdres(const std::string& adres) const { return getAdres().compare(adres) == 0; }
+bool NAW::heeftPlaats(const std::string& woonplaats) const { return getPlaats().compare(woonplaats) == 0; }
+
+std::ostream& operator << (std::ostream& output, const NAW& naw) {
+ output <<
+ "naam: " << naw.getNaam() << std::endl <<
+ "adres: " << naw.getAdres() << std::endl <<
+ "plaats: " << naw.getPlaats() << std::endl;
+ return output;
+}
diff --git a/algo1w3/NAW.h b/algo1w3/NAW.h
new file mode 100644
index 0000000..75fd2c6
--- /dev/null
+++ b/algo1w3/NAW.h
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <string>
+#include <stdbool.h>
+
+class NAW {
+public:
+ NAW();
+ NAW(const std::string&, const std::string&, const std::string&);
+ virtual ~NAW();
+
+public:
+ int compareTo(const NAW&) const;
+
+public:
+ virtual const std::string& getNaam() const;
+ virtual const std::string& getAdres() const;
+ virtual const std::string& getPlaats() const;
+
+public:
+ virtual void setNaam(const std::string&);
+ virtual void setAdres(const std::string&);
+ virtual void setPlaats(const std::string&);
+
+public:
+ virtual bool heeftNaam(const std::string&) const;
+ virtual bool heeftAdres(const std::string&) const;
+ virtual bool heeftPlaats(const std::string&) const;
+
+public:
+ friend std::ostream& operator << (std::ostream& output, const NAW& naw);
+
+private:
+ std::string _naam, _adres, _woonplaats;
+};
+
diff --git a/algo1w3/NAWLink.cpp b/algo1w3/NAWLink.cpp
new file mode 100644
index 0000000..776d649
--- /dev/null
+++ b/algo1w3/NAWLink.cpp
@@ -0,0 +1,13 @@
+#include "NAWLink.h"
+#include "NAW.h"
+
+NAWLink::NAWLink() { }
+
+NAWLink::NAWLink(const NAW& value, NAWLink* next) {
+ this->value = new NAW(value);
+ this->next = next;
+}
+
+NAWLink::~NAWLink() {
+ delete this->value;
+}
diff --git a/algo1w3/NAWLink.h b/algo1w3/NAWLink.h
new file mode 100644
index 0000000..e29cfc5
--- /dev/null
+++ b/algo1w3/NAWLink.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include "NAW.h"
+
+class NAWLink {
+private:
+ NAWLink();
+ NAWLink(const NAW&, NAWLink*);
+public:
+ virtual ~NAWLink();
+
+private:
+ NAWLink* next = nullptr;
+ NAW* value = nullptr;
+
+private:
+ friend class NAWLinkedList;
+};
+
diff --git a/algo1w3/NAWLinkedList.cpp b/algo1w3/NAWLinkedList.cpp
new file mode 100644
index 0000000..06e46d8
--- /dev/null
+++ b/algo1w3/NAWLinkedList.cpp
@@ -0,0 +1,61 @@
+#include <iostream>
+
+#include "NAWLinkedList.h"
+#include "NAW.h"
+#include "NAWLink.h"
+
+NAWLinkedList::NAWLinkedList() { }
+
+NAWLinkedList::~NAWLinkedList() {
+ NAWLink* node = this->next;
+ while (node != nullptr) {
+ NAWLink* next = node->next;
+ delete node; // also deletes NAW instance -> see NAWLink::~NAWLink
+ node = next;
+ }
+}
+
+void NAWLinkedList::addToStart(const NAW& value) {
+ this->next = new NAWLink(value, this->next);
+ this->size++;
+}
+
+NAWLink* NAWLinkedList::search(const NAW& value) const {
+ NAWLink* node = this->next;
+ while (node != nullptr) {
+ if (node->value->compareTo(value) == 0) return node;
+ node = node->next;
+ }
+ return nullptr;
+}
+
+NAWLink* NAWLinkedList::searchParent(const NAW& value) const {
+ NAWLink* node = this->next;
+ while (node != nullptr) {
+ if (node->next == nullptr) return nullptr;
+ if (node->next->value->compareTo(value) == 0) return node;
+ node = node->next;
+ }
+ return nullptr;
+}
+
+void NAWLinkedList::showAll() const {
+ std::cout << "/------------------------------\\" << std::endl;
+ NAWLink* node = this->next;
+ while (node != nullptr) {
+ std::cout << *node->value; // prints values -> see operator << (std::ostream&, const NAW&)
+ node = node->next;
+ if (node != nullptr) std::cout << " ---- " << std::endl;
+ }
+ std::cout << "\\------------------------------/" << std::endl;
+}
+
+NAWLink* NAWLinkedList::removeFirst(const NAW& value) {
+ NAWLink* parent = searchParent(value);
+ if (parent == nullptr) return nullptr;
+
+ NAWLink* node = parent->next;
+ parent->next = parent->next->next;
+
+ return node;
+}
diff --git a/algo1w3/NAWLinkedList.h b/algo1w3/NAWLinkedList.h
new file mode 100644
index 0000000..411da61
--- /dev/null
+++ b/algo1w3/NAWLinkedList.h
@@ -0,0 +1,26 @@
+#pragma once
+
+#include <stdlib.h>
+
+class NAW;
+class NAWLink;
+
+class NAWLinkedList {
+public:
+ NAWLinkedList();
+ virtual ~NAWLinkedList();
+
+public:
+ virtual void addToStart(const NAW&);
+ virtual NAWLink* search(const NAW&) const;
+ /** @brief return parent node of node found, if found */
+ virtual NAWLink* searchParent(const NAW&) const;
+ virtual void showAll() const;
+ /** @brief remove first *FOUND* */
+ virtual NAWLink* removeFirst(const NAW&);
+
+private:
+ size_t size = 0;
+ NAWLink* next = nullptr;
+};
+
diff --git a/algo1w3/main.cpp b/algo1w3/main.cpp
new file mode 100644
index 0000000..38a88b1
--- /dev/null
+++ b/algo1w3/main.cpp
@@ -0,0 +1,83 @@
+// Week3Deel1.cpp : Defines the entry point for the console application.
+//
+
+#include "NAWLinkedList.h"
+#include "IntLinkedList.h"
+
+#include "NAW.h"
+#include "NAWLink.h"
+
+#include <chrono>
+#include <iostream>
+#include <sstream>
+
+void testNAWLinkedList();
+void testintLinkedList();
+
+int main() {
+ testNAWLinkedList();
+ testintLinkedList();
+
+ return 0;
+}
+
+void testNAWLinkedList() {
+ NAWLinkedList linkedList;
+ NAWLink *link1, *link2;
+
+ for (int n = 0; n < 20; n++) {
+ std::stringstream naam, adres, plaats;
+
+ naam << "avans " << n + 1;
+ adres << "onderwijsboulevard " << n + 1;
+ plaats << "den bosch " << n + 1;
+
+ linkedList.addToStart({ naam.str(), adres.str(), plaats.str() });
+ }
+
+ linkedList.showAll();
+
+ std::stringstream naam, adres, plaats;
+
+ naam << "avans " << 7;
+ adres << "onderwijsboulevard " << 7;
+ plaats << "den bosch " << 7;
+
+ link1 = linkedList.search({ naam.str(), adres.str(), plaats.str() });
+ link2 = linkedList.removeFirst({ naam.str(), adres.str(), plaats.str() });
+
+ std::cout << link1 << " =?= " << link2 << std::endl;
+}
+
+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;
+
+ linkedList.setAt( 7, 8);
+ linkedList.setAt(37, 38);
+
+ std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl;
+ std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl;
+
+ std::cout << linkedList.length1() << " =?= " << linkedList.length2() << 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<std::chrono::microseconds>(end - start).count() << " us" << std::endl;
+
+ linkedList.showAll();
+}
diff --git a/algo1w3/makefile b/algo1w3/makefile
new file mode 100644
index 0000000..c414a31
--- /dev/null
+++ b/algo1w3/makefile
@@ -0,0 +1,37 @@
+CPP = g++
+LD = g++
+CC = gcc
+RM = rm -f
+TARGET = main
+OUTPUT_ZIP = Huiswerk_2180996.zip
+
+LFLAGS += -lstdc++
+
+SRCS += $(wildcard *.cpp)
+SRCS += $(wildcard *.c)
+OBJS := $(SRCS)
+OBJS := $(patsubst %.cpp,%.o, $(OBJS))
+OBJS := $(patsubst %.c,%.o, $(OBJS))
+
+.PHONY: clean compile_commands zip
+
+all: $(TARGET)
+
+%.o: %.c
+ $(CC) -c $(CFLAGS) $< -o $@
+
+%.o: %.cpp
+ $(CPP) -c $(CFLAGS) $< -o $@
+
+$(TARGET): $(OBJS)
+ $(LD) $^ $(LFLAGS) -o $@
+
+clean:
+ $(RM) $(TARGET) $(OBJS) $(OUTPUT_ZIP)
+
+compile_commands: clean
+ compiledb make -Bn
+
+zip: all
+ zip -q $(OUTPUT_ZIP) makefile $(wildcard *.cpp) $(wildcard *.h) $(wildcard *.hpp) $(wildcard *.c) $(wildcard *.svg)
+