Какви са структурите на данните?

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

Какво включва концепцията за структурата на данните?

Този термин може да има няколко близки, но все пак отличителни значения. Това са:

• абстрактен тип;
• прилагане на абстрактен тип информация;
• Пример за тип данни, например конкретен списък.

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

Какво представлява структурата?

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

Ако вземем B-дървета, те обикновено са подходящи за формиране на бази данни и само за тях. В същото време хеш таблетите се използват навсякъде на практика за създаване на различни речници, например за демонстриране на имена на домейни в интернет адресите на компютрите, а не само за формирането на бази данни.

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

Трябва да се отбележи, че много програмни езици имат утвърден тип модулност, което позволява структурите на данните да бъдат безопасно използвани в различни приложения. Силни примери са езиците Java, C # и C ++. Сега класическата структура на използваните данни е представена в стандартни библиотеки на езици за програмиране или директно е вече вградена в самия език. Например, тази структура на хеш таблиците е изградена в Lua, Python, Perl, Ruby, Tcl и други. Стандартната библиотека с шаблони в C ++ се използва широко.

Сравняваме структурата във функционално и императивно програмиране

Трябва незабавно да се предвиди, че е по-трудно да се проектират структури за функционални езици, отколкото за императивни езици, поне има две причини за това:

1. Всъщност, всички структури често използват задание на практика, което не се използва в чисто функционален стил.
2. Функционалните структури са гъвкави системи. При императивното програмиране по-старите версии просто се заменят с нови версии, но във функционалното програмиране всичко работи, тъй като работи. С други думи, в императивните програмни структури са ефимерни и във функционалност те са постоянни.

Какво включва структурата?

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

Най-простият масив подходящ за честа позоваване на компонентите монтиран на индексите и тяхната промяна и изтриване на елементи от средата на основните функции на O (N) О (N). Ако трябва да изтриете елементи, за да разрешите конкретни задачи, ще трябва да използвате различна структура. Например, двоично дърво (STD :: комплект) ви позволява да направите това на O (LOGN) O (log⁡N), но тя не работи с индекси, извършвани изключително алтернативни обходни елементи и тяхното търсене на смисъла. По този начин може да се каже, че структурата се различава при операциите, които е в състояние да изпълни, както и скоростта на тяхното създаване. Да разгледаме например най-простите структури, които не осигуряват повишаване на ефективността, но имат добре дефиниран набор от поддържани операции.

купчина

Това е един от видовете структури от данни, представени под формата на ограничен елементарен масив. Класическият стек поддържа само три варианта:

• Добавете елемент към стека (Сложност: O (1) O (1)).
• Извличане на елемент от комина (Сложност: O (1) O (1)).
• Проверете дали стека е празен или не (сложност: O (1) O (1)).

За да изясните принципа на стека, можете да приложите на практика аналогия с кутия бисквитки. Представете си, че на дъното на съда се намират няколко бисквити. На горния етаж можете да поставите още няколко парчета, или можете, напротив, да вземете една "бисквитка" от върха. Останалите бисквитки ще бъдат затворени от върха и няма да знаете нищо за тях. Такъв е случаят със стека. За да се опише концепцията, се използва съкращението LIFO (Last In, First Out), което подчертава, че компонентът, който е влязъл в последната стака, ще бъде първият и извлечен от него.

На опашката

Това е друг тип структура от данни, който поддържа същите опции като стека, но има противоположна семантика. За да се опише опашката, се използва съкращението FIFO (First In, First Out), защото първият елемент, който беше добавен за първи път, е извлечен. Името на структурата говори за себе си - принципът на работа напълно съвпада с опашките, които могат да се видят в магазина, супермаркета.

декември

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

• Добавете елемент в началото (сложност: O (1) O (1)).
• Извличайте компонента от самото начало (сложност: O (1) O (1)).
• Добавяне на елемент в края (сложност: O (1) O (1)).
• Извличане на елемент от края (сложност: O (1) O (1)).
• Проверете дали палубите са празни (Сложност: O (1) O (1)).

списъци

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

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

В този списък елементите са равни. Разпределението на първия и последния е условност.

дървета

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

брои

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

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

Повече информация за абстрактната структура

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

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

Анализът на структурите на данните се извършва от следните обекти:

• Цели и реални числа.
• Булеви стойности.
• Символи.

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

Структурата на организацията за данни включва:

• Вектори.
• Динамични структури.
• Таблица.
• Многоизмерни масиви.
• Графики.

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

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

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

Какви са методологическите препоръки за работа със структури?

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

Кой трябва да знае това?

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

Не забравяйте, че ако говорите за определена структура, имайте предвид нейното логическо представяне, защото физическото представяне е напълно скрито от "външния наблюдател".

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

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