Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar04
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 /Seminar04
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
7 files changed, 0 insertions, 516 deletions
-rw-r--r--Seminar04/README.md209
-rw-r--r--Seminar04/find-middle.cpp28
-rw-r--r--Seminar04/insert-at-beg.cpp20
-rw-r--r--Seminar04/linked-list-utils.h74
-rw-r--r--Seminar04/media/AmortizedAnalysis.pngbin1586478 -> 0 bytes
-rw-r--r--Seminar04/reorder-linked-list.cpp160
-rw-r--r--Seminar04/reverse-linked-list.cpp25
diff --git a/Seminar04/README.md b/Seminar04/README.md
deleted file mode 100644
index eb35f37..0000000
--- a/Seminar04/README.md
+++ /dev/null
@@ -1,209 +0,0 @@
-# Динамичен масив - преговор с разширение
-
-## Какво беше динамичен масив
-Динамичния масив е линейна структура от данни с произволен достъп до елементите. Различава се от статичния масив по това, че можем да имаме произволен брой елементи в колекцията. Тази структура от данни трябва да ви е добре позната, най - малкото от нейната реализация в STL наречена std::vector\<T>;
-Вектора е изключително популярна структура и да я познаваме ни помага да пишем по - бързи и по - сигурни програми.
-
-Част от интерфейса на std::vector:
-* push_back(const T&) - добавя елемент в края
-* pop_back() - премахва елемент от края
-* operator[](size_t index) - връща елемент на индекс за четене/писане. Не прави проверка дали индекса е валиден или не
-* at(size_t index) - връща елемент на индекс за четене/писане. Хвърля std::out_of_range грешка ако индексът е невалиден.
-
-Нека разгледаме следния код:
-```cpp
-int main() {
- int arr[100];
- int n = 0;
- std::cin >> n;
-
- for(int i = 0; i < n; i++)
- arr[i] = getValue(); // Просто някаква стойност
-}
-```
-Тук главния проблем е какво правим когато n стане по - голямо от 100. Много просто, заделяме 200 елемента вместо 100. Лесно виждаме, как това води до множество проблеми и прави кода неефикасен когато за n не знаем достатъчно. Сега вектора ни идва на помощ:
-
-```cpp
-#include<vector>
-
-int main() {
- std::vector<int> v;
- int n = 0;
- std::cin >> n;
-
- for(int i = 0; i < n; i++)
- v.push_back(getValue());
-}
-```
-Припомняме как работи вектора: Първоначално алокираме някакъв масив. Пазим две променливи *size* и *capacity*. В *size* пишем колко елемента имаме а в *capacity* - колко е размера на алокирания масив. Момента в който *size* стане колкото *capacity* удвояваме масива. Това става чрез просто заделяне на два пъти повече памет, копиране на всичко от старата памет в новата и изтриване на новата памет.
-
-Примерно, за начално *capacity* равно на 1 ще имаме следния сценарий:
-```
- +--+
-Insert 11 |11|
- +--+
- +--+--+
-Insert 12 |11|12|
- +--+--+
- +--+--+--+--+
-Insert 13 |11|12|13| |
- +--+--+--+--+
- +--+--+--+--+
-Insert 14 |11|12|13|14|
- +--+--+--+--+
- +--+--+--+--+--+--+--+--+
-Insert 15 |11|12|13|14|15| | | |
- +--+--+--+--+--+--+--+--+
-```
-
-Тази идея изглежда прекрасно. Можем да си правим колкото искаме *push_back()* и да не мислим за нищо - те хората са го измислили. Е, има още един малък проблем. Алокацията на памет не е евтина операция.
-``` cpp
-class DynArray {
- T* data;
- size_t size = 0;
- size_t capacity = 8;
-};
-```
-Нека в началото *capacity* да е 8. Кога ще имаме алокация? Първо, ще алокираме памет при създаването на масива. След това, когато се опитаме да добавим девети елемент ще алокираме 16 \* sizeof(T) байта. След това когато се опитаме да добавим седемнадесети елемент ще алокираме 32 \* sizeof(T) байта.
-Тоест, когато въртя for цикъла във втория пример, всеки път когато *i = 2^k + 1* ще имам алокация на памет.
-
-Това за наше щастие има как да се оправи. Когато знаем колко елемента ще пазим в динамичния масив можем да извикаме *resize(size_t)*.
-Това ще направи точно една алокация.
-
-```cpp
-#include<vector>
-
-int main() {
- int n = 0;
- std::cin >> n;
- std::vector<int> v;
-
- v.resize(n); // Ресайзва масива за да съдържа точно n елемента.
-
- for(int i = 0; i < n; i++)
- v[i] = getValue();
-}
-```
-Това е удобен трик, но не прекалявайте с него - не е нужно да ресайзваме навсякъде! Просто, ако знаете предварително колко голяма е дължината на вектора, може да направите само една алокация.
-Примерно, в следния случай няма да е добра идея да правим *resize*:
-
-```cpp
-std::vector<int> filter(const std::vector<int>& arr, bool (*pred)(int)) {
- std::vector<int> result;
- // Тук не знаем предварително колко ще е размерът на result.
- for(int i = 0; i < arr.size(); i++)
- if(pred(arr[i]))
- result.push_back(arr[i]);
- return result;
-}
-```
-
-## Сложността на push_back
-До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждаме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка.
-
-В случая worst case сложността е твърде песимистична. Интересува ни по - скоро колко време ще отнеме цялото изпълнение на алгоритъма използващ push_back() а не колко време ще отнеме на 17 стъпка, примерно. Приемаме по - оптимистичен подход - нека не се интересуваме от това колко е най - лошия случай на операцията а да разгледаме колко време ни отнема да направим всички операции.
-Това неформално е целта на така наречения амортизиран анализ на сложност. С него няма да се занимаваме особено много, но е добре да го знаем от обща култура.
-![](media/AmortizedAnalysis.png)
-
-## Сложност на вмъкване на елемент на произволен индекс
-Вмъкването в края на вектора се оказа практически ефикасна операция. Но дали това остава така ако примерно искаме да вмъкнем елемент по средата? Отговорът е не - това вече си е линейна операция. В най - лошия случай ако искаме да вмъкнем елемент на първа позиция ще трябва да изместим надясно всички елементи на масива. Какво става обаче ако такъв тип вмъквания станат нужни? Има ли начин да ги направим бързи?
-
-# Свързани списъци
-Свързания списък е линейна структура от данни в която елементите не се пазят в последователна памет. Всеки елемент пази указател към следващия а ако няма следващ пазим nullptr.
-
-```cpp
-template<class T>
-struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
-
- // Удобен конструктор!
- LinkedListNode(const T& elem, LinkedListNode<T>* n = nullptr) : data{elem}, next {n} {}
-}
-```
-Тук е добро място да си поговорим какво наричаме пряк и последователен достъп (или Random/direct access и Sequential access).
-* При прекия достъп можем да достъпим всеки елемент от колекцията за равно време
-* При последователния достъп не можем да достъпим елемент преди да сме обходили елементите преди него в наредбата.
-
-Свързания списък е добър пример за структура с последователен достъп. Пряк достъп имат масивите.
-Има различни видове свързани списъци с които ще се занимаваме с течение на курса.
-Едносвързания списък поддържа следните операции:
-* push_front(const T& elem) - Добавя елемент в началото O(1)
-* push_at(size_t idx, const T& elem) - Добавя елемент на индекс. O(n)
-* pop_front() - Премахва елемента в началото - O(1)
-* pop_at(size_t index) - Премахва елемента на позиция index O(n)
-
-Свързания списък стандартно се представя чрез указател към първия му елемент. Доста често обаче се пази и указател към последния. Това ни помага да имаме бързо добавяне в края на списъка. Наистина, представяме списъка като два указателя - към първия и последния елемент и искаме да обединим два такива списъка това би станало за O(1) време.
-
-```cpp
-template<class T>
-class LinkedList {
-private:
- struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
- };
-
- LinkedListNode* head; // Началото на списъка
- LinkedListNode* tail; // Края на списъка
-
-public:
- void merge(const LinkedList<T>& second) {
- // O(1) сливане на два списъка без значение от размерите им
- tail->next = second.head;
- tail = second.tail;
- }
-};
-
-```
-Също така, ако имаме указател към дадена позиция в списъка, можем да добавяме колкото си искаме елементи на тази позиция. Всичко става чрез пренасочване на пойнтъри.
-Засега ще представяме свързания списък просто като структура с информация и указател. В следващите семинари ще разгледаме алтернативни представяния и ще видим колко точно ефикасни са спрямо дадени операции!
-
-# Задачи
-
-## Задача първа
-Да се напише функция, която добавя елемент в началото на едносвързан списък
-
-Пример:
-
-LL = 2 -> 3 -> 4
-
-insert(LL, 1)
-
-LL = 1 -> 2 -> 3 -> 4
-
-## Задача втора
-Да се напише функция, която обръща едносвързан списък.
-
-Пример:
-
-LL = 1 -> 2 -> 3 -> 4 -> 5
-
-reverse(LL);
-
-LL = 5 -> 4 -> 3 -> 2 -> 1
-
-## Задача трета
-Да се напише функция, която открива средата на свързан списък.
-Пример:
-
-```
-1 -> 2 -> 3 -> 4 -> 5 => 3
-
-1 -> 2 -> 3 -> 4 => 3
-```
-
-## Задача четвърта
-да се напише функция която пренарежда свързания списък по следния начин:
-
-LL = 1 -> 2 -> 3 -> 4 -> 5
-
-reorder(LL);
-
-LL = 1 -> 5 -> 2 -> 4 -> 3
-
-Когато пишете задачи за свързан списък винаги пробвайте случая когато:
-* Имате празен списък
-* Имате списък с един елемент
-* Имате списък и четни елементи
-* Имате списък с нечетни елементи
diff --git a/Seminar04/find-middle.cpp b/Seminar04/find-middle.cpp
deleted file mode 100644
index dc587ba..0000000
--- a/Seminar04/find-middle.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include"linked-list-utils.h"
-
-template<class T>
-LinkedListNode<T>* findMiddle(LinkedListNode<T>* ll) {
- LinkedListNode<T>* fast = ll;
- LinkedListNode<T>* slow = ll;
-
-
- while(fast && fast->next) {
- fast = fast->next->next;
- slow = slow->next;
- }
-
- return slow;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4))));
- LinkedListNode<int>* lls = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4, new LinkedListNode(5)))));
-
- LinkedListNode<int>* firstMiddle = findMiddle(ll);
- LinkedListNode<int>* secondMiddle = findMiddle(lls);
-
- std::cout << firstMiddle->data << " " << secondMiddle->data;
-
- freeList(ll);
- freeList(lls);
-} \ No newline at end of file
diff --git a/Seminar04/insert-at-beg.cpp b/Seminar04/insert-at-beg.cpp
deleted file mode 100644
index 88c3d74..0000000
--- a/Seminar04/insert-at-beg.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-#include"linked-list-utils.h"
-
-template<class T>
-void insertAtBegin(LinkedListNode<T>*& ll, const T& elem) {
- LinkedListNode<T>* toInsert = new LinkedListNode(elem, ll);
- ll = toInsert;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3)));
- printLinkedList(ll);
- insertAtBegin(ll, 0);
- printLinkedList(ll);
- freeList(ll);
-}
-
-int main() {
-
-
-} \ No newline at end of file
diff --git a/Seminar04/linked-list-utils.h b/Seminar04/linked-list-utils.h
deleted file mode 100644
index bf093ba..0000000
--- a/Seminar04/linked-list-utils.h
+++ /dev/null
@@ -1,74 +0,0 @@
-#include<iostream>
-#include<initializer_list>
-
-template<class T>
-struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
-
- LinkedListNode(const T& elem, LinkedListNode<T>* n = nullptr) : data{elem}, next {n} {}
-};
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- std::cout << iterate->data << " ";
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll, void (*print)(T)) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- print(iterate->data);
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll, void (*print)(const T&)) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- print(iterate->data);
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-LinkedListNode<T>* fromList(const std::initializer_list<T>& l) {
- LinkedListNode<T>* toReturn = nullptr;
- LinkedListNode<T>* iter = nullptr;
-
- for(const auto& elem : l) {
- LinkedListNode<T>* toInsert = new LinkedListNode<T>(elem);
- if(iter == nullptr) {
- toReturn = toInsert;
- iter = toInsert;
- }
- else {
- iter->next = toInsert;
- iter = iter->next;
- }
- }
- return toReturn;
-}
-
-template<class T>
-void freeList(LinkedListNode<T>* ll) {
- while(ll) {
- LinkedListNode<T>* toDelete = ll;
- ll = ll->next;
- delete toDelete;
- }
-} \ No newline at end of file
diff --git a/Seminar04/media/AmortizedAnalysis.png b/Seminar04/media/AmortizedAnalysis.png
deleted file mode 100644
index 77f570a..0000000
--- a/Seminar04/media/AmortizedAnalysis.png
+++ /dev/null
Binary files differ
diff --git a/Seminar04/reorder-linked-list.cpp b/Seminar04/reorder-linked-list.cpp
deleted file mode 100644
index 6259a36..0000000
--- a/Seminar04/reorder-linked-list.cpp
+++ /dev/null
@@ -1,160 +0,0 @@
-#include"linked-list-utils.h"
-#include<deque>
-
-// O(n) time
-// O(n) complexity
-void reorderWithDeque(LinkedListNode<int>* head) {
- if(!head || !head->next)
- return;
-
- std::deque<LinkedListNode<int>*> dq;
-
- LinkedListNode<int>* it = head;
-
- while(it) {
- dq.push_back(it);
- it = it->next;
- }
-
- // Винаги пазим края на вече готовия списък
- // Ако не е ясно как го използвам прочети обяснението над втория метод
- // идеята е същата.
- LinkedListNode<int>* backOfNewList = nullptr;
-
- while(!dq.empty()) {
- // Ако размерът е 1 то имаме нечетен брой елементи и просто добавяме последния в края
- if(dq.size() == 1) {
- backOfNewList->next = dq.front();
- backOfNewList = backOfNewList->next;
- break;
- }
-
- // Първия елемент останал в дека започва да сочи към последния.
- // Генерираме коректна двойка.
- dq.front()->next = dq.back();
-
- // Ако края на списъка не е nullptr следващите два елемента
- // в списъка са dq.front()->dq.front()->next (което е dq.back())
- if(backOfNewList)
- backOfNewList->next = dq.front(); // Сложи следващите два елемента накрая
-
- backOfNewList = dq.front()->next; // Вече края на списъка е друг. Преместваме се там.
-
- dq.pop_back();
- dq.pop_front();
- }
-
- // next на последния елемент от списъка е nullptr, този ред е важен.
- backOfNewList->next = nullptr;
-}
-
-// Това ще ни помогне за второто решение
-template<class T>
-void reverseLinkedList(LinkedListNode<T>*& ll) {
- LinkedListNode<T>* previous = nullptr;
- LinkedListNode<T>* next = nullptr;
- LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- next = iterate->next;
- iterate->next = previous;
- previous = iterate;
- iterate = next;
- }
-
- ll = previous;
-}
-
-// Това също
-template<class T>
-LinkedListNode<T>* findMiddle(LinkedListNode<T>* ll) {
- LinkedListNode<T>* fast = ll;
- LinkedListNode<T>* slow = ll;
-
- while(fast && fast->next) {
- fast = fast->next->next;
- slow = slow->next;
- }
-
- return slow;
-}
-
-/*
-Тук идеята е да намерим средата и да я обърнем. Две неща, които вече знаем как да правим. Как ще протече алгоритъма:
-
-Вход: 1 -> 2 -> 3 -> 4 -> 5
-Среда: 3 -> 4 -> 5
-
-Обърната среда: 5 -> 4 -> 3 -> nullptr
-Как изглежда първоначалния масив: 1 -> 2 -> 3 -> nullptr
-
-Дали е бъг, че и в двата списъка имаме еднакъв последен елемент? Малко неточно е, но за да го оправя трябва да променя функциите.
-С цел да са разбираеми нещата го оставям така.
-
-В случая става нещо подобно:
-1-> 2 -> 3 -> nullptr
- ^
-5 -> 4 /
-
-Виждаме, че последователно трябва да вземаме двойки (L_0 -> L_n) -> (L_1 -> L_{n-1}) -> (L_2 -> L_{n - 2}) -> ... и да ги поставяме една след друга.
-
-* firstHalf -> първата половина от списъка
-* mid -> Втората половина от списъка
-* currentPair -> текущата двойка (L_i -> L_{n - i})
-* backOfList -> Края на коректния списък от двойки
-
-Сега имаме този сценарий:
-[някакъв коректен списък] [коректна двойка]
-* Насочи края на този коректен списък да сочи към коректната двойка. Това става лесно понеже му пазя края!
-[някакъв вече готов списък] -> [коректна двойка]
-* Сега насочи указателя който пази края на коректния списък да сочи към края на този списък, понеже този списък е корекрен.
-[стария коректен списък -> коректната двойка] - готов за още коректни двойки!
-
-Така добавямe коректни двойки докато не стигна края на списъка съдържащ обърнатата дясна част.
-*/
-void reorderWithTwoPointers(LinkedListNode<int>* ll) {
- if(!ll || !ll->next)
- return;
-
- LinkedListNode<int>* mid = findMiddle(ll);
- reverseLinkedList(mid);
-
- LinkedListNode<int>* firstHalf = ll;
- LinkedListNode<int>* currentPair = nullptr;
- LinkedListNode<int>* backOfList = nullptr;
-
- while(mid) {
- currentPair = firstHalf;
- firstHalf = firstHalf->next;
-
- // Случая в който имаме нечетен брой елементи
- if(!firstHalf) {
- backOfList->next = currentPair;
- backOfList = backOfList->next;
- break;
- }
-
- currentPair->next = mid;
- mid = mid->next;
-
- if(backOfList)
- backOfList->next = currentPair; // Пренасочи края към коректната двойка. Ако е nullptr нямаме какво да пренасочваме.
-
- backOfList = currentPair->next; // И един бърз ъпдейт на края - вече края на коректния лист е стария лист + новата двойка
- }
-
- backOfList->next = nullptr;
-}
-
-int main() {
- LinkedListNode<int>* ll = new LinkedListNode<int>
- (1, new LinkedListNode<int>
- (2, new LinkedListNode<int>
- (3, new LinkedListNode<int>
- (4, new LinkedListNode<int>
- (5)))));
-
- reorderWithTwoPointers(ll);
- printLinkedList(ll);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Seminar04/reverse-linked-list.cpp b/Seminar04/reverse-linked-list.cpp
deleted file mode 100644
index 486b41e..0000000
--- a/Seminar04/reverse-linked-list.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-#include "linked-list-utils.h"
-
-template<class T>
-void reverseLinkedList(LinkedListNode<T>*& ll) {
- LinkedListNode<T>* previous = nullptr;
- LinkedListNode<T>* next = nullptr;
- LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- next = iterate->next;
- iterate->next = previous;
- previous = iterate;
- iterate = next;
- }
-
- ll = previous;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4))));
- printLinkedList(ll);
- reverseLinkedList(ll);
- printLinkedList(ll);
- freeList(ll);
-} \ No newline at end of file