Какво са структурите от данни?
Много често, когато пишем програми ни се налага да работим с множество от данни. Понякога добавяме и премахваме елементи, друг път искаме да ги подредим или да обработваме данните по друг специфичен начин. Поради това са изработени различни начини за съхранение на данните в зависимост от задачата, като най-често между елементите съществува някаква наредба. Като можем да дадем за пример няколко алгоритма за подредби като bubble sort, selection sort, insertion sort. Като всяка от тях работи по-различен начин и с различна скорост затова имаме и по-бавни алгоритми и по-бързи.
В този момент използваме структурите от данни – множество от данни организирани на основата на логически и математически закони. Много често изборът на правилната структура прави програмата много по-ефективна – можем да спестим памет и време за изпълнение. Затова имаме различни структури, които с добра оптимизация биха постигнали по-добри резултати.
А) Основни структури от данни в програмирането
- Линейни – към тях спадат списъците, стековете и опашките
- Дървовидни – различни типове дървета
- Речници – хеш-таблици
- Множества
Линейни Линейният списък е редица от елементи от един и същи тип. Основни операции, които могат да бъдат извършвани с елементите, са добавяне и премахване. Дървовидни
В програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дърветата са в сила твърденията:
Всеки връх може да има 0 или повече преки наследници (деца).
Всеки връх има най-много един баща. Съществува точно един специален връх, който няма предшественици – коренът (ако дървото не е празно).
Всички върхове са достижими от корена, т.е. съществува път от корена до всички тях.
Речници
Всяко едно от различните имена подчертава една и съща характеристика на тази структура от данни, а именно, че в тях всеки елемент представлява съответствие между ключ и стойност – наредена двойка. Аналогията идва от факта, че в един речник, например тълковния речник, за всяка дума (ключ) имаме обяснение (стойност). Подобни са тълкованията и на другите имена.
Множества
Това е структура от данни, която съдържа колекция от непресичащи се динамични множества, разделени на няколко несвързани подмножества. Всяко множество има представител, който индетифицира множество.
Линеен списък
Линейните списъци представляват динамични структури от данни. При тях както стойностите така и структурата се променят по време на изпълнение на програмата. Всеки елемент е свързан с не повече от 2 други елемента от списъка: предшественик и наследник. Допустимо е един елемент да е свързан само към един елемент от списъка, т.е. да има само предшественик или само наследник.
Сподели с приятели: |
