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

от Уикипедия, свободната енциклопедия
(пренасочване от Структури от данни)
Направо към навигацията Направо към търсенето

Структурите от данни са множество от данни, които са организирани на основата на логически и математически закони. Често изборът на правилната структура прави програмата по-ефективна, тъй като се спестява памет и време за изпълнение.[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., Основи на компютърните алгоритми.
     Портал „Информатика“         Портал „Информатика