2.3. Структурные типы данных

Объекты структурных типов данных содержат несколько объектов простых или структурных типов.

2.3.1. Массивы

Массив -- это структура данных с компонентами одинакового типа, которые идентифицируются индексами. Массивы описываются следующим образом:

type имя_типа is array (T1) of T2;

Здесь T1 -- тип индексов, T2 -- тип компонентов массива.

Каждой компоненте массива однозначно соответствует некоторое значение типа T1.

П р и м е р 2.8. Описание массива:

type ИНДЕКС is integer range 1.. 10;

type ВЕКТОР is array (ИНДЕКС) of real;

Здесь вводится тип ВЕКТОР, представляющий собой массив из 10 действительных чисел, каждое из которых индексируется целым числом от 1 до 10.

Массив можно представлять как реализацию некоторой функции, отображающей множество значений типа T1 в множество значений типа T2. Например, переменная

V: ВЕКТОР;

реализует функцию V: {1,..., 10} --> R. Поэтому для получения значения некоторой компоненты массива (т.е. значения функции в некоторой точке) используется функциональная запись V(7). Массив предоставляет также возможность модификации реализуемой функции: можно изменять значение функции для некоторого значения индекса, например

V(7):=1. О;

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

Над компонентами массива можно выполнять все те операции, которые можно выполнять над данными типа компонентов массива. Кроме этого, над массивами, рассматриваемыми как единое целое, можно выполнять операции сравнения на равенство и неравенство, а также оператор присваивания (так как они применимы ко всем типам по определению).

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

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

динамические, у которых нет указанных ограничений на тип индексов.

П р и м е р 2.9. Описание статического массива:

type ИНДЕКС is integer range 1.. 10;

type ВЕКТОР is array (ИНДЕКС) of real;

V: ВЕКТОР; -- размер массива равен 10

П р и м е р 2. 10. Описание динамического массива:

N: positive;

type ИНДЕКСN is integer range 1.. N;

type ВЕКТОРN is array(ИНДЕКСN) of real;

........

N:=5;

block

use ВЕКТОРN: type, N: in out positive;

V: ВЕКТОРN; -- размер массива равен 5

begin

N:=10;

block

use ВЕКТОРN: type;

V: ВЕКТОРN; -- размер массива равен 10

begin

............

end block;

end block;

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

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

V: ВЕКТОР;

Тогда к вырезкам массива V можно обращаться следующим образом:

V(6.. 9)массив из четырех элементов, являющихся

6, 7, 8, 9 элементами массива V

V(I.. J) -- массив из (J-I+1) элементов, являющихся

I, I+1,..., J элементами массива V

Чтобы использовать вырезки в сильно типизированном языке с именной эквивалентностью типов, необходимо выяснить, какой тип имеет вырезка. Очевидно, что типом вырезки не может быть тип исходного массива. Отсюда следует, что тип вырезки не имеет имени, является анонимным (т.е. неизвестным программисту). Далее возможны две альтернативы. Одна из них заключается в определении типа вырезки как анонимном типа. Типом вырезки V(6.. 9) может быть

type ** is array(****) of real;

где

type **** is ИНДЕКС range 6.. 9;

**, **** -- анонимные идентификаторы. В этом случае не правильны следующие операторы:

type ИНДЕКС1 is integer range 6.. 9;

type ВЕКТОР1 is array (ИНДЕКС1) of real;

V : ВЕКТОР;

W: ВЕКТОР1;

............

V(1 .. 4):=V(6 .. 9); -- разные типы

V(6.. 9):=W; -- разные типы

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

Пусть V(6.. 9) имеет тип **

где

subtype ** is ВЕКТОР (****);

subtype **** is ИНДЕКС range 6.. 9;

Тогда правильны следующие операторы:

subtype ИНДЕКС1 is ИНДЕКС range 6.. 9;

subtype ВЕКТОР1 is ВЕКТОР (ИНДЕКС1);

V,U ВЕКТОР;

W: ВЕКТОР1;

..........

V(1 .. 4):=V(6 .. 9);

V(6 .. 9):=W;

V(6 .. 9):=U(6 .. 9);

W:=U(1.. 4);

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

Теперь рассмотрим взаимодействие различных типов массивов.

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

────────────────

П р и м е р 2. 11. Преобразование типа массива при присваивании:

type ИНДЕКС is integer range 1.. 10;

type ВЕКТОР is array (ИНДЕКС) of real;

type ВЕКТОР2 is array (ИНДЕКС) of integer;

V: ВЕКТОР;

W : ВЕКТОР2;

..................

V:=ВЕКТОР(W);

Здесь компоненты массива W преобразуются в действительный тип. Конечно, типы индексов должны быть одинаковы (либо должны быть подтипами одного и того же типа). Типы V и W различны, поэтому непосредственное присваивание массива W массиву V недопустимо.

