Динамические структуры данных. Указатели

Данные, описываемые стандартным образом в разделе описания переменных, имеют статистическую, неизменяемую во время исполнения программы структуру. Во время работы программы изменяются только значения переменных, в то время как количество переменных всегда остается постоянным (отсюда и название - статистические структуры). Это не всегда удобно.

Задачи, обрабатывающие данные, которые по своей природе являются динамическими, удобно решать с помощью динамических структур.

Для создания динамических структур используются переменные специального типа - указатели.

Указатель - это переменная, значением которой является адрес другой переменой или структуры данных.

Указатель, как и любая другая переменная программы, должен быть объявлен в разделе объявления переменных. В общем виде объявления указатели выглядят следующим образом:

Имя: ^ Тил;

где:

имя- имя переменной указателя;

Тип- тип переменной, на которую указывает переменная- указатель;

значок ^ показывает, что объявляемая переменная является указателем.

Приведем примеры объявлений указателей:

p1:^integer;p2^real;

В приведенном примере переменная p1-  это указатель на переменную типа integer, а p2-  указатель на переменную типа real.

Тип переменной, на которую ссылается указатель, называют типом указателя. Например, если в программе объявлен указатель p:^integer, то говорят: ^p- указатель целого типа "или "p- это указатель на целое".

В начале работы программы переменная- указатель "ни на что не указывает". В этом случае говорят, что значение указателя равно NIL. Зарезервированное слово NIL соответствует значению указателя, который ни на что не указывает.

Идентификатор NIL можно использовать в инструкциях присваивания и в условиях. Например, если переменные pi и p2 объявлены как указатели, то инструкция p1:=NIL; устанавливает значение переменной, а инструкция if p2 = NIL then Show Message (' Указатель p2 не инициализирован!'); проверяет, инициализирован ли указатель p2.

Указателю можно присвоить значение- адрес переменной соответствующего типа ( в тексте программы адрес переменной- это имя переменной, перед которым стоит оператор @). Ниже приведена инструкция, после выполнения которой переменная p будет содержать адрес переменной п.

p:=@n;

Помимо адрес переменной, указателю можно присвоить значение другого указателя при условии, что они являются указателями на переменную одного типа.

Указатель можно использовать для доступа к переменной, адрес которой содержит указатель.

Динамические переменные

Динамической переменной называется переменная, память для которой выделяется во время работы программы.

Выделение памяти для динамической переменной осуществляется вызовом процедуры new. У процедуры new один параметр- указатель на переменную того типа, память для которой надо выделить. Например, если p является указателем на тип real, то в результате выполнения процедуры new(p); будет выделена память для переменной типа real (создана переменная типа real) , и переменная- указатель p будет содержать адрес памяти, выделенной для этой переменной.

У динамической переменной нет имени, поэтому обратится к ней можно только при помощи указателя.

Процедура, использующая динамические переменные, перед завершением своей работы должна освободить занимаемую этими переменными память или, как говорят программисты, уничтожить динамические переменные". Для освобождения памяти, занимаемой динамической переменной, используется процедура Dispose, которая имеет один параметр- указатель на динамическую переменную.

 Например, если p- указатель на динамическую переменную, память для которой выделена инструкцией new(p) , то инструкция dispose(p) освобождает занимаемую динамической переменной память.

Списки

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

Каждый элемент списка (узел) представляет собой запись, состоящую из двух частей. Первая часть- информационная. Вторая часть отвечает за связь со следующим и, возможно, с предыдущим элементом списка. Список, в котором обеспечивается связь только со следующим элементом, называется односвязным.

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

 type

TPStudent=^TStudent;// указатель на переменную типа TStudent// описание типа элемента списка

TStudent= record

surname:string[20];// фамилия

name:string[20];'// имя

group:integer;// номер группы

address:string[60];// домашний адрес

next:TPStudent;// указатель на следующий элемент списка

end;

var

head: TPStudent;// указатель на первый элемент списка

Добавлять данные можно в начало, в конец или в нужное место списка. Во всех этих случаях необходимо корректировать указатели.

Как правило, списки упорядочены. Порядок следования элементов в списке определяется содержимым одного из полей. Например, список с информацией о людях обычно упорядочены по полю, содержащему фамилии.

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

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

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