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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Структури от данни се използват за ефективно съхраняване на данни в компютри. Данните биват групирани по определен начин, за да се улесни достъпът до тях и управлението им. При избор на подходяща структура е възможно по-бързо и икономично (с ползване на минимум ресурси) обработване на информация.

Дефиниране на структури[редактиране | edit source]

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

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

Основни видове структури[редактиране | edit source]

Линеен списък[редактиране | edit source]

Линейният списък е редица от елементи от един и същи тип.

Основни операции с елементите[редактиране | edit source]

  • добавяне на нов елемент
  • премахване на елемент
  • достъп до елемент

Видове линейни списъци[редактиране | edit source]

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

Дърво[редактиране | edit source]

Дърветата са мрежови структури от данни.

Едно от най-важните понятия в теория на графите e понятието “ дърво “. Ще дадем три еквивалентни дефиниции на понятието “ неориентирано дърво “:

• Свързан граф, съдържащ n върха и n-1 ребра;

• Свързан граф, несъдържащ цикъл;

• Граф, в който всяка двойка върхове е съединена с проста верига:

Ако G=(X,A) е неориентиран граф с n върха, то всяко дърво, образувано от негови дъги се нарича “ покриващо дърво “ , ако включва в себе си всички върхове на графа. Очевидно покриващото дърво има n-1 ребра.

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

Граф[редактиране | edit source]

Графи са мрежови структури от данни.

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

Означение(Х,А)

Източници[редактиране | edit source]

  • Преслав Наков, TopTeam Co., Основи на компютърните алгоритми.