diff options
add Sem03
1 files changed, 185 insertions, 0 deletions
| -rw-r--r-- | Seminar03/README.md | 185 |
diff --git a/Seminar03/README.md b/Seminar03/README.md new file mode 100644 index 0000000..3dad403 --- /dev/null +++ b/Seminar03/README.md @@ -0,0 +1,185 @@ +# Опашка +Опашката е линейна структура от данни, която работи на принципа 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; // Представлява последния елемент, който е добавен. +} +``` + +При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? + +### Чрез масив +Можем да представим опашката чрез статичен или динамичен масив и два индекса - към първия и последния елемент добавен към опашката. + + +При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката? + +# Декове +Декът или 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 |