Изследвайте поведението на масиви, свързани списъци, стекове и опашки. Контролирайте всяка операция и наблюдавайте как състоянието се променя стъпка по стъпка.
Масивът е последователна структура от данни, достъпна чрез индекс и подходяща за линейно пресичане.
Сравнете линейното и двоичното търсене. Въведете стойности, изберете алгоритъм и проследете стъпките.
Последна стъпка: —
Псевдокод
обход за i от 0 до n
връщане на индекса при съвпадение
върни -1 при липса
Приложете показаните операции в реална C# имплементация.
Работа с масив (C#)
Управление на последователни данни.
Достъпът по индекс в масива е операция с константна сложност O(1), тъй като адресът се изчислява директно.
Избор на подходящ алгоритъм за търсене.
Линейното търсене проверява всеки елемент последователно, докато двоичното изисква сортиран масив и разделя диапазона наполовина.
Оценка на цената на модификациите.
Добавянето в края е O(1) (амортизирано), а в началото – O(n), защото елементите се преместват.
Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.
Въпрос 1: Каква е сложността на линейното търсене в масив?
Въпрос 2: Какво изисква двоичното търсене?
Въпрос 3: Коя операция е O(1) при масив?
Въпрос 4: Какво представлява амортизирана сложност?
Въпрос 5: Кога изтриването в масив е най-скъпо?
Свързаният списък съхранява елементи чрез възли с препратки към следващия (и предишния) елемент.
Вижте как се вмъкват и премахват възли, като следите връзките между тях.
Index 0
3
Index 1
7
Index 2
11
Изходно състояние на списъка.
Псевдокод
нов възел = { стойност, next }
нов възел.next = текущ head
head = нов възел
прескачане на възел за изтриване
Приложете показаните операции в реална C# имплементация.
Свързан списък (C#)
Разбиране на референтната структура.
Всеки възел съдържа стойност и указател към следващия възел. Паметта не е последователна.
Управление на указатели за манипулация на възлите.
Вмъкването в началото и изтриването са O(1), а намирането на елемент е O(n), тъй като се обхожда списъкът.
Избор между масив и списък спрямо контекста.
Свързаните списъци са динамични и пестят преместването на елементи, но имат по-голям разход на памет.
Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.
Въпрос 1: Каква е сложността за добавяне на нов възел в началото?
Въпрос 2: Как се намира елемент със стойност X?
Въпрос 3: Какво става при липса на актуализиране на указателите при изтриване?
Въпрос 4: Какъв е разходът на памет на възел?
Въпрос 5: Кое е предимство на двусвързания списък?
Стекът работи по принципа последен влязъл – първи излязъл (LIFO) и се използва за управление на извикванията на функции.
Наблюдавайте добавянето и премахването на елементи от върха и какво се случва при пъл/празен стек.
Демонстрация на push и pop операции.
Псевдокод
push(x): ако има място → постави елемента на върха
ако стекът е пълен → overflow
pop(): премахни върха и върни стойността
ако стекът е празен → underflow
Приложете показаните операции в реална C# имплементация.
Стек операции (C#)
Създаване на практически асоциации.
Стекът се използва за рекурсивни извиквания, отмяна на операции и парсинг на изрази.
Избор на подходяща базова структура.
Може да се реализира върху масив или списък. Капацитетът се проверява за да се избегне overflow.
Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.
Въпрос 1: Как се нарича премахването на елемент от стека?
Въпрос 2: Каква е сложността на push?
Въпрос 3: Какво е overflow?
Въпрос 4: Как се проверява дали стекът е празен?
Въпрос 5: Кое е пример за използване на стек?
Опашката работи по принципа първи влязъл – първи излязъл (FIFO) и се прилага при управление на задачи.
Вижте как опашката обслужва елементите в реда на постъпване.
FIFO обработка на елементи.
Псевдокод
enqueue(x): добави елемент в края
dequeue(): премахни елемент от началото
ако queue е пълна → overflow
ако queue е празна → underflow
Приложете показаните операции в реална C# имплементация.
Опашка операции (C#)
Оптимизиране на използваната памет.
Кръговата опашка използва масив и два индекса (front и rear), които се въртят при достигане на края.
Свързване с реални сценарии.
Опашките са основа за BFS, управление на заявки до сървъри и буфериране.
Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.
Въпрос 1: Каква е сложността на dequeue?
Въпрос 2: Какво е underflow?
Въпрос 3: Кой алгоритъм използва опашка?
Въпрос 4: Как се отбелязва празна кръгова опашка?
Въпрос 5: Какво е предимство на опашката пред стека?
Предстоящи теми
TODO: Хеш таблици – допълнителни визуализации, дървета, графи, BFS/DFS.