Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar06 / README.md
diff options
context:
space:
mode:
Commit0ada48f859ab59acdbd67e67e887026cacc29e33 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2022-11-09 22:56:24 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2022-11-09 22:56:24 +0200
Files4b4edeee0fc768ddf48073804c4a0f8719e580ed /Seminar06/README.md
Data-structures-and-algorithms-0ada48f859ab59acdbd67e67e887026cacc29e33.tar
Data-structures-and-algorithms-0ada48f859ab59acdbd67e67e887026cacc29e33.tar.gz
Data-structures-and-algorithms-0ada48f859ab59acdbd67e67e887026cacc29e33.zip
Parent16a916c1fc7ecf89bfbf910445740fb4596aae8f (diff)
add Seminar06
1 files changed, 73 insertions, 0 deletions
-rw-r--r--Seminar06/README.md73
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 @@
+# Двойно свързани списъци. Допълнителни задачи върху списъци.
+
+При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния.
+
+![](media/dll.png)
+
+Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са:
+* Добавяне на елемент на произволна позиция: 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