Статические структуры данных

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

Векторы

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

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

Рис. 3.6. Представление вектора в памяти:

@Имя — адрес вектора или адрес первого элемента вектора

Двумерные массивы

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

 

Множества

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

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

 

Рис. 3.7. Представление множества в памяти:

@S — адрес данного типа множество

 

Размер памяти (в байтах), выделяемых под множество, вычисляется по формуле: S- (max div 8) - (min div 8) + 1, где max и min — верхняя и нижняя границы базового типа данного множества, a div —- целочисленное деление.

Записи

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

Пример записи — набор сведений о сотруднике кафедры.

Объект «сотрудник» может обладать следующими свойствами:

• табельный номер — целое положительное число;

• фамилия-имя-отчество — строка символов и т. д.;

• пол — символ;

• ученая степень — строка символов;

• заработная плата — вещественное число;

• и др.

В памяти эта структура может быть представлена в одном из двух видов:

• в виде последовательности полей, занимающих непрерывную область памяти (рис. 3.8). Чтобы получить доступ к любому элементу записи, нужно знать адрес начала записи и смещение относительно начала. При этом достигается экономия памяти компьютера, но затрачивается лишнее время на вычисление адресов полей;

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

Рис. 3.8. Представление в памяти переменной типа запись в виде последовательности полей

Рис. 3.9. Размещение в памяти переменной типа запись в виде указателей