Алгоритмы обработки одномерных числовых массивов

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

Доступ к любому элементу массива осуществляется по его номеру (индексу). Поэтому для обращения к элементу массива используют имя массива (номер элемента), например, А(5).

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

Рассмотрим простой алгоритм ввода элементов одномерного числового массива A из 9 элементов. В этом циклическом алгоритме условие выхода из цикла определяется значением специальной переменной К, которая называется счетчиком элементов массива А (рис. 16). Эта же переменная К определяет количество итераций циклического алгоритма ввода элементов массива. На каждом шаге итерации переменная К (значение номера элемента массива А) изменяется на 1, то есть происходит переход к новому элементу массива. В дальнейшем, при рассмотрении алгоритмов обработки одномерных массивов в целях устранения дублирования алгоритм ввода элементов массива будем

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

циклического алгоритма, представленного на рис. 16.

Пример 9. Составить алгоритм определения в одномерном числовом массиве А

из N элементов суммы положительных элементов.

Решение. Алгоритм представлен на рисунке 17. В этом алгоритме переменная К

является счетчиком элементов массива, S – сумма элементов массива, она вычис-ляется по рекуррентной формуле S=S+A(K). Ввод количества и значений элемен-тов массива осуществляется сначала в отдельном блоке ввода, который реализу-ется по схеме алгоритма ввода элементов массива, изображенного на рис. 16.

Часто для проверки правильности работы алгоритмов на конкретных наборах

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

Пример 10. Составить алгоритм поиска элемента с максимальным значением в

одномерном массиве А(1..n) и его таблицу трассировки для значений (3, 7, 0, 9).

Решение. Введем обозначения: K – текущий номер элемента, A[K] – текущее

значение элемента массива, N=4 – количество элементов одномерного массива,

M – номер максимального элемента массива, A[M] – значение максимального элемента массива. Основной идеей алгоритма является выполнение сравнения текущего элемента массива A[K] и элемента с максимальным значением A[М], определенным на предыдущем шаге итерации. По алгоритму, изображенному на рис. 18, получено максимальное значение для массива (3, 7, 0, 9), процесс и правильный результат поиска которого показаны в табл. 3.