Массив (программирование)

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

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

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

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

Общее описание

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

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

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

    {Одномерный массив целых чисел.
     Нумерация элементов от 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

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

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

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

  type
    TArrayType = array [0..9] of Integer; (* Объявления типа "массив" *)
  var
    arr1, arr2, arr3: TArrayType; (* Объявление трёх переменных-массивов одного типа *)

Специфические типы массивов

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

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

Пример динамического массива на Delphi

  byteArray  : Array of Byte;           // Одномерный массив
  multiArray : Array of Array of string;  // Многомерный массив

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

  float *array1; // Одномерный массив 
  int **array2;  // Двумерный массив
  array1 = (float*) malloc(10 * sizeof(float)); // выделение 10 блоков по sizeof(float) байт каждый 
  array2 = (int**) malloc(16 * sizeof(int*));   // выделение 16 блоков по sizeof(int*) байт каждый. Сюда будут записаны указатели на одномерные массивы-строки
  for(i = 0; i < 16; ++i)
       array2[i] = (int*) malloc(8 * sizeof(int)); // выделение 8 блоков по sizeof(int) байт каждый. Это одномерные массивы - строки матрицы.
  // Обращение к массиву
  array1[i] = 5.0;      // Записи эквивалентны. Первая с использованием индекса,
  *(array1+i) = 5.0;    // вторая с операцией разыменования.
  array2[i][j] = 6;     // Записи эквивалентны. Первая с использованием индекса,
  *(*(array2+i)+j) = 6; // вторая с операцией разыменования.
  free(array1);  // Важно не забывать возвращать выделенную память системе.
  for(i = 0; i < 16; ++i)
      free(array2[i]);  // Возвращаем память, используемую для строк матрицы.
  free(array2);         // Возвращаем память, используемую для столбцов матрицы.

Пример динамического массива на С++

  float *array1; // Одномерный массив 
  int **array2;  // Многомерный массив
  array1 = new float[10];    // выделение 10 блоков размером типа float
  array2 = new int*[16];     // выделение 16 блоков размером типа указателя на int
  for(int i = 0; i < 16; ++i)
       array2[i] = new int[8];
 
  // Работаем с массивами.
 
  delete []array1;            // Важно не забывать возвращать выделенную память системе.
  for(int i = 0; i < 16; ++i)
       delete []array2[i];    // Возвращаем память, используемую для строк матрицы.
  delete []array2;            // Возвращаем память, используемую для столбцов матрицы.

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

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

Реализация

Одним из способов реализации статических массивов с одним типом элементов является следующий (в Фортране порядок индексов противоположен таковому в Си):

1. Под массив выделяется непрерывный блок памяти объёмом S*m₁*m₂*m₃…m_n, где S — размер одного элемента, а m₁…m_n — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
2. При обращении к элементу массива A[i₁, i₂, i₃, …, i_n] адрес соответствующего элемента вычисляется как B+S*((…(i_1p*m₁+i_2p)*m₂+…+i_(n-1)p)*m_n-1+i_np), где B — база (адрес начала блока памяти массива), i_kp — значение k-го индекса, приведённое к целому с нулевым начальным смещением.

Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково.

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

Более сложные типы массивов — динамические и гетерогенные — реализуются сложнее.

Достоинства

• лёгкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
• одинаковое время доступа ко всем элементам
• малый размер элементов: они состоят только из информационного поля

Недостатки

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

См. также

• Ассоциативный массив
• Дерево отрезков
• V-список
• Параллельный массив
• Динамический массив
• Разрежённый массив

Литература

• Вирт Н. Алгоритмы и структуры данных = Algoritms and data structure. — М.: Мир, 1989. — 360 с. — ISBN 5-03-001045-9.
• Хювёнен Э., Сеппянен Й. Мир Лиспа. Введение в язык ЛИСП и функциональное программирование. В 2-х т. = Lisp-maailma: Johdatus kieleen ja ohjelmointiin / Пер. с финск. — М.: Мир, 1990. — ISBN 5-03-001935-9.
• Магариу Н. А. Язык программирования АПЛ. — М.: «Радио и связь», 1983. — 96 с.
• Бартеньев О. В. Современный Фортран. — 3-е изд., доп. и перераб.. — М.: ДИАЛОГ-МИФИ, 2000. — 449 с.

Ссылки

• Массивы в C++