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

Костерин В В

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

которая характеризуется:

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

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

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

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

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

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

Статическая запись — конечное упорядоченное множество полей, характеризующихся различным типом данных. Записи являются чрезвычайно удобным средством для представления программных моделей реальных объектов предметной области, ибо, как правило, каждый такой объект обладает набором свойств, характеризуемых данными различных типов.

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

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

<имя переменной — записи>.<имя поля>

В ряде прикладных задач программист может столкнуться с группами объектов, чьи наборы свойств перекрываются лишь частично. Для задач подобного рода развитые языки программирования предоставляют в распоряжение программиста записи с вариантами (union в С, case в Turbo Pascal).

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

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

Базовыми операциями над строками являются:

• определение длины строки;

• присваивание строк;

• конкатенация (сцепление) строк;

• выделение подстроки;

• поиск вхождения.

Операция определения длины строки имеет вид функции, возвращаемое значение которой является целым числом, равным текущему числу символов в строке.

Операция присваивания имеет тот же смысл, что и для других типов данных.