В Камаев - Технологии программирования

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

Динамические переменные размещаются в динамически распределяемой области памяти (ДРП). Область ДРП находится вне области кода программы. В зарубежных источниках ДРП обозначается термином "heap" — куча. Обычно заполнение области ДРП осуществляется при помощи стандартных процедур диспетчирования ДРП.

Связные динамические структуры данных. Связность — особое продуманное логическое устройство сохранения целостности структуры данных, элементы которой могут находиться в произвольных, несмежных, неконтролируемых по адресации участках ДРП.

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

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

Поскольку элементы связной динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Связные структуры данных связаны в единую сущность системой указателей, содержащихся как в элементах, так и статических структурах, обеспечивающих доступ к особым элементам. Такие статические структуры называют дескрипторами. Именно такое представление данных в памяти называют связным. Элемент связной динамической структуры состоит из двух полей:

— информационного поля, или поля данных, в котором содержатся те данные (в том числе и интегрированные), ради которых оно и создается;

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

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

Достоинства связного представления данных заключаются в возможности обеспечения значительной изменчивости структур:

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

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

Недостатки связного представления:

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

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

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

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

По признаку физического размещения структуры данных различают оперативные и файловые структуры. Структуры данных, размещаемые в оперативной памяти, называют оперативными структурами. Файловые структуры соответствуют структурам данных внешней памяти. Оперативная память является быстрой, а внешняя — медленной.

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