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

Структурированные типы данных основываются на простых типах и могут содержать их сочетание. В языке Паскаль предусмотрены следующие типовые структуры: массив (array), запись (record), множество (set), файл (file). При выполнении программы с данными этих типов меняются только значения данных, а структура остается постоянной. Поэтому эти структуры называются статическими. На Паскале можно создавать и так называемые динамические структуры, которые в программе только объявляются, но создаются и уничтожаются в процессе работы программы. К динамическим структурам относятся очереди, деревья, стеки, списки.

8.1. Массивы

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

Объявить массив в программе можно двумя способами:

1) через объявление типа массива:

Type имя_типа_массива=array[список типов индексов] of тип_элемента_массива;

Var имя_массива: имя_типа_массива;

2) сразу в разделе переменных:

Var имя_массива: array[список типов индексов] of тип_элемента_массива;

Список типов индексов – это один или несколько типов индексов, разделенных запятыми. Типом индекса может быть любой порядковый тип, кроме типа Longint. Обычно в качестве типа индекса используется тип-диапазон, в котором задаются значения индекса: 1..15, ‘b’..’f’.

Ниже приведены примеры, в которых массивы m1, m2, m3 объявлены через объявление типов, массивы ms1, ms2, msb, A, B, C объявлены непосредственно в разделе объявления переменных. Типами индексов массивов m1, m2, m3, ms1, ms2, A, B, C являются ограниченные типы (или типы-диапазоны) как подмножества типа integer, а в качестве типа индексов массива msb принято подмножество русского алфавита ‘б’.. ‘ф’, то есть количество элементов массива msb равно количеству букв диапазона от ‘б’ до ‘ф’.

Type T1=array[1..10] of real;{Т1-имя типа одномерного массива, содержащего 10 целых чисел типа real}

Т2=array[1..4,1..7] of real; {Т2-имя типа двумерного массива (или матрицы), содержащего 4 строки, в каждой из которых по 7 элементов – вещественных чисел типа real}

TT=array[1..5] of T1; {TT – имя типа массива, содержащего 5 элемнтов, а каждый элемент представляет собой массив типа Т1. Таким образом, ТТ – имя типа двумерного массива. Такой способ объявления массива удобен, когда необходимо объявить не только двумерный массив типа ТТ, но и одномерный массив типа Т1}

Var m1: T1; {m1 – имя одномерного массива типа Т1}

m2: T2; {m2 – имя двумерного массива типа Т2. Возможно объявление этого же массива и без объявления типа Т2 следующим образом: m2:array[1..4,1..7] of real;}

m3: TT; {m3 – имя двумерного массива типа ТТ}

ms1,ms2: array[1..12] of char; {ms1 и ms2 – имена одномерных массивов, элементами которых являются символы}

msb: array[‘б’..’ф’] of byte; {msb – имя одномерного массива, элементами которого являются коды типа byte}

A,B,C:array [1..5] of real; {A,B,C – имена одномерных массивов, содержащих по 5 вещественных чисел}

Обработка массива возможна только поэлементно. Для обращения к элементу следует указать имя массива и в квадратных скобках индекс элемента. Примеры обращения к элементам массивов, объявленных выше:

m1[3]:=25; m2[4,2]:=9.15; C[i]:=A[i] +B[i];{значеие i должно быть известно к моменту выполнения этого оператора}

ms1[6]:=‘Б’;ms2[6]:=pred(ms1[6]);{шестой элемент массива ms2 принимает значение буквы А русского алфавита}

m3[5][4]:=1024;{!!! При обращении к элементам массива ms3 значение каждого индекса должно заключаться в свои квадратные скобки, так как отдельно объявлены типы ТТ и Т1; сравни обращение к элементам массива m2}

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

Каждый элемент массива занимает участок памяти, размер которого определяется типом элемента (см.главу 6): элемент типа char занимает 1 байт, элемент типа integer – 2 байта, элемент типа real – 4 байта и т.д. Элементы вектора А, то есть одномерного массива А[1..n], располагаются в последовательных участках памяти. Элементы матрицы А2[1..m,1..k] располагаются строка за строкой, то есть сначала элементы первой строки

А2[1,1], А2[1,2],…, А2[1,k], затем элементы второй строки

А2[2,1], А2[2,2],…, А2[2,k] и т.д. до последней строки

А2[m,1], А2[m,2],…, А2[m,k].

Элементы многомерного массива располагаются в памяти ЭВМ, начиная с элементов, определяемых последним индексом в списке индексов массива, затем предыдущим индексом и т.д. Например, элементы трехмерного массива А3[1..5,1..3,1..10] располагаются, начиная с элементов

А3[1,1,1], A3[1,1,2],…, A3[1,1,10], затем элементы

A3[1,2,1], A3[1,2,2],…, A3[1,2,10], и т. д. и, наконец, элементы А3[5,3,1],A3[5,3,2],…, A3[5,3,10].

