I.2. Структури от данни (СД) — Разширена писмена разработка
Разширена писмена разработка. I.2. Структури от данни (СД)
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Структури от данни (СД). Определение. Класификация на структурите от данни. Представяне и основни операции за работа със СД низ, множество и масив.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Структури от данни (СД) — 1. Определение и нива на описание
- Определение — 1. Определение и нива на описание
- Класификация на структурите от данни — 2. Класификация на структурите от данни
- Представяне и основни операции за работа със СД низ, множество и масив — 3. Масив: представяне и основни операции; 4. Низ: представяне и операции; 5. Множество: договор, реализации и избор
Кратък план за изпита
- Структура от данни, абстрактен тип и представяне.
- Класификация и критерии за избор.
- Масив: адресиране и операции.
- Низ: представяне, дължина, сравнение и търсене.
- Множество: свойства, операции и реализации.
- Съпоставка на сложността при конкретни предпоставки.
1. Определение и нива на описание
Структурата от данни е организация на елементи и отношения между тях, която поддържа определени операции. При анализа разграничаваме логическия модел, допустимите операции и физическото представяне в паметта. Абстрактният тип данни описва какви стойности и операции са допустими и какъв резултат трябва да дават. Конкретната структура определя как този договор се реализира.
Например множество от читателски номера поддържа добавяне, премахване и проверка за принадлежност. То може да бъде реализирано чрез масив, свързан списък, хеш-таблица или балансирано дърво. Логическият смисъл остава един и същ, но времето и паметта за операциите се различават. Изборът трябва да се обоснове с очаквания брой елементи, честотата на операциите и изискванията към реда.
Коректността зависи и от инварианти на представянето. При сортиран масив елементите трябва да останат в зададения ред; при множество не трябва да се появяват логически дубликати. Една операция е правилна, когато изпълнява договора си и запазва тези инварианти.
2. Класификация на структурите от данни
Линейните структури подреждат елементите в последователност — масив, низ, списък, стек и опашка. Нелинейните задават по-сложни отношения, например дърво или граф. Хомогенна структура съдържа елементи от един тип, а хетерогенната съчетава различни типове, както запис с номер, име и дата. Статичният размер се определя предварително; динамичната структура може да променя размера си по време на работа.
Последователното представяне използва съседни области в паметта, докато свързаното съхранява връзки между възли. Тези класификации са различни оси: динамичният масив е динамичен по размер, но има последователно представяне. „Линейна структура“ не означава „всяка операция е с линейна сложност“. Прекият достъп до масив е константен при обичайния RAM модел, докато търсенето по стойност може да е линейно.
В оценките n означава брой елементи, а m — дължина на втори обект, ако има такъв. O(f(n)) е асимптотична горна граница; когато посочваме Θ(f(n)), твърдим съответстващи горна и долна граница при дадения модел. Трябва да разграничаваме най-лош случай, очаквана и амортизирана цена.
3. Масив: представяне и основни операции
Масивът е индексирана последователност от еднотипни елементи. При непрекъснато разполагане и еднакъв размер w на елемент адресът на елемент с индекс i е base + (i − lower) · w. Формулата обяснява достъпа за O(1), но предполага валиден индекс. Обхождането на всички елементи е Θ(n), защото всеки трябва да бъде посетен.
За масив [12, 7, 19, 4] четенето на елемент с индекс 2 при индекси от нула дава 19. Ако вмъкнем 8 преди 7 и пазим реда, трябва да преместим елементите след мястото на вмъкване. В най-лошия случай това струва O(n). Изтриването със запазване на реда също може да изисква преместване. Ако редът няма значение, изтритият елемент може да се замени с последния, но това променя договора на операцията.
Търсенето в несортиран масив е O(n) в най-лошия случай. В сортиран масив двоичното търсене е O(log n), тъй като многократно намалява интервала наполовина и има пряк достъп до средата му. При динамичен масив добавянето накрая е амортизирано O(1), ако капацитетът нараства геометрично; отделна операция с преразпределяне остава O(n). Това не е гаранция за константно време на всяко добавяне.
Двумерен масив може да се разполага по редове или колони. При редово разполагане на матрица с c колони елементът a[i][j] се намира чрез отместване (i · c + j) · w при индекси от нула. Подредбата влияе върху локалността на паметта при обхождане.
4. Низ: представяне и операции
Низът е крайна последователност от символи, при която редът и повторенията са съществени. В класическо C представяне той е масив от байтове, завършващ с нулев байт. Друг вариант съхранява дължина отделно, както управляваните низови структури. При първия вариант определянето на дължината изисква обхождане до терминатора, а при втория може да бъде O(1).
Основните операции са достъп до позиция, сравнение, конкатенация, извличане на подниз, търсене, вмъкване и изтриване. Лексикографското сравнение разглежда първата различаваща се позиция; ако единият низ е префикс на другия, по-късият е по-малък при обичайното определение. Сравняването по адреси не сравнява съдържанието на два низа.
Копиращото слепване на низове с дължини n и m струва Θ(n+m). Наивното търсене на шаблон с дължина m в текст с дължина n проверява до n−m+1 позиции и до m символа на позиция: O(nm). Съществуват по-добри алгоритми, но оценката трябва да назовава конкретния алгоритъм. Вмъкването в непрекъснат буфер може да премести суфикс и да струва O(n).
При Unicode трябва да уточним дали броим байтове, кодови единици, кодови точки или видими графеми. В UTF-8 един български знак не е непременно един байт. Следователно постоянният достъп до байт в масив не доказва постоянен достъп до произволен видим символ.
5. Множество: договор, реализации и избор
Множеството е съвкупност от различни елементи, без логически значим ред. Добавянето на вече наличен елемент не увеличава броя му. За A={1,3,5} и B={3,4} обединението е {1,3,4,5}, сечението е {3}, а разликата A∖B е {1,5}. Разликата е насочена: B∖A={4}. Принадлежност, включване, равенство, обединение, сечение и разлика са основни операции.
Несортиран списък позволява проста реализация, но проверката за принадлежност изисква O(n). Сортиран масив дава O(log n) търсене и линейно сливане за обединение на две множества, но вмъкването е скъпо. Балансираното дърво дава O(log n) търсене, добавяне и изтриване. Хеш-таблицата дава очаквано O(1) при подходяща хеш-функция и контрол на запълването; неблагоприятни колизии могат да доведат до O(n).
За малка предварително известна област от U възможни стойности може да се използва битов вектор. Принадлежността проверява един бит, а множествените операции използват побитови действия. Паметта е Θ(U) бита независимо от броя действително налични елементи, затова представянето е неподходящо за огромна рядко населена област.
Изводът е, че една и съща логическа задача може да има различни разумни реализации. Масивът подчертава индекса, низът — последователността от символи, множеството — принадлежността без повторения. На изпит след определението трябва да се посочат представяне, операции, инвариант и сложност при ясни предпоставки.
Уточнения по официалния учебник: представяне и цена на операциите
Сверка със СУ 2: Определения/класификация: ориг. 9–19 / нов PDF 9–18; оценка: ориг. 19–25 / нов PDF 17–22; множества: ориг. 104–108 / нов PDF 99–103; търсене: ориг. 300–303 / нов PDF 282–286.
Логическата структура определя допустимите стойности и връзки, а физическото представяне — как ги пазим и достигаме. Едно множество например може да е реализирано чрез списък, но редът и повторенията на списъка не стават автоматично свойства на математическото множество. При A={2,5,8} и B={5,9}, обединението е {2,5,8,9}, сечението е {5}, а A\B е {2,8}.
В реализацията чрез неподреден списък операцията member претърсва последователно. Ако проверяваме всеки от n елемента на A за принадлежност към B с m елемента, само проверките могат да струват O(nm). При подредени списъци обхождането с два текущи възела позволява сечение за O(n+m). Изводът за изпита е да посочим представянето и предпоставките, преди да дадем сложност.
При последователен масив индексът позволява пряк достъп; търсенето по стойност е отделна задача. Линейното търсене не изисква сортиране, а двоичното изисква подреден диапазон и подходящ достъп до средния елемент. Вариантът с бариера записва служебен елемент след данните, затова буфер за n стойности трябва да има място за n+1, ако използваме именно този вариант.
Функцията binSearch в учебника има особен договор: връща −1 за стойност пред първата, n за стойност след последната и иначе първата позиция с елемент, не по-малък от търсения. Това не е просто булева проверка за наличие. Преди да приемем намерено съвпадение, проверяваме допустим индекс и равенство. В проверената версия празният диапазон дава 0.
Низовете и основите на масивите са част от предварителните знания, с които книгата работи. Пълният раздел за низове в тази разработка, включително разграничаването между кодови единици и видими знаци, не се приписва на тези страници. Той запазва отделната си литературна опора.
СУ 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 г.; използваме номера на раздели, не предполагаеми страници на печатното издание. За абстракция на данни и представяне на множества: §2.1 и §2.3.3. Това не е източник за всеки детайл на C++ масивите.
- Допълнителен университетски източник, извън списъка: MIT 6.006, лекции 8–10 — хеширане, удвояване на таблица и обработка на низове. Анализът на масиви и низове използва изрично заявения в текста модел на операции.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.