Методы сортировки и поиска

Массивы


Как и в ряде предыдущих разделов, понятия массива и типа массива сильно различаются в сильно и слабо типизированных языках. Начнем с классического понятия в сильно типизированных языках (например, в языке Паскаль). Тип массива в таких языках определяется на основе двух вспомогательных типов: типа элементов массива (базового типа) и типа индекса массива. В языке Паскаль определение типа массива выглядит следующим образом: type T = array [I] of T0, где T0 - базовый тип, а I - тип индекса. T0 может быть любым встроенным или ранее определенным типом. Тип индекса I должен состоять из конечного числа перечисляемых значений, т.е. быть уточненным, перечисляемым, символьным или булевским типом. В языках линии Паскаль допускается и неявное определение уточненного типа массива. Например, допустимы следующие определения типа массива: type T = array [1..6] of integer или type T = array ['a'..'e'] of real.

Если мощность множества значений типа индекса есть n, то значение типа массива - это регулярная структура, включающая n элементов базового типа. Соответствующим образом устроены и переменные типа массива. Для любого сконструированного типа массива предопределены две операции - операция конструирования значения типа массива и операция выборки элемента массива. Если x - переменная типа массива T, а i - значение соответствующего типа индекса, то для конструирования значения используется языковое средство x:= T (c1, c2, ..., cn), где c1, c2, ..., cn - значения базового типа. Для выборки элемента массива используется конструкция x[i], значением которой является значение i-того элемента массива (вместо i в квадратных скобках может содержаться любое допустимое выражение, значение которого принадлежит множеству значений типа индекса). Эта же конструкция может использоваться в левой части оператора присваивания, т.е. элементы массива могут изменяться индивидуально. Кроме того, при подобной строгой типизации массивов допустимы присваивания значений переменных типа массива, функции, возвращающие значение типа массива и т.п.

Базовым типом типа массива может быть любой встроенный или определенный тип, в том числе и тип массива.
В последнем случае говорят о многомерных массивах или матрицах. Для работы с многомерными массивами в языках используют сокращенную запись. Например, вместо определения type T = array [1..10] of array [1..5] of real можно написать type T = array [1..10],[1..5] of real, а если x - переменная такого типа T, то для выборки скалярного элемента вместо x[i][j] можно написать x[i,j]. В сильно типизированных языках для любого значения типа массива известно число элементов базового типа. Поэтому в принципе всегда возможен контроль значения индекса, хотя на практике такой контроль обычно отменяется при использовании программы в производственном режиме. Для иллюстрации приемов работы с массивами в слабо типизированных языках используем язык Си. В этом языке нет средств определения типов массива, хотя имеется возможность определения "массивных переменных". Число элементов в массивной переменной определяется либо явно, либо с помощью задания списка инициализирующих значений базового типа. Например, массивную переменную с четырьмя элементами целого типа можно определить как int x[4] (неинициализированный вариант) или как int x[] = { 0, 2, 8, 22} (инициализированная массивная переменная). Доступ к элементам массивной переменной производится с помощью конструкции выбора, по виду аналогичной соответствующей конструкции в сильно типизированных языках x[i], где i - выражение, принимающее целое значение (мы специально отметили внешний характер аналогии, поскольку в отличие от языка Паскаль в языке Си зафиксирована интерпретация операции выбора на основе более примитивных операций адресной арифметики). Однако, по причинам, которые мы обсудим в разделе, посвященном указателям, в реализациях языка Си в принципе невозможен контроль выхода значения индекса за пределы массива. Кроме того, по аналогичным причинам невозможно присваивание значений массивных переменных и не допускаются функции, вырабатывающие "массивные значения".

Содержание раздела