diff options
add Seminar06
1 files changed, 73 insertions, 0 deletions
| -rw-r--r-- | Seminar06/README.md | 73 |
diff --git a/Seminar06/README.md b/Seminar06/README.md new file mode 100644 index 0000000..deb6873 --- /dev/null +++ b/Seminar06/README.md @@ -0,0 +1,73 @@ +# Двойно свързани списъци. Допълнителни задачи върху списъци. + +При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния. + + + +Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са: +* Добавяне на елемент на произволна позиция: 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
\ No newline at end of file |
