Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar06
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar06
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
8 files changed, 0 insertions, 672 deletions
-rw-r--r--Seminar06/DLLSkeleton.cpp70
-rw-r--r--Seminar06/DoublyLinkedList.hpp294
-rw-r--r--Seminar06/Linked-List-Palindrome.cpp29
-rw-r--r--Seminar06/README.md73
-rw-r--r--Seminar06/insertSorted.cpp63
-rw-r--r--Seminar06/linkedListCycle.cpp33
-rw-r--r--Seminar06/media/dll.pngbin10452 -> 0 bytes
-rw-r--r--Seminar06/task02.cpp110
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 @@
-# Двойно свързани списъци. Допълнителни задачи върху списъци.
-
-При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния.
-
-![](media/dll.png)
-
-Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са:
-* Добавяне на елемент на произволна позиция: 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
deleted file mode 100644
index 03b98d7..0000000
--- a/Seminar06/media/dll.png
+++ /dev/null
Binary files 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<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