I.3. Линейни списъци (ЛС) от общ вид
I. Обща част · Тема 3 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027
Обхват от конспекта
Линейни списъци (ЛС) от общ вид. Рекурсивни операции с ЛС. СД стек, опашка. Сортирани ЛС.
Цел на подготовката
Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.
Примерна писмена разработка
Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.
Линейни списъци и рекурсия
Линейният списък е крайна последователност от елементи, всеки от които има определено място спрямо останалите. При едносвързано представяне възелът съдържа стойност и връзка към следващия възел. При двусвързано представяне има и връзка към предходния. Празният списък е самостоятелен допустим случай. Цикличните списъци свързват края с началото и изискват подходящо условие за прекратяване на обхождането.
Едносвързан списък може рекурсивно да се разглежда като празен списък или като глава и остатък. Дължината е 0 за празния случай и 1 плюс дължината на остатъка за непразния. Сумиране, търсене, филтриране и копиране могат да се дефинират по същия принцип. Коректната рекурсия има базов случай, намалява задачата и запазва смисъла на резултата. При n възела подобно обхождане е O(n) по време и използва до O(n) стекови кадъра, ако няма оптимизация на опашната рекурсия.
Основни операции и сортиран списък
Вмъкването в началото и премахването на първия възел са O(1). Вмъкване след вече известен възел също е O(1), но намирането на позицията може да е O(n). Премахване на възел от едносвързан списък обичайно изисква неговия предшественик; наличието само на адреса на възела не гарантира постоянно време във всички случаи. Достъпът до i-тия елемент е O(i), а не O(1). Трябва да се обработват отделно празен списък, първи и последен възел и освобождаване на паметта.
В сортиран списък елементите удовлетворяват условие за наредба. При търсене може да се спре, когато текущият елемент надмине търсения, но най-лошата сложност остава O(n). Вмъкването първо намира мястото и после пренасочва връзките. Два сортирани списъка с дължини n и m могат да се слеят за O(n+m), като на всяка стъпка се избира по-малката текуща глава.
Стек и опашка
Стекът е абстрактен тип с дисциплина LIFO: последният добавен елемент се премахва първи. Операциите са push, pop и преглед на върха. Използва се за извиквания, връщане назад и обработка на вложени конструкции. Опашката следва FIFO: първият добавен излиза първи. Нейни операции са добавяне в края и премахване отпред; използва се при обслужване на заявки и BFS. Свързаната опашка с указатели към начало и край осигурява O(1) за двете операции. Цикличният масив е алтернативна реализация с индекси и ясно разграничение между пълен и празен буфер.
Следователно списъкът е обща организация на последователност, а стекът и опашката ограничават достъпните операции според задачата. Разграничаването между интерфейс и реализация е основа за правилния им избор.
Литературна опора
За сверяване с литературата от конспекта: позиции 2 и 5 в библиографията. Допълнително: MIT 6.006 — структури и алгоритми.
Уроци за четене
- Линеен списък от общ вид — вмъкване в средата
- Рекурсивни операции с линейни списъци — дължина
- Стек и опашка
- Сортиран линеен списък
Литература
Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.
Примери и упражнения
Всеки урок има самостоятелна задача с четири отговора за самопроверка.
Писмена разработка и устни въпроси
Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:
- Въведение: предмет, предназначение и място на темата.
- Точни определения, означения и основни понятия.
- Последователно изложение на подточките от конспекта и връзките между тях.
- Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
- Важни свойства, ограничения, сравнения и типични грешки.
- Кратко обобщение.
Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.