diff options
Cleanup
1 files changed, 0 insertions, 73 deletions
| -rw-r--r-- | Seminar06/README.md | 73 |
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 @@ -# Двойно свързани списъци. Допълнителни задачи върху списъци. - -При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния. - - - -Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са: -* Добавяне на елемент на произволна позиция: O(n) -* Добавяне на елемент в началото/края O(1) -* Премахване на елемент от произволна позиция: O(n) -* Премахване на елемент от началото / **края**: O(1) -* Обхождане: O(n) -Тук вече премахването на елемент от края на списъка е O(1) (Защо?) - -Елемента на двойно свързания списък би изглеждал по следния начин: -```cpp -template<class T> -struct DLListElement { - T data; - DLListElement<T>* prev; - DLListElement<T>* next; -} -``` - -## Задача първа -Да се напише функция -```cpp -template<class T> -void insertSorted(std::list<T>& 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 |
