From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar03/Linked-Queue.hpp | 162 ------------------------------------ Seminar03/QueueTests.cpp | 28 ------- Seminar03/README.md | 185 ------------------------------------------ Seminar03/media/arr-queue.png | Bin 3564 -> 0 bytes Seminar03/media/qexample.png | Bin 9249 -> 0 bytes Seminar03/task01.cpp | 27 ------ Seminar03/task02.cpp | 93 --------------------- Seminar03/task03.cpp | 41 ---------- 8 files changed, 536 deletions(-) delete mode 100644 Seminar03/Linked-Queue.hpp delete mode 100644 Seminar03/QueueTests.cpp delete mode 100644 Seminar03/README.md delete mode 100644 Seminar03/media/arr-queue.png delete mode 100644 Seminar03/media/qexample.png delete mode 100644 Seminar03/task01.cpp delete mode 100644 Seminar03/task02.cpp delete mode 100644 Seminar03/task03.cpp (limited to 'Seminar03') diff --git a/Seminar03/Linked-Queue.hpp b/Seminar03/Linked-Queue.hpp deleted file mode 100644 index 325f4c4..0000000 --- a/Seminar03/Linked-Queue.hpp +++ /dev/null @@ -1,162 +0,0 @@ -#ifndef LINKED_QUEUE_IMPL -#define LINKED_QUEUE_IMPL - -#include - -template -class LinkedQueue { -private: - struct LinkedNode { - T data; - LinkedNode* next; - - LinkedNode(const T& argData, LinkedNode* argNext = nullptr) : data {argData}, next{argNext} {} - }; - - LinkedNode* head; // Първия добавен елемент в опашката - LinkedNode* tail; // Последния добавен елемент в опашката - size_t queueSize; - - void copy(const LinkedQueue&); - void free(); - -public: - LinkedQueue(); - - LinkedQueue(const LinkedQueue&); - LinkedQueue& operator=(const LinkedQueue&); - - LinkedQueue(LinkedQueue&&) noexcept; - LinkedQueue& operator=(LinkedQueue&&) noexcept; - - void push(const T&); - void pop(); - const T& front() const; - - bool empty() const; - - size_t size() const; - - ~LinkedQueue(); -}; - -template -LinkedQueue::LinkedQueue() : head {nullptr}, tail{nullptr}, queueSize{0} {} - -template -LinkedQueue::LinkedQueue(const LinkedQueue& other) { - copy(other); -} - -template -LinkedQueue& LinkedQueue::operator=(const LinkedQueue& other) { - if(this != &other){ - free(); - copy(other); - } - - return *this; -} - -template -LinkedQueue::LinkedQueue(LinkedQueue&& other) noexcept { - head = other.head; - tail = other.tail; - size = other.size; - - other.head = nullptr; - other.tail = nullptr; -} - -template -LinkedQueue& LinkedQueue::operator=(LinkedQueue&& other) noexcept { - if(this != &other) { - head = other.head; - tail = other.tail; - size = other.size; - - other.head = nullptr; - other.tail = nullptr; - } - return *this; -} - -template -void LinkedQueue::copy(const LinkedQueue& other) { - LinkedNode* iter = other.head; - - while(iter) { - push(iter->data); - iter = iter->next; - } -} - -template -void LinkedQueue::free() { - LinkedNode* iter = head; - while(iter) { - LinkedNode* removeMe = iter; - iter = iter->next; - delete removeMe; - } -} - -template -bool LinkedQueue::empty() const { - return head == nullptr; -} - -template -size_t LinkedQueue::size() const { - return queueSize; -} - -template -void LinkedQueue::push(const T& elem) { - LinkedNode* toPush = new LinkedNode(elem); - if(empty()) { - tail = toPush; - head = toPush; - } - else { - tail->next = toPush; - tail = toPush; - } - - ++queueSize; -} - -template -void LinkedQueue::pop() { - if(empty()) { - throw "Empty queue"; - } - else if(head == tail) { - delete head; - head = nullptr; - tail = nullptr; - } - else { - LinkedNode* deleteMe = head; - head = head->next; - delete deleteMe; - } - - --queueSize; -} - -template -const T& LinkedQueue::front() const { - if(empty()){ - throw "Empty queue"; - } - - return head->data; -} - -template -LinkedQueue::~LinkedQueue() { - free(); -} - -#endif diff --git a/Seminar03/QueueTests.cpp b/Seminar03/QueueTests.cpp deleted file mode 100644 index 221a09a..0000000 --- a/Seminar03/QueueTests.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#include"Linked-Queue.hpp" -#include -#include - -void runTest() { - LinkedQueue q; - - for (size_t i = 0; i < 1000; i++) - q.push(i); - - std::cout << "Passed size test" << std::endl; - assert(q.size() == 1000); - - for (size_t i = 0; i < 1000; i++) { - assert(q.front() == i); - q.pop(); - } - - std::cout << "Push, pop and top working as expected" << std::endl; - - assert(q.empty() && q.size() == 0); - - std::cout << "Passed empty test" << std::endl; -} - -int main() { - runTest(); -} diff --git a/Seminar03/README.md b/Seminar03/README.md deleted file mode 100644 index dc36329..0000000 --- a/Seminar03/README.md +++ /dev/null @@ -1,185 +0,0 @@ -# Опашка -Опашката е линейна структура от данни, която работи на принципа FIFO (first in first out). Опашката отговаря точно на представата за реална опашка. -Операции: -* Enqueue (или push) - добавя елемент в края на опашката -* Dequeue (или pop) - премахва първия добавен елемент в опашката -* Front - връща първия елемент в опашката - -Опционални операции към интерфейса: -* empty() - Връща дали опашката е празна или не -* size() - Връща размера на опашката - -В STL имаме готова реализация на опашка. Тя се намира в библиотеката \ и се създава чрез std::queue\. -Пример: -```cpp -#include -#include - -int main() { - std::queue q; - - q.push(1); - q.push(2); - q.push(3); - q.push(4); - - std::cout << q.front(); // Извежда 1 - q.pop() // Премахва 1 от опашката - std::cout << q.front(); // Извежда 2 - q.pop(); // Премахва 2 от опашката - q.pop(); // Премахва 3 от опашката -} -``` - -## Приложения -Едно от основните приложения на опашката е използването ѝ в различни алгоритми за обхождане на графи, като най - ясен пример за това би бил алгоритъма BFS. Други алгоритми върху графи също използват опашка (или нейни разновидности) за да обхождат графа и да решават различни задачи върху него. -Опашките също намират голямо приложение в операционните системи и компютърните мрежи. - -## Начини за реализация -### Свързани компоненти - -Представяме елемента на опашката по следния начин: -```cpp -template -struct QueueNode { - T data; - QueueNode* next; -} -``` -В класа представящ опашка пазим два указателя, head и tail: -```cpp -template -class LinkedQueue { - QueueNode* head; // Представлява първия елемент, който е добавен. - QueueNode* tail; // Представлява последния елемент, който е добавен. -} -``` -![](media/qexample.png) -При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? - -### Чрез масив -Можем да представим опашката чрез статичен или динамичен масив и два индекса - към първия и последния елемент добавен към опашката. -![](media/arr-queue.png) - -При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката? - -# Декове -Декът или deque (от double ended queue) е линейна структура от данни, за която можем да си мислим като опашка, позволяваща добавяне и премахване на елементи и от двете страни. - -Операции: -* push_front(x) - Добавя x в началото -* push_back(x) - Добавя х в края -* pop_back() - Премахва последния елемент -* pop_front() - Премахва първия елемент - -*A deque ("double ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list*. - -Стандартната библиотека ни предлага реализация на дек. Тази реализация обаче трябва да се използва внимателно. Примерно, std::deque ни позволява достъп на произволен елемент в колекцията. Това, дори да изглежда като функционалност, която не бихме отказали, често може да доведе до различен тип грешки. - -Пример: -```cpp -#include - -int main() { - std::deque dq; - - dq.push_front(1); - dq.push_back(2); - - dq[0] = 10; - // Позволява промяна, но доста често такава промяна е безсмислена. - // Наложи ли ви се да правите такава промяна - // вероятно използвате грешната структура от данни. - dq[3] = 1; - // Какво става когато такъв елемент няма? - // Отговорът е зависи - недефинирано поведение (undefined behaviour). -} -``` - -# Неща, които използвам в решението на задачите - -## Статични масиви и std::array -Всички знаем, че статичният масив е бърза и удобна структура от данни. STL ни предлага готова реализация на статичен масив. Тя се намира в библиотеката \. -Пример: -```cpp -#include - -int main() { - std::array arr; - arr[0] = 42; -} -``` -В случая arr се държи като нормален статичен масив, но идва с допълнителни помощни функции и поддържа логика за итератори. - -## Нетипови параметри -Нетиповите параметри често се използват за определяне на някакви максимуми, минимуми или константи свързани с класа. Примерно, нека имаме следния код: - -```cpp -const size_t MAX_SIZE = 100; - -template -class staticArray { - T data[MAX_SIZE]; -} -``` -Това върши работа до момента в който не ни потрябват два различни варианта на staticArray - един с максимум елемента 100 а втория с максимум 50. Този проблем се решава чрез нетипови параметри по следния начин: -```cpp -template -class staticArray { - T data[maxSize]; -} -``` -Сега много лесно мога да си направя два статични масива с различна горна граница: - -```cpp -int main() { - staticArray fst; - staticArray snd; -} -``` -Тук компилаторът няма да ни се скара, понеже maxSize задължително трябва да е константа. -Едно хубаво свойство на нетиповите параметри е, че `staticArray` и `staticArray` са два различни типа. - -# Задачи - -## Задача първа -Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка. - -Пример: -> n = 10 ➡ 1 10 11 100 101 110 111 1000 1001 1010 - -## Задача втора -Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната. - -Пример: -> {(0, 0), (2, 1)} -> 1 -> -> {(0, 0), (7, 7)} -> 6 - -## Задача трета - Sliding window maximum -Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец. - -Пример: - -> Вход: **[1, 3, -1, -3, 5, 3, 6, 7]**, k = 3 -> -> Output: [3, 3, 5, 5, 6, 7] - -Обяснение: -> -> **[1 3 -1]** -3 5 3 6 7 => 3 -> -> 1 **[3 -1 -3]** 5 3 6 7 => 3 -> -> 1 3 **[-1 -3 5]** 3 6 7 => 5 -> -> 1 3 -1 **[-3 5 3]** 6 7 => 5 -> -> 1 3 -1 -3 **[5 3 6]** 7 => 6 -> -> 1 3 -1 -3 5 **[3 6 7]** => 7 - -Като бонус можете да направите втора задача да не извежда само минималния път, но и клетките през които сме минали. - -Алтернативни решения на задачи 1 и 2 както и още задачи за упражнение можете да намерите на: -https://github.com/ivanahristova/data-structures-fmi/tree/main/sem04 \ No newline at end of file diff --git a/Seminar03/media/arr-queue.png b/Seminar03/media/arr-queue.png deleted file mode 100644 index ba4e1fe..0000000 Binary files a/Seminar03/media/arr-queue.png and /dev/null differ diff --git a/Seminar03/media/qexample.png b/Seminar03/media/qexample.png deleted file mode 100644 index b43a02c..0000000 Binary files a/Seminar03/media/qexample.png and /dev/null differ diff --git a/Seminar03/task01.cpp b/Seminar03/task01.cpp deleted file mode 100644 index 2a2eff3..0000000 --- a/Seminar03/task01.cpp +++ /dev/null @@ -1,27 +0,0 @@ -#include -#include -#include - -// Сложност по време: ? -// Сложност по памет: ? -void printAllBinaryNumbers(size_t n) { - std::queue q; - - q.push("1"); - - while(n) { - std::string currentNumber = q.front(); - q.pop(); - - std::cout << currentNumber << " "; - - q.push(currentNumber + "0"); - q.push(currentNumber + "1"); - - n--; - } -} - -int main() { - printAllBinaryNumbers(10); -} \ No newline at end of file diff --git a/Seminar03/task02.cpp b/Seminar03/task02.cpp deleted file mode 100644 index ffc6a30..0000000 --- a/Seminar03/task02.cpp +++ /dev/null @@ -1,93 +0,0 @@ -#include -#include -#include - -template -class minMoves { - using position = std::pair; - using positionAndSteps = std::pair; - using board = std::array, boardSize>; - - board playground; - - void cleanPlayground() { - for (auto &row : playground) - for (auto &pos : row) - pos = false; - } - - static bool equalPositions(const position &fst, const position &snd) { - return fst.first == snd.first && fst.second == snd.second; - } - - static bool isValidPos(const position &p) { - return p.first >= 0 && p.second >= 0 && p.first < boardSize && p.second < boardSize; - } - - void mark(const position &toMark) { - playground[toMark.first][toMark.second] = true; - } - - bool isMarked(const position &pos) const { - return playground[pos.first][pos.second]; - } - - void pushAndMarkIfValid(std::queue &q, const position &toPush, int steps) { - if (isValidPos(toPush) && !isMarked(toPush)) { - q.push({toPush, steps}); - mark(toPush); - } - } - - int process(const position &startPos, const position &endPos) { - std::queue q; - - q.push({startPos, 0}); - - while (!q.empty()) { - positionAndSteps currentPosition = q.front(); - - q.pop(); - - if (equalPositions(currentPosition.first, endPos)) - return currentPosition.second; - - int x = currentPosition.first.first; - int y = currentPosition.first.second; - int moves = currentPosition.second + 1; - - pushAndMarkIfValid(q, {x + 1, y + 2}, moves); - pushAndMarkIfValid(q, {x - 1, y - 2}, moves); - pushAndMarkIfValid(q, {x + 1, y - 2}, moves); - pushAndMarkIfValid(q, {x - 1, y + 2}, moves); - pushAndMarkIfValid(q, {x + 2, y - 1}, moves); - pushAndMarkIfValid(q, {x + 2, y + 1}, moves); - pushAndMarkIfValid(q, {x - 2, y + 1}, moves); - pushAndMarkIfValid(q, {x - 2, y - 1}, moves); - } - return -1; - } - -public: - minMoves() { cleanPlayground(); } - - int getMinMoves(const position &start, const position &end) { - cleanPlayground(); - - return process(start, end); - } -}; - -int main() { - minMoves m; - - std::cout << m.getMinMoves({0, 0}, {5, 3}) << std::endl; - - minMoves<12> ms; - - std::cout << ms.getMinMoves({0, 0}, {11, 11}) << std::endl; - - minMoves<2> mt; - - std::cout << mt.getMinMoves({0, 0}, {12, 212}); -} diff --git a/Seminar03/task03.cpp b/Seminar03/task03.cpp deleted file mode 100644 index eef4cf4..0000000 --- a/Seminar03/task03.cpp +++ /dev/null @@ -1,41 +0,0 @@ -#include -#include -#include - -std::vector maxSlidingWindow(const std::vector& v, size_t k) { - std::deque window; - std::vector result; - - for (size_t i = 0; i < k; i++) { - while(!window.empty() && window.back() < v[i]) { - window.pop_back(); - } - window.push_back(v[i]); - } - - result.push_back(window.front()); - - for (size_t i = k; i < v.size(); i++) { - if(window.front() == v[i - k]) { - window.pop_front(); - } - - while(!window.empty() && window.back() < v[i]) { - window.pop_back(); - } - - window.push_back(v[i]); - result.push_back(window.front()); - } - - return result; -} - -int main() { - std::vector example = {1, 3, -1, -3, 5, 3, 6, 7}; - - std::vector result = maxSlidingWindow(example, 3); - - for(auto elem : result) - std::cout << elem << " "; -} \ No newline at end of file -- cgit v1.3.1-26-gb76a