Массив (программирование)
Массив (в некоторых языках программирования также таблица, ряд, матрица) — структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом, что позволяет обращаться к элементам по числовому индексу. Массив можно рассматривать, как реализацию абстрактного типа данных список. Однако, за счёт индексирования вычислительная сложность для доступа к конкретному элементу (в отличие, например, от связного списка) константна[1], т.е. массив относится к структурам данных с произвольным доступом.
Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива[2][3]. Форма или структура массива — сведения о количестве размерностей и размере (протяжённость) массива для каждой из размерностей[4]; может быть представлена одномерным массивом[5].
В языке программирования APL массив является основным типом данных (при этом нуль-мерный массив называется скаляром, одномерный — вектором, двумерный — матрицей)[5].
Содержание
Общее описание[править | править код]
Массив — упорядоченный набор данных, используемый для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа.
Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и т. д. Одномерный массив — нестрого соответствует вектору в математике; двумерный («строка», «столбец»)— матрице. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко.
- Пример фиксированного массива на языке Паскаль
{Одномерный массив целых чисел.
Нумерация элементов от 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.
В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами[6].
- Пример двумерного массива на 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"). *)
Специфические типы массивов[править | править код]
Динамические массивы[править | править код]
Динамическими называются массивы, размер которых может изменяться во время выполнения программы. Обычные (не динамические) массивы называют ещё фиксированными или статическими.
Динамические массивы могут реализовываться как на уровне языка программирования, так и на уровне системных библиотек. Во втором случае динамический массив представляет собой объект стандартной библиотеки, и все операции с ним реализуются в рамках той же библиотеки. Так или иначе, поддержка динамических массивов предполагает наличие следующих возможностей:
- Описание динамического массива. На уровне языка это может быть специальная синтаксическая конструкция, на уровне библиотеки - библиотечный тип данных, значение которого объявляется стандартным образом. Как правило, при описании (создании) динамического массива указывается его начальный размер, хотя это и не обязательно.
- Операция определения текущего размера динамического массива.
- Операция изменения размера динамического массива.
Ниже приведён пример конструкций для работы с динамическими массивами на 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])
Гетерогенные массивы[править | править код]
Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.
Реализация[править | править код]
Одним из способов реализации статических массивов с одним типом элементов является следующий (в Фортране порядок индексов противоположен таковому в Си[4]):
- Под массив выделяется непрерывный блок памяти объёмом S*m1*m2*m3…mn, где S — размер одного элемента, а m1…mn — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
- При обращении к элементу массива 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 (с указателями) и при отсутствии дополнительных средств контроля — угроза выхода за границы массива и повреждения данных
См. также[править | править код]
- Ассоциативный массив
- Дерево отрезков
- V-список
- Параллельный массив
- Динамический массив
- Разрежённый массив
Примечания[править | править код]
- ↑ Вирт, 1989, 1.6 Массив.
- ↑ Дрот В. Л., Новиков Ф. А. «Толковый словарь современной компьютерной лексики», Размерность массива
- ↑ Хювёнен, Сеппянен, 1990, с. 349.
- ↑ 1 2 Бартеньев, 2000.
- ↑ 1 2 Магариу, 1983.
- ↑ Michael McMillan. Data Structures and Algorithms with JavaScript. — "O'Reilly Media, Inc.", 10 March 2014. — P. 30–32. — ISBN 978-1-4493-7396-2.
Литература[править | править код]
- Вирт Н. Алгоритмы и структуры данных = 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 с.