Глава 6. Структурированные типы данных

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

Массивы

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

Определение массива имеет вид:

Type <имя> = array [T1] of [T2];

Var <имя>[, …] : array [T1] of [T2];

Здесь Т1 обозначает тип индексов массива, Т2 – тип элементов массива. В качестве типа индекса можно использовать любой дискретный тип, кроме Longint, в основном используются диапазоны. Элементами массива могут быть значения любого типа, кроме файлового.

Пример:

Type

M2 = array [1..100] of real;

Z = array [boolean] of integer;

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

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

Var Mass: array [1..10] of array [char] of array [boolean] of byte;

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

Mass[i+5]['A'][True]

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

Var Mass: array [1..10,char,boolean] of byte

например, с таким обращением

Mass[x+1,gamm,bool2]

В конкретной реализации Турбо-Паскаль, работающей в ОС MS DOS, есть ограничение на общее количество элементов одного массива, связанное с сегментной организацией памяти: максимальный размер 2¹⁶ = 64Кбайт.

Строки

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

В стандартном Паскале для строковых массивов были введены некоторые дополнительные правила, в Турбо-Паскале такие массивы выделены в отдельный тип – строки.

Строки описываются следующим образом:

Type <имя> = string [[<длина>]];

Var <имя>[, ...] : string [[<длина>]];

Здесь необязательный параметр <длина> указывает максимальное количество символов в строке. Если длина не задана, то по умолчанию (автоматически) принимается максимально возможная длина 255. Это связано с тем, что один байт как раз и указывает на длину строки, но в сам текст строки не включается.

Строка в Турбо Паскале трактуется как цепочка символов. К любому символу в строке можно обратиться точно так же, как к элементу одномерного массива ARRAY [0..N] OF CHAR: указывается имя и в квадратных скобках позиция символа. Например:

var

st: String;

begin

…

if st[5] = 'A' then…

…

В дополнение к операциям, применимым к переменным типа Char, введены групповые операции сцепления (конкатенации, объединения) нескольких строк с использованием знака «+». При этом длина итоговой строки увеличивается, и это главное отличие строк от массивов. Элементы строки нумеруются, начиная с единицы, отсутствие элементов – строка нулевой длины. Запись константы имеет вид строки, в следующем примере объединяются три константы:

Writeln(' Это'+' – '+'строка');

Результат: вывод строки «Это – строка»

Для работы со строками используются следующие стандартные процедуры и функции.

Функцию Concat (<строка> [, …])можно использовать вместо операции сцепления. Тогда пример сцепления строк будет выглядеть как:

