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

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

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

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

Общее описание

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

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

Пример фиксированного массива на языке Паскаль

    {Одномерный массив целых чисел.
     Нумерация элементов от 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.

В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами.

Пример двумерного массива на JavaScript

    //ES6. Создание двумерного массива чисел: 
    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

  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;            // Возвращаем память, используемую для столбцов матрицы.

Гетерогенные массивы

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

Реализация

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

1. Под массив выделяется непрерывный блок памяти объёмом S*m₁*m₂*m₃…m_n, где S — размер одного элемента, а m₁…m_n — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
2. При обращении к элементу массива A[i₁, i₂, i₃, …, i_n] адрес соответствующего элемента вычисляется как B+S*((…(i_1p*m₁+i_2p)*m₂+…+i_(n-1)p)*m_n-1+i_np), где B — база (адрес начала блока памяти массива), i_kp — значение k-го индекса, приведённое к целому с нулевым начальным смещением.

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

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

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

Достоинства

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

Недостатки

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

См. также

• Ассоциативный массив
• Дерево отрезков
• V-список
• Параллельный массив
• Динамический массив
• Разрежённый массив

Литература

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

Ссылки

• [code-live.ru/post/cpp-arrays/ Массивы в C++]

Отрывок, характеризующий Массив (программирование)

– И с цыганками его сюда привести? – спросил Николай смеясь. – Ну, ну!…
В это время неслышными шагами, с деловым, озабоченным и вместе христиански кротким видом, никогда не покидавшим ее, вошла в комнату Анна Михайловна. Несмотря на то, что каждый день Анна Михайловна заставала графа в халате, всякий раз он конфузился при ней и просил извинения за свой костюм.
– Ничего, граф, голубчик, – сказала она, кротко закрывая глаза. – А к Безухому я съезжу, – сказала она. – Пьер приехал, и теперь мы всё достанем, граф, из его оранжерей. Мне и нужно было видеть его. Он мне прислал письмо от Бориса. Слава Богу, Боря теперь при штабе.
Граф обрадовался, что Анна Михайловна брала одну часть его поручений, и велел ей заложить маленькую карету.
– Вы Безухову скажите, чтоб он приезжал. Я его запишу. Что он с женой? – спросил он.
Анна Михайловна завела глаза, и на лице ее выразилась глубокая скорбь…
– Ах, мой друг, он очень несчастлив, – сказала она. – Ежели правда, что мы слышали, это ужасно. И думали ли мы, когда так радовались его счастию! И такая высокая, небесная душа, этот молодой Безухов! Да, я от души жалею его и постараюсь дать ему утешение, которое от меня будет зависеть.
– Да что ж такое? – спросили оба Ростова, старший и младший.
Анна Михайловна глубоко вздохнула: – Долохов, Марьи Ивановны сын, – сказала она таинственным шопотом, – говорят, совсем компрометировал ее. Он его вывел, пригласил к себе в дом в Петербурге, и вот… Она сюда приехала, и этот сорви голова за ней, – сказала Анна Михайловна, желая выразить свое сочувствие Пьеру, но в невольных интонациях и полуулыбкою выказывая сочувствие сорви голове, как она назвала Долохова. – Говорят, сам Пьер совсем убит своим горем.
– Ну, всё таки скажите ему, чтоб он приезжал в клуб, – всё рассеется. Пир горой будет.
На другой день, 3 го марта, во 2 м часу по полудни, 250 человек членов Английского клуба и 50 человек гостей ожидали к обеду дорогого гостя и героя Австрийского похода, князя Багратиона. В первое время по получении известия об Аустерлицком сражении Москва пришла в недоумение. В то время русские так привыкли к победам, что, получив известие о поражении, одни просто не верили, другие искали объяснений такому странному событию в каких нибудь необыкновенных причинах. В Английском клубе, где собиралось всё, что было знатного, имеющего верные сведения и вес, в декабре месяце, когда стали приходить известия, ничего не говорили про войну и про последнее сражение, как будто все сговорились молчать о нем. Люди, дававшие направление разговорам, как то: граф Ростопчин, князь Юрий Владимирович Долгорукий, Валуев, гр. Марков, кн. Вяземский, не показывались в клубе, а собирались по домам, в своих интимных кружках, и москвичи, говорившие с чужих голосов (к которым принадлежал и Илья Андреич Ростов), оставались на короткое время без определенного суждения о деле войны и без руководителей. Москвичи чувствовали, что что то нехорошо и что обсуждать эти дурные вести трудно, и потому лучше молчать. Но через несколько времени, как присяжные выходят из совещательной комнаты, появились и тузы, дававшие мнение в клубе, и всё заговорило ясно и определенно. Были найдены причины тому неимоверному, неслыханному и невозможному событию, что русские были побиты, и все стало ясно, и во всех углах Москвы заговорили одно и то же. Причины эти были: измена австрийцев, дурное продовольствие войска, измена поляка Пшебышевского и француза Ланжерона, неспособность Кутузова, и (потихоньку говорили) молодость и неопытность государя, вверившегося дурным и ничтожным людям. Но войска, русские войска, говорили все, были необыкновенны и делали чудеса храбрости. Солдаты, офицеры, генералы – были герои. Но героем из героев был князь Багратион, прославившийся своим Шенграбенским делом и отступлением от Аустерлица, где он один провел свою колонну нерасстроенною и целый день отбивал вдвое сильнейшего неприятеля. Тому, что Багратион выбран был героем в Москве, содействовало и то, что он не имел связей в Москве, и был чужой. В лице его отдавалась должная честь боевому, простому, без связей и интриг, русскому солдату, еще связанному воспоминаниями Итальянского похода с именем Суворова. Кроме того в воздаянии ему таких почестей лучше всего показывалось нерасположение и неодобрение Кутузову.
– Ежели бы не было Багратиона, il faudrait l'inventer, [надо бы изобрести его.] – сказал шутник Шиншин, пародируя слова Вольтера. Про Кутузова никто не говорил, и некоторые шопотом бранили его, называя придворною вертушкой и старым сатиром. По всей Москве повторялись слова князя Долгорукова: «лепя, лепя и облепишься», утешавшегося в нашем поражении воспоминанием прежних побед, и повторялись слова Ростопчина про то, что французских солдат надо возбуждать к сражениям высокопарными фразами, что с Немцами надо логически рассуждать, убеждая их, что опаснее бежать, чем итти вперед; но что русских солдат надо только удерживать и просить: потише! Со всex сторон слышны были новые и новые рассказы об отдельных примерах мужества, оказанных нашими солдатами и офицерами при Аустерлице. Тот спас знамя, тот убил 5 ть французов, тот один заряжал 5 ть пушек. Говорили и про Берга, кто его не знал, что он, раненый в правую руку, взял шпагу в левую и пошел вперед. Про Болконского ничего не говорили, и только близко знавшие его жалели, что он рано умер, оставив беременную жену и чудака отца.


3 го марта во всех комнатах Английского клуба стоял стон разговаривающих голосов и, как пчелы на весеннем пролете, сновали взад и вперед, сидели, стояли, сходились и расходились, в мундирах, фраках и еще кое кто в пудре и кафтанах, члены и гости клуба. Пудренные, в чулках и башмаках ливрейные лакеи стояли у каждой двери и напряженно старались уловить каждое движение гостей и членов клуба, чтобы предложить свои услуги. Большинство присутствовавших были старые, почтенные люди с широкими, самоуверенными лицами, толстыми пальцами, твердыми движениями и голосами. Этого рода гости и члены сидели по известным, привычным местам и сходились в известных, привычных кружках. Малая часть присутствовавших состояла из случайных гостей – преимущественно молодежи, в числе которой были Денисов, Ростов и Долохов, который был опять семеновским офицером. На лицах молодежи, особенно военной, было выражение того чувства презрительной почтительности к старикам, которое как будто говорит старому поколению: уважать и почитать вас мы готовы, но помните, что всё таки за нами будущность.
Несвицкий был тут же, как старый член клуба. Пьер, по приказанию жены отпустивший волоса, снявший очки и одетый по модному, но с грустным и унылым видом, ходил по залам. Его, как и везде, окружала атмосфера людей, преклонявшихся перед его богатством, и он с привычкой царствования и рассеянной презрительностью обращался с ними.
По годам он бы должен был быть с молодыми, по богатству и связям он был членом кружков старых, почтенных гостей, и потому он переходил от одного кружка к другому.
Старики из самых значительных составляли центр кружков, к которым почтительно приближались даже незнакомые, чтобы послушать известных людей. Большие кружки составлялись около графа Ростопчина, Валуева и Нарышкина. Ростопчин рассказывал про то, как русские были смяты бежавшими австрийцами и должны были штыком прокладывать себе дорогу сквозь беглецов.
Валуев конфиденциально рассказывал, что Уваров был прислан из Петербурга, для того чтобы узнать мнение москвичей об Аустерлице.
В третьем кружке Нарышкин говорил о заседании австрийского военного совета, в котором Суворов закричал петухом в ответ на глупость австрийских генералов. Шиншин, стоявший тут же, хотел пошутить, сказав, что Кутузов, видно, и этому нетрудному искусству – кричать по петушиному – не мог выучиться у Суворова; но старички строго посмотрели на шутника, давая ему тем чувствовать, что здесь и в нынешний день так неприлично было говорить про Кутузова.
Граф Илья Андреич Ростов, озабоченно, торопливо похаживал в своих мягких сапогах из столовой в гостиную, поспешно и совершенно одинаково здороваясь с важными и неважными лицами, которых он всех знал, и изредка отыскивая глазами своего стройного молодца сына, радостно останавливал на нем свой взгляд и подмигивал ему. Молодой Ростов стоял у окна с Долоховым, с которым он недавно познакомился, и знакомством которого он дорожил. Старый граф подошел к ним и пожал руку Долохову.
– Ко мне милости прошу, вот ты с моим молодцом знаком… вместе там, вместе геройствовали… A! Василий Игнатьич… здорово старый, – обратился он к проходившему старичку, но не успел еще договорить приветствия, как всё зашевелилось, и прибежавший лакей, с испуганным лицом, доложил: пожаловали!
Раздались звонки; старшины бросились вперед; разбросанные в разных комнатах гости, как встряхнутая рожь на лопате, столпились в одну кучу и остановились в большой гостиной у дверей залы.
В дверях передней показался Багратион, без шляпы и шпаги, которые он, по клубному обычаю, оставил у швейцара. Он был не в смушковом картузе с нагайкой через плечо, как видел его Ростов в ночь накануне Аустерлицкого сражения, а в новом узком мундире с русскими и иностранными орденами и с георгиевской звездой на левой стороне груди. Он видимо сейчас, перед обедом, подстриг волосы и бакенбарды, что невыгодно изменяло его физиономию. На лице его было что то наивно праздничное, дававшее, в соединении с его твердыми, мужественными чертами, даже несколько комическое выражение его лицу. Беклешов и Федор Петрович Уваров, приехавшие с ним вместе, остановились в дверях, желая, чтобы он, как главный гость, прошел вперед их. Багратион смешался, не желая воспользоваться их учтивостью; произошла остановка в дверях, и наконец Багратион всё таки прошел вперед. Он шел, не зная куда девать руки, застенчиво и неловко, по паркету приемной: ему привычнее и легче было ходить под пулями по вспаханному полю, как он шел перед Курским полком в Шенграбене. Старшины встретили его у первой двери, сказав ему несколько слов о радости видеть столь дорогого гостя, и недождавшись его ответа, как бы завладев им, окружили его и повели в гостиную. В дверях гостиной не было возможности пройти от столпившихся членов и гостей, давивших друг друга и через плечи друг друга старавшихся, как редкого зверя, рассмотреть Багратиона. Граф Илья Андреич, энергичнее всех, смеясь и приговаривая: – пусти, mon cher, пусти, пусти, – протолкал толпу, провел гостей в гостиную и посадил на средний диван. Тузы, почетнейшие члены клуба, обступили вновь прибывших. Граф Илья Андреич, проталкиваясь опять через толпу, вышел из гостиной и с другим старшиной через минуту явился, неся большое серебряное блюдо, которое он поднес князю Багратиону. На блюде лежали сочиненные и напечатанные в честь героя стихи. Багратион, увидав блюдо, испуганно оглянулся, как бы отыскивая помощи. Но во всех глазах было требование того, чтобы он покорился. Чувствуя себя в их власти, Багратион решительно, обеими руками, взял блюдо и сердито, укоризненно посмотрел на графа, подносившего его. Кто то услужливо вынул из рук Багратиона блюдо (а то бы он, казалось, намерен был держать его так до вечера и так итти к столу) и обратил его внимание на стихи. «Ну и прочту», как будто сказал Багратион и устремив усталые глаза на бумагу, стал читать с сосредоточенным и серьезным видом. Сам сочинитель взял стихи и стал читать. Князь Багратион склонил голову и слушал.