1. Теоретические сведения

1.1. Указатели

Часто возникает необходимость использовать в программе такие структуры данных, форма и размер которых изменяются в процессе выполнения программы. В таких случаях используются динамические переменные. Явно динамические переменные не объявляются. Вместо этого используется специальная переменная, которая содержит адрес памяти, начиная с которого размещается динамическая переменная. Такая переменная называется переменной-указателем.

В объявлении типа указателя вслед за символом указателя (^ - капа) записывается идентификатор типа динамических переменных, называемый базовым типом. Если базовый тип еще не объявлен, то он должен быть объявлен в той же самой части объявления, в которой объявлен тип указателя. Например,

type

PersonPointer = ^PersonRecord;

PersonRecord = record

Name: String[50];

Job : String[5];

Next: PersonPointer;

end;

var

FirstPerson, LastPerson, NewPerson: PersonPointer;

Здесь тип PersonPointer объявляется как указатель на переменные типа PersonRecord. Таким образом, переменные FirstPerson, LastPerson и NewPerson являются переменными указателями, которые могут указывать на записи типа PersonRecord.

Ссылка на динамическую переменную записывается как идентификатор переменной-указателя, за которым следует символ указателя (^). Например, FirstPerson^.

Выделение памяти для динамической переменной и сохранение адреса памяти, начиная с которого размещается динамическая переменная, в переменной-указателе выполняется при помощи стандартной процедуры New. Например, New(NewPerson);

Переменные, создаваемые при помощи стандартной процедуры New, размещаются в области памяти, которая называется “куча”. “Куча” занимает всю или часть свободной памяти, оставшейся после загрузки программы.

Освобождение памяти, ранее занятой динамической переменной, выполняется при помощи стандартной процедуры Dispose.

Например, Dispose(LastPerson);

1.2. Связные списки записей

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

1

2

nil

Каждый узел двунаправленного списка содержит указатель на следующий узел этого списка и на предыдущий узел этого списка. Указатель на следующий узел в последнем узле содержит nil. Указатель на предыдущий узел в первом узле содержит nil. На рисунке приведен пример двунаправленного линейного связного списка.

nil

nil