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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

В ряде языков программирования, например, Лисп, JavaScript, PHP, Ruby применяются также ассоциативные массивы (или хэш-массивы), в которых элементы не обязательно являются однотипными, а доступ к ним не обязательно осуществляется по индексу.

Общее описание[править | править исходный текст]

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

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

Пример фиксированного массива на языке Паскаль
    {Одномерный массив целых чисел.
     Нумерация элементов от 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;            // Возвращаем память, используемую для столбцов матрицы.

Гетерогенные массивы[править | править исходный текст]

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

Реализация[править | править исходный текст]

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

  1. Под массив выделяется непрерывный блок памяти объёмом S*m1*m2*m3…mn, где S — размер одного элемента, а m1…mn — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
  2. При обращении к элементу массива A[i1, i2, i3, …, in] адрес соответствующего элемента вычисляется как B+S*((…(i1p*m1+i2p)*m2+…+i(n-1)p)*mn-1+inp), где B — база (адрес начала блока памяти массива), ikp — значение k-го индекса, приведённое к целому с нулевым начальным смещением.

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

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

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

Достоинства[править | править исходный текст]

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

Недостатки[править | править исходный текст]

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

См. также[править | править исходный текст]

Литература[править | править исходный текст]

  • Вирт Н. Алгоритмы и структуры данных = 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 с.

Ссылки[править | править исходный текст]

Примечания[править | править исходный текст]