Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar03 / README.md
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 /Seminar03/README.md
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
1 files changed, 0 insertions, 185 deletions
-rw-r--r--Seminar03/README.md185
diff --git a/Seminar03/README.md b/Seminar03/README.md
deleted file mode 100644
index dc36329..0000000
--- a/Seminar03/README.md
+++ /dev/null
@@ -1,185 +0,0 @@
-# Опашка
-Опашката е линейна структура от данни, която работи на принципа FIFO (first in first out). Опашката отговаря точно на представата за реална опашка.
-Операции:
-* Enqueue (или push) - добавя елемент в края на опашката
-* Dequeue (или pop) - премахва първия добавен елемент в опашката
-* Front - връща първия елемент в опашката
-
-Опционални операции към интерфейса:
-* empty() - Връща дали опашката е празна или не
-* size() - Връща размера на опашката
-
-В STL имаме готова реализация на опашка. Тя се намира в библиотеката \<queue> и се създава чрез std::queue\<T>.
-Пример:
-```cpp
-#include<iostream>
-#include<queue>
-
-int main() {
- std::queue<int> q;
-
- q.push(1);
- q.push(2);
- q.push(3);
- q.push(4);
-
- std::cout << q.front(); // Извежда 1
- q.pop() // Премахва 1 от опашката
- std::cout << q.front(); // Извежда 2
- q.pop(); // Премахва 2 от опашката
- q.pop(); // Премахва 3 от опашката
-}
-```
-
-## Приложения
-Едно от основните приложения на опашката е използването ѝ в различни алгоритми за обхождане на графи, като най - ясен пример за това би бил алгоритъма BFS. Други алгоритми върху графи също използват опашка (или нейни разновидности) за да обхождат графа и да решават различни задачи върху него.
-Опашките също намират голямо приложение в операционните системи и компютърните мрежи.
-
-## Начини за реализация
-### Свързани компоненти
-
-Представяме елемента на опашката по следния начин:
-```cpp
-template<class T>
-struct QueueNode {
- T data;
- QueueNode<T>* next;
-}
-```
-В класа представящ опашка пазим два указателя, head и tail:
-```cpp
-template<class T>
-class LinkedQueue {
- QueueNode<T>* head; // Представлява първия елемент, който е добавен.
- QueueNode<T>* tail; // Представлява последния елемент, който е добавен.
-}
-```
-![](media/qexample.png)
-При такова представяне как биха изглеждали алгоритмите за добавяне и премахване?
-
-### Чрез масив
-Можем да представим опашката чрез статичен или динамичен масив и два индекса - към първия и последния елемент добавен към опашката.
-![](media/arr-queue.png)
-
-При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката?
-
-# Декове
-Декът или deque (от double ended queue) е линейна структура от данни, за която можем да си мислим като опашка, позволяваща добавяне и премахване на елементи и от двете страни.
-
-Операции:
-* push_front(x) - Добавя x в началото
-* push_back(x) - Добавя х в края
-* pop_back() - Премахва последния елемент
-* pop_front() - Премахва първия елемент
-
-*A deque ("double ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list*.
-
-Стандартната библиотека ни предлага реализация на дек. Тази реализация обаче трябва да се използва внимателно. Примерно, std::deque ни позволява достъп на произволен елемент в колекцията. Това, дори да изглежда като функционалност, която не бихме отказали, често може да доведе до различен тип грешки.
-
-Пример:
-```cpp
-#include<deque>
-
-int main() {
- std::deque<int> dq;
-
- dq.push_front(1);
- dq.push_back(2);
-
- dq[0] = 10;
- // Позволява промяна, но доста често такава промяна е безсмислена.
- // Наложи ли ви се да правите такава промяна
- // вероятно използвате грешната структура от данни.
- dq[3] = 1;
- // Какво става когато такъв елемент няма?
- // Отговорът е зависи - недефинирано поведение (undefined behaviour).
-}
-```
-
-# Неща, които използвам в решението на задачите
-
-## Статични масиви и std::array
-Всички знаем, че статичният масив е бърза и удобна структура от данни. STL ни предлага готова реализация на статичен масив. Тя се намира в библиотеката \<array>.
-Пример:
-```cpp
-#include<array>
-
-int main() {
- std::array<int, 10> arr;
- arr[0] = 42;
-}
-```
-В случая arr се държи като нормален статичен масив, но идва с допълнителни помощни функции и поддържа логика за итератори.
-
-## Нетипови параметри
-Нетиповите параметри често се използват за определяне на някакви максимуми, минимуми или константи свързани с класа. Примерно, нека имаме следния код:
-
-```cpp
-const size_t MAX_SIZE = 100;
-
-template<class T>
-class staticArray {
- T data[MAX_SIZE];
-}
-```
-Това върши работа до момента в който не ни потрябват два различни варианта на staticArray - един с максимум елемента 100 а втория с максимум 50. Този проблем се решава чрез нетипови параметри по следния начин:
-```cpp
-template<class T, size_t maxSize>
-class staticArray {
- T data[maxSize];
-}
-```
-Сега много лесно мога да си направя два статични масива с различна горна граница:
-
-```cpp
-int main() {
- staticArray<int, 50> fst;
- staticArray<int, 100> snd;
-}
-```
-Тук компилаторът няма да ни се скара, понеже maxSize задължително трябва да е константа.
-Едно хубаво свойство на нетиповите параметри е, че `staticArray<T, 50>` и `staticArray<T, 100>` са два различни типа.
-
-# Задачи
-
-## Задача първа
-Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка.
-
-Пример:
-> n = 10 ➡ 1 10 11 100 101 110 111 1000 1001 1010
-
-## Задача втора
-Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната.
-
-Пример:
-> {(0, 0), (2, 1)} -> 1
->
-> {(0, 0), (7, 7)} -> 6
-
-## Задача трета - Sliding window maximum
-Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.
-
-Пример:
-
-> Вход: **[1, 3, -1, -3, 5, 3, 6, 7]**, k = 3
->
-> Output: [3, 3, 5, 5, 6, 7]
-
-Обяснение:
->
-> **[1 3 -1]** -3 5 3 6 7 => 3
->
-> 1 **[3 -1 -3]** 5 3 6 7 => 3
->
-> 1 3 **[-1 -3 5]** 3 6 7 => 5
->
-> 1 3 -1 **[-3 5 3]** 6 7 => 5
->
-> 1 3 -1 -3 **[5 3 6]** 7 => 6
->
-> 1 3 -1 -3 5 **[3 6 7]** => 7
-
-Като бонус можете да направите втора задача да не извежда само минималния път, но и клетките през които сме минали.
-
-Алтернативни решения на задачи 1 и 2 както и още задачи за упражнение можете да намерите на:
-https://github.com/ivanahristova/data-structures-fmi/tree/main/sem04 \ No newline at end of file