Связное представление данных в памяти

Динамические структуры характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) в процессе ее обработки. Элементы динамической структуры располагаются по непредсказуемым адресам памяти, поэтому адрес элемента структуры не может быть вычислен по адресу начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным.

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

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

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

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

Достоинства связного представления данных:

- возможность обеспечения значительной изменчивости структур;

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

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

Вместе с тем связное представление не лишено и недостатков:

- работа с указателями требует, как правило, более высокой квалификации от разработчика;

- на поля связок расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

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

Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее выполняется поиск требуемого элемента путем следования по цепочке указателей от элемента к элементу. Поэтому связное представление не применяется в задачах, где логическая структура данных имеет вид вектора или массива (с доступом по номеру элемента), но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.).