Динамични структури от данни

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

От динамични структури в програмите най-често използваните линейни списъци, стекове, опашки и двоични дървета. Те са различни начини за свързване на отделните елементи и допустимите дейности. Динамична структура, за разлика от масива или запис могат да заемат не-съседни части на RAM.

Динамична структура се използва широко за по-ефективна работа с размера на данните, от които се знае, особено за решения за сортиране задачи.

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

динамична структура елемент е описан като запис, например:

ЗАБЕЛЕЖКА

Помислете как да се работи с основните динамични структури.

линейни списъци

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

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

Следните операции могат да се извършват в списъка:

първоначалното образуване на списъка (създаването на първия елемент);
добавяне на елемент в края на списъка;
четене елемент с предварително определен ключ;
вмъкване на елемент в списък, утвърден място (или преди, или след определен ключов елемент);
преместване на актива с указания ключ;
подредбата на списъка с ключове.

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

Да разгледаме програма, която генерира единично свързан списък от пет елемента, съдържащи номера и текст представяне, и след това изпълнява вмъкване и отстраняване на посочения елемент. Броят използва като ключ.

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

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

Те казват, че стека прилага принципа на LIFO услуга (последен - А по навън, последно в - първа изходяща). Между другото, сегментът на стека е наречена така, защото паметта за локални променливи се разпределят въз основа на LIFO. Купища са широко използвани в софтуерни системи, компилатори, различни рекурсивни алгоритми.

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

двоични дървета

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

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

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

Функцията за маса дава възможност за получаване на последователност от клавиши, сортирани във възходящ ред:

По този начин, дърветата от търсенето могат да се използват за сортиране ценности. Преминаващи възли на дърветата не са отстранени.

операции са определени за двоично дърво:

комутационен възел в дървото;
търсене дърво;
четене елемент с предварително определен ключ;
прекосява;