Массив (тип данных)

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

Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива. По количеству используемых индексов массивы делятся на одномерные, двумерные, трёхмерные и т. д.

Форма или структура массива — сведения о количестве размерностей и размере (протяжённости) массива по каждой из размерностей; может быть представлена одномерным массивом.

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

В простейшем случае массив имеет константную длину по всем размерностям и может хранить данные только одного, заданного при описании, типа. Ряд языков поддерживает также динамические массивы, длина которых может изменяться во время выполнения программы, и гетерогенные массивы, которые могут в разных элементах хранить данные различных типов. Некоторые специфичные типы массивов, используемые в различных языках и реализациях — ассоциативный массив, дерево отрезков, V-список, параллельный массив, разреженный массив.

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

Варианты реализации

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

Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и так далее. Одномерный массив — нестрого соответствует вектору в математике; двумерный («строка», «столбец») — матрице. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко.

Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчётом от нуля (zero-based), с отсчётом от единицы (one-based) и с отсчётом от специфического значения заданного программистом (n-based). Отсчёт от нуля более характерен для низкоуровневых языков программирования, хотя встречается и в языках высокого уровня, например, используется почти во всех языках семейства Си. В ряде языков (Паскаль, Ада, Модула-2) диапазон индексов может определяться как произвольный диапазон значений любого типа данных, приводимого к целому, то есть целых чисел, символов, перечислений, даже логического типа (в последнем случае массив имеет два элемента, индексируемых значениями «Истина» и «Ложь»).

Пример фиксированного массива на языке Паскаль

    {Одномерный массив целых чисел.
     Нумерация элементов от 1 до 15} 
  a: array [1..15] of Integer;
    {Двумерный массив символов.
     Нумерация по столбцам по типу Byte (от 0 до 255)
     по строкам от 1 до 5}
  multiArray : array [Byte, 1..5] of Char; 
    {Одномерный массив из строк.
     Нумерация по типу word (от 0 до 65536)}
  rangeArray : array [Word] of String;

Пример фиксированного массива на Си

  int Array[10];         // Одномерный массив: целых чисел, размера 10;
                         // Нумерация элементов — от 0 до 9.
                         
  double Array[12][15];  // Двумерный массив: 
                         // вещественных чисел двойной точности, 
                         // размера 12 на 15;
                         // Нумерация: по строкам — от 0 до 11, 
                         // по столбцам — от 0 до 14.

В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами.

Пример двумерного массива на JavaScript

    //Создание двумерного массива чисел: 
    var array = [
        [11, 12, 13, 14, 15, 16], // Первая строка-массив
        [21, 22, 23, 24, 25, 26], // Вторая
        [31, 32, 33, 34, 35, 36]  // Третья
    ];
    
    // Вывод массива на консоль:
    array.forEach((subArray) => {   // Для каждого под-массива,
       subArray.forEach((item) => { // для каждого его элемента,
           console.log(item);       // — вывести этот элемент на консоль.
       });
    });

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

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

Объявление типа «массив» в языке Паскаль

  type
    TArrayType = array [0..9] of Integer; 
    (* Массивы, имеющие заданные параметры:
        1. Размер — 10 ячеек; 
        2. Тип элементов, пригодных для хранения — 
                — целые числа диапазона [−32 768; 32 767],
        — объявляются типом операндов, называющимся "TArrayType". *)

  var
    arr1, arr2, arr3: TArrayType; 
    (* Объявление трёх переменных-массивов одного типа 
        (вышеуказанного "TArrayType"). *)

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

Динамические массивы

Основная статья: Динамический массив

Динамическими называются массивы, размер которых может изменяться во время выполнения программы. Обычные (не динамические) массивы называют ещё фиксированными или статическими.

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

1. Описание динамического массива. На уровне языка это может быть специальная синтаксическая конструкция, на уровне библиотеки — библиотечный тип данных, значение которого объявляется стандартным образом. Как правило, при описании (создании) динамического массива указывается его начальный размер, хотя это и не обязательно.
2. Операция определения текущего размера динамического массива.
3. Операция изменения размера динамического массива.

Пример конструкций для работы с динамическими массивами на Delphi:

var  // Описания динамических массивов
  byteArray  : Array of Byte;           // Одномерный массив
  multiArray : Array of Array of string;  // Многомерный массив
...
  SetLength(byteArray, 1); // Установка размера массива в 1 элемент.
  byteArray[0] := 16;       // Запись элемента.
  SetLength(byteArray, Length(byteArray)+1); // Увеличение размера массива на единицу
  byteArray[Length(byteArray) - 1] := 10;    // Запись значения в последний элемент.
  WriteLn(byteArray[Length(byteArray) - 1]); // Вывод последнего элемента массива. 
...
  SetLength(multiArray, 20, 30); // Установка размера двумерного массива
  multiArray[10,15] := 12;       // Запись значения
  SetLength(multiArray, 10, 15); // Уменьшение размера 
  WriteLn(Length(multiArray), '  ', Length(multiArray[0])

Гетерогенные массивы

Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.

Работа с памятью

Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является выделение непрерывного блока памяти объёмом $S\cdot m_{1}\cdot m_{2}\cdot \dots m_{n}$, где $S$ — размер одного элемента, а $m_{1},\dots m_{n}$ — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс). При обращении к элементу массива с индексом $(i_{1},i_{2},\dots i_{n})$ адрес соответствующего элемента вычисляется как $B+S\cdot \left(\left(\dots \left(i_{\text{1p}}m_{1}+i_{\text{2p}}\right)\cdot m_{2}+\dots +i_{(n-1){\text{p}}}\right)\cdot m_{n-1}+i_{n{\text{p}}}\right)$, где $B$ — база (адрес начала блока памяти массива), $i_{k\mathrm {p} }$ — значение $k$-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. (Этот способ соответствует реализации в большинстве компиляторов языка Си; в Фортране порядок индексов противоположен).

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

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

Для динамических массивов может использоваться тот же механизм размещения, что и для статических, но с выделением некоторого объёма дополнительной памяти для расширения и добавлении механизмов изменения размера и перемещения содержимого массива в памяти.

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

Литература

• Вирт Н. Алгоритмы и структуры данных = Algoritms and data structure. — М.: Мир, 1989. — 360 с. — ISBN 5-03-001045-9.
• Магариу Н. А. Язык программирования АПЛ. — М.: «Радио и связь», 1983. — 96 с.
• Бартеньев О. В. Современный Фортран. — 3-е изд., доп. и перераб.. — М.: Диалог-МИФИ, 2000. — 449 с.