СД типа массив

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

type A = array [T1] of T2,

где Т1 – базовый тип массива, Т2 – тип индекса.

Если D_T1 – множество значений элементов типа Т1, D_Т2 – множество значений элементов типа Т2, то А: D_T1 ® D_Т2 (отображение).

Кардинальное число Car(T) структуры типа Т – это множество значений, которое может принимать данная структура типа Т. Кардинальное число характеризует объем памяти, необходимый данной структуре. Для массива A: Car(A) = [Car(T2)] ^Car(T1).

Набор допустимых операций для СД типа массив:

1. Операция доступа (доступ к элементам массива – прямой; от размера структуры операция не зависит).

2. Операция присваивания.

3. Операция инициализации (определение начальных условий).

На физическом уровне СД типа массив представляет собой непрерывный участок памяти элементов одинакового объема. Участок памяти, необходимый для одного элемента называется слотом.

Var B: A {определяем переменную В как переменную типа массив А}

p £ i £ g, где p – индекс первого элемента массива, g – индекс последнего элемента массива, i – индекс рассматриваемого элемента.

Учитывая введенные обозначения, формула для вычисления размера слота одномерного массива выглядит следующим образом:

Adr(B[i]) = Adr(B[p]) + (i-p)*S = Adr(B[p]) – p* S + i* S,

где S – количество слов, которое необходимо для одного элемента (зависит от типа элемента), Adr(B[p]) – p* S является константой, а i* S – переменная.

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

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

Var A: array [-5.. 4] of Char

дескриптор будет выглядеть таким образом:

V	A
Adr (A[-5])
-5
Char

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

Дата добавления: 2014-01-07