Динамические структуры по определению характеризуются от-
сутствием физической смежности элементов структуры в памяти не-
постоянством и непредсказуемостью размера (числа элементов)
структуры в процессе ее обработки. В этом разделе рассмотрены
особенности динамических структур, определяемые их первым харак-
терным свойством. Особенности, связанные со вторым свойством
рассматриваются в последнем разделе данной главы.
Поскольку элементы динамической структуры располагаются по
непредсказуемым адресам памяти, адрес элемента такой структуры не
может быть вычислен из адреса начального или предыдущего элемен-
та. Для установления связи между элементами динамической структу-
ры используются указатели, через которые устанавливаются явные
связи между элементами. Такое представление данных в памяти назы-
вается связным. Элемент динамической структуры состоит из двух
полей:
- информационного поля или поля данных, в котором содержатся
те данные, ради которых и создается структура; в общем случае ин-
формационное поле само является интегрированной структурой - век-
тором, массивом, записью и т.п.;
- поле связок, в котором содержатся один или несколько ука-
зателей, связывающий данный элемент с другими элементами
структуры;
Когда связное представление данных используется для решения
прикладной задачи, для конечного пользователя "видимым" делается
только содержимое информационного поля, а поле связок использует-
ся только программистом-разработчиком.
Достоинства связного представления данных - в возможности
обеспечения значительной изменчивости структур;
- размер структуры ограничивается только доступным объемом
машинной памяти;
- при изменении логической последовательности элементов
структуры требуется не перемещение данных в памяти, а только кор-
рекция указателей.
Вместе с тем связное представление не лишено и недостатков,
основные из которых:
- работа с указателями требует, как правило, более высокой
квалификации от программиста;
- на поля связок расходуется дополнительная память;
- доступ к элементам связной структуры может быть менее эф-
фективным по времени.
Последний недостаток является наиболее серьезным и именно им
ограничивается применимость связного представления данных. Если в
смежном представлении данных для вычисления адреса любого элемен-
та нам во всех случаях достаточно было номера элемента и информа-
ции, содержащейся в дескрипторе структуры, то для связного предс-
тавления адрес элемента не может быть вычислен из исходных
данных. Дескриптор связной структуры содержит один или несколько
указателей, позволяющих войти в структуру, далее поиск требуемого
элемента выполняется следованием по цепочке указателей от элемен-
та к элементу. Поэтому связное представление практически никогда
не применяется в задачах, где логическая структура данных имеет
вид вектора или массива - с доступом по номеру элемента, но часто
применяется в задачах, где логическая структура требует другой
исходной информации доступа (таблицы, списки, деревья и т.д.).