From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar06/README.md | 73 ----------------------------------------------------- 1 file changed, 73 deletions(-) delete mode 100644 Seminar06/README.md (limited to 'Seminar06/README.md') 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 -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 -- cgit v1.3.1-26-gb76a