Абстрактни структури от данни. Списъци - дефиниция и основни операции, видове, реализация.


Категория на документа: Информатика


Тема6
Абстрактни структури от данни. Списъци - дефиниция и основни операции, видове, реализация

В езиците за програмиране се използват опр методи и свойства за дефиниране на типове на данните. Във всеки език за програмиране се включват определен брой първични, примитивни типове данни, като числови(цели и реални), символни и логически. Първичните, примитивните типове данни се дефинират чрез множества от стойности, които са прости.Тези първични типове данни се използват за конструиране на нови типове данни наречени структурирани. Структурирани типове данни са масивите, записите, множество, символен низ, таблици. Структурираните типове могат да бъдат дефинирани чрез други структурирани типове данни така, че да се построи йерархия от типове данни.Когато става въпрос за абстрактни типове данни трябва да се имат предвид следните нюанси при абстрахирането на структурите данни.1.АТД означава, че концепцията за тях, за техните свойства и за операциите с тях са независими от представянето по един начин, чрез опр структури от данни или по друг начин, с други структури от данни.2.АТД се свързват със създаването на съответен математически модел за операциите и свойствата им.3.АТД позволяват да се игнорират и скрият някой детайли и характеристики от потребителя.Дефиницията на един абстрактен тип данни се състои от: описание(функционална спецификация) и реализация на АТД.Функционалната спецификация на един АТД е описание на всички свойства на АТД и това описание е независимо от представянето на АТД чрез средствата на езика за програмиране. Тя включва:-дефиниране на множество от стойности на АТД; на множество от функции, съответстващи на множество от операции за АТД;-спецификация на семантиката на множеството от операции за АТД; включва описание на свойствата на АТД във вид на аксиоми. Реализацията на един АТД включва:-представяне на множеството обекти и стойности на АТД чрез средствата на езика за програмиране, т.е. чрез съответни типове данни.-реализация на множеството операции с АТД чрез програмни средства (процедури и функции).Могат да се отбележат следните общи за всеки АТД операции:- създаване; достъп и модификация(добавяне или отстраняване на елемент). АТД се нарича статичен ако за него се използват само операции създаване и достъп. Ако има и операция модификация то типа е динамичен.АТД се делят на две големи групи: линейни и нелинейни. АТД се нарича линеен, ако в множеството стойности от тип Т, съставящи АТД има дефинирана линейна наредба. АТД е нелинеен,няма дефинирана линейна наредба. Основни класически линейни АТД в информатиката са: списък, стек, опашка, а нелинейни: дърво и граф.
Дефиниции, валидни операции. Примери в Pascal.Списъка е линейно наредена структура от данни от краен брой елементи, като за всеки елемент се знае кой е следващия. Списъка може да има променлив брой елементи. Първият елемент на списъка се посочва от специален указател за начало на списък. Основните операции със списък са : създаване на списък; включване на елемент; изключване на елемент; следващ елемент; търсене на елемент.В зависимост от начина на свързване на елементите в списъка различаваме: линейно-свързан списък; цикличен списък;двойно свързан списък;множествено-свързани списъци За целта всеки един от елементите на физическия списък трябва да съхранява освен адреса на следващия физически елемент също и толкова адресни части, колкото са логическите списъци, които искаме да поддържаме. За всеки един от логическите списъци се поддържа съответен външен указател.Схематично списъка може да се представи по следния начин:???
Р е променлива указател, която сочи към първия елемент на списъка. Всеки един елемент на списъка се състои от две кпоненти: указател към следващия елемент и данни за елемента от списъка. Данните за всеки елемент имат една и съща структура и са от един и същ тип. Указателят на последният елемент има винаги стойност NIL. Валидни операции - включване на елемент в началото на списък- включване на елемент преди друг- проверяване на празен списък- извличане на първия елемент- извличане на елемент след даден- изключване на първия елемент- изключване на елемент след даден- търсене на елемент-Стек-Стекът е абстрактен линеен тип данни, който се състои от променлив брой елементи, за които са в сила следните операции: -създаване на стек;-проверка за празен стек;-включване на елемент в стек -се извършва винаги след последния елемент на стека и новия елемент става последен;-изключване на елемент от стек. изключва се само последният елемент от стека;-достъп до елемент-може да се осъществява само до последния включен елемент.Стекът е линейна структура в която елементите се включват по реда на тяхното пристигане, а се изключват по обратен ред. Стека се състои от м-во елементи и един указател за последния въведен елемент. Принципът на изграждане и работа със стека е LIFO (последен пристигнал-пръв обслужен). Указателят на стека сочи към последния въведения елемент. Елементите са информационно свързани, а структурата може динамично да се изменя (записва и чете) без да се фиксира предварително броя на елементите.???
Основните операции със стека са:-PUSH - за добавяне на нов елемент-POP - за изключване на елемент от стека-INIT - инициализация на стека-EMPTY - проверка за празен стек-ONTOP - прочитане на елемент - обръщаме се към последния елемент, прехвърляме го върху друга област от паметта и тогава го изтривамеОпашката е линеен абстрактен тип данни, който се състои от променлив брой елементи, като редът на включване се запазва при реда на изключване. Опашката може да се разглежда като линеен списък, при които вкл на елементи се извършва винаги от единия край на списъка, а изключването на елементи се извършва от другия.Съдържа елементи и два указателя. Единия указател показва къде се намира последния въведен елемент, а другия - кой елемент трябва да се изведе. Принципът на изграждане и поддържане на опашка е FIFO (първи дошъл-първи обслужен). Опер. с опашки са следните:- създаване -проверка за празна опашка-включване на елемент-изключване на елемент от стека-достъп до елемент???
Операции:-INITQ - инициализира празна опашка; процедура-EMPTYQ - проверява празна опашка; функция-PUSHQ - включва елемент в опашката; процедура-POPQ - измъква елемент от опашката; функция. Опашката може да се реализира чрез масив и две променливи за начало и край на опашката или пък чрез списъчни структури и два указателя за началото и края на опашката.- Дърво Чрез тях се изразяват отношения на йерархия между елементите на дадено множество. Дървото се състои от елементи (възли) и връзки между тях, така че няма обратни връзки. Дефинира се чрез корен и поддърво. Дървото Т:1.Има един специален възел наречен корен на дървото;2.Всички останали възли съдържат Т>=0 непресичащи се множества, всяко от които е също дърво-поддървета.Възлите от едно дърво, което няма поддървета се наричат листа.Между възлите на едно дърво може да се установи отношение на предшестване и наследяване. Коренът е възел, които няма предшественик Отношенията на предшестване следване между възлите се наричат ребра. ???
- Двоични дървета.Двои д. Т се дефинира като крайно множество от елементи от даден тип, което е или празно или се състои от елементи наречени възли за които е изпълнено:-Има корен на дървото;-Всички останали възли се съдържат в две непресичащи се множества Т1 и Т2, всяко от които са също двоични дървета.Всеки възел от двоичното дърво(без листата) може да има ляв и десен наследник, само ляв или само десен.Двоичното дърво е динамичен АТД. В него могат да се добавят и да се премахват елементи. Всеки възел от едно двоично дърво може да се разглежда като структура данни, състояща се от три компоненти:-данни от определен тип, -указател към ляво двоично поддърво;дясно двоично поддървоДърветата често се използват за съхраняване на данни за бързо обхождане Условията са:- всички елементи които са по-малки по стойност от корена да се намират в лявото поддърво- всички елементи които са по-големи по стойност от корена да са в дясното поддървоВалидни операции - обхождане - всеки възел се посещава по веднъж- търсене на елемент - перкурсивен и рекурсивен начин- включване на елемент- изключване на елемент, съществуват 3 начина- ако елемента е листо, за да се изключи е достатъчно да се посочи на предходния му, че тази наследник го няма- ако елемента има само един наследник, е необходимо да се посочи на предходния му, че изключеният елемент няма да бъде корен на поддърво, а такъв ще бъде неговият наследник- ако елемента има два наследника то на мястото на изключения елемент се поставя и елемента от лявото или от дясното му поддърво. Основните операции, които се извършват с АТД дв.дърво са следните:-създаване -вмъкване на елемент;-обхождане -търсене на елемент;-премахване на елемент;-проверка за празно дв.дърво.Графът е нелинейна структура с голямо практическо приложение.Максималния брой връзки от един възел към други се нарича валентност на графа. Графите са насочени (връзките са еднопосочни) и ненасочени (връзките са двупосочни). Графът се състои от крайно множество върхове и крайно множество от ребра. На всяко ребро съответства двойка върхове. Графът се изобразява по следния начин: всеки връх се задава като точка(кръг) и всяко ребро със линия, която съединява две точки. Графът се нарича ориентиран, ако двойките върхове отговарящи на едно ребро, е наредена.Всеки възел има степен - броя на съседните му възли. Има няколко различни начина за представяне на един граф:1.Матрица на съседство-т.е чрез двумерни масиви предоставя удобни възможности за извършване на някой операции с графи, защото те се свеждат до операции с матрици. 2.Списъци на съседство - графът се представя чрез н броя списъци.Операции, които се извършват с един граф са:-добавяне на ребро-премахване на ребро-добавяне на връх-обхождане на граф-намиране на път м/у 2 върха-намиране на пътища с определена дължинаСложни абстрактни структури от данни се наричат съставни структури, комбинация от няколко от описаните структури. Такава структура например е дърво на който всеки елемент е начало на списък.





Сподели линка с приятел:





Яндекс.Метрика
Абстрактни структури от данни. Списъци - дефиниция и основни операции, видове, реализация. 9 out of 10 based on 2 ratings. 2 user reviews.