Тема 2.5 Одномерные и многомерные массивы. Обработка массивов

 

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

 

Такую таблицу называют линейной. Она представляет собой последовательность упорядоченных чисел. Если требуется какая то математическая обработка этих данных, то для их обозначения обычно вводят индексную символику. Например, через 7 1, обозначается температура января (первого месяца), Т 5 — температура мая и т.д. В общем виде множество значений, содержащихся в таблице, обозначается так:

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

Теперь представьте, что нам требуется собрать информацию о среднемесячных температурах за 10 лет, например с 1981 по 1990 г. Очевидно, что для этого удобна прямоугольная таблица, в которой столбцы соответствуют годам, а строки — месяцам.

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

    Для значений, хранящихся в такой таблице, удобно использовать двухиндексные обозначения. Например, Н ₁₉₈₂ обозначает температуру в феврале 1981 г. и т.п. А вся совокупность данных, составляющих таблицу, обозначается так:

    Обработка подобных данных производится с использованием двухиндексных величин. Например, средняя температура марта за 10 лет вычисляется по формуле:

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

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

      Массив, хранящий линейную таблицу, называется одномерным, прямоугольную таблицу — двумерным. В программах могут использоваться массивы и большей размерности. 

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

     Чаще всего в качестве типа индекса употребляется интервальный тип. Например, рассмотренный выше одномерный массив среднемесячных температур опишется так:

      Описание массива определяет, во-первых, размещение массива в памяти, вовторых, правила его дальнейшего употребления в программе. Последовательные элементы массива располагаются в последовательных ячейках памяти (т [ 1 ], т [2 ] и т.д.), причем значения индекса не должны выходить из диапазона 1... 12. В качестве индекса может употребляться любое выражение соответствующе­ го типа. Например, T[i+j ], T[m div 2].

      Тип индекса может быть любым скалярным порядковым типом, кроме integer. Например, в программе могут присутство­ вать следующие описания:

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

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

      И если, например, элемент ciass_10[A] равен 35, то это означает, что в 10«А» классе 35 чел. Такое индексирование улучшает наглядность программы. 

    Часто структурированному типу присваивается имя в разделе типов, которое затем используется в разделе описания переменных.

    До сих пор речь шла об одномерных массивах, в которых типы элементов скалярные.

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

 Var H: Array[1981..1990] Of Array[1..12] Of Real; 

Вот примеры обозначения некоторых элементов этого массива: 

Н[1981][1]; Н[1985][10]; Н[1990][12] 

     Однако чаще употребляется другая, эквивалентная форма обозначения элементов двумерного массива: Н[1981,1]; Н[1985,Ю]; Н[1990,12] Переменная н [1981] обозначает всю первую строку таблицы, т.е. весь массив температур за 1981 г. 

     Другим вариантом, эквивалентным приведенному выше опи­ санию, является следующий:

Наиболее краткий вариант описания данного массива такой:

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

 Var A: Array[1..10,1..20,1..30] Of Integer; Это массив, состоящий из 10-20-30 = 6000 целых чисел и зани­ мающий в памяти 6000-2 = 12000 байт.

       В Паскале нет ограниче­ ния сверху на размерность массива. Однако в каждой конкретной реализации Паскаля ограничивается объем памяти, выделяемый под массивы. В Турбо Паскале это ограничение составляет 64 килобайта. По аналогии с математикой одномерные числовые массивы часто называют векторами, а двумерные — матрицами.

        В Паскале не допускается употребление динамических массивов, т. е. таких, размер которых определяется в процессе выполнения. Изменение размеров массива происходит через изменение в тексте программы и повторную компиляцию. Для упрощения та­ ких изменений удобно определять индексные параметры в разде­ ле констант: Const Imax=10; Jmax=20; Var Mas: Array[1..Imax,1..Jmax] Of Integer; Теперь для изменения размеров массива Mas и всех операторов программы, связанных с этими размерами, достаточно отредактировать только одну строку в программе — раздел констант. 

Действия над массивом как единым целым. Такие действия допу­ стимы лишь в двух случаях:

• присваивание значений одного массива другому; 

• операции отношения «равно», «не равно».

В обоих случаях массивы должны иметь одинаковые типы (тип индексов и тип элементов). Пример: Var P,Q: Array[l..5,1..10] Of Real;

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

1981 г. (девятой строке присвоить значение первой строки), то это можно делать так: Н[1989]:=Н[1981] А если нужно поменять местами значения этих строк, то это делается через третью переменную того же типа:

 Р:=Н[1989];Н[1989]:=Н[1981];Н[1981]:=Р; где р описана так: 

Var P: Array[1..12] Of Real;

    Обработка массивов в программах производится покомпонентно. Вот примеры ввода значений в массивы: 

For I:=l To 12 Do 

ReadLn(T[I]); 

For I:=l To IMax Do

 For J:=l To JMax Do 

