Массивы. Типы массивов.

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

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

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

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

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

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

Практически все языки программирования высокого уровня требуют явного описания массивов.

Одномерный массив:

• var A: array[0..99] of integer;
• А − имя массива
• Array − служебное слово (в переводе с английского означает "массив", "набор");
• [0..99] − в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива; в этом примере первый элемент имеет номер 0, а последний − номер 99;
• Of − служебное слово (в переводе с английского означает "из");
• Integer − тип всех элементов массива.

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

• Array[n1..n2] Of <тип элементов>;
• где:
• n1 − номер первого элемента,
• n2 − номер последнего элемента, в качестве типа элементов может использоваться любой тип данных, кроме файлового.

Можно определить, какой объем оперативной памяти потребуется для хранения элементов массива. Для этого нужно общий размер массива умножить на объем памяти, занимаемой одной величиной базового для массива типа. В нашем примере это 100×2=200 байт.

Для того чтобы обратиться к элементу этого массива, необходимо указать имя массива и в квадратных скобках − номер элемента. Например, первый элемент массива А − А[0], а пятый − А[4].

Заполнить массив можно различными способами.

Задача 1. Заполнить одномерный массив с помощью датчика случайных чисел таким образом, чтобы все его элементы были различны.

Turbo Pascal

• Program create;
• Type Mas = array [0..99] of integer;
• Var A: Mas; i, j, N: byte; Log: Boolean;
• Begin
• Write ('Количество элементов массива?'); readLn(N);
• Randomize; A[l]:=-1000+random(2001);
• For i:=2 to N do
• Begin
• Log:=true;
• Repeat
• A[i]:=-1000+random(2001); j:=1;
• While Log and (j<=i—1) do
• Begin
• Log:= A[i]<>A[j];
• j:=j+1
• End
• Until Log
• End;
• For i:=1 to N do write(A[i]:7); writeln
• End.

Задача 2. Заполнить массив вводом с клавиатуры. Turbo Pascal

• Procedure Init1 (Var m: myarray);
• Var i: Integer;
• {Переменная для работы с элементами массива}
• Begin
• Writeln('Введите ',n, ' чисел');
• For i:=1 to n Do {Ввод элементов массива с клавиатуры}
• Readln(m[i]); {Чтение i-гo элемента}
• End; {Init1}

Задача 3. Третий способ заполнения массива − чтение значений элементов из файла. Можно заранее создать типизированный файл одномерных массивов (например, по тридцать элементов), а затем считывать из него сразу целый массив. Но мы воспользуемся текстовым файлом, так как его создавать намного удобнее. Пусть в файле записано несколько строк, а в каждой из них по 30 целых чисел. Тогда вся программа может быть такой:

• Program Array_of_file;
• Const n=30;
• {Количество элементов массива}
• Type myarray=Array [l..n] Of Integer;
• Var A: myarray; F: text;
• Procedure Init3 (Var m:myarray);
• {Процедура заполнения (инициализации) массива}
• Var i: Integer;
• Begin
• For i:=1 to n Do Read(f, m[i])
• {Чтение из файла очередного числа}
• End;
• Procedure Print (m:myarray);
• {Процедура вывода (распечатки) массива}
• Var i: Integer;
• Begin
• For i:=l to n Do {Вывод массива}
• Write (m[i]:3);
• {Вывод i-гo элемента}
• Writeln;
• End;
• Begin
• {Связываем файловую переменную с файлом на диске}
• Assign (F, '{имя файла и путь к нему}..');
• Reset (F);
• {Открываем файл для чтения}
• While Not EOf (F) Do
• Begin {Считываем очередную строку }
• Init3(А);
• {Обращение к процедуре заполнения массива}
• Print(A); {Обращение к процедуре вывода}
• Readln(F);
• End;
• Repeat Until KeyPressed;
• End.

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

• поиск значений по заданному признаку;
• сортировка элементов в порядке возрастания или убывания;
• изменения элементов массива по определенным правилам;
• комбинированные задачи.

Сумму элементов массива можно подсчитать по формуле S=S+A[i], первоначально задав S=0. Количество элементов массива, отвечающих заданному условию, можно подсчитать по формуле К=К+1 для всех А[i], удовлетворяющих условию, первоначально задав К=0. Произведение элементов массива можно подсчитать по формуле Р=Р×A[i], первоначально задав Р=1.

Рассмотрим еще две задачи обработки массивов.

Задача 4. Дан массив натуральных чисел. Найти сумму элементов, кратных заданному числу.

Идея решения. Будем суммировать элементы, удовлетворяющие данному условию, то есть только те, которые делятся нацело на заданное число (остаток от деления на данное число равен 0).

• Function Sum(m: myarray): Integer;
• Var i, s, k: Integer;
• Begin
• Writeln('Введите число');
• Readln(k);
• s:=0; {Начальное значение суммы}
• For i:=l To n Do {Нахождение суммы}
• If m[i] Mod k=0 Then s:=s+m[i];
• {Если элемент кратен k, то прибавляем его к сумме}
• Sum:=s;
• End;

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

Задача 5. Выполнить сортировку заданного линейного массива, используя алгоритм сортировки выбором.

Кратко опишем алгоритм сортировки выбором. Пусть некоторая часть массива отсортирована. В неотсортированном фрагменте массива выбираем минимальный элемент и меняем его местами с первым элементом неотсортированного фрагмента. Первоначально отсортированная часть массива состоит из нулевого количества элементов. В конечном итоге получаем отсортированный в порядке возрастания массив.

• Program Sort;
• Var a: array [0..100] of integer;
• i, j, min, n, vsp: integer;
• Begin
• Randomize;
• write('Количество элементов массива?');
• Readln(n);
• for i:=0 to n-1 do
• Begin
• a[i]:=-1000+random(2001);
• write(a[i]:5)
• End;
• Writeln;
• For i:=0 to n-2 do
• Begin
• Min:=i;
• For j:=i+1 to n-1 do
• If a[j]
• vsp:=a[i];
• a[i]:=a[min];
• a[min]:=vsp
• End;
• For i:=0 to n-1 do write(a[i]:5);
• Writeln
• End.

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

При описании массива задается требуемый объем памяти под двухмерный массив, указываются имя массива и в квадратных скобках диапазоны изменения индексов.

• Var A: array[0..99, 0..99] of integer;

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

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

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

Задача 6. Дана целочисленная квадратная матрица. Найти в каждой строке наибольший элемент и поменять его местами с элементом главной диагонали.

• Program Obmen;
• Type Matrica=array[0..30, 0..30] of integer;
• Var n, i, j, ind, vsp: integer;
• a: Matrica;
• Begin
• Write('Введите порядок матрицы:');
• Readln(n); randomize;
• For i:=0 to n-1 do
• Begin
• For j:=0 to n-1 do
• Begin
• a[i, j]:=-100+random(201);
• Write(a[i, j]:5)
• End;
• Writeln
• End;
• For i:=0 to n-1 do
• Begin
• ind:=0;
• For j:=1 to n-1 do
• If a[i, j]>a[i, ind] then ind:=j;
• vsp:=a[i, i]; a[i, i]:=a[i, ind]; a[i, ind]:=vsp;
• End;
• Writeln;
• For i:=0 to n-1 do
• Begin
• For j:=0 to n-1 do write(a[i, j]): 5);
• Writeln;
• End;
• End.