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

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

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

x, y : integer;

name : string;

end;

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

varArrOfPointer : 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;

next = nil baseObject

next baseObject

next baseObject

next baseObject

. . . . .

Естественно, что список указателей может иметь заголовок и быть двунаправленным. В любом случае обработка полей базовых объектов выполняется с помощью соответствующих указателей (поле 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;

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