Динамичният структурата на списъци с данни

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

В програмни езици (Pascal, C, и др.), Има и друг метод за разпределяне на паметта за данни, който се нарича динамичен. В този случай, паметта за определената стойност по време на изпълнение. Тези стойности ще се наричат ​​динамични. КАТЕГОРИЯ памет, за да бъдат разпределени статично, наречена статична памет; динамично разпределя раздел памет, наречена динамична памет (паметта на стека) а.

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

Работа с динамични стойности, свързани с използването на друг тип данни - референтен тип. Променливи със справка тип, наречени указатели.

След това ще обсъдим по-подробно указатели и действия с тях на езика на Паскал, примери ще доведат до Pascal и C.

Големината на референтния тип (стрелка) е описано в раздел описва променливите, както следва:

Ето примери за описания на признаци:

Тук Р1 - указател към динамичната стойност на типа число; P2 - указател към динамичната стойност на низ тип; Pm - указател към динамичен масив от типа, посочен в раздел Type.

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

Как тогава това се случи при стойност на динамичния разпределение на паметта? Памет за динамична стойност, свързана с показалеца се освобождава от извършване на стандартната процедура NEW. Формат на прибягва до тази процедура:

Смята се, че след тази декларация създава динамична стойност, чието име е както следва:

Нека програмата, която има по-горното описание, има следните твърдения:

След тяхното изпълнение е посветена пространство за три стойности (две скаларни и един масив), които имат идентификатори в динамична памет:

Например, Р1 ^ символ може да се декодира, както следва: динамична променлива, която е посочен от Р1 на показалеца.

По-нататъшната работа с динамичните променливи е точно същата като статичните променливи на съответните видове. Те могат да се зададат стойности, те могат да се използват като операнди в изрази, параметри, практики и др. Например, ако променливата Р1 ^ искате да зададете броя 25, променливата Р2 ^ присвоява стойност на "Write" символ, и набор от Pm ^ попълнете числа за поръчката от 1 до 100, се извършва, както следва:

В допълнение към новата процедура указател стойност може да бъде определена от оператора на задача:

За справка можете да използвате израза

• указател;
• позоваване функция (т.е. функция, чиято стойност е указател);
• постоянен Nil.

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

Преди определянето на стойност на референтния променлива (с помощта на оператора за присвояване или нова процедура) не е сигурно.

Входни и изходни указатели не са разрешени.

Помислете за пример. Нека програмата, описана в следните насоки:

След това операторите валиден за присвояване са като спазват принципа тип като. К оператор: = D погрешно защото основни типа в дясната и лявата страна са различни.

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

Представете си, че в програмата, в които има указатели в секцията по-горе твърдения, написани на следните изисквания:

По този начин, динамична променлива, равна на 5, загуби показалеца му и става недостъпен. Въпреки това, пространството на паметта, което заема. Това е пример на появата на "отпадъци". Тази диаграма показва какво се е случило в резултат на Р оператор: = D.

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

Например, ако вече не е нужен на динамична променлива P ^, операторът

да я премахнете от паметта. След това, показалка стойност Р става несигурно. Особено ефект става значителна икономия на памет при отстраняване на големи масиви.

В версии на Turbo Pascal, работещ под операционната система MS DOS, 64 килобайта памет е предназначена за една програма (или, за да бъдем точни, 65,520 байта). Това е статичен площ памет. Ако е необходимо, да работи с големи масиви от информация, която не може да бъде достатъчно. Heap размер - много по-големи (стотици килобайти). Следователно, използването на динамична памет може значително да увеличи количеството на информацията се обработва.

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

Пример. При един текстов файл, а не по-голям от 64 Kb, включващи реални числа, по един във всеки ред. Презаписване на съдържанието на даден файл в масив, което я поставя в купчина. Изчислява се средната стойност на елементите на масива. Изчистване на купчина. Създаване на цяла поредица от размер 10 000, го напълни с произволни числа в интервала от -100 до 100, и се изчислява средната стойност.

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

Нека разгледаме следния пример. В хода на физически експеримент, показанията се вземат няколко пъти (например, термометър) и се записват в паметта на компютъра за по-нататъшна обработка. Не е известно колко ще бъдат направени измервания.

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

тук Inf # 151; връзка информация на списъка (стойността на всеки прост или структуриран вид, с изключение на файла), в непосредствена близост # 151; указател към следващия линк в списъка; първи # 151; указател към връзката на списък заглавие.

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

Има BT # 151; някои основни типа на елементи от списъка.

Ако показалецът се отнася само до нишката в списъка (както е показано в структурата над обявената), а след това на такъв списък, наречен еднопосочно. Ако на следващите и предишните връзки # 151; двупосочен списък. Ако стрелката на последното звено не е инсталиран в Nil, а заглавието се отнася до списъка с линк, този списък се нарича пръстен. Ring може да бъде еднопосочни и двупосочни списъци.

Един по-близък поглед към работата с свързани списъци за пример на еднопосочно без пръстеновидно списък.

Различаваме типичните операции на списъка:

• добавяне на линк в горната част на списъка;
• премахване от списъка за връзка началото на;
• добавяне на връзка към списъка произволно място, различно от от началото (например, след показалеца на връзка, който е описан);
• отстраняване от списъка връзка на произволно място, различно от началото (например, след показалеца на връзка е посочен);
• проверете дали списъкът е празен;
• Изчистване на списъка;
• списък печат.

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

1. Добавяне на линк към началото на списъка