Динамические структуры данных

Введение

Статическими являются такие величины, объём памяти под которые задаётся при компиляции и не изменяется во время всего действия программного продукта. В некоторых программных языках используется иной метод выделения памяти для информационных данных, который носит название динамический. При таком методе необходимый для какой-либо величины объём памяти назначается при исполнении программы. Эти величины считаются динамическими. Участок оперативной памяти, который распределяется статическим методом, носит название статической памяти. Участок оперативной памяти, который распределяется в динамическом режиме, определяется как динамическая память.

Динамические структуры данных

Применение динамических величин даёт специалисту дополнительные возможности:

1. Применение динамической памяти позволяет обрабатывать больше информационных данных.
2. Если при работе программы отпала необходимость в этих информационных данных, то это позволяет использовать выделенную под них память для иных целей.
3. Применение динамического режима выделения памяти даёт возможность формировать структурную организацию данных переменой величины.

Применение динамических величин сопряжено с применением специального типа данных, который называется ссылочным. Величины, которые имеют ссылочный тип, называются указателями. В указатель занесён адрес зоны в динамической памяти, которая хранит величину определённого типа, а сам указатель расположен в зоне статической памяти. Адресом величины является нумерация начального байта зоны памяти, где расположена эта величина. Объём этой зоны памяти должен определяться её типом. Величины, которым установлен ссылочный тип, могут быть описаны в подразделе, где описываются переменные, так (язык Pascal):

Vàr : ^;

Ниже приведены способы задания указателей:

Typè Мas1 = Аrrày[2..99] Of Integèr;
Vàr Р1 : ^Intèger;
Р2 : ^Strìng;
Рm : ^Mas2;

Тут:

• P1 является указателем динамической величины целочисленного типа.
• Р2 является указателем динамической величины, имеющей строковый тип.
• Рm является указателем динамического массива, с типом, определяемым в подразделе Typè.

Саму динамическую величину можно не описывать в программном приложении, так как при компиляции выделение памяти для них не производится. Выделение памяти при компиляции приложения осуществляется только для статических величин. А так как указатели являются статическими величинами, то необходимо их в программе описать. Выделение памяти для динамической величины, которая связана с указателем, осуществляется заданием стандартной процедуры NEW. Чтобы обратиться к данной процедуре, следует записать:

NÈW();

Предполагается, что по завершении действия данной команды будет сформирована динамическая величина, следующего вида:

 := 
^

Предположим, что в программе, имеющей записанное выше отображение, имеются такие операторы:

NÈW(Р1); NÈW(Р2); NÈW(Рm);

Когда они будут выполнены, то в динамической памяти будет зарезервировано место для трёх величин (двух скалярных и одного массива), обладающие следующей идентификацией:

Р1^, Р2^, Рm^

Далее обработка динамических переменных выполняется аналогично статическим переменным такого же типа. Им могут быть присвоены величины, они могут применяться как операнды в формулах, параметры подпрограмм и тому подобное. К примеру, когда переменная P1^ должна быть равна 31, переменная P2^ должна равняться Wrìte, а элементами массива Pm^ должны стать целые числа от двух до девяноста девяти, то нужно сделать следующим образом:

P1^ := 31;
Р2^ := 'Wrìte';
Fòr I:= 2 Tò 99 Dò Рm^[I] := I;

Помимо оператора NEW величину указателя возможно задать при помощи оператора присваивания:

:= ;

Ссылочным выражением может быть:

1. Выражение указателя.
2. Функция ссылки, то есть функция, у которой указатель служит значением.
3. Константа Nìl.

Nìl считается запасной постоянной, которая обозначает незаполненную ссылку, то есть ссылку, которая никуда не посылает. При осуществлении присваивания базовый тип указателя и выражения в ссылке обязаны быть одного типа. Константа Nìl назначается указателем какого-либо из базовых типов. До момента пока значение ссылочной переменной не присвоено (командой присваивания или при помощи NEW) она остаётся в разряде неопределённых переменных. Осуществлять вывод и ввод указателя не разрешается.

Если вдруг динамическая величина по каким-то причинам остаётся без указателя, то она превращается в «мусорную». Программисты под этим термином подразумевают наличие информации, занимающей какой-то объём памяти, но которая уже больше не потребуется. Программа Паскаль оснащена стандартной процедурой, которая позволяет очищать оперативную память от мусорной информации. Эта процедура имеет следующую форму:

DISPOSE();

К примеру, когда необходимость в динамической переменной Р^ отпала, то команда

DÌSPOSE(Р)

выполнит её удаление из памяти. Далее величина указателя Р станет неопределённой. Это особенно актуально и эффективно, когда удаляются значительные массивы данных.

В вариантах Турбо-Паскаль, которые работают под управлением MS DOS, для хранения данных одного приложения отводится шестьдесят четыре килобайта памяти. Это и будет зоной статической памяти. Но когда возникает потребность в использовании значительных информационных массивов, этого объёма бывает недостаточно. Объём динамической памяти может быть гораздо больше. То есть видим, что применение динамической памяти даёт возможность значительно расширить размеры информационных данных, которые возможно обрабатывать. Но нужно помнить, что использование динамических данных снижает быстродействие программных приложений.