В отличие от таких статических переменных в программах, написанных на языке Паскаль, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что они создаются, и память для них выделяется во время выполнения программы. Размещаются динамические переменные в динамической области памяти (heap - области).
Динамическая переменная не указывается явно в описаниях переменных и к ней нельзя обратиться по имени. Доступ к таким переменным осуществляется с помощью указателей и ссылок.
Работа с динамической областью памяти в Turbo Pascal реализуется с помощью процедур и функций New, Dispose, GetMem, FreeMem, Mark, Release, MaxAvail, MemAvail, SizeOf.
Процедура New (var p: Pointer) выделяет место в динамической области памяти для размещения динамической переменной p^ и ее адрес присваивает указателю p.
Процедура Dispose (var p: Pointer) освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя p становится неопределенным.
Процедура GetMem (var p: Pointer; size: Word) выделяет участок памяти в heap - области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.
Процедура FreeMem (var p: Pointer; size: Word) освобождает участок памяти, адрес начала которого определен указателем p, а размер параметром size. Значение указателя p становится неопределенным.
Процедура Mark (var p: Pointer) записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова.
Процедура Release (var p: Pointer) освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, то-есть, очищает ту динамическую память, которая была занята после вызова процедуры Mark.
Функция MaxAvail: Longint возвращает длину в байтах самого длинного свободного участка динамической памяти.
Функция MemAvail: Longint полный объем свободной динамической памяти в байтах.
Вспомогательная функция SizeOf (X): Word возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.
Понятие списка. Типы списков: однонаправленные и двунаправленные.
Каждая компонента списка определяется ключом. Обычно ключ - либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.
Основные отличия связного списка от стека и очереди следующие:
-для чтения доступна любая компонента списка;
-новые компоненты можно добавлять в любое место списка;
-при чтении компонента не удаляется из списка.
Надсписками выполняются следующие операции:
-начальное формирование списка (запись первой компоненты);
-добавление компоненты в конец списка;
-чтение компоненты с заданным ключом;
-вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);
-исключение компоненты с заданным ключом из списка.
Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая - конец списка, остальные- вспомогательные.
Описание компоненты списка и переменных типа указатель дадим следующим образом:
Type
PComp= ^Comp;
Comp= record
D:T;
pNext: PComp
end;
Var
pBegin, pEnd, pCKey, pPreComp, pAux: PComp;
где pBegin - указатель начала списка, pEnd - указатель конца списка, pCKey, pPreComp, pAux - вспомогательные указатели.
Иерархические и ассоциативные списки.
Используются тогда, когда объединяют информационные записи в списки, тем самым образуя группу записи с определенным внутренним порядком.
Эту группу можно рассмотреть как единый информационный объект и из таких групп образуются новые списки. Полученные новые списки можно включать в другие списки и т.д.
Такие списки принято называть иерархическими.
Т.о. иерархический список представляет собой список, элементы, которых могут быть также списки и т.д.
Иерархические списки позволяют хранить информацию в соответствии с подчинением одних данных другим. Они также представляют возможным получать доступ и обрабатывать данные.
Ассоциативные списки.
Часто одни и те же объекты представляют интерес с различных точек зрения. И возникает потребность включать информацию об этих объектах в различные списки.
Если в разные списки включена одна и та же информация, то возникает дублирование одних и тех же записей. Для устранения такого дублирования используются ассоциативные списки. Они организуются на одном и том же общем наборе записи, причем каждый из ассоциативных списков объединяют в определенном порядке те записи из этого набора, которые обладают нужным наборов признаков. Он организуется в виде цепочки, а каждый ассоциативный список имеет свое заглавное звено и ссылки для объедения звеньев в соответственный список.
Каждое звено имеет для каждого ассоциативного списка свою ссылку.
Стеки.
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
-начальное формирование стека (запись первой компоненты);
-добавление компоненты в стек;
-выборка компоненты (удаление).
Очереди.
Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) поступивший первым, обслуживается первым.
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая - конец очереди, третья - вспомогательная.
Описание компоненты очереди и переменных типа указатель дадим следующим образом:
Type
PComp=^Comp;
Comp=record
D:T;
pNext:PComp
end;
Var
pBegin, pEnd, pAux: PComp;
где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель.
Тип Т определяет тип данных компоненты очереди.
В стеки или очереди компоненты можно добавлять только в какой либо один конец структуры данных, это относится и к извлечению компонент.
Связный (линейный) список является структурой данных, в произвольно выбранное место которого могут включаться данные, а также изыматься оттуда.