1. Контрольные вопросы

1. Что представляет собой объектный тип?

2. В чем заключается идея сокрытия информации?

3. Для чего необходимы директивы видимости и свойства?

4. Опишите способы структурированной обработки ошибок.

5. Приведите примеры описания классов и использования объектов.

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

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

Ряд языков (PL/1, ALGOL-60) допускают размещение статических структур в памяти на этапе выполнения по явному требованию, но и в этом случае объем выделенной памяти остается неизменным до уничтожения структуры. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач их используют даже для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.

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

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

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

1. 4.1. Векторы

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

Элементы вектора размещаются в памяти в расположенных подряд (смежных) ячейках. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов. В языках программирования вектор представляется одномерным массивом:

< имя >: array[n..k]of< тип >;

где n-номер первого элемента, k-номер последнего элемента.

Представление в памяти вектора показано табл. 4.1. Здесь и далее смещение указано в байтах относительно начального адреса расположения вектора.

Табл. 4.1. Представление вектора в памяти.

Смещение	+0	+SizeOf(тип)	…	+(k-n)*SizeOf(тип)
Идентификатор	Имя [n]	Имя [n+1]	…	Имя [k]

В таблице приняты следующие обозначения:

@Имя - адрес вектора (адрес первого элемента вектора);

SizeOf(тип) - размер слота (количество байтов памяти для записи одного элемента вектора);

(k-n)SizeOf(тип) - относительный адрес элемента с номером k (смещение элемента с номером k).

Пусть объявлен следующий вектор:

varv:array[-2..2]ofreal;

Представление вектора в памяти показано в табл. 4.2.

Табл. 4.2. Представление вектора v в памяти.

Смещение	+0	+6	+12	+18	+24
Идентификатор	v[-2]	v[-1]	v[0]	v[1]	v[2]

В языках, где память под массив выделяется на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индексов должны быть определены. В языках, где память может распределяться динамически (ALGOL, PL/1), значения индексов могут быть заданы во время выполнения программы.

Количество байт непрерывной области памяти, одновременно занятых вектором равно:

ByteSize = (k-n+1)·SizeOf(тип)

Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора равно:

ByteNumer= (i-n)·SizeOf(тип)

а его адрес:

@ByteNumber = @имя + ByteNumber

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

Например:

var v: array[5..10] of Word

Базовый тип элемента вектора Word, поэтому на каждый элемент выделяется по два байта. Смещения элементов относительно @v показано в табл. 4.3.

Табл. 4.3. Представление вектора v.

Смещение	+0	+2	+4	+6	+8	+10
Идентификатор	v[5]	v[6]	v[7]	v[8]	v[9]	v[10]

Данный вектор будет занимать в памяти: (10-5+1)·2 = 12 байт. Смещение к элементу вектора с номером 8: (8-5) ·2 = 6. Адрес элемента с номером 8: @v + 6.

При доступе к вектору задается имя вектора и номер элемента вектора. Адрес i-го элемента может быть вычислен:

@Имя[i] = @Имя+i·SizeOf(тип)-n·SizeOf(тип) (4.1)

Такое вычисление не может быть выполнено на этапе компиляции, т.к. значение переменной i в это время еще неизвестно. Следовательно, вычисление адреса элемента должно производиться на этапе выполнения при каждом обращении к элементу вектора. Для этого, во-первых, должны быть известны параметры формулы (4.1), во-вторых, при каждом обращении должны выполняться две операции умножения и две операции сложения. Преобразовав формулу (4.1), получим:

@Имя[i] =A0+i·SizeOf(тип) (4.2)

где A0 = @Имя-n·SizeOf(тип)

Число хранимых параметров может быть сокращено до двух, а число операций – до одного умножения и одного сложения, т.к. значение A0 может быть вычислено на этапе компиляции и сохранено вместе с SizeOf(тип) в дескрипторе вектора.

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

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

В языке C, например, дескриптор вектора отсутствует, точнее, не сохраняется на этапе выполнения. Индексация массивов в C обязательно начинается с нуля. Компилятор каждое обращение к элементу массива заменяет на последовательность команд, реализуя частный случай формулы (4.1) при n = 0.