blob: e333dc2ada4ed730e04f717b734d6ccbba5f812f (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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
|
