imported>Well, Well, Bot!: уборка лишних параметров шаблона {{переход}}

2026-03-25T08:06:32Z

уборка лишних параметров шаблона {{переход}}

Новая страница

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

Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива<ref>{{Cite web |url=http://comp.vslovar.org.ru/828.html |title=Дрот В. Л., Новиков Ф. А. «Толковый словарь современной компьютерной лексики», Размерность массива |access-date=2012-10-18 |archive-date=2013-07-03 |archive-url=https://web.archive.org/web/20130703234601/http://comp.vslovar.org.ru/828.html |url-status=live }}</ref>. По количеству используемых индексов массивы делятся на одномерные, двумерные, трёхмерные и т. д.

Форма или структура массива — сведения о количестве размерностей и размере (протяжённости) массива по каждой из размерностей{{sfn|Бартеньев|2000|cc = 108-109}}; может быть представлена одномерным массивом{{sfn|Магариу|1983|cc = 18-19}}.

Особенностью массива как структуры данных (в отличие, например, от [[Связный список|связного списка]]) является константная [[вычислительная сложность]] доступа к элементу массива по индексу {{sfn|Вирт|1989|loc = 1.6 Массив}}. Массив относится к структурам данных с [[Произвольный доступ|произвольным доступом]].

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

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

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

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

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

;Пример фиксированного массива на языке Паскаль
<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">{{книга |заглавие=Data Structures and Algorithms with JavaScript |ссылка=https://books.google.com/books?id=1ywEAwAAQBAJ&pg=PA30 |издательство=[[O’Reilly|O’Reilly Media]] |isbn=978-1-4493-7396-2 |страницы=30—32 |язык=en |автор=Michael McMillan |день=10 |месяц=3 |год=2014}}</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 (язык программирования)|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>

== Гетерогенные массивы ==
''Гетерогенным'' называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным [[тип данных|типам данных]]. Массив, хранящий [[указатель (тип данных)|указатели]] на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка. В ряде языков программирования гетерогенные массивы называются записями.<ref>{{Cite web|url=https://studfile.net/preview/10097283/page:9/|title=1.9. Массивы и записи|lang=ru|website=StudFiles|access-date=2025-03-25}}</ref>

== Работа с памятью ==
Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является выделение непрерывного блока памяти объёмом <math>S \cdot m_1 \cdot m_2 \cdot \dots m_n</math>, где <math>S</math> — размер одного элемента, а <math>m_1, \dots m_n</math> — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс). При обращении к элементу массива с индексом <math>(i_1, i_2, \dots i_n)</math> адрес соответствующего элемента вычисляется как <math>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)</math>, где <math>B</math> — база (адрес начала блока памяти массива), <math>i_{k\mathrm p}</math> — значение <math>k</math>-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. (Этот способ соответствует реализации в большинстве компиляторов языка [[Си (язык программирования)|Си]]; в [[Фортран]]е порядок индексов противоположен{{sfn|Бартеньев|2000|сс = 108-112}}).

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

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

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

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

== Примечания ==
{{примечания}}

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

{{Структуры данных}}
{{Типы данных}}

[[Категория:Структуры данных]]
[[Категория:Составные типы данных]]

Массив (тип данных) - История изменений

imported>Well, Well, Bot!: уборка лишних параметров шаблона {{переход}}