Расположение элементов массивов в памяти ЭВМ полезно знать при организации циклической обработки массивов. Так, при обработке матрицы B2[1..5,1..7] следует иметь в виду, что первый индекс определяет номер строки, второй – номер столбца. Поэтому, например, для расчета среднего значения третьей строки SB2[3] надо подсчитать сумму элементов этой строки и полученную сумму разделить на число элементов в строке. Начальное значение суммы надо предварительно установить в 0:

SB2[3]:=0;

For j:=1 to 7 do SB2[3]:= SB2[3] + B2[3,j];

SB2[3]:=SB2[3] / 7;

Примечание. Здесь при подсчете суммы элементов строки как промежуточной операции используем для обозначения суммы то же имя (идентификатор) SB2[3], что и для среднего значения, так как в задаче не требуется сохранять значение суммы. Такой прием часто применяется в программировании – для экономии памяти ЭВМ.

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

For i:=1 to 5 do SB2[i]:=0;

For i:=1 to 5 do

Begin

For j:=1 to 7 do SB2[i]:= SB2[i] + B2[i,j];

SB2[i]:=SB2[i] / 7;

End;

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

Пример 4. Известны значения температур за март месяц. Найти среднемесячную температуру за март, и определить самый теплый день марта.

Program t_mart;

Const n=31;

Var i,d_max: byte;

S_t,max:real;

Mt: array[1..n] of real;{!!!При объявлении массива значение n должно быть известно и здесь задано в виде константы}

Begin writeln(‘Ввод значений температуры по дням:’);

For i:=1 to n do

Begin

Write(i, ‘ марта температура Т = ’); read(Mt);

End;

S_t:=0;

{Вычисление средней температуры: сумма всех температур/n}

for i:=1 to n do s_t:=s_t + mt[i];

s_t:=s_t/n;

{Поиск дня марта с максимальной температурой:}

{Пусть максимальная температура была 1 марта, т.е.}

d_max:=1; max:= mt[1];

{Если в i-тый день температура была выше, то значение max

меняем на mt[i]:}

for i:=1 to n do

if max<mt[i] then {замена:}

begin max:=mt[i]; d_max:=i;

end;

{Печать результатов работы программы:}

writeln(‘Средняя температура марта Тсредн = ’, s_t:8:1);

write(‘Самый теплый день – ‘, d_max,’ марта.’);

writeln(‘ В этот день температура была ’, max:5:1);

writeln(‘Выти из программы - Enter’);readln

End.

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

{Для удобства вычисления средних значений последовательность температур представим в виде двумерного массива (матрицы) Т_apr, содержащего три строки по 10 элементов. Средние значения температур за декады представим в виде одномерного массива T_dek:}

Program t_dekada;

Var i,j,n_max:integer;{n_max – номер декады с максимальной

средней температурой}

Max:real;

T_apr:array[1..3,1..10] of real;

T_dek:array[1..3] of real;

{Начало операторной части программы:}

Begin writeln(‘Ввод значений температуры по дням:’);

For i:=1 to 3 do{цикл по строкам матрицы}

Begin writeln(i,‘-я декада:’);

For j:=1 to 10 do {цикл по столбцам матрицы}

Begin

Write(10*(i-1)+j,‘ апреля, температура Т = ’);

{по формуле 10*(i-1)+j определяется день месяца}

Read(t_apr[i,j]);

End;

End;

{Установка в состояние 0 элементов массива t_dek:}

For i:=1 to 3 do t_dek[i]:=0;

{Вычисление средних температур каждой i-той декаде: }

For i:=1 to 3 do

Begin {суммирование температур за декаду в цикле по j: }

for j:=1 to 10 do t_dek[i]:=t_dek[i] + t_apr[i,j];

t_dek[i]:=t_dek/10;{расчет средней температуры}

End;

{Поиск декады с максимальной средней температурой. Допустим, что максимальная средняя температура была в первую декаду, то есть индекс массива средних температур принимаем равным 1:}

n_max:=1; max:= t_dek[n_max];

{Если в i-тую декаду температура была выше, то значение max меняем на t_dek[i] и n_max на i:}

For i:=1 to 3 do

if max<t_dek[i] then {замена:}

begin max:=t_dek[i]; n_max:=i

end;

{Печать результатов работы программы:}

writeln(‘Средние температуры по декадам апреля: ’);

writeln( t_dek[1]:5:1, t_dek[2]:5:1, t_dek[3]:5:1);

write(‘Наиболее теплые в среднем были дни с ‘,10*(n_max -1)+1);

writeln(‘ по ‘,10*(n_max -1)+10) ,’ апреля.’);

writeln(‘ В эту декаду средняя температура была ’,

t_dek[n_max]:5:1);

writeln(‘Выти из программы - Enter’);readln

End.{Конец программы}