Массивы. Самым традиционным и широко известным из структурированных типов данных являетсямассив (иначе называемый регулярным типом) - однородная упорядоченная

Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная статическая структура прямого доступа.

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

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

Рис. 1.32. Одномерный массив - набор элементов (компонентов)

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

В некоторых системах программирования существуют специальные виды массивов. Например, массив литер (символов) определяется как строка.

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

Рассмотрим в качестве примера задачу сортировки набора некоторых данных, для которых имеют смысл отношения «больше» или «меньше». Представьте себе, что надо карточки в картотеке разместить в порядке возрастания записанных на них чисел. Используем для сортировки набора чисел (т.е. записи их в порядке возрастания) одномерный (линейный) массив. Дадим емуимя А, тогда a₁, a₂, a₃,..., а_n - компоненты массива.

Существует огромное число методов сортировки массивов. Рассмотрим один из самых простых (но не самых быстрых) - метод выбора.

В начале процесса имеем заполненный числами массив (неотсортированный). Процесс сортировки строится по индукции. Допустим, мы уже отсортировали часть массива и имеем упорядоченную последовательность

a₁ < a₂ < … < a_i-l

и оставшуюся неотсортированной последовательность

a_i, a_i+1,… a_N.

При каждом шаге, начиная с i = 1, из неотсортированной части последовательности извлекается наименьший элемент х = a_i, и меняется местами с i -м элементом. Затем этот процесс повторяется для i = 2, i = 3 и т.д., до тех пор пока не останется один, самый большой элемент.

Этот алгоритм потребует многократного нахождения наименьшего элемента массива. Этот «вспомогательный» алгоритм поиска наименьшего среди а_i,..., а_N может быть следующим:

1) фиксируется в качестве значения вспомогательной переменной т первый слева элемент массива: т = а_i (в конце процесса т будет иметь значение наименьшего элемента);

2) выполняется сравнение т с элементом массива a_j, (начиная с номера j = i + 1) и, если a_j < т, то т заменяется на а_j;

3) далее выполняется сравнение т с очередным элементом массива, т.е. j увеличивается на единицу и шаги 2, 3 выполняются снова, до тех пор пока у не достигнет максимального значения индекса элемента массива.

После выполнения этих предписаний переменная т будет соответствовать наименьшему элементу массива.

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

Рассмотрим пример обработки данных, хранящихся в двумерном массиве. Допустим, что на некоторой территории (например, страны) «квадратно-гнездовым» способом расставлены температурные датчики, и их показания обраны в одном центре (что вполне близко к реальной деятельности метеослужбы). Тогда в таблицу - двумерный массив - попадут значения температуры t_ij в сответствующих точках. Требуется, просматривая таблицу построчно, найти те точки (т.е. индексы узлов), между которыми температура принимает некоторое заданное значение Т.

Таблица 1.10 Графический образ двумерного массива

i j					…
	a11	a12	a13	a14	…
	a21	a22	a23	a24	…
	a31	a32	a33	a34	…
	a41	a42	a43	a44	…
…	…	…	…	...	…

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

Вспомогательный алгоритм (k):

1) положить j = 1;

2) если t_k,j < T < t_k.j+1, то см. п. 2;

3) увеличить j на 1,

4) если j < m, то вернуться к п. 2;

5) задача решена, ответ: (k,j), (k,j + 1);

6)конец.

Основной алгоритм:

1) положить k= 1;

2) выполнить вспомогательный алгоритм (K);

3) увеличить k на 1;

4) если k > n, то вернуться к п.2;

5)конец.