12. Простые и статические структуры данных;

Простые структуры данных служат основой для построения более сложных структур. Их называют также примитивными или базовыми структурами (типами данных). К ним относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. Структура простых типов данных для языка Pascal приведена на рис. 3.2 (в других языках программирования набор и размеры простых типов могут отличаться от приведенного на рисунке). Размер каждого типа данных указан на рисунке в байтах через запятую от названия типа. Как уже было сказано, разные типы данных имеют различный формат представления их в машинной памяти. Статические структуры представляют собой структурированное множество примитивных структур. Например, вектор может быть представлен упорядоченным множеством чисел. Изменчивость несвойственна статическим структурам, т. е. размер памяти компьютера, отводимый для таких данных, постоянен и выделяется на этапе компиляции или выполнения программы.

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

определяемое базовым типом элемента этого вектора. Тогда размер памяти, отводимой для размещения вектора, будет определяться следующим соотношением: S= k* Sizeof(Tnn), где к — количество элементов (длина) вектора, a Sizeof(™n) — размер памяти, необходимой для хранения одного элемента вектора.

Двумерные массивы Двумерный массив (матрица) — это вектор, каждый элемент которого вектор. Поэтому то, что справедливо для вектора, справедливо и для матрицы (аналогично для я-мерных массивов).

Множества Множеством является структура, представляющая собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Поскольку базовый тип не должен превышать 256 возможных значений, типом элементов множества могут быть byte, char и производные от них типы. Множество в памяти хранится как массив битов, в котором каждый бит указывает, является ли элемент принадлежащим объявленному множеству или нет. Таким образом, максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.

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

13. Полустатические и динамические структуры данных;

Свойства полустатических структур данных:

• они имеют переменную длину и простые способы ее изменения;

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

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

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

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

структур:

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

• при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей. С другой стороны, такие структуры обладают рядом недостатков:

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

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

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

Связные линейные списки

Линейные связные списки являются простейшими динамическими структурами данных. Они являются упорядоченными множествами, содержащими переменное число элементов, на которые не накладываются ограничения по длине.

Двусвязные списки

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