────────────────

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

type ВЕКТОР3 is array (integer range 1.. 10) of real;

эквивалентно описанию

subtype **** is integer range 1..10;

type ВЕКТОР3 is array (****) of real;

где **** -- анонимный идентификатор. Более того, приведенное описание можно сократить:

type ВЕКТОР3 is array(1.. 10) of real;

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

type ВЕКТОР3 is array (integer range 1.. 10) of real;

содержит в качестве типа индексов анонимный тип, а не подтип, то это описание эквивалентно следующему:

type **** is integer range 1.. 10;

type ВЕКТОР3 is array(****) of real;

Конечно, использование типов вместо подтипов в принципе повысило бы надежность языка, причем это совершенно не повлияло бы на его мощность. Однако очевидно, что анонимные типы индексов практически бесполезны в качестве индексов можно указывать только предопределенные константы. Поэтому пришлось бы всегда явно вводить типы индексов, что отрицательно сказалось бы на удобочитаемости программ. В противоположность этому использование анонимного типа в качестве типа компонент массива вполне допустимо: преобразования можно осуществлять, указав имя типа массива. Описание

type ВЕКТОР4 is array (ИНДЕКС) of real range -1. О.. 1. О;

эквивалентно описанию

type **** is real range -1.0..1.0;

type ВЕКТОР4 is array(ИНДЕКС) of ****;

Тогда, имея переменные

W:ВЕКТОР4;

V: ВЕКТОР;

можем записать правильный оператор:

W:=ВЕКТОР4(V);

При работе с массивами можно использовать константы соответствующих типов, называемые составными значениями или агрегатами. Константа называется п 2о 0зиционным агрегатом, если компоненты массива сопоставляются своим значениям по позициям: первое значение -- первой компоненте массива, второе -- второй и т.д. Можно использовать и непозиционные агрегаты, в которых связь между компонентами и значениями указана явно.

──────────────────

П р и м е р 2. 12. Описание позиционного агрегата:

type ВЕКТОР is array ('А'.. 'Е' ) of integer;

W: ВЕКТОР;

...........

W:=(1, 2, 3, 4, 5);

Здесь W(' А' ) станет равным 1, W(' В' ) -- 2 и т.д.

────────────────────────

────────────────────

П р и м е р 2. 13. Описание непозиционных агрегатов:

W:=(' А' .. 'С'=>1, 'D'.. 'E'=> 0);

-- эквивалентно (1,1,1,0,0)

W:=(' А' .. 'С'=>1,others=>0);

-- еще одно представление того же значения

W:=('А'|'С'|'E'=>1,others =>0);

--эквивалентно (1,0,1,0,1)

W:=('Е' =>5,'D'=>4,'C'=>3,'B'=>2,'A'=>1);

--эквивалентно (1,2,3,4,5)

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

type ДНИ_НЕДЕЛИ is (ПН, ВТ, СР, ЧТ, ПТ, СБ, ВС);

type ВРЕМЯ is intеgеr range О.. 24;

type РАБОЧЕЕ_ВРЕМЯ is array(ДНИ НЕДЕЛИ)

оf ВРЕМЯ;

РАБОТА: constant РАБОЧЕЕ_ВРЕМЯ

:= (ПН.. ПТ=>8, others=>О);

Иногда по виду агрегата нельзя определить, к какому типу он принадлежит. В этом случае для указания типа используется функция преобразования типа:

type СВОБОДНОЕ_ВРЕМЯ is array(ДНИ_НЕДЕЛИ)

оf ВРЕМЯ;

СВОБОДНОЕ_ВРЕМЯ(6, 6, 6, 6, 6, 16, 16)

-массив типа СВОБОДНОЕ_ВРЕМЯ

РАБОЧЕЕ_ВРЕМЯ(8, 8, 8, 8, 8, О, О)

-массив типа РАБОЧЕЕ_ВРЕМЯ

Рассмотрим теперь два частных вида массивов: строки и многомерные массивы.

Строки -- мо массивы, тип индексов которых целый, а тип компонент символьный. Для описания строк используется предопределенный тип STRING, который определяется следующим образом:

type STRING is array (integer) оf сhаrасtеr;

Тогда типы всех строковых переменных описываются как

подтипы типа STRING:

subtype STRING10 is STRING(1.. 10);

СТРОКА1: STRING10;

СТРОКА2: STRING(1..10);

СТРОКА3: STRING(11..30);

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

"АВСВ" -- эквивалентно (' А', ' В', ' С','D')

"A" -- эквивалентно ('А'), но не 'A'

" " -- эквивалентно (' ')

"" -- эквивалентно ()

Во-вторых, объекты строкового типа можно сравнивать не только на равенство и неравенство, но и по лексикографическому порядку:

В: Ьоо1еаn;

 2...

