From 0ada48f859ab59acdbd67e67e887026cacc29e33 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 9 Nov 2022 22:56:24 +0200 Subject: add Seminar06 --- Seminar06/DLLSkeleton.cpp | 70 ++++++++++++++++++++++++++ Seminar06/Linked-List-Perm.cpp | 28 +++++++++++ Seminar06/README.md | 73 +++++++++++++++++++++++++++ Seminar06/insertSorted.cpp | 30 +++++++++++ Seminar06/linkedListCycle.cpp | 33 +++++++++++++ Seminar06/media/dll.png | Bin 0 -> 10452 bytes Seminar06/task02.cpp | 110 +++++++++++++++++++++++++++++++++++++++++ 7 files changed, 344 insertions(+) create mode 100644 Seminar06/DLLSkeleton.cpp create mode 100644 Seminar06/Linked-List-Perm.cpp create mode 100644 Seminar06/README.md create mode 100644 Seminar06/insertSorted.cpp create mode 100644 Seminar06/linkedListCycle.cpp create mode 100644 Seminar06/media/dll.png create mode 100644 Seminar06/task02.cpp diff --git a/Seminar06/DLLSkeleton.cpp b/Seminar06/DLLSkeleton.cpp new file mode 100644 index 0000000..77811b8 --- /dev/null +++ b/Seminar06/DLLSkeleton.cpp @@ -0,0 +1,70 @@ +#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/Linked-List-Perm.cpp b/Seminar06/Linked-List-Perm.cpp new file mode 100644 index 0000000..ee2b1e4 --- /dev/null +++ b/Seminar06/Linked-List-Perm.cpp @@ -0,0 +1,28 @@ +#include"../Seminar04/linked-list-utils.h" + +bool isLinkedListPermRec(const LinkedListNode*& begin, const LinkedListNode* end) { + if(end == nullptr) + return true; + + bool res = isLinkedListPermRec(begin, end->next) && (begin->data == end->data); + + begin = begin->next; + return res; +} + +template +bool isLinkedListPerm(const LinkedListNode* ll) { + if(ll == nullptr) + return true; + + const LinkedListNode* begin = ll; + const LinkedListNode* end = ll; + + return isLinkedListPermRec(begin, end); +} + +int main() { + LinkedListNode* ll = new LinkedListNode(0, new LinkedListNode(1, new LinkedListNode(1))); + + std::cout << isLinkedListPerm(ll); +} \ No newline at end of file diff --git a/Seminar06/README.md b/Seminar06/README.md new file mode 100644 index 0000000..deb6873 --- /dev/null +++ b/Seminar06/README.md @@ -0,0 +1,73 @@ +# Двойно свързани списъци. Допълнителни задачи върху списъци. + +При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния. + +![](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 \ No newline at end of file diff --git a/Seminar06/insertSorted.cpp b/Seminar06/insertSorted.cpp new file mode 100644 index 0000000..5bed694 --- /dev/null +++ b/Seminar06/insertSorted.cpp @@ -0,0 +1,30 @@ +#include +#include +#include + +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 new file mode 100644 index 0000000..4aa33c6 --- /dev/null +++ b/Seminar06/linkedListCycle.cpp @@ -0,0 +1,33 @@ +#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 new file mode 100644 index 0000000..03b98d7 Binary files /dev/null and b/Seminar06/media/dll.png differ diff --git a/Seminar06/task02.cpp b/Seminar06/task02.cpp new file mode 100644 index 0000000..5f8bf92 --- /dev/null +++ b/Seminar06/task02.cpp @@ -0,0 +1,110 @@ +#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