Просмотр кода страницы Массив (тип данных)

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

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


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

В простейшем случае массив имеет константную длину по всем размерностям и может хранить данные только одного, заданного при описании, типа. Ряд языков поддерживает также [[динамический массив|динамические массивы]], длина которых может изменяться во время выполнения программы.

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

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

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

Первый элемент массива, в зависимости от [[язык программирования|языка программирования]], может иметь различный индекс.

;Пример фиксированного массива на языке Паскаль
‎‎<syntaxhighlight 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;   
‎‎</syntaxhighlight> 

;Пример фиксированного массива на Си

‎‎<syntaxhighlight lang="cpp" line>
  int Array[10];         // Одномерный массив: целых чисел, размера 10;
                         // Нумерация элементов — от 0 до 9.
                         
  double Array[12][15];  // Двумерный массив: 
                         // вещественных чисел двойной точности, 
                         // размера 12 на 15;
                         // Нумерация: по строкам — от 0 до 11, 
                         // по столбцам — от 0 до 14.
‎‎</syntaxhighlight> 

В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами<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
‎‎<syntaxhighlight lang="javascript" line>

    //Создание двумерного массива чисел: 
    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);       // — вывести этот элемент на консоль.
       });
    });
‎‎</syntaxhighlight> 

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

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

;Объявление типа «массив» в языке Паскаль
‎‎<syntaxhighlight lang="pascal" line>
  type
    TArrayType = array [0..9] of Integer; 
    (* Массивы, имеющие заданные параметры:
        1. Размер — 10 ячеек; 
        2. Тип элементов, пригодных для хранения — 
                — целые числа диапазона [−32 768; 32 767],
        — объявляются типом операндов, называющимся "TArrayType". *)

  var
    arr1, arr2, arr3: TArrayType; 
    (* Объявление трёх переменных-массивов одного типа 
        (вышеуказанного "TArrayType"). *)
‎‎</syntaxhighlight> 

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

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

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

Динамические массивы могут реализовываться как на уровне языка программирования, так и на уровне системных библиотек. Во втором случае динамический массив представляет собой объект стандартной библиотеки, и все операции с ним реализуются в рамках той же библиотеки. Так или иначе, поддержка динамических массивов предполагает наличие следующих возможностей:
# Описание динамического массива. На уровне языка это может быть специальная синтаксическая конструкция, на уровне библиотеки — библиотечный тип данных, значение которого объявляется стандартным образом. Как правило, при описании (создании) динамического массива указывается его начальный размер, хотя это и не обязательно.
# Операция определения текущего размера динамического массива.
# Операция изменения размера динамического массива.

Пример конструкций для работы с динамическими массивами на [[Delphi (язык программирования)|Delphi]]:
‎‎<syntaxhighlight lang="pascal" line>
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])  

‎‎</syntaxhighlight>

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