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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4. КЛАССИФИКАЦИЯ ВИДОВ ОПЕРАТИВНЫХ СТРУКТУР ДАННЫХ ПО ИХ ЛОГИЧЕСКОМУ УСТРОЙСТВУ

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

Статический массив — такая структура данных, которая характеризуется:

1) фиксированным набором элементов одного и того же типа;

2) каждый элемент имеет уникальный набор значений индексов;

3) количество индексов определяет мерность массива, например, два индекса — двухмерный массив, или матрица, три индекса — трехмерный массив, один индекс — одномерный массив, или вектор;

4) обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.

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