|
<br />
{{другие значения|Массив}}
'''Массив''' (в некоторых [[язык программирования|языках программирования]] также таблица, ряд, матрица) — [[структура данных]], хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив можно рассматривать как реализацию [[абстрактный тип данных|абстрактного типа данных]] вектор.
*
Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива<ref>[http://comp.vslovar.org.ru/828.html Дрот В. Л., Новиков Ф. А. «Толковый словарь современной компьютерной лексики», Размерность массива]</ref>{{sfn|Хювёнен, Сеппянен|1990|с = 349}}. По количеству используемых индексов массивы делятся на одномерные, двумерные, трёхмерные и т. д.
Форма или структура массива — сведения о количестве размерностей и размере (протяжённости) массива по каждой из размерностей{{sfn|Бартеньев|2000|cc = 108-109}}; может быть представлена одномерным массивом{{sfn|Магариу|1983|cc = 18-19}}.
Особенностью массива как структуры данных (в отличие, например, от [[Связный список|связного списка]]) является константная [[вычислительная сложность]] доступа к элементу массива по индексу {{sfn|Вирт|1989|loc = 1.6 Массив}}. Массив относится к структурам данных с [[Произвольный доступ|произвольным доступом]].
В простейшем случае массив имеет константную длину по всем размерностям и может хранить данные только одного, заданного при описании, типа. Ряд языков поддерживает также '''динамические массивы''', длина которых может изменяться по ходу работы программы, и '''гетерогенные массивы''', которые могут в разных элементах хранить данные различных типов.
== Общее описание ==
Массив — упорядоченный набор элементов, каждый из которых хранит одно значение, идентифицируемое с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа, а в качестве индексов выступают целые числа.
Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и т. д. Одномерный массив — нестрого соответствует [[Вектор (математика)|вектору]] в математике; двумерный («строка», «столбец»)— [[Матрица (математика)|матрице]]. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко.
;Пример фиксированного массива на языке Паскаль
<source lang="pascal">
{Одномерный массив целых чисел.
Нумерация элементов от 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;
</source>
;Пример фиксированного массива на С/С++
<source lang="cpp">
int Array[10]; // Одномерный массив: целых чисел, размера 10;
// Нумерация элементов — от 0 до 9.
double Array[12][15]; // Двумерный массив:
// вещественных чисел двойной точности,
// размера 12 на 15;
// Нумерация: по строкам — от 0 до 11,
// по столбцам — от 0 до 14.
</source>
В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами<ref name="McMillan2014">{{cite book|author=Michael McMillan|title=Data Structures and Algorithms with JavaScript|url=https://books.google.com/books?id=1ywEAwAAQBAJ&pg=PA30|date=10 March 2014|publisher="O'Reilly Media, Inc."|isbn=978-1-4493-7396-2|pages=30–32}}</ref>.
; Пример двумерного массива на JavaScript
<source lang="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); // — вывести этот элемент на консоль.
});
});
</source>
Поддержка индексных массивов (свой синтаксис объявления, функции для работы с элементами и т. д.) есть в большинстве [[язык программирования высокого уровня|высокоуровневых языков программирования]]. Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и (или) конкретным [[транслятор]]ом.
В языках программирования, допускающих объявления программистом собственных [[тип данных|типов]], как правило, существует возможность создания типа «массив». В определении такого типа задаются типы и/или диапазоны значений каждого из индексов и тип элементов массива. Объявленный тип в дальнейшем может использоваться для определения переменных, формальных параметров и возвращаемых значений функций. Некоторые языки поддерживают для переменных-массивов операции присваивания (когда одной операцией всем элементам массива присваиваются значения соответствующих элементов другого массива).
;Объявление типа «массив» в языке Паскаль
<source lang="pascal">
type
TArrayType = array [0..9] of Integer;
(* Массивы, имеющие заданные параметры:
1. Размер — 10 ячеек;
2. Тип элементов, пригодных для хранения —
— целые числа диапазона [−32 768; 32 767],
— объявляются типом операндов, называющимся "TArrayType". *)
var
arr1, arr2, arr3: TArrayType;
(* Объявление трёх переменных-массивов одного типа
(вышеуказанного "TArrayType"). *)
</source>
В языке программирования [[APL (язык программирования)|APL]] массив является основным типом данных (при этом нуль-мерный массив называется скаляром, одномерный — вектором, двумерный — матрицей){{sfn|Магариу|1983}}. Помимо присваивания массивов в этом языке поддерживаются операции векторной и матричной арифметики, каждая из которых выполняется одной командой, операции сдвига данных в массивах, сортировка строк матрицы и т. п.
== Специфические типы массивов ==
=== Динамические массивы ===
{{main|Динамический массив}}
Динамическими называются массивы, размер которых может изменяться во время выполнения программы. Обычные (не динамические) массивы называют ещё ''фиксированными'' или ''статическими''.
Динамические массивы могут реализовываться как на уровне языка программирования, так и на уровне системных библиотек. Во втором случае динамический массив представляет собой объект стандартной библиотеки, и все операции с ним реализуются в рамках той же библиотеки. Так или иначе, поддержка динамических массивов предполагает наличие следующих возможностей:
# Описание динамического массива. На уровне языка это может быть специальная синтаксическая конструкция, на уровне библиотеки - библиотечный тип данных, значение которого объявляется стандартным образом. Как правило, при описании (создании) динамического массива указывается его начальный размер, хотя это и не обязательно.
# Операция определения текущего размера динамического массива.
# Операция изменения размера динамического массива.
Ниже приведён пример конструкций для работы с динамическими массивами на Delphi.
<source lang="pascal">
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])
</source>
=== Гетерогенные массивы ===
''Гетерогенным'' называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным [[тип данных|типам данных]]. Массив, хранящий [[указатель (тип данных)|указатели]] на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.
== Реализация ==
Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является следующий :
# Под массив выделяется непрерывный блок памяти объёмом S*m<sub>1</sub>*m<sub>2</sub>*m<sub>3</sub>…m<sub>n</sub>, где S — размер одного элемента, а m<sub>1</sub>…m<sub>n</sub> — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
# При обращении к элементу массива A[i<sub>1</sub>, i<sub>2</sub>, i<sub>3</sub>, …, i<sub>n</sub>] адрес соответствующего элемента вычисляется как B+S*((…(i<sub>1p</sub>*m<sub>1</sub>+i<sub>2p</sub>)*m<sub>2</sub>+…+i<sub>(n-1)p</sub>)*m<sub>n-1</sub>+i<sub>np</sub>), где B — база (адрес начала блока памяти массива), i<sub>kp</sub> — значение k-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. Приведённый соответствует реализации в большинстве компиляторов языка [[Си (язык программирования)|Си]]; в [[Фортран]]е порядок индексов противоположен{{sfn|Бартеньев|2000|сс = 108-112}}.
Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково. (Здесь одинаковость времени доступа следует понимать как отсутствие теоретической зависимости времени доступа от положения элемента и размера массива. В действительности особенности конкретной вычислительной платформы могут дать определённый разброс времени доступа. Например, [[CAS-латентность]] [[ОЗУ]] приводит к увеличению времени доступа к данным, расположенным в другой колонке (странице) ОЗУ, по отношению к предыдущим считанным данным. В практике программирования такими тонкостями, за редчайшими исключениями, пренебрегают.)
Первый элемент массива, в зависимости от [[язык программирования|языка программирования]], может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для [[Низкоуровневый язык программирования|низкоуровневых языков программирования]], хотя встречается и в языках высокого уровня, например, в том же Си. В ряде языков ([[Паскаль (язык программирования)|Паскаль]], [[Ада (язык программирования)|Ада]], [[Модула-2]]) диапазон индексов может определяться как произвольный диапазон значений любого типа данных, приводимого к целому, то есть целых чисел, символов, перечислений, даже логического типа (в последнем случае массив имеет два элемента, индексируемых значениями «Истина» и «Ложь»).
Обычным способом реализации гетерогенных массивов является отдельное хранение самих значений элементов и размещение в блоке памяти массива (организованного как обычный гомогенный массив, описанный выше) указателей на эти элементы. Поскольку указатели на значения любых типов, как правило, имеют один и тот же размер, удаётся сохранить простоту вычисления адреса, хотя возникают дополнительные накладные расходы на размещение значений элементов и обращение к ним.
Для динамических массивов может использоваться тот же механизм размещения, что и для статических, но с выделением некоторого объёма дополнительной памяти для расширения и добавлении механизмов изменения размера и перемещения содержимого массива в памяти.
Также динамические и гетерогенные массивы могут реализовываться путём использования принципиально иных методов хранения значений в памяти, например, одно- или двухсвязных списков. Такие реализации могут быть более гибкими, но требуют, как правило, дополнительных накладных расходов. Кроме того, в них обычно не удаётся выдержать требование константного времени доступа к элементу.
== Достоинства ==
* лёгкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
* одинаковое время доступа ко всем элементам
* малый размер элементов: они состоят только из информационного поля.
== Недостатки ==
* для статического массива — отсутствие динамики, невозможность удаления или добавления элемента без сдвига других.
* для динамического и/или гетерогенного массива — более низкое (по сравнению с обычным статическим) быстродействие и дополнительные накладные расходы на поддержку динамических свойств и/или гетерогенности.
* при работе с массивом в стиле C (с указателями) и при отсутствии дополнительных средств контроля — угроза выхода за границы массива и повреждения данных.
== См. также ==
* [[Ассоциативный массив]]
* [[Дерево отрезков]]
* [[V-список]]
* [[Параллельный массив]]
* [[Динамический массив]]
* [[Разрежённый массив]]
== Примечания ==
{{примечания}}
== Литература ==
* {{книга |заглавие=Алгоритмы и структуры данных|оригинал=Algoritms and data structure|автор=Вирт Н.|место=М. |издательство=Мир |год=1989 |страниц=360|isbn=5-03-001045-9|ref=Вирт}}
* {{книга|автор=Хювёнен Э., Сеппянен Й.|заглавие=Мир Лиспа. Введение в язык ЛИСП и функциональное программирование. В 2-х т.|оригинал=Lisp-maailma: Johdatus kieleen ja ohjelmointiin|ответственный=Пер. с финск|место=М.|издательство=Мир|год=1990|isbn=5-03-001935-9|ref=Хювёнен, Сеппянен}}
* {{книга|автор=Магариу Н. А.|заглавие=Язык программирования АПЛ|издательство=«Радио и связь»|год=1983|место=М.|страниц=96|ref=Магариу}}
* {{книга|автор=Бартеньев О. В.|заглавие=Современный Фортран|издание=3-е изд., доп. и перераб.|место=М.|издательство=ДИАЛОГ-МИФИ|год=2000|страниц=449|ref=Бартеньев}}
== Ссылки ==
* [http://code-live.ru/post/cpp-arrays/ Массивы в C++]
{{Структуры данных}}
{{Типы данных}}
[[Категория:Структуры данных]]
| 