Массивы - Структуры данных

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

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

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

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

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

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

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

Рассмотрим в качестве примера задачу сортировки набора некоторых данных, для которых имеют смысл отношения "больше" или "меньше". Представьте себе, что надо карточки в картотеке разместить в порядке возрастания записанных на них чисел. Используем для сортировки набора чисел (т. е. записи их в порядке возрастания) одномерный (линейный) массив. Дадим ему имя А, тогда A1, a2, A3,..., АN - компоненты массива.

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

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

A1 < A2 < ... < AI-l

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

AI, aI+1,... aN.

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

Этот алгоритм потребует многократного нахождения наименьшего элемента массива. Этот "вспомогательный" алгоритм поиска наименьшего среди АI,..., аN может быть следующим:

    1) фиксируется в качестве значения вспомогательной переменной Т первый слева элемент массива: Т = аI (в конце процесса Т будет иметь значение наименьшего элемента); 2) выполняется сравнение Т с элементом массива AJ, (начиная с номера J = i + 1) и, если AJ < т, то Т заменяется на АJ; 3) далее выполняется сравнение Т с очередным элементом массива, т. е. J увеличивается на единицу и шаги 2, 3 выполняются снова, до тех пор, пока у не достигнет максимального значения индекса элемента массива.

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

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

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

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

I J

1

2

3

4

...

1

A11

A12

A13

A14

...

2

A21

A22

A23

A24

...

3

A31

A32

A33

A34

...

4

A41

A42

A43

A44

...

...

...

...

...

...

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

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

    1) положить J = 1; 2) если TK, j < t < TK. 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)конец.

Похожие статьи




Массивы - Структуры данных

Предыдущая | Следующая