Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

ся программно в зависимости от задачи. Пример автоматического создания де-

рева мы рассмотрим в разделе сортировка и поиск с помощью двоичного дере-

ва.

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

Достоинства представления деревьев в виде массивов – относительная простота реализации. Для небольших деревьев, особенно если количество вер-

шин заранее известно, использование массивов может оказаться более эффек-

тивным решением. Но отсюда вытекает и недостаток, если количество вершин дерева заранее неизвестно, то, как и в случае со стеком, приходится резервиро-

вать память по максимуму. А каков этот максимум? Определенных критериев нет. Память расходуется непродуктивно. Еще один существенный недостаток – порядок расположения поддеревьев в массиве не поддается формализации.

Паскаль предоставляет значительно более удобный механизм для пред-

ставления списков и, следовательно, для реализации стека и деревьев. Рассмот-

рим этот механизм.

4.3.4 Указатели

Существует ряд задач, где статические структуры данных неэффективны для реализации алгоритма, поэтому в Паскале предусмотрена возможность ра-

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

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

Эффективным средством построения связанных списков являются указа-

тели.

Об указателях мы уже вели разговор в разделе 3.2.1.6, где шла речь о типе данных – указатель.

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

361

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

____________________________________________________________________

type

Pint = ^integer;

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

var

ptr: pointer; {нетипизированный указатель}

Описание указателей p и p2 эквивалентны, т.е. можно применять тот и другой способ.

Указатель фактически является адресом памяти, по которому осуществля-

ется доступ к значениям динамической переменной.

Над указателями допустимы операции проверки на равенство (=) и нера-

венство (<>), а также возможно выполнение оператора присваивания := . Если список пуст, то значение переменной-указателя равно nil.

Память для динамических структур, реализуемых при помощи указателей,

распределяется в специальной области оперативной памяти компьютера и на-

зывается "кучей" (от англ. heap – куча) или динамически распределяемой памя-

тью (ДРП).

Для работы с динамическими переменными в Паскале предусмотрены процедуры:

New(p) – выделить в динамически распределяемой памяти (ДРП) необхо-

димую память для переменной заданного типа с типизированным указателем p;

Dispose(p) – освободить участок ДРП, занятый переменной с типизиро-

362

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

ванным указателем р.

Getmem(p, size) – второй способ выделить память переменной с указа-

телем p размером size байтов. Этой процедурой можно выделить память как для типизированных, так и для нетипизированных указателей.

Freemem(p, size) ) – освободить память распределенной переменной с указателем p размером size байтов.

Пример:

New(p);{Выделяется память для переменной целого типа} New(p1); {Выделяется память для строки символов}

Getmem(p2, 1000); {Выделяется память размером 1000 байт для пе-

ременной с указателем p2}

Как вы видите, динамические переменные не имеют собственного имени и доступ к значению такой переменной осуществляется через операцию разыме-

нования указателя. Для этого используется тот же символ "^", что использовал-

ся при описании указателей.

Пример:

p^:= 25;

p1^:= 'Это строка символов';

p2^:= 44;

При выделении памяти процедурой Getmem для типизированных указате-

лей и определении размера выделяемой памяти, лучше всего использовать про-

цедуру SizeOf так как, размеры памяти, отводимой под тот или иной тип, мо-

гут разниться в различных версиях компиляторов, например:

Getmem(p2, SizeOf(integer));

Обязательно освобождайте память после использования! Имейте в виду только, что после освобождения памяти значения указателей не изменятся, что

363

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

____________________________________________________________________

может привести к ошибкам. Необходимо присваивать значениям указателей nil после освобождения памяти. Кроме того, нельзя смешивать методы выде-

ления и освобождения памяти. Так, если память была выделена процедурой

New(), то нельзя освобождать память процедурой Freemem() и, наоборот,

если память была выделена процедурой Getmem(), то нельзя освобождать процедурой Dispose().

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

го достаточно определить тип данных – запись и указатель на него. Структура записи будет следующей:

type

PMyList = ^TMyList; TMyList = record data: integer; next: PMyList; end;

var

mylist: PMyList;

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

Поле next – указатель. В нем содержится ссылка на следующий элемент спи-

ска. Благодаря этому указателю можно передвигаться к следующему элементу списка. В качестве признака окончания списка используют пустой указатель nil. Если необходимо двигаться по списку в прямом и обратном направлении,

то в структуру записи добавляют еще одно поле – указатель, в котором указы-

вают адрес предыдущего элемента списка. Такие списки с двумя указателями называются двусвязными или двунаправленными.

Если в конце списка вместо пустого указателя nil поставить ссылку на

364

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

начало списка, т.е. на первый элемент списка, то получим так называемый

кольцевой список.

Для всех видов списков можно определить стандартные операции, которые производятся над списками и которые должен уметь реализовывать програм-

мист. К таким операциям относятся добавление нового элемента в список, уда-

ление элемента из списка, поиск нужного элемента в списке. Рассмотрим их.

4.3.5 Стандартные операции с линейными списками

Запишем стандартные операции с линейными списками в виде готовых

процедур и функций.

Процедура добавления (вставки) нового элемента в список:

procedure Insert_MyList(Elem: integer;

var pHead, pCurrent: PMyList);

{pHead - указатель на первый элемент списка ("голову" списка)

pCurrent - указатель на текущий элемент списка}

var

p: PMyList; // рабочий указатель

{Если список был пустой, то головой списка становится p} if pHead = nil then

begin

p^.next:= nil; pHead:= p;

end else

365