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 — структури и алгоритми.

Уроци за четене

  1. Линеен списък от общ вид — вмъкване в средата
  2. Рекурсивни операции с линейни списъци — дължина
  3. Стек и опашка
  4. Сортиран линеен списък

Литература

Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.

Примери и упражнения

Всеки урок има самостоятелна задача с четири отговора за самопроверка.

Писмена разработка и устни въпроси

Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:

  1. Въведение: предмет, предназначение и място на темата.
  2. Точни определения, означения и основни понятия.
  3. Последователно изложение на подточките от конспекта и връзките между тях.
  4. Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
  5. Важни свойства, ограничения, сравнения и типични грешки.
  6. Кратко обобщение.

Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.