Основные алгоритмы обработки массивов

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

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

Именованный набор однотипных элементов, доступ к каждому из которых осуществляется по общему имени набора и номеру элемента в наборе, называется массивом. Количество элементов в таком наборе определяет размер массива.

Уникальный номер элемента массива называется индексом. Индексы элементов массива являются целыми числами, следующими друг за другом в порядке возрастания. При программной реализации алгоритма первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения, заданного программистом (n-based). В языке Fortran (по умолчанию) и языке системы Matlab индексация элементов массива начинается с единицы, как это принято в математике. Отсчет от нуля характерен для массивов в языках C/C++, Java, Python, Visual Basic, открытых массивов в языке Pascal. В языках Fortran и Pascal также широко используется произвольное задание начального индекса.

Очень важно не путать порядковый номер элемента в массиве с его индексом. Если в словесном описании алгоритма для указания конкретного элемента массива используется порядковое числительное (первый, второй, десятый, двадцать четвертый), то нужно понимать, что это именно порядковый номер элемента, а не индекс, и нужно делать поправку на точку отсчета. Например, если индексация начинается с нуля, то первый элемент будет иметь индекс 0, второй – 1, двадцать четвертый – 23. Если индексация начнется с -5, то первый элемент – это элемент с индексом -5, второй – с индексом -4, а двадцать четвертый – с индексом 18. И только если индексация начинается с единицы, индекс элемента и его порядковый номер будут совпадать.

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

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

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

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

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

Память под массив может выделяться разными способами. Если количество элементов в массиве известно, то создается переменная типа «массив из такого-то количества таких-то элементов». При этом число элементов предпочтительно задать именованной константой. Если в программе понадобится изменить размер массива, достаточно будет изменить только одно число – значение этой константы.

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

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