ReadLn(Mas[I,J]); 

      Здесь каждое следующее значение будет вводиться с новой строки. Для построчного ввода используется оператор Read. Аналогично в цикле по индексной переменной организуется вывод значений массива. Например: For I:=l То 12 Do Write(T[I]:8:4); Следующий фрагмент программы организует построчный вы­ вод матрицы на экран:

 For I:=l To IMax Do 

Begin 

For J:=l To JMax Do 

Write(Mas[I,J]:6); 

WriteLn

End; 

       После печати очередной строки матрицы оператор WriteLn без параметров переведет курсор в начало новой строки. Следует заметить, что в последнем примере матрица на экране будет получена в естественной форме прямоугольной таблицы, если JMax не превышает 12 (сами подумайте почему). Рассмотрим несколько примеров типовых программ обработки массивов. 

       Пример 1. Вернемся к массиву среднемесячных температур Т [1.. 12]. Требуется вычислить среднегодовую температуру, а также ежемесячные отклонения от этой величины. 

Program Example;

Const N = 12; 

Type Vec=Array [1..N] Of Real;

 Var T,Dt: Vec; 

St: Real; I: Integer; 

Begin {Ввод исходных данных} 

WriteLn('Вводите таблицу температур'); 

For I:=l To N Do 

Begin 

Write (I: 2, ': '); 

ReadLn(T[I]) End; 

{Вычисление средней температуры} St:=0; For I:=l To N Do 

St:=St+T[I]; 

St:=St/N; 

{Вычисление таблицы отклонений от среднего} For I:=l To N Do 

Dt[I]:=T[I]-St; 

{Вывод результатов} 

WriteLn('Средняя температура равна',St:6:2); 

WriteLn; 

WriteLn('Отклонения от средней температуры:'); For I:=l To N Do 

WriteLn (1:1, ':',Dt[I]:б:2)

 End. 

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

     Пример 2. Выбор максимального элемента. Пусть из рассмотренного выше массива температур требуется отобрать самую высокую температуру и номер месяца, ей соответствующего. Идея алгоритма решения этой задачи: чтобы получить максимальную температуру в вещественной переменной тмах, сначала в нее заносится первое значение массива т [ 1 ]. Затем поочередно сравнивается значение тмах с остальными элементами массива температур, и каждое значение большее, чем тмах, присваивается этой переменной. Для получения номера самого теплого месяца в целой переменной NumMax в нее следует каждый раз засылать номер элемента массива температур одновременно с занесе­ нием в тмах его значения.

 ТМах:=Т[1]; 

NumMax:=1; 

For I:=2 To 12 Do If T[I]>Tmax Then 

Begin 

TMax:=T[I]; 

NumMax:=I 

End; 

        Заметим, что если в массиве температур несколько значений, равных максимальному, то в NumMax будет получен первый номер из этих элементов. Чтобы получить последнюю дату, нужно в операторе if заменить знак отношения > на >=.                           Пример 3. Сортировка массива. В одномерном массиве X из N элементов требуется произвести перестановку значений так, что­ бы они расположились по возрастанию, т.е. Х { < Х 2 <... <X N. 

        Существует целый класс алгоритмов сортировки. Ниже описан алгоритм, который называется «метод пузырька». 

         Идея: производится последовательное упорядочивание смежных пар элементов массива: Х х и Х ъ Х 2 и Х 3>..., X N _ X и X N. В итоге максимальное значение переместится в X N. Затем ту же процедуру повторяют до X N^ и т.д., вплоть до цепочки из двух элементов Х х и Х 2. Такой алгоритм будет иметь структуру двух вложенных циклов с внутренним циклом — переменной (сокращающейся) длины. 

For I:=l To N-l Do 

For K:=l To N-I Do 

If Х[К]>Х [K+l]

 Then 

Begin 

А:=Х[К]; 

Х[К]:=Х[К+1];

 Х[К+1]:=А 

End;

          Пример 4. Дан описанный выше двумерный массив среднемесячных температур за 10 лет. Определить, в каком году было самое теплое лето, т.е. в каком году была наибольшая средняя температура летних месяцев.

          Идея решения: в векторе.S получить средние температуры летних месяцев за 10 лет. Затем найти номер наибольшего элемента в этом векторе, это и будет искомый год. 

Program Example_2; 

Type Month=Array[l..12] Of Real; 

Year=Array[1981..1990] Of Month;

 Var H: Year;

 S: Array[1981..1990] Of Real; I,J,K: Integer; 

Begin {Ввод данных с клавиатуры) 

For I:=1981 To 1990 Do 

For J:=l To 12 Do Begin 

Write(J:2, •.',1:4, ': '); 

ReadLn(H[I,J]) 

End; {Вычисление вектора средних летних температур) 

For I:=1981 To 1990 Do 

Begin S[I]:=0; 

For J:=6 To 8 Do

 S[I]:=S[I]+H[I, J];

 S[I]:=S[I]/3 

End; {Определение года с самым теплым летом) 

К:=1981; 

For I:=1982 То 1990 Do 

If S[I]>S[K] Then K:=I; 

WriteLn('Самое теплое лето было в', К, '-м году') 

End.