I.3. Линейни списъци (ЛС) от общ вид — Разширена писмена разработка
Разширена писмена разработка. I.3. Линейни списъци (ЛС) от общ вид
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Линейни списъци (ЛС) от общ вид. Рекурсивни операции с ЛС. СД стек, опашка. Сортирани ЛС.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Линейни списъци (ЛС) от общ вид — 1. Линейни списъци от общ вид; 2. Основни операции и коректност
- Рекурсивни операции с ЛС — 3. Рекурсивни операции с линейни списъци
- СД стек, опашка — 4. Стек и опашка
- Сортирани ЛС — 5. Сортирани линейни списъци и извод
Кратък план за изпита
- Линеен списък и неговото логическо устройство.
- Едносвързано, двусвързано и циклично представяне.
- Основни операции, гранични случаи и сложност.
- Рекурсивно определение и операции.
- Стек и опашка като ограничени интерфейси.
- Сортирани списъци и обобщение.
1. Линейни списъци от общ вид
Линейният списък е крайна последователност от елементи. При непразен списък има първи и последен елемент; всеки вътрешен елемент има непосредствен предшественик и наследник в логическия ред. Стойностите могат да се повтарят. Позицията и стойността са различни: в [4,7,4] двата елемента със стойност 4 заемат различни позиции. „От общ вид“ означава, че не ограничаваме всички операции само до единия или до двата края.
Списъкът като абстрактен обект не е тъждествен на свързаната реализация. В последователно представяне може да използваме масив. В едносвързано представяне всеки възел съдържа стойност и указател към следващия, а head сочи първия възел. Последният сочи към липсващ възел. В двусвързан списък има и указател към предишния възел. Цикличният списък свързва края с началото, поради което условието за приключване на обхождането е различно.
head → [12 | next] → [7 | next] → [19 | ∅]
Предимство на свързаното представяне е, че вмъкване до известен възел не премества останалите елементи. Недостатъци са паметта за връзките, разпръснатото разполагане и липсата на пряк достъп до произволна позиция. Динамичният размер не означава неограничена памет: всяко заделяне може да се провали и собствеността върху възлите трябва да е определена.
2. Основни операции и коректност
Типичните операции са създаване на празен списък, проверка за празнота, обхождане, търсене, достъп, добавяне и премахване. При едносвързан списък добавянето в началото пренасочва новия възел към стария първи и след това променя head. При изтриване на първия възел новият head става старият head.next, а старият възел се освобождава, ако структурата го притежава.
За добавяне след известен възел p първо насочваме новия възел към p.next, след това p.next към новия. Обратният ред без запазване на старата връзка може да изгуби остатъка от списъка. За изтриване след p пренасочваме p към наследника на премахвания възел. Тези промени са O(1), но откриването на p по стойност или индекс обичайно е O(n).
Търсенето по стойност и достъпът до k-тата позиция са линейни в най-лошия случай. Добавянето в края е O(1), ако поддържаме валиден указател tail; без него е нужно обхождане. При двусвързан списък изтриването на известен възел е O(1), но трябва да се поправят и двете посоки. Особено се проверяват празният списък, единственият възел, началото и краят.
3. Рекурсивни операции с линейни списъци
Рекурсивното описание е: списъкът е празен или се състои от първи елемент и остатък, който също е списък. Това задава естествена схема за алгоритми. Базовият случай обработва празния списък; рекурсивната стъпка обработва първия елемент и извиква операцията за остатъка. За да има завършване при ацикличен краен списък, всяка стъпка трябва да преминава към по-къс остатък.
length(p):
if p = ∅: return 0
return 1 + length(p.next)
contains(p, x):
if p = ∅: return false
if p.value = x: return true
return contains(p.next, x)
За показания списък дължината е 3. Доказателството за алгоритъма следва структурна индукция: празният списък има дължина нула, а добавянето на един първи елемент увеличава дължината на остатъка с едно. Времето е Θ(n), а дълбочината на рекурсията е Θ(n). Това означава допълнителна стекова памет O(n) при обикновена реализация; не бива автоматично да се предполага оптимизация на опашкова рекурсия.
Рекурсивно отпечатване първо на остатъка, а после на текущата стойност показва елементите в обратен ред, без да променя връзките. То се различава от обръщане на самия списък. Наивно конструиране на обратен списък чрез многократно добавяне в края може да изисква O(n²). Натрупването в началото или пренасочването на връзките дава линеен алгоритъм.
4. Стек и опашка
Стекът поддържа дисциплина LIFO: последният добавен е първи за премахване. Основните операции са push, pop, top и проверка за празнота. Ако добавим последователно A, B и C, първото премахване връща C. Стекът се използва при извикване на функции, проверка на скоби, обработка на изрази и търсене в дълбочина.
Стек може да се реализира чрез динамичен масив с връх в края или чрез списък с връх в началото. При списъка основните операции са O(1); при геометрично растящ масив добавянето е амортизирано O(1). Опитът за pop върху празен стек изисква определено поведение — грешка или специален резултат, а не произволен достъп до памет.
Опашката използва FIFO: първият добавен е първи за премахване. enqueue добавя в края, dequeue премахва от началото, а front чете първия. При добавяне A, B, C първото премахване връща A. Приложения са обработка на заявки, буфери и търсене в ширина.
Свързаната опашка с head и tail изпълнява добавянето и премахването за O(1). При премахване на последния възел и двата указателя трябва да станат празни. Цикличен масив използва индекси, които се връщат в началото по модул капацитета. Нужен е допълнителен брояч или свободна позиция, за да се различават пълно и празно състояние. Опашка, която мести всички елементи след всяко премахване, е възможна, но има O(n) цена на тази операция.
5. Сортирани линейни списъци и извод
Сортираният списък пази инвариант за ред, например всяка стойност да е не по-голяма от следващата. При търсене можем да спрем, щом текущата стойност стане по-голяма от търсената. Това подобрява някои случаи, но най-лошата сложност в свързан списък остава O(n). Двоичното търсене не придобива автоматично O(log n) общо време, защото средният възел не е достъпен за O(1).
Вмъкването първо открива правилната позиция, после променя връзките. Добавяне на 6 към [2,5,9] дава [2,5,6,9]. Трябва да е определено дали се допускат равни стойности и къде се поставят. Сливането на два сортирани списъка последователно избира по-малкия от двата първи необработени елемента и има O(n+m) време. То е полезно при merge sort, който сортира списък за O(n log n).
Общият извод е, че списък, стек и опашка трябва да се разглеждат чрез договора на операциите, а не само чрез картинка на възли. Рекурсивното определение помага за правилност, а анализът на представянето обяснява сложността. При всяка оценка уточняваме дали позицията вече е известна и дали включваме времето за нейното намиране.
Сверка на операциите и граничните случаи
Сверка със СУ 2: Стек: ориг. 30–55 / нов PDF 27–52; опашка: ориг. 55–77 / нов PDF 51–73; списък: ориг. 78–89 / нов PDF 73–84; сортиране/сливане: ориг. 95–99 / нов PDF 89–94.
В едносвързания списък от учебника се поддържат указатели към началото, края и текущия възел за обхождане. Това са помощни данни на реализацията, различни от логическата последователност. Премахването на последния възел трябва да възстанови празното състояние; итератор, сочещ към изтрит възел, вече не е валиден. При собственост върху възлите копирането създава нови възли.
Операцията „вмъкни след известен възел“ е константна, но „вмъкни пред този възел“ в едносвързана структура може да изисква търсене на предшественик. При двусвързана структура връзката prev го прави непосредствено достъпен, срещу повече памет и повече указатели за обновяване. В цикличен списък не чакаме NULL, а спираме при повторно достигане на началото.
Стекът и опашката са ограничения върху достъпа, а не отделен вид стойности. Една и съща поредица 4,7,9 дава 9 при първо pop от стек и 4 при първо dequeue от опашка. В цикличния масив индексите се връщат в началото; препълването и празнотата се различават чрез допълнително състояние, не само по равенството на два индекса.
Сливането на [1,4,8] и [2,4,9] дава [1,2,4,4,8,9], ако списъците допускат повторения. Това е различно от обединение на множества. Линейната оценка O(n+m) предполага последователно движение по двата входа и добавяне в края за O(1). Конкатенирането със самия списък също има нужда от определен договор: редактираната версия първо запазва независимо копие, за да не обхожда безкрайно собствените си нови възли.
Рекурсивните length и contains по-горе са авторски учебни алгоритми върху същото логическо устройство. Те не са представени като препис от книгата, където много списъчни операции са итеративни. Рекурсивният случай скъсява остатъка, а базовият случай е празният списък; за циклична структура този базов случай няма да бъде достигнат без допълнително правило.
СУ 2: учебник, проверен код и таблица за всички 20 теми · Допълнение по точните страници на учебника
Литературна опора и граници на сверяването
Официална библиография на СУ — номерата по-долу са от нея.
- СУ 2 — М. Тодорова, Структури от данни и програмиране на C++, 2011; СУ 5 — L. Ammeraal, Algorithms and data structures in C++, 1996.
- Сверка с наличен пълен текст: СУ 2 вече е наличен като проверена дигитализация. Точните оригинални и нови PDF страници са посочени в раздела със сверка. СУ 5 (Ammeraal) остава библиографска опора без сверка с пълен текст в проекта.
- СУ 9 — Abelson, Sussman, Structure and Interpretation of Computer Programs, 2. изд., 1996. Наличен е пълен текст: MIT PDF. PDF е преформатирана Texinfo версия от 2016 г.; използваме номера на раздели, не предполагаеми страници на печатното издание. Проверими раздели: §1.2.1–1.2.3 (рекурсия и растеж), §2.2.1 (последователности), §2.3.3 (подредени множества), §3.3.1–3.3.2 (изменяеми списъци и опашки). Псевдокодът тук е авторски и не следва Scheme синтаксиса на книгата.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.