Тема № 9: «Структурированные типы данных»

9.1. Массивы

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

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

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

Объявление одномерного массива:

VAR

Имя_массива: ARRAY[1..k] OF <Тип_данных>;

Здесь переменная k задает количество элементов в массиве, при этом значение индекса элементов лежит в интервале от 1 до k и может принимать только целые значения.

Массивы могут иметь и более одного измерения. Размерность ("мерность") массива определяет количество индексов отдельного элемента.

Объявление двумерного массива (двумерной матрицы):

Имя_массива: ARRAY [1..k1,1..k2] OF Тип_данных;

Здесь k1 задает количество строк и диапазон изменения индекса строк, k2 - количество столбцов и диапазон изменения индекса столбцов.

Объявление трехмерного массива:

Имя_массива: ARRAY[1..k1,1..k2,1..k3] OF < Тип_данных>;

Здесь k1 задает количество строк и диапазон изменения индекса строк, k2 - количество столбцов и диапазон изменения индекса столбцов, k3 - количество слоев и диапазон изменения индекса слоев.

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

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

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

На примере двумерного массива А(5х6) рассмотрим ввод элементов массива и вывод их на экран в виде строк и столбцов.

Program Wwod_Wywod;

Var A : Array [1..5,1..6] of integer;

I,J : Integer;

Begin

For I:=1 to 5 do

For J:=1 to 6 do

read(A[I,J]); - считывание в цикле всех 30 элементов массива

For I:=1 to 5 do Begin

For J:=1 to 6 do Write (A[i,J]:4); - вывод в одну строку значений элементов массива вложенного цикла длиной в 4 символа.

Writeln; переход на новую строку.

End;

End.

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

Program Wwod;

Var A : Array [1..8,1..10] of Integer;

I, J : Integer;

Begin

For I:=1 to 8 do

For J:=1 to 10 do A[I,J] := Random(100);

……………

End.

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

Сортировка выбором:

Устанавливаем номер наименьшего элемента массива и меняем местами наименьший и первый элементы массива. Затем эту процедуру повторяем над оставшимися элементами массива, до тех пор, пока остаток не сократится до одного элемента.

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

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

Обменная сортировка:

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

Пример.

Отсортировать массив в порядке убывания (сортировка осуществляется при помощи двух вложенных циклов)

For j:=1 to N-1 do

Begin

NEW:=MAS[N];

K:=N;

For i:=N downto j do

If MAS[i]>NEW then

Begin

K:=i;

NEW:=MAS[i]

End;

MAS[K]:=MAS[j];

MAS[J]:=NEW;

End;