Структура от данни

(пренасочване от Структури от данни)

Структурите от данни са множество от данни, които са организирани на основата на логически и математически закони. Често изборът на правилната структура прави програмата по-ефективна, тъй като се спестява памет и време за изпълнение.[1] Данните биват групирани по определен начин, за да се улесни достъпът до тях и управлението им. За различни задачи са подходящи различни структури. За най-общо групиране може да се използва специфичен идентификатор, както например при речника думите са групирани по начална буква. За по-сложни случаи могат да се създадат много по-сложни структури.[2] При избор на подходяща структура е възможно по-бързо и икономично (с ползване на минимум ресурси) обработване на информацията.[3]

Дефиниране на структуриРедактиране

Дефинирането на структури от данни става посредством задаване на общи правила за връзките между данните и възможните операции с тях.

От основните видове са изведени специфични структури за определени задачи (например двоични дървета за реализиране на бази данни).

Основни видове структуриРедактиране

ЛинейниРедактиране

Линейните структури от данни са списъци, стекове и опашки.

Линейният списък е редица от елементи от един и същи тип. Основни операции, които могат да бъдат извършвани с елементите, са добавяне и премахване.[3]

Видове линейни списъциРедактиране

  • линеен едносвързан списък – всеки елемент, с изключение на последния, е свързан със следващия с една връзка. Списъкът се обхожда от началото към края.
  • линеен двусвързан списък – всеки елемент, с изключение на последния, е свързан със следващия посредством две връзки. Това улеснява операциите. Например до елемент на списък лесно се стига в зависимост от това, дали е по-близо до началото или до края на списъка.
  • цикличен списък – двусвързан или едносвързан списък, при който последният елемент е и предшественик на първия. Тази реализация премахва условната поредност на елементи в списък и улеснява операциите с тях.
  • паралелен списък – Съвкупност от няколко списъка. Възможен е паралелен достъп до елементи от тях.
  • стек – в един стек елементи се добавят и премахват само от единия край, като се спазва правилото LIFO (last in first out – от англ. – „последният влязъл пръв излиза“), т.е. елементът, добавен най-скоро, е пръв при достъп до стека. Така операциите върху елементите биват ограничени.
  • опашка – достъпът до елементи на опашка е също ограничен като при стек. Тук действа обаче правилото FIFO (first in, fisrt out – от англ. – „първият влязъл пръв излиза“), според което елементът, който най-дълго време е в опашката (е най-рано добавен), се обработва пръв. Добавянето на елементи става само от края на опашката, а премахването – от началото.

ДървовидниРедактиране

Дървовидните структури от данни включват различни типове дървета.[3]

Дърветата са мрежови структури от данни, едно от най-важните понятия в теория на графите. Следват три еквивалентни дефиниции на понятието „неориентирано дърво“:

  • Свързан граф, съдържащ n върха и n-1 ребра;
  • Свързан граф, несъдържащ цикъл;
  • Граф, в който всяка двойка върхове е съединена с проста верига:

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

Ориентирано дърво: ориентиран граф без цикли, в който степента-вход на всеки връх (с изключение на един) е равна на 1, а на отбелязания връх изключение (наречен корен) е 0.

Графи са мрежови структури от данни, съвкупност от множеството Х, елементите на което се наричат върхове и множеството А от наредени двойки върхове, наречени дъги (ребра). Означението е (Х, А).

МасивРедактиране

Масивът е колекция от елементи (стойности или променливи), до които може да се получи достъп директно чрез индекс.

ИзточнициРедактиране

  1. data structure. // Free On-line Dictionary of Computing. Посетен на 8 декември 2017. (на английски)
  2. Data structure. // Енциклопедия Британика, 12 април 2017. Посетен на 8 декември 2017. (на английски)
  3. а б в Наков, Светлин. Принципи програмирането със C#. Велико Търново, 2018. ISBN 978-619-00-0778-4. с. 665.
  • Преслав Наков, TopTeam Co., Основи на компютърните алгоритми.