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

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

type TRec = record {описание базового типа-записи}.

x, y: integer;

name: string;

end;

TpRec = ^TRec; {описание ссылочного типа}.

var ArrOfPointer: array [1.100]of TpRec;

{объявление массива указателей на записи}.

Поиск заданного элемента в данном случае реализуется очень просто:

i:= 1;

While (i <= 100) and (ArrOfPointer [i]^.name `заданное значение') do i:= i + 1;

Добавление нового элемента предполагает выделение памяти для этого элемента и включение в массив ссылок адреса элемента:

ArrOfPointer [i]: = pTemp;

Массив указателей позволяет быстро и эффективно производить перестановку элементов. Например, для перестановки элементов i и j достаточно выполнить три простых присваивания:

pTemp:= ArrOfPointer [i];

ArrOfPointer [i]: = ArrOfPointer [j];

ArrOfPointer [j]: = pTemp;

Эти присваивания переставляют лишь значения адресов в соответствующих элементах, НЕ перемещая сами базовые объекты, которые могут занимать значительные объемы памяти.

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

Type pInf = ^TInf; {ссылочный тип для адресации базовых объектов}.

TInf = record {тип-базовая структура}.

end;

pItem = ^TItem;

{ссылочный тип для адресации элементов списка указателей}.

TItem = record {описание структуры элемента списка указателей}.

next: pItem; {поле-указатель на соседний элемент списка}.

baseObject: pInf; {поле-указатель на базовый объект}.

end;

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

Добавление нового элемента требует двукратного выделения памяти: сначала для самого базового объекта (переменная-указатель pTempObject типа pInf), потом — для элемента списка (переменная-указатель pTemp типа pItem). Основные операции:

• · new (pTempObject);
• · «заполнение полей базовой структуры pTempObject^ «;
• · new (pTemp);
• · pTemp^.baseObject:= pTempObject;
• · «добавление элемента в список» ;

Аналогично, удаление элемента требует двукратного освобождения памяти: сначала — для базового объекта, потом — для элемента списка. Как и в случае использования массива, очень легко производится перестановка двух элементов за счет взаимной замены адресных полей baseObject без перемещения самих базовых объектов.

Пусть pCurrent1 и pCurrent2 — указатели на элементы списка, у которых надо обменять базовые объекты. Тогда сам обмен реализуется с помощью вспомогательной переменной pTempObject типа pInf следующим образом:

pTempObject:= pCurrent1^.baseObject;

pCurrent1^.baseObject:= pCurrent2^.baseObject;

pCurrent2^.baseObject:= pTempObject;

Отметим, что операции перестановки очень часто используются в алгоритмах сортировки массивов и списков.