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




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

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;

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;

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

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-03-31 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: