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

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

Масив

Най-простият тип структура от данни е линеен масив. Известна е също като едноизмерен масив. Масивът съдържа няколко стойности от един и същи тип (Integer, Floats, String и т.н.). Достъпът до елементите в масива е много бърз. Обикновено масивът е с фиксиран размер. След като размерът на масива е определен в началото, може да не е възможно да се увеличи размерът на масива, без да се създаде нов по-голям масив и да се копират всички стойности в новия масив. В информатиката масивна структура от данни или просто масив е структура от данни, състояща се от колекция от елементи (стойности или променливи), всеки от които се идентифицира с поне един индекс или ключ на масива. Масивът се съхранява така, че позицията на всеки елемент да може да се изчисли от неговия индексен кортеж чрез математическа формула.

Например масив от 10 целочислени променливи с индекси от 0 до 9 може да бъде съхранен като 10 думи на адреси в паметта 2000, 2004, 2008, 2036, така че елементът с индекс i да има адрес 2000 + 4 × i.

Тъй като математическата концепция за матрица може да се представи като двуизмерна мрежа, двуизмерните масиви понякога се наричат матрици. В някои случаи терминът "вектор" се използва в компютрите за обозначаване на масив, въпреки че по-скоро кортежи, отколкото вектори, са по-правилният математически еквивалент. Масивите често се използват за реализиране на таблици, особено на таблици за търсене; думата таблица понякога се използва като синоним на масив.

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

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

Терминът масив често се използва за означаване на тип данни масив, вид тип данни, предоставен от повечето езици за програмиране от високо ниво, който се състои от колекция от стойности или променливи, които могат да бъдат избрани чрез един или повече индекси, изчислени по време на изпълнение. Типовете масиви често се реализират чрез структури от масиви; в някои езици обаче те могат да се реализират чрез хеш-таблици, свързани списъци, дървета за търсене или други структури от данни.

Свързан списък

Свързана структура от данни е набор от информация/данни, свързани помежду си чрез препратки. Данните често се наричат възли. Препратките често се наричат връзки или указатели. Оттук нататък за тези понятия ще се използват думите възел и указател.

В свързаните структури от данни указателите се препращат или сравняват само за равенство. По този начин свързаните структури от данни се различават от масивите, които изискват добавяне и изваждане на указатели.

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

Стек

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

Основната реализация на стека се нарича още структура "Последен влязъл - първи излязъл"; съществуват обаче различни варианти на реализация на стека.

Има основно три операции, които могат да се извършват върху стекове. Те са:

• вмъкване ("избутване") на елемент в стек
• изтриване ("изскачане") на елемент от стека
• показване на съдържанието на най-горния елемент от купчината ("надничане").

Опашка

Опашката е абстрактен тип данни или линейна структура от данни, в която първият елемент се вмъква от единия край ("опашката"), а изтриването на съществуващ елемент се извършва от другия край ("главата"). Опашката е структура от типа "първи влязъл, първи излязъл". "Първи по ред" означава, че елементите, поставени в опашката първи, ще излязат първи, а елементите, поставени в опашката последни, ще излязат последни. Пример за опашка са опашките от чакащи хора. Първият човек на опашката излиза пръв, а последният човек на опашката - последен.

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

Графика

Графът е абстрактен тип данни, който има за цел да реализира концепциите за графи и хиперграфи от математиката.

Графовата структура от данни се състои от краен (и евентуално променлив) набор от подредени двойки, наречени ребра или дъги, на определени обекти, наречени възли или върхове. Както и в математиката, за реброто (x,y) се казва, че сочи или отива от x към y. Възлите могат да бъдат част от графовата структура или могат да бъдат външни обекти, представени чрез целочислени индекси или препратки. Структурата от данни на графа може също така да асоциира с всеки ръб някаква стойност на ръба, например символен етикет или цифров атрибут.

Дърво

Дървото е една от най-мощните съвременни структури от данни. Тя често се появява в напреднали дисциплини като изкуствен интелект (ИИ) и дизайн. Изненадващо, дървото е важно в едно много по-елементарно приложение - поддържането на ефективен индекс.

Когато се използва дърво, има голяма вероятност да се използва индекс. Най-простият тип индекс е сортиран списък от ключови полета. Дървото обикновено има определена структура. В случай на двоично дърво можете да използвате двоично търсене, за да намерите всеки елемент, без да се налага да преглеждате всеки елемент.

Типът данни дърво е вид граф, което означава, че много алгоритми, създадени за обхождане на граф, работят и с дърво, но алгоритмите могат да бъдат много сходни и трябва да имат специален начален възел, т.е. възел, към който няма други възли.

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

Хеш таблица

Хеш-таблицата е масив, в който всеки индекс сочи към свързан списък въз основа на хеш-стойност. Хеш стойността е стойност, определена от хеш функция. Хеш функцията определя уникална стойност въз основа на данните, които съхранява. Това позволява достъп до данни в постоянно време, тъй като компютърът винаги знае къде да търси.

Всеки възел сочи към друг възел.