§ 1.4. Обработка одномерных массивов целых чисел на языке Паскаль

Пока данных немного, каждой величине в программе достаётся собственное имя: a, b, s, max. Но представьте, что нужно обработать отметки всего класса за четверть, показания уличного термометра за месяц или результаты всех участников школьной олимпиады. Придумывать отдельную переменную для каждого из сотен однотипных чисел бессмысленно: такую программу невозможно ни написать, ни прочитать. Выход в том, чтобы собрать однотипные данные в одну упорядоченную конструкцию — структуру данных. Самая простая и самая употребительная из них — массив.

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

Похожую запись вы видели в математике: члены последовательности обозначают одной буквой с номером — b₁, b₂, b₃ и так далее. Буква у всех общая, а конкретный член выделяет номер. В Паскале номер пишут не внизу, а в квадратных скобках после имени: T[1], T[2], T[3]. Имя массиву выбирают по тем же правилам, что и имя обычной переменной.

Посмотрите на рис. 1. На нём изображён массив T из семи элементов. Его удобно представлять как ряд пронумерованных ячеек: номер ячейки — это индекс элемента, число внутри — значение элемента. Запись T[3] читается «тэ третье» или «элемент массива T с индексом 3»; на рисунке T[3] = 8. Эти два понятия нельзя путать: индекс говорит, где лежит число, а значение — какое число там лежит. У элемента T[4] индекс равен 4, а значение равно 0; у элемента T[2] индекс 2, а значение −3.

Индекс не обязательно записывать числом. В квадратных скобках может стоять переменная целого типа или целое арифметическое выражение: если k = 2, то T[k] — это T[2], а T[2*k+1] — это T[5], то есть 11. Индексом может оказаться даже значение другого элемента того же массива, лишь бы оно попадало в диапазон допустимых номеров. В массиве на рис. 1 T[7] = 6, поэтому запись T[T[7]] означает T[6], а это 2. Вычисляют такую запись изнутри наружу: сначала внутренние скобки, потом внешние.

Размерность массива — количество индексов, которое нужно указать, чтобы однозначно добраться до элемента. Массиву-ряду хватает одного индекса, такой массив называют одномерным. Таблице из строк и столбцов понадобятся два индекса — номер строки и номер столбца, это двумерный массив; бывают массивы и большей размерности. В этом параграфе речь идёт только об одномерных массивах целых чисел.

Длина массива — количество его элементов; у массива на рис. 1 длина равна семи. Длину принято хранить отдельно — в константе или переменной, например n = 7. Тогда при переходе к массиву другого размера правят одно число, а не каждый цикл программы, и программа не ошибётся, если какой-то цикл забыли исправить.

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

Описание массива

Прежде чем пользоваться массивом, программа обязана его описать: сообщить имя массива, сколько в нём элементов и какого они типа. Зная это, компьютер отводит под массив участок памяти нужного размера. Описание одномерного массива в общем виде:

var <имя массива>: array [<первый индекс>..<последний индекс>] of <тип элементов>;

Служебное слово array переводится как «массив», of — как предлог «из». Между первым и последним индексом ставят две точки подряд. Например, для дневных температур за неделю подойдёт такое описание:

var T: array [1..7] of integer;

Здесь T — имя массива, 1 — начальное значение индекса, 7 — конечное, integer — тип каждого элемента. Выполнив это описание, компьютер выделит в памяти место под семь целых чисел, расположенных подряд. Тип у всех элементов одного массива одинаковый: массив, в котором часть чисел целая, а часть вещественная, описать нельзя.

Если значения элементов известны заранее, массив можно описать сразу вместе с ними — в разделе констант:

const P: array [1..6] of integer = (2, 3, 5, 7, 11, 13);

Такое описание не только отводит шесть ячеек памяти, но и сразу записывает в них перечисленные в скобках числа по порядку: P[1] = 2, P[2] = 3, …, P[6] = 13.

Заполнение массива

Описанный массив нужно заполнить значениями. Способов несколько.

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

for k := 1 to 7 do read(T[k]);

На первом проходе цикла прочитанное число попадёт в T[1], на втором — в T[2], и так до T[7].

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

for k := 1 to 6 do D[k] := 3 * k + 1;

После этого цикла D[1] = 4, D[2] = 7, D[3] = 10, …, D[6] = 19: каждый следующий элемент на три больше предыдущего. А цикл, в котором элементу присваивается его собственный номер, даёт массив 1, 2, 3, …, n.

Третий способ — случайные числа. Функция random(m) выдаёт случайное целое число от 0 до m − 1. Поэтому цикл

for k := 1 to 15 do R[k] := random(100);

заполнит пятнадцать элементов числами от 0 до 99, а запись random(21) - 10 даст число от −10 до 10. Случайное заполнение удобно, когда программу нужно испытать на большом массиве, а набирать сотни чисел вручную не хочется.

Вывод массива

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

for k := 1 to 15 do write(R[k], ' ');

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

for k := 1 to 15 do writeln('R[', k, '] = ', R[k]);

Такой цикл напечатает строки вида R[1] = 47, R[2] = 3 и так далее. Соберём всё вместе в программу, которая заполняет массив из пятнадцати элементов случайными числами от 0 до 99 и выводит его на экран:

var k: integer; R: array [1..15] of integer; begin for k := 1 to 15 do // заполнение массива R[k] := random(100); for k := 1 to 15 do // вывод массива writeln('R[', k, '] = ', R[k]) end.

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