В:=(" АВ" < "АС" ); 2  0-- значение true

В:=(" АВ" < "АВС" ); 2  0-- значение true

В:=(" АВ" >= "АВС" ); -- значение false

В-третьих, к строкам применима также операция конкатенации (сцепления)  2& 0:

"AB" & "CD" - в результате дает "ABCD"

"AB" & 'С' - в результате дает "ABC"

'А' & 'В' - в результате дает "AB"

'A' & "" - в результате дает "А"

Это еще один пример перегруженной операции (операнды могут быть симвопьными и строковыми).

Тип компонент массива может быть любым, в том числе и другим массивом, например:

type ИНДЕКС is integer range 1.. 10;

type ВЕКТОР is array(ИНДЕКС) of real;

type МАТРИЦА 1 array(ИНДЕКС) of ВЕКТОР;

Константа типа МАТРИЦА записывается следуюшим образом:

( 1 => (1/5/9=> 1.О, others => О.О),

3 => (5 => 1.О, others => О.О),

others => (others => О.5) )

Для массивов вида

type МАТРИЦА1 is array (ИНДЕКС) of

array (ИНДЕКС) of real;

допустимо сокращение:

type МАТРИЦА1 is array (ИНДЕКС, ИНДЕКС) of real;

(конечно, типы различных индексов не обязателы~о одинаковые). Возможно сокращение для операции индексирования, например:

МАТРИЦА1(I,J) -- эквивалентно МАТРИЦА1(I)(J)

МАТРИЦА1(5 .. 7, I .. J) -- эквивалентно

МАТРИЦА1(5.. 7)(I.. J)

Чтобы узнать размер массивов, используются следующие атрибуты типа:

имя_типа'FIRST - нижняя граница индексов одно-

мерного массива

имя_типа'LAST - верхняя граница индексов одно-

мерного массива

имя_типа'LENGTH - число компонент (длина) одно-

мерного массива

имя_типа'FIRST(I) - нижняя граница I-го индекса

имя_типа'LAST(I) - верхняя граница I-го индекса

имя_типа'LENGTH(I) - длина по I-му индексу (тип ре-

зультата есть integer)

(вместо имени типа можно указывать имя переменной).

2.3.2. Записи

Запись -- это структура данных с компонентами не обязательно одинакового типа, которые идентифицируются селекторами. Записи описываются следующим образом:

type имя_типа is гесогd

S₁: Т₁;

S₂: T₂;

...

S_n: T_n;

end record;

Здесь T₁, T₂,..., Т_n - типы компонент записи, а

S₁, S₂,..., S_n - селекторы, используемые для идентификации компонент. Каждой компоненте записи однозначно соответствует некоторый селектор.

__________

П р и м е р 2. 14. В описаиии

type ДЕНЬ is iпtеgег гаngе 1..31;

type МЕСЯЦ is (ЯНВ, ФЕВ, МАР, АПР, МАИ, ИЮН,

ИЮЛ, АВГ, СЕН, ОКТ, НОЯ, ДЕК);

type ГОД is 1п1еgег гаngе 0.. 2000;

type ДАТА isгесогd

Д: ДЕНЬ;

М: МЕСЯЦ;

Г: ГОД;

end гесогd;

вводится тип ДАТА, представляющий собой запись из трех компонент типа ДЕНЬ, МЕСЯЦ, ГОД; компоненты идентифицируются селекторами соответственно Д, М, Г.

_____________

Запись можно представить как реализацию декартова произведения множеств Т₁хТ₂х... хТ_n, представляющих множества значений указанных типов данных. Например, переменная

СЕГОДНЯ: ДАТА;

реализует декартово произведение ДЕНЬхМЕСЯЦхГОД. Отсюда следует, что при ее использовании важно расположение компонент в записи. Так, тип

type ДАТА1 is гесогd

Г: ГОД;

М: МЕСЯЦ;

Д: ДЕНЬ;

еnd гесогd;

отличен от типа ДАТА. Для получения/изменения значения компоненты записи применяется конструкция вида

СЕГОДНЯ. МЕСЯЦ.

Над компонентами записи можно выполнять все те операции, которые можно выполнять над данными типа компонент записи. Кроме этого, над записями, рассматриваемыми как единое целое, можно выполнять операции сравнения на равенство и неравенство и операторы присваивания (так как они применимы ко всем типам по определению).

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

__________

П р и м е р 2. 15. Описание агрегатов-записей:

НОВЫЙ_ГОД: соnstant ДАТА:= (31, ДЕК, 1990);

- позиционный агрегат

СЕГОДНЯ:= ДАТА(Г=>1990, М=>ДЕК, Д=>31);

- типизированный непозиционный агре-

гат, эквивалентный (31, ДЕК, 1990)

___________

2.3.3. Объединения

