diff options
Cleanup
8 files changed, 0 insertions, 672 deletions
| -rw-r--r-- | Seminar06/DLLSkeleton.cpp | 70 | ||||
| -rw-r--r-- | Seminar06/DoublyLinkedList.hpp | 294 | ||||
| -rw-r--r-- | Seminar06/Linked-List-Palindrome.cpp | 29 | ||||
| -rw-r--r-- | Seminar06/README.md | 73 | ||||
| -rw-r--r-- | Seminar06/insertSorted.cpp | 63 | ||||
| -rw-r--r-- | Seminar06/linkedListCycle.cpp | 33 | ||||
| -rw-r--r-- | Seminar06/media/dll.png | bin | 10452 -> 0 bytes | |||
| -rw-r--r-- | Seminar06/task02.cpp | 110 |
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<exception> - -template<class T> -class DoublyLinkedList { -private: - struct DLListNode {}; - - using Node = DLListNode; - - Node* head; - Node* tail; - - void copy(const DoublyLinkedList<T>& 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<T>; - }; - -public: - DoublyLinkedList(); - - DoublyLinkedList(const DoublyLinkedList<T>&); - DoublyLinkedList& operator=(const DoublyLinkedList<T>&); - - DoublyLinkedList(DoublyLinkedList<T>&&); - DoublyLinkedList& operator=(DoublyLinkedList<T>&&); - - 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<exception> - -template<class T> -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<T>& 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<T>; - }; - -public: - DoublyLinkedList(); - - DoublyLinkedList(const DoublyLinkedList<T>&); - DoublyLinkedList& operator=(const DoublyLinkedList<T>&); - - DoublyLinkedList(DoublyLinkedList<T>&&); - DoublyLinkedList& operator=(DoublyLinkedList<T>&&); - - 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<class T> -DoublyLinkedList<T>::DoublyLinkedList() : head { nullptr }, tail { nullptr } {} - -template<class T> -DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& other) : head {nullptr}, tail {nullptr} { - copy(other); -} - -template<class T> -DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(const DoublyLinkedList<T>& other) { - if(this != &other) { - free(); - copy(other); - } - return *this; -} - -template<class T> -DoublyLinkedList<T>::DoublyLinkedList(DoublyLinkedList<T>&& other) { - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; -} - -template<class T> -DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(DoublyLinkedList<T>&& other) { - if(this != &other) { - free(); - - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; - } - return *this; -} - -template<class T> -void DoublyLinkedList<T>::copy(const DoublyLinkedList<T>& other) { - Node* iter = other.head; - - while(iter) { - pushBack(iter->data); - iter = iter->next; - } -} - -template<class T> -void DoublyLinkedList<T>::free() { - while(head) { - Node* toDelete = head; - head = head->next; - delete toDelete; - } -} - -template<class T> -bool DoublyLinkedList<T>::empty() const { - return head == nullptr; -} - -template<class T> -void DoublyLinkedList<T>::pushBack(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->prev = tail; - tail->next = toInsert; - tail = toInsert; - } -} - -template<class T> -void DoublyLinkedList<T>::pushFront(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->next = head; - head->prev = toInsert; - head = toInsert; - } -} - -template<class T> -void DoublyLinkedList<T>::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<class T> -void DoublyLinkedList<T>::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<class T> -typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::begin() { - return Iterator(head); -} - -template<class T> -typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::end() { - return Iterator(nullptr); -} - -template<class T> -void DoublyLinkedList<T>::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<class T> -const T& DoublyLinkedList<T>::back() const { - if(empty()) - throw std::exception(); - - return tail->data; -} - -template<class T> -const T& DoublyLinkedList<T>::front() const { - if(empty()) - throw std::exception(); - - return head->data; -} - -template<class T> -DoublyLinkedList<T>::~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<class T> -bool isLinkedListPalRec(const LinkedListNode<T>*& begin, const LinkedListNode<T>* end) { - if(end == nullptr) - return true; - - bool res = isLinkedListPalRec(begin, end->next) && (begin->data == end->data); - - begin = begin->next; - return res; -} - -template<class T> -bool isLinkedListPal(const LinkedListNode<T>* ll) { - if(ll == nullptr) - return true; - - const LinkedListNode<T>* begin = ll; - const LinkedListNode<T>* end = ll; - - return isLinkedListPalRec(begin, end); -} - -int main() { - LinkedListNode<int>* 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 @@ -# Двойно свързани списъци. Допълнителни задачи върху списъци. - -При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния. - - - -Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са: -* Добавяне на елемент на произволна позиция: O(n) -* Добавяне на елемент в началото/края O(1) -* Премахване на елемент от произволна позиция: O(n) -* Премахване на елемент от началото / **края**: O(1) -* Обхождане: O(n) -Тук вече премахването на елемент от края на списъка е O(1) (Защо?) - -Елемента на двойно свързания списък би изглеждал по следния начин: -```cpp -template<class T> -struct DLListElement { - T data; - DLListElement<T>* prev; - DLListElement<T>* next; -} -``` - -## Задача първа -Да се напише функция -```cpp -template<class T> -void insertSorted(std::list<T>& 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<iostream> -#include<list> -#include"../Seminar04/linked-list-utils.h" -#include<algorithm> - -template<class T> -void insertSorted(LinkedListNode<T>*& ll, const T& elem) { - LinkedListNode<T>* toInsert = new LinkedListNode<T>(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<T>* it = ll; - - while (it->next != nullptr) { - if (it->next->data > elem) { // Намерена е позицията на елемента - LinkedListNode<T>* nNext = it->next; - it->next = toInsert; - toInsert->next = nNext; - return; - } - - it = it->next; - } - - it->next = toInsert; // Ако сме стигнали до тук то мястото на елемента е в края на списъка - } -} - -template<class T> -void insertSorted(std::list<T>& 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<int> 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<int>* head) { - LinkedListNode<int> *fast = head; - LinkedListNode<int> *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<int>; - - 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 Binary files differdeleted file mode 100644 index 03b98d7..0000000 --- a/Seminar06/media/dll.png +++ /dev/null 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<list> -#include<iostream> -#include<queue> -#include<stack> - -bool isSymethric(const std::list<int>& 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<char> q) { - std::stack<int> 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<std::queue<char>>& ll) { - std::list<int> l; - - for(auto elem : ll) - l.push_back(evaluateQueue(elem)); - - return isSymethric(l); -} - -int main() { - std::list<std::queue<char>> 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 |
