From 2bb7c5e97111c7c92dbf682ef49c54a229dfcfce Mon Sep 17 00:00:00 2001 From: lonkaars Date: Tue, 14 Feb 2023 18:30:33 +0100 Subject: week 3 deel 1 --- algo1w3/IntLink.cpp | 11 +++++ algo1w3/IntLink.h | 16 +++++++ algo1w3/IntLinkedList.cpp | 111 ++++++++++++++++++++++++++++++++++++++++++++++ algo1w3/IntLinkedList.h | 30 +++++++++++++ algo1w3/NAW.cpp | 42 ++++++++++++++++++ algo1w3/NAW.h | 36 +++++++++++++++ algo1w3/NAWLink.cpp | 13 ++++++ algo1w3/NAWLink.h | 19 ++++++++ algo1w3/NAWLinkedList.cpp | 61 +++++++++++++++++++++++++ algo1w3/NAWLinkedList.h | 26 +++++++++++ algo1w3/main.cpp | 83 ++++++++++++++++++++++++++++++++++ algo1w3/makefile | 37 ++++++++++++++++ bertfix | 23 ++++++++++ 13 files changed, 508 insertions(+) create mode 100644 algo1w3/IntLink.cpp create mode 100644 algo1w3/IntLink.h create mode 100644 algo1w3/IntLinkedList.cpp create mode 100644 algo1w3/IntLinkedList.h create mode 100644 algo1w3/NAW.cpp create mode 100644 algo1w3/NAW.h create mode 100644 algo1w3/NAWLink.cpp create mode 100644 algo1w3/NAWLink.h create mode 100644 algo1w3/NAWLinkedList.cpp create mode 100644 algo1w3/NAWLinkedList.h create mode 100644 algo1w3/main.cpp create mode 100644 algo1w3/makefile create mode 100755 bertfix 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 + +#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 + +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 + +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 +#include + +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 + +#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 + +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 +#include +#include + +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(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) + diff --git a/bertfix b/bertfix new file mode 100755 index 0000000..d2f761f --- /dev/null +++ b/bertfix @@ -0,0 +1,23 @@ +#!/bin/sh +# unbertfix: unzip and fix files from bert +# - unzips +# - dos2unix-es +# - fix code format using lazy sed + +INPUT_ZIP="$1" + +unzip -qj "$INPUT_ZIP" +rm -f *.log *.log *.sln *.vcxproj *.vcxproj.filters stdafx.cpp stdafx.h targetver.h +dos2unix -q * +sed -z \ + -e 's/\n\s*{/ {/g' \ + -e 's/( /(/g' \ + -e 's/ )/)/g' \ + -e 's/ /\t/g' \ + -e 's/#include "stdafx.h"\n//g' \ + -e 's/#include "targetver.h"\n//g' \ + -e 's/\([^\n\t]\)\t\t*/\1 /g' \ + -e 's/ */ /g' \ + -e 's/\n\n\n*/\n\n/g' \ + -i * + -- cgit v1.2.3