Объединения -- это механизм, существенно отличающийся от механизма массивов и записей. Если массивы и записи предоставляют средства для структурирования данных в пространстве, то объединения -- для структурирования во времени. Описание объединения:

type имя типа is uniоn

Т₁;

Т₂;

...

T_n;

епd uniоn;

Переменная этого типа может в различные моменты времени принимать значения одного из перечисленных типов Т1, Т2,..., Тn (все эти типы должны быть различны).

__________

П р и м е р 2. 16. Описание обьединения:

type ЧИСЛО is uniоn

integer;

real;

епd union;

Х: ЧИСЛО;

Здесь вводится тип ЧИСЛО, являющийся объединением чис-

ловых типов, и переменная типа ЧИСЛО.

_____________

Для переменной Х типа ЧИСЛО правильны следующие операторы:

У: integer;

Z: real;

...

Х:=1;

Х:=1. О;

Х:=У;

Х:=Z;

Z:=Х;

Однако есть и примеры неправильных операторов; иапример, второй оператор неправилен:

Х:=У;

Z:=Х; - разные типы (Х в данный момент целот типа)

Ясно, что неправомерность последнего оператора в общем случае можно установить лишь при выполнении программы.

Следовательно, использование объединений увеличивает объем динамическот контроля типов. Однако механизм объединений необходим, например, для реализации динамических структур данных (см. п. 2. 4).

Чтобы узнать тип текущего значения некоторой переменной, используется атрибут типа

имя типа' ТУРЕ

являющийся функцией, параметром которой является данная переменная, а результатом -- логическое значение. Эта функция выдает true, если текущее значение переменной относится к указанному типу. Например, для переменной Х

типа ЧИСЛО имеем

Х:=1;

integer' ТYРЕ(Х) дает значение true

real' ТYРЕ(Х) дает значение false

ЧИСЛО'TYPE(X) дает значение true

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

Х, У: ЧИСЛО;

...

Х:=1; У:=1.0;

if Х=У then ...

значения Х и У не равны.

В качестве объединяемых типов могут выступать не только простые типы, но и любые другие, например:

type ВЕКТОР is array(integer) of real;

type ДИНАМ_ВЕКТОР is union

ВЕКТОР(1.. 2);

ВЕКТОР(1.. 3);

ВЕКТОР(1.. 4);

ВЕКТОР(1.. 5);

еnd union;

V: ДИНАМ_ВЕКТОР;

Здесь переменная V может принимать в качестве значений массивы из 2, 3, 4, 5 компонент. Следующие операторы правильны:

V:=(1. О, 2. О, 3. 0);

- здесь ВЕКТОР(1 .. 3)' ТУРЕ(V)= true, а V' LENGTH= 3

V:=(1. 0,2. 0,3. 0,4. 0,5. 0);

- здесь ВЕКТОР(1 .. 5)' ТУРЕ(V) = true, а V' LENGTH= 5

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

type ДИНАМ ВЕКТОР is union for N: 2.. 5

ВЕКТОР(1.. N);

еnd union;

Здесь имя N автоматически описывается как

N:integer range 2.. 5;

внутри объединения (аналогично локальным переменным блока) -- его можно использовать только в этом объединении; вне объединения можно описывать переменные с тем же именем. В общем случае эта конструкция имеет вид

type имя_типа is union for Р₁:ТР₁, Р₂:ТР₂,...,P_k:TP_k

Т₁;

Т₂;

...

T_n;

end union;

Здесь ТР₁, ТР₂,..., ТР_k - некоторые дискретные типы. Если тип Т₁ параметризованный с параметром Р_j или содержит в своем описании свободный идентификатор Р_j, то эта запись означает объединение типов, получаемых из Т_i, заменой параметров или свободных идентификаторов всеми значениями соответствующих типов ТР_j . Если же тип Т_i,непараметризован и не содержит свободных идентификаторов или параметры и свободные идентификаторы отличны от Р₁ Р₂..., Р_k, то эта запись не производит никакого действия. Например, объединение

type ДИНАМ_ВЕКТОР is union

for

N1: integer range 1..100,

N2: integer range N1..100

ВЕКТОР(N1 .. N2);

end union;

эквивалентно объединению

type ДИНАМ_ВЕКТОР is union

ВЕКТОР(1 .. 1);

ВЕКТОР(1 .. 2);

...

ВЕКТОР(1 .. 100);

ВЕКТОР(2.. 2);

ВЕКТОР(2.. 3);

...

ВЕКТОР(100.. 100);

end union;

Это объедицение можно записать еще короче:

type ДИНАМ_ВЕКТОР is union

for N1: 1..100, N2: N1..100

ВЕКТОР(N1..N2);

end union;

Можно описывать объединение массивов произвольного

type ДИНАМ_ВЕКТОР is union for N: positive

ВЕКТОР(1..N);

end union;