Динамические структуры данных, указатели, страница 2

В примере

type

VP_ptr = ^VP__type;

VP_type = array[l..n] of Integer;

var

VP : VP_ptr;

begin

New(VP);

for k := 1 to max do

VP^[k] := 3 * k + 1;

Dispose(VP);

VP := ml;

end.

после того как процедура New отвела память под переменную, VP^ является именем массива, и в следующем операторе его элементам присваиваются значения. Действие процедуры Dispose обратно по отношению к действию процедуры New — она освобождает память, отведенную под динамическую переменную, и делает эту память доступной для повторного использования. Следующий оператор присваивает VP значение nil. Эта встроенная константа представляет собой значение «нулевого» указателя, который ни на что не указывает. После того как к указателю применена процедура Dispose, обязательно следует присвоить ему значение nil. Процедуру Dispose следует использовать сразу после того, как отпала необходимость использовать динамическую переменную. Нарушение этого правила может привести к неприятностям.

Присвоить значение переменной типа Pointer можно с помощью обращения к функции Ptr или с помощью операции Pvarjnarae. Функция Ptr имеет тип Pointer, а два ее аргумента (типа Word) задают сегмент и смещение адреса, на который и будет указывать переменная-указатель в левой части оператора присваивания:

var_point := Ptr($50, $55);

Символ @ задает унарную, (то есть применяемую только к одному операнду) операцию — создание указателя на переменную, функцию или процедуру, идентификатор которой записывается справа от знака операции. Следующий пример взят из справочной системы Турбо Паскаля:

type

TwoChar = array[0..1] of Char;

var

Int: Integer;

TwoCharPtr: ^TwoChar;

begin

TwoCharPtr := @Pint;

. . .

Здесь переменной TwoCharPtr присваивается значение указателя на целую переменную Int. После этого появляется возможность трактовать значение целой переменной Int как символьный массив из двух элементов, используя обращение TwoCharPtr^.

1.2  Списки

Рассмотрим структуры данных, которые можно создавать с помощью указателей. Начнем со связных списков. Связный список представляет собой цепочку записей-узлов, в которой каждая запись содержит основные данные и ссылку на следующую запись и цепочке. Во главе списка находится указатель («корень»), который указывает на первую запись в списке (рисунок - 1).

Указателю в последней закиси списка обычно присваивается значение nil, служащее признаком конца списка. Такая структура является динамической, она может изменяться в процессе выполнения программы.

Основными операциями, которые можно выполнять над списками, являются операции включения записи в список и удаления ее из списка. Чтобы добавить в связный список новый узел, достаточно изменить один указатель, сами узлы при этом перемещаться не должны. Удаление узла также осуществляется изменением соответствующего указателя так, чтобы он ссылался на узел, следующий за удаляемым.

Принято выделять следующие типы связных списков:

·  односвязные линейные списки;

·  односильные циклические списки;

·  двусвязные линейные списки;

·  двусвязные циклические списки.

Программа linkedjist содержит процедуры создания списка, его размещения в памяти, добавления и удаления узлов списка, удаления всего списка, а также демонстрирует их работу. До и после выполнения каждой операции на экран выводится объем доступной памяти, который определяется функцией MenAvail. Базовым типом здесь является запись (nodetype), которая состоит из двух полей. Первое поле (number) содержит данные, а второе поле (nextnode) — указатель на следующий узел в списке. Данные представляют собой единственное целое значение.