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

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

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

постоянством и непредсказуемостью размера (числа элементов)

структуры в процессе ее обработки. В этом разделе рассмотрены

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

терным свойством. Особенности, связанные со вторым свойством

рассматриваются в последнем разделе данной главы.

Поскольку элементы динамической структуры располагаются по

непредсказуемым адресам памяти, адрес элемента такой структуры не

может быть вычислен из адреса начального или предыдущего элемен-

та. Для установления связи между элементами динамической структу-

ры используются указатели, через которые устанавливаются явные

связи между элементами. Такое представление данных в памяти назы-

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

полей:

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

те данные, ради которых и создается структура; в общем случае ин-

формационное поле само является интегрированной структурой - век-

тором, массивом, записью и т.п.;

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

зателей, связывающий данный элемент с другими элементами

структуры;

Когда связное представление данных используется для решения

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

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

ся только программистом-разработчиком.

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

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

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

машинной памяти;

- при изменении логической последовательности элементов

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

рекция указателей.

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

основные из которых:

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

квалификации от программиста;

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

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

фективным по времени.

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

ограничивается применимость связного представления данных. Если в

смежном представлении данных для вычисления адреса любого элемен-

та нам во всех случаях достаточно было номера элемента и информа-

ции, содержащейся в дескрипторе структуры, то для связного предс-

тавления адрес элемента не может быть вычислен из исходных

данных. Дескриптор связной структуры содержит один или несколько

указателей, позволяющих войти в структуру, далее поиск требуемого

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

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

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

вид вектора или массива - с доступом по номеру элемента, но часто

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

исходной информации доступа (таблицы, списки, деревья и т.д.).