Какви типове структури от данни съществуват?

В компютърните науки „структури от данни“ се нарича определен начин, по който се организират данните в даден компютър, за да могат те да бъдат достъпни и да подлежат на ефикасна модификация. Още по-точно казано структурата от данни е комбинацията от стойностите на различни данни, техните взаимовръзки и функции или операции които могат да бъдат извършени с тези данни.

Съществуват множество различни типове и подтипове структури от данни. Тези типове се обуславят от множество принципи. Ето някои от типовете структури от данни, които са по-популярни:

Линейни типове структури от данни

Ако елементите в една структура от данни формират последователност от някакъв тип, то тя се счита за линейна. Сред по-популярните линейни структури от данни са:

• Масив - В компютърните науки "масив" наричаме линейна структура от данни, която представлява колекция от елементи (стойности или променливи), всяка от които се идентифицира с някакъв точно определен пореден номер (или "индекс") или ключ в този масив. Данните се съхраняват по такъв начин, че позицията на всеки един елемент може да бъде изчислена логически по един или друг начин. Съществуват множество типове масиви, като най-простият са линейните масиви, които са наричани още и "едноизмерни масиви";
• Списъци - В компютърната наука "списък" наричаме абстрактен тип данни, който представлява преброимо количество от подредени стойности. В него една и съща стойност може да се прояви повече от един път. Списъците също така са базов пример за контейнери, тъй като те съдържат други стойности. Ако една и съща стойност се прояви множество пъти, то всяко нейно проявяване е отделен елемент. Тези неща обаче са валидни и за масивите. Къде е тогава разликата?

Най-голямата разлика между тези два линейни типа е идеята за direct access срещу идеята за sequential access. При масивите са възможни и двата подхода за достъп - както direct, така и sequential. При списъците единствено може да се използва sequential допстъп. Това е така заради начина по който тези два типа структури се съхраняват в паметта.

Подобно на масивите, списъците също имат множество подтипове, някои от които много често се наричат просто "списъци", което внася объркване в по-неформалните разговори.

Дървета

"Дърво" е широко разпространен абстрактен тип данни, чиято подредба представлява йерархична структура, визуално наподобяваща дърво. Общи черти на този тип структури от данни, че те винаги имат главна стойност, която се нарича "корен" или "root", от която тръгват разклонения от възли, които оформят йерархична връзка на принципа "parent-child". Всеки възел от който произлизат едно или повече разклонения, се води "родител" или "parent", а подчинените му възли са "детето" или "child". По този начин се създава сложна разклоняваща се структура. Структурите от данни, тип "Дърво" имат няколко основни разновидности, всяка с множество подразновидности. Ето какви са техните основни разновидности:

• Бинарни дървета (binary tree) - Бинарно дърво наричаме всяка структура от данни, в която от всеки възел произлизат най-много два нови възела (children).
• B-Trees - B-Tree е самобалансираща се структура от данни, тип "Дърво". Тя позволява със сортираните данни да се извършва търсене, последователен достъп, вмъкване или изтривана в логаритмично време. Този тип структура от данни позволява да се създават "възли-родители" с повече от два "възела-деца". Те са изключително подходящи за системи за съхранение на информация, които боравят с относително големи обеми от данни, затова и са често използвани в базите данни и файловите системи.
• Heap - Това е специална дървесно-базирана структура от данни, която се отличава с това, че е почти завършено дърво, което удовлетворява heap свойството: при максимален heap, за всеки възел-дете "C", ако "P" е възел-родител на "C", тогава стойността на "Р" е по-голяма или равна на стойността на "С". Обратно при min heap, стойността на "Р" е по-малка или равна на тези на възлите-деца.
• Многопосочни дървета - Многопосочното дърво е дървовидна структура от данни, която подобно на B-Trees също има неограничен брой "връзки-деца". За разлика от B-tree обаче, при което един възел може да има само една стойност, многопосочните дървета могат да имат повече от една стойност на всеки възел, но идеята е същата. Вие избирате посоката, в която да продължите от всеки възел нататък, като винаги ще стигате до нов възел, който съдържа в себе си множество стойности.
• Space-partitioning trees - Тези типове данни се използват за преразпределяне на пространство (space partitioning). Тази дейност е изключително важна при компютърните графики, особено при ray tracing технологията, където се използва за да организира обектите във виртуална сцена. Типичната сцена може да съдържа милиони полигони. За да се осъществи интеракцията "лъч-полигон" за всеки един полигон би било изчислително доста натоварваща задача. Запазването на обектите в space-partitionig структура от данни (като например K-D Tree или BSP Tree) прави по-бързо изпълението на определени заявки за геометрични калкулации.

Съществуват още няколко типа и множество подтипове структури от данни, които, подобно на различните back-end технологии, могат да имат по-общо предназначение или по-специфично такова. Ако искате да навлезете в света на Data Structures с езика Java, то предстоящият курс Data Structures Fundamentals (with Java), е перфектната първа крачка. Запишете се още днес!