From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar06/DLLSkeleton.cpp | 70 --------- Seminar06/DoublyLinkedList.hpp | 294 ----------------------------------- Seminar06/Linked-List-Palindrome.cpp | 29 ---- Seminar06/README.md | 73 --------- Seminar06/insertSorted.cpp | 63 -------- Seminar06/linkedListCycle.cpp | 33 ---- Seminar06/media/dll.png | Bin 10452 -> 0 bytes Seminar06/task02.cpp | 110 ------------- 8 files changed, 672 deletions(-) delete mode 100644 Seminar06/DLLSkeleton.cpp delete mode 100644 Seminar06/DoublyLinkedList.hpp delete mode 100644 Seminar06/Linked-List-Palindrome.cpp delete mode 100644 Seminar06/README.md delete mode 100644 Seminar06/insertSorted.cpp delete mode 100644 Seminar06/linkedListCycle.cpp delete mode 100644 Seminar06/media/dll.png delete mode 100644 Seminar06/task02.cpp (limited to 'Seminar06') diff --git a/Seminar06/DLLSkeleton.cpp b/Seminar06/DLLSkeleton.cpp deleted file mode 100644 index 77811b8..0000000 --- a/Seminar06/DLLSkeleton.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#ifndef DOUBLY_LINKED_LIST_IMPL_ -#define DOUBLY_LINKED_LIST_IMPL_ - -#include - -template -class DoublyLinkedList { -private: - struct DLListNode {}; - - using Node = DLListNode; - - Node* head; - Node* tail; - - void copy(const DoublyLinkedList& other); - void free(); - - class Iterator { - private: - Node* current; - Iterator(Node* c) {} - - public: - Iterator& operator++() {} - - Iterator operator++(int) {} - - Iterator& operator--() {} - - Iterator operator--(int) {} - - const T& operator*() {} - - bool operator==(const Iterator& other) const {} - - bool operator!=(const Iterator& other) const {} - - friend class DoublyLinkedList; - }; - -public: - DoublyLinkedList(); - - DoublyLinkedList(const DoublyLinkedList&); - DoublyLinkedList& operator=(const DoublyLinkedList&); - - DoublyLinkedList(DoublyLinkedList&&); - DoublyLinkedList& operator=(DoublyLinkedList&&); - - void pushBack(const T&); - void popBack(); - - void pushFront(const T&); - void popFront(); - - bool empty() const; - - const T& back() const; - const T& front() const; - - Iterator begin(); - Iterator end(); - - void insert(Iterator at, const T& elem); - - ~DoublyLinkedList(); -}; - -#endif \ No newline at end of file diff --git a/Seminar06/DoublyLinkedList.hpp b/Seminar06/DoublyLinkedList.hpp deleted file mode 100644 index f1bb01e..0000000 --- a/Seminar06/DoublyLinkedList.hpp +++ /dev/null @@ -1,294 +0,0 @@ -#ifndef DOUBLY_LINKED_LIST_IMPL_ -#define DOUBLY_LINKED_LIST_IMPL_ - -#include - -template -class DoublyLinkedList { -private: - struct DLListNode { - T data; - DLListNode* next; - DLListNode* prev; - - DLListNode(const T& d, DLListNode* n = nullptr, DLListNode* p = nullptr) : - data {d}, - next {n}, - prev {p} {} - }; - - using Node = DLListNode; - - Node* head; - Node* tail; - - void copy(const DoublyLinkedList& other); - void free(); - - class Iterator { - private: - Node* current; - Iterator(Node* c = nullptr) : current { c } {} - - public: - Iterator& operator++() { - if(current == nullptr) - return *this; - current = current->next; - return *this; - } - - Iterator operator++(int) { - if(current == nullptr) - return *this; - - Iterator tmp = *this; - current = current->next; - return tmp; - } - - Iterator& operator--() { - if(current == nullptr) - return *this; - - current = current->prev; - return *this; - } - - Iterator operator--(int) { - if(current == nullptr) - return *this; - - Iterator tmp = *this; - current = current->prev; - return tmp; - } - - const T& operator*() { - if(current == nullptr) - throw std::exception(); - - return current->data; - } - - bool operator==(const Iterator& other) const { - return current == other.current; - } - - bool operator!=(const Iterator& other) const { - return !(*this == other); - } - - friend class DoublyLinkedList; - }; - -public: - DoublyLinkedList(); - - DoublyLinkedList(const DoublyLinkedList&); - DoublyLinkedList& operator=(const DoublyLinkedList&); - - DoublyLinkedList(DoublyLinkedList&&); - DoublyLinkedList& operator=(DoublyLinkedList&&); - - void pushBack(const T&); - void popBack(); - - void pushFront(const T&); - void popFront(); - - bool empty() const; - - const T& back() const; - const T& front() const; - - Iterator begin(); - Iterator end(); - - void insert(Iterator at, const T& elem); - - ~DoublyLinkedList(); -}; - -template -DoublyLinkedList::DoublyLinkedList() : head { nullptr }, tail { nullptr } {} - -template -DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList& other) : head {nullptr}, tail {nullptr} { - copy(other); -} - -template -DoublyLinkedList& DoublyLinkedList::operator=(const DoublyLinkedList& other) { - if(this != &other) { - free(); - copy(other); - } - return *this; -} - -template -DoublyLinkedList::DoublyLinkedList(DoublyLinkedList&& other) { - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; -} - -template -DoublyLinkedList& DoublyLinkedList::operator=(DoublyLinkedList&& other) { - if(this != &other) { - free(); - - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; - } - return *this; -} - -template -void DoublyLinkedList::copy(const DoublyLinkedList& other) { - Node* iter = other.head; - - while(iter) { - pushBack(iter->data); - iter = iter->next; - } -} - -template -void DoublyLinkedList::free() { - while(head) { - Node* toDelete = head; - head = head->next; - delete toDelete; - } -} - -template -bool DoublyLinkedList::empty() const { - return head == nullptr; -} - -template -void DoublyLinkedList::pushBack(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->prev = tail; - tail->next = toInsert; - tail = toInsert; - } -} - -template -void DoublyLinkedList::pushFront(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->next = head; - head->prev = toInsert; - head = toInsert; - } -} - -template -void DoublyLinkedList::popBack() { - if(empty()) - throw std::exception(); - - if(tail == head) { - delete head; - tail = head = nullptr; - return; - } - - tail->prev->next = nullptr; - - Node* toDelete = tail; - tail = tail->prev; - delete toDelete; -} - - -template -void DoublyLinkedList::popFront() { - if(empty()) - throw std::exception(); - - Node* toDelete = head; - - if(head == tail) { - delete toDelete; - head = tail = nullptr; - return; - } - - head->next->prev = nullptr; - head = head->next; - delete toDelete; -} - -template -typename DoublyLinkedList::Iterator DoublyLinkedList::begin() { - return Iterator(head); -} - -template -typename DoublyLinkedList::Iterator DoublyLinkedList::end() { - return Iterator(nullptr); -} - -template -void DoublyLinkedList::insert(Iterator at, const T& elem) { - // Ако е nullptr предполагам, че са подали .end() и добавям в края - if(at.current == nullptr) { - tail->next = new Node(elem, nullptr, tail); - tail = tail->next; - return; - } - - Node* toInsert = new Node(elem, at.current, at.current->prev); - - if(at.current->prev != nullptr) - at.current->prev->next = toInsert; - - at.current->prev = toInsert; - - if(at.current == head) - head = toInsert; - - if(at.current == tail) - tail = toInsert; - - at.current = toInsert; -} - -template -const T& DoublyLinkedList::back() const { - if(empty()) - throw std::exception(); - - return tail->data; -} - -template -const T& DoublyLinkedList::front() const { - if(empty()) - throw std::exception(); - - return head->data; -} - -template -DoublyLinkedList::~DoublyLinkedList(){ free(); } - -#endif \ No newline at end of file diff --git a/Seminar06/Linked-List-Palindrome.cpp b/Seminar06/Linked-List-Palindrome.cpp deleted file mode 100644 index 256246a..0000000 --- a/Seminar06/Linked-List-Palindrome.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include"../Seminar04/linked-list-utils.h" - -template -bool isLinkedListPalRec(const LinkedListNode*& begin, const LinkedListNode* end) { - if(end == nullptr) - return true; - - bool res = isLinkedListPalRec(begin, end->next) && (begin->data == end->data); - - begin = begin->next; - return res; -} - -template -bool isLinkedListPal(const LinkedListNode* ll) { - if(ll == nullptr) - return true; - - const LinkedListNode* begin = ll; - const LinkedListNode* end = ll; - - return isLinkedListPalRec(begin, end); -} - -int main() { - LinkedListNode* ll = new LinkedListNode(0, new LinkedListNode(1, new LinkedListNode(1))); - - std::cout << isLinkedListPal(ll); -} diff --git a/Seminar06/README.md b/Seminar06/README.md deleted file mode 100644 index e333dc2..0000000 --- a/Seminar06/README.md +++ /dev/null @@ -1,73 +0,0 @@ -# Двойно свързани списъци. Допълнителни задачи върху списъци. - -При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния. - -![](media/dll.png) - -Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са: -* Добавяне на елемент на произволна позиция: O(n) -* Добавяне на елемент в началото/края O(1) -* Премахване на елемент от произволна позиция: O(n) -* Премахване на елемент от началото / **края**: O(1) -* Обхождане: O(n) -Тук вече премахването на елемент от края на списъка е O(1) (Защо?) - -Елемента на двойно свързания списък би изглеждал по следния начин: -```cpp -template -struct DLListElement { - T data; - DLListElement* prev; - DLListElement* next; -} -``` - -## Задача първа -Да се напише функция -```cpp -template -void insertSorted(std::list& ll, const T& elem); -``` -която приема сортиран свързан списък и добавя *elem* на правилното място. - -## Задача втора -Нека имаме двусвързан списък от опашки и символи. Във всяка опашка от началото към края е записан валиден израз в обратна полска нотация. Операторите са [+, -, \*, /] а операндите за улеснение са **едноцифрени числа**. - -Да се напише функция, която приема такъв списък, изчислява стойността на всички опашки, и връща дали списъка от резултатите е симетричен спрямо средата. - -Пример: - -``` - * * + - | | | - 7 * 3 - | | | -+ + 7 * -| | | | -5 6 7 3 -| | | | -4 1 8 1 2 -| | | | | -* <-> * <-> * <-> * <-> * -``` -Изход: 1 - -Примера ще се оцени до 9 <-> 49 <-> 8 <-> 49 <-> 9, който е симетричен списък. - -## Задача трета - Linked List Cycyle -Да се напише функция, която проверява дали в едносвързан списък има цикъл. - -## Задача четвърта -Да се провери дали едносвързан списък е палиндром. - -Пример: - -Вход: -``` 1 -> 2 -> 3 -> 2 -> 1 ``` - -Изход: true - -Вход: -``` 1 -> 2 -> 3 ``` - -Изход: false diff --git a/Seminar06/insertSorted.cpp b/Seminar06/insertSorted.cpp deleted file mode 100644 index c8563fb..0000000 --- a/Seminar06/insertSorted.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include -#include -#include"../Seminar04/linked-list-utils.h" -#include - -template -void insertSorted(LinkedListNode*& ll, const T& elem) { - LinkedListNode* toInsert = new LinkedListNode(elem); - - if (ll == nullptr) { // Празен списък - ll = toInsert; - } - else if (ll->data > elem) { // Елементът е по - малък от всички - toInsert->next = ll; - ll = toInsert; - } - else if (ll->next == nullptr) { // Списъкът е от един елемент и елементът не стои в началото (ако стоеше щяхме да сме в сл2) - ll->next = toInsert; - } - else { // Елементът може да е в средата или в края - LinkedListNode* it = ll; - - while (it->next != nullptr) { - if (it->next->data > elem) { // Намерена е позицията на елемента - LinkedListNode* nNext = it->next; - it->next = toInsert; - toInsert->next = nNext; - return; - } - - it = it->next; - } - - it->next = toInsert; // Ако сме стигнали до тук то мястото на елемента е в края на списъка - } -} - -template -void insertSorted(std::list& ll, const T& elem) { - auto iter = ll.begin(); - - while(iter != ll.end()) { - if(*iter > elem) { - ll.insert(iter, elem); - break; - } - ++iter; - } - - if(iter == ll.end()) - ll.push_back(elem); -} - -int main() { - std::list ll; - - srand(time(NULL)); - - for (size_t i = 0; i < 55555; i++) - insertSorted(ll, rand()); - - std::cout << std::is_sorted(ll.begin(), ll.end()); -} \ No newline at end of file diff --git a/Seminar06/linkedListCycle.cpp b/Seminar06/linkedListCycle.cpp deleted file mode 100644 index 4aa33c6..0000000 --- a/Seminar06/linkedListCycle.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include"../Seminar04/linked-list-utils.h" - -bool hasCycle(LinkedListNode* head) { - LinkedListNode *fast = head; - LinkedListNode *slow = head; - - while (fast && fast->next && slow) { - fast = (fast->next)->next; - slow = slow->next; - - if (fast == slow) - return true; - } - - return false; -} - -int main() { - using Node = LinkedListNode; - - Node* last = new Node(6); - - Node* list = new Node(1, - new Node(2, - new Node(3, - new Node(4, - new Node(5, - last))))); - - last->next = list->next->next; - - hasCycle(list); -} \ No newline at end of file diff --git a/Seminar06/media/dll.png b/Seminar06/media/dll.png deleted file mode 100644 index 03b98d7..0000000 Binary files a/Seminar06/media/dll.png and /dev/null differ diff --git a/Seminar06/task02.cpp b/Seminar06/task02.cpp deleted file mode 100644 index 5f8bf92..0000000 --- a/Seminar06/task02.cpp +++ /dev/null @@ -1,110 +0,0 @@ -#include -#include -#include -#include - -bool isSymethric(const std::list& ll) { - auto start = ll.begin(); - auto end = --(ll.end()); - - while(start != end) { - if(*start != *end) - return false; - - ++start; - if(start == end) - break; - --end; - } - - return true; -} - -int evaluateExpr(char op, int fst, int snd) { - // assert(isOperator(op)); - - switch (op) { - case '+': - return (fst + snd); - break; - case '-': - return (fst - snd); - break; - case '*': - return (fst * snd); - break; - case '/': - return (snd / fst); - break; - } -} - -size_t evaluateQueue(std::queue q) { - std::stack nums; - - while(!q.empty()) { - if(isdigit(q.front())) { - int cDigit = q.front() - '0'; - q.pop(); - nums.push(cDigit); - } - else { - int fst = nums.top(); - nums.pop(); - int snd = nums.top(); - nums.pop(); - char op = q.front(); - q.pop(); - - nums.push(evaluateExpr(op, fst, snd)); - } - } - return nums.top(); -} - -bool solution(const std::list>& ll) { - std::list l; - - for(auto elem : ll) - l.push_back(evaluateQueue(elem)); - - return isSymethric(l); -} - -int main() { - std::list> test(5); - - auto it = test.begin(); - (*it).push('4'); - (*it).push('5'); - (*it).push('+'); - - ++it; - - (*it).push('1'); - (*it).push('6'); - (*it).push('+'); - (*it).push('7'); - (*it).push('*'); - ++it; - - (*it).push('8'); - ++it; - - (*it).push('1'); - (*it).push('7'); - (*it).push('7'); - (*it).push('*'); - (*it).push('*'); - - ++it; - - (*it).push('2'); - (*it).push('3'); - (*it).push('*'); - (*it).push('3'); - (*it).push('+'); - - - std::cout << solution(test); -} \ No newline at end of file -- cgit v1.3.1-26-gb76a