Writeln(Concat(' Это',' – ','строка');

Функция Length (<строка>) позволяет определить не предельную, а фактическую длину строки. Результат – целое число. Например:

If Length(st)<>0 then …

Функция UpCase (<символ>) позволяет преобразовать символ любой латинской буквы из строчной в прописную.

Функция Copy (<строка>, <номер первого символа>, <количество символов>) позволяет копировать или выделять фрагмент строки, например:

Writeln(Copy('Выводятся символы этой строки', 11,7));

Результат: вывод строки «символы».

Функция Pos (<искомая подстрока>, <строка>) позволяет произвести поиск определенного фрагмента в некоторой строке и определить номер символа, с которого начинается вхождение подстроки. Например:

Writeln(Pos('сл','Поиск слова');

Результат: вывод числа 7.

Процедура Insert (<вставляемая подстрока>, <строка>, <номер символа в строке>)вставляет в исходную строку, начиная с указанной позиции, другую строку. Например:

Insert('важного ','Поиск слова',7);

Результат – строка (второй аргумент) изменится на «Поиск важного слова».

Процедура Delete (<строка>, <номер первого удаляемого символа>, <количество символов>) удаляет в исходной строке фрагмент определенной длины:

Delete('Это – строка',4,2);

Результат – строка (первый аргумент) изменится на «Это строка». Удаляются 2 символа, так как пробел – тоже символ.

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

VAL ('135.67',x,cod)

Результат: значение переменных х=135.67 (1.3567´10²), cod=0.

Записи

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

При выборе элементов применяется конкретное имя, которое дается каждому элементу и не может вычисляться, в отличие от массивов.

Общий вид описания типа «запись»:

Type T = Record

<список полей>

end;

Например:

Type Complex = Record

Re: real;

Im: real;

End;

Здесь Re и Im – имена полей. При наличии этого фрагмента программы в дальнейшем можно вводить переменные комплексного типа, например:

Var X, Y, Z: Complex;

При обращении к компонентам указывается имя переменной – записи, и через сочленяющую точку – имя поля:

X.Re:=5.2; X.Im:=3.1;

Пример подпрограмм арифметики комплексных чисел:

{ Функция сложения двух комплексных чисел }

Function CADD(A,B:Complex):Complex;

Begin

CADD.Re:=A.Re+B.Re;

CADD.Im:=A.Im+B.Im;

End;

{ Функция умножения }

Function CMUL(A,B:Complex):Complex;

Begin

CMUL.Re:=A.Re*B.Re-A.Im*B.Im;

CMUL.Im:=A.Re*B.Im+A.Im*B.Re;

End;

{ Функция деления }

Function CDIV(A,B:Complex):Complex;

Var x:real;

Begin

x:=sqr(B.Re)+sqr(B.Im);

CDIV.Re:=(A.Re*B.Re+A.Im*B.Im)/x;

CDIV.Im:=(B.Re*A.Im-A.Re*B.Im)/x;

End;

Пример вычисления выражения XY+XZ+YZ:

CADD(CMUL(X,Y),CADD(CMUL(X,Z),CMUL(Y,Z)))

В языке Паскаль разрешается использовать тип Record при описании других структур данных и наоборот, например:

{ Формирование одной строки таблицы дней рождения из максимально 100 строк }

Type

Data = Record

D:1..31;

M:string[10];

G:word;

End;

Rec = Record

FIO:string;

Dr:Data;

End;

Var List: array [1..100] of rec;

Begin

Z[1].FIO:=’Иванов Иван Иванович';

Z[1].Dr.D:=5;

Z[1].Dr.M:=’Май’;

Z[1].Dr.G:=’1975’;

…

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

Type T=Record

<список полей>:<тип>;

…

[Case <признак варианта> of

<список констант выбора>:

(<список полей>:<тип>;

…);]

…

end;

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

With <список переменных записи> Do <оператор>;

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

Begin

…

Z[1].FIO:='Иванов Иван Иванович';

With Z[1].Dr do

Begin

D:=5;

M:=’Май’;

G:=’1975’;

End;

…

Оператор With R1,R2,…,Rn do S; эквивалентен записи

With R1 do

With R2 do

…

With Rn S;

Множества

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

{A, B, C}, {A, C, B}, {B, C, A}

и т.д., то есть элементы множества не упорядочены.

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

Описание типа:

Туре <тип_множество> = SET OF <базовый_тип>

Var <список_переменных>: SET OF <базовый_тип>

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

[Blue, Yellow, Red] или [1,4..8,12,15].

Существует единственное пустое множество, которое принадлежит всем типам множеств и обозначается как [ ].

Пусть есть описание:

Var A, B, C: Set of 0..9;

D, E: Set of '0'..'9';

F, G: Set of Boolean;

Тогда:

A:=[1, 3, 5];

D:=['3', '6'..'9'];

F:=[5, 7]; {неверная строка – «не то» множество}

При использовании диапазонов, если значение первой константы меньше значения второй константы диапазона, то задается пустое множество. Запись [5..3] эквивалентна [ ].

Операции над множествами – обычные из теории множеств и математической логики. Пусть S1 и S2 – однотипные множества, тогда над ними можно выполнять следующие операции.

1. Объединение множеств.

S1+S2 содержит элементы, которые принадлежат либо S1, либо S2, либо и тому и другому:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A+B;

что эквивалентно

C:=[1, 2, 3, 5, 9];

2. Пересечение множеств.

S1*S2 содержит элементы, которые принадлежат как S1, так и S2:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A*B;

что эквивалентно

C:=[1];

Или выражение

C:=A*[8];

соответствует пустому множеству:

C:=[ ];

3. Относительное дополнение или разность множеств.

S1-S2 содержит элементы из S1, которые не принадлежат S2:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A-B;

что эквивалентно

C:=[2, 3];

Или выражение

C:=A-[3..9];

соответствует:

C:=[1, 2 ];

4. Проверка на равенство, неравенство и включение множеств.

S1=S2 тогда и только тогда, когда S1 и S2 содержат одни и те же элементы. В противном случае истинно выражение S1<>S2. S1<=S2 принимает истинное значение, когда все элементы S1 являются элементами S2 (множество S2 включает в себя множество S1). Пусть

A:=[1..5];

B:=[1..5];

C:=[1..6];

Тогда логические выражения примут значения:

A=B — истинно;

А=С — ложно;

B<>C — истинно;

A<=C — истинно (С включает А).

5. Проверка принадлежности множеству (включение во множество).

Эта логическая операция обозначается служебным словом in. Выражение X in S1 истинно, если элемент Х принадлежит множеству S1 и ложно в противном случае:

2 in A — истинно;

9 in A — ложно.

Этот тип данных используется довольно редко, за исключением операции проверки принадлежности к множеству. Например, нажата ли клавиша «p» в любом регистре и алфавите:

If CH in ['p', 'P', 'з', 'З'] then ... {нажата клавиша «р»}