Массив это в программировании тест

В информатикеструктура данных массиваили просто массив-это структура данных , состоящая из набора элементов (значений или переменных), каждый из которых идентифицируется по крайней мере одним индексом массива или ключом. Массив хранится таким образом. Что положение каждого элемента может быть вычислено из его индексного кортежа по математической формуле.[1][2][3] Простейшим типом структуры данных является линейный массив. Также называемый одномерным массивом.

Например, массив из 10 32-бит (4-байтовое) целое число переменных с индексами от 0 до 9, могут быть сохранены в виде 10 слов на память адресов 2000, 2004, 2008, …, 2036, (в

шестнадцатеричном виде: 0x7D0, 0x7D4, 0x7D8, …, 0x7F4), так что элемент с индексом меня есть адрес, 2000 + (я × 4).[4]

Адрес памяти первого элемента массива называется первым адресом. Базовым адресом или базовым адресом.

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

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

Массивы полезны в основном потому. Что индексы элементов могут быть вычислены во время выполнения. Помимо всего прочего. Эта функция позволяет одному итеративному оператору обрабатывать сколь угодно много элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и использовать одно и то же представление данных. Набор допустимых индексных кортежей и адреса элементов (и. Следовательно. Формула адресации элементов) обычно[3][5], но не всегда[2] фиксируются во время использования массива.

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

Этот термин также используется. Особенно в описании алгоритмов, для обозначения ассоциативного массива или «абстрактного массива», теоретической модели информатики (абстрактного типа данных или ADT). Предназначенной для захвата существенных свойств массивов.

Первые цифровые компьютеры использовали программирование на машинном языке для создания и доступа к массивным структурам для таблиц данных. Векторных и матричных вычислений и для многих других целей. Джон фон Нейман написал первую программу сортировки массивов (merge sort) в 1945 году. Во время создания первого компьютера с хранимой программой.[6]стр. 159 Индексация массивов первоначально осуществлялась с помощью самоизменяющегося кода, а затем с помощью индексных регистров и косвенной адресации. Некоторые мэйнфреймы. Разработанные в 1960-х годах. Такие как Burroughs B5000 и его преемники. Использовали сегментацию памяти для выполнения проверки границ индекса в аппаратном обеспечении.[7]

Языки ассемблера обычно не имеют специальной поддержки массивов, кроме той. Которую обеспечивает сама машина. Самые ранние языки программирования высокого уровня. Включая FORTRAN (1957), Lisp (1958), COBOL (1960) и ALGOL 60 (1960). Поддерживали многомерные массивы. Как и C (1972). В C++ (1983) шаблоны классов существуют для многомерных массивов. Размерность которых фиксирована во время выполнения[3][5], а также для гибких во время выполнения массивов.[2]

Массивы используются для реализации математических векторов и матриц, а также других видов прямоугольных таблиц. Многие базыданных . Большие и малые. Состоят из одномерных массивов. Элементами которых являются записи.

Массивы используются для реализации других структур данных. Таких как списки, кучи, хэш-таблицы, деки, очереди, стеки, строкии списки VLIST. Реализации других структур данных на основе массивов часто просты и экономичны по пространству (неявные структуры данных), требуют небольших пространственных накладныхрасходов . Но могут иметь низкую пространственную сложность. Особенно при модификации. По сравнению с древовидными структурами данных (сравните сортированный массив с деревом поиска).

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

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

Идентификатор элемента и формулы адресации

Когда объекты данных хранятся в массиве. Отдельные объекты выбираются индексом. Который обычно является неотрицательным скалярным целымчислом . Индексы также называются индексами. Индекс сопоставляет значение массива с хранимым объектом.

Существует три способа индексирования элементов массива:

0 (индексация на основе нуля)
Первый элемент массива индексируется индексом 0.]
1 (однонаправленная индексация)
Первый элемент массива индексируется индексом 1.
n (индексация на основе n)
Базовый индекс массива может быть выбран свободно. Обычно языки программирования . Допускающие индексацию на основе n, также допускают отрицательные значения индекса и другие скалярные типы данных. Такие как перечисленияили символы, которые могут использоваться в качестве индекса массива.

Использование индексации на основе нуля-это выбор дизайна многих влиятельных языков программирования, включая C, Java и Lisp. Это приводит к более простой реализации. Где подстрочный индекс ссылается на смещение от начальной позиции массива. Поэтому первый элемент имеет смещение. Равное нулю.

Массивы могут иметь несколько измерений. Поэтому доступ к массиву с использованием нескольких индексов не является редкостью. Например, двумерный массив Aс тремя строками и четырьмя столбцами может обеспечить доступ к элементу во 2-й строке и 4-м столбце с помощью выражения A[1][3]в случае системы индексирования на основе нуля. Таким образом. Два индекса используются для двумерного массива. Три-для трехмерного массива и n-для n-мерного массива.

Число индексов. Необходимых для указания элемента. Называется размерностью. Размерностью или рангом массива.

В стандартных массивах каждый индекс ограничен определенным диапазоном последовательных целых чисел (или последовательных значений некоторого перечисляемого типа), а адрес элемента вычисляется по

Одномерные массивы

Одномерный массив (или одномерный массив)-это тип линейного массива. Доступ к его элементам включает в себя один индекс. Который может представлять собой индекс строки или столбца.

В качестве примера рассмотрим объявление языка Сиint anArrayName[10];, которое объявляет одномерный массив из десяти целых чисел. Здесь массив может хранить десять элементов типа int. Этот массив имеет индексы. Начинающиеся с нуля до девяти. Например, выражения anArrayName[0]и anArrayName[9]являются первым и последним элементами соответственно.

Для вектора с линейной адресацией элемент с индексом i расположен по адресу B + c × i, где B-фиксированный базовый адрес, а c-фиксированная константа. Иногда называемая приращением адреса или шагом.

Если допустимые индексы элементов начинаются с 0, то константа B-это просто адрес первого элемента массива. По этой причине язык программирования C определяет. Что индексы массива всегда начинаются с 0; и многие программисты будут называть этот элемент нулем

Однако можно выбрать индекс первого элемента путем соответствующего выбора базового адреса B. Например, если массив состоит из пяти элементов, проиндексированных от 1 до 5, а базовый адрес B заменен на B + 30c, то индексы этих же элементов будут равны от 31 до 35. Если нумерация не начинается с 0, константа B не может быть адресом какого-либо элемента.

Многомерные массивы

Для многомерного массива элемент с индексами i,j будет иметь адрес B + c · i + d · j, где коэффициенты c и d-приращения адреса строки и столбцасоответственно.

В более общем случае в k-мерном массиве адрес элемента с индексами i1, i2,…, ik равен

B + c1 · i1 + c2 · i2 + … + ck · ik.

Например: int a[2][3];

Это означает. Что массив а имеет 2 строки и 3 столбца. Причем массив имеет целочисленный тип. Здесь мы можем хранить 6 элементов. Они будут храниться линейно. Но начиная с первой строки линейно. А затем продолжая со второй строки. Вышеприведенный массив будет храниться как a11, a12, a13, a21, a22, a23.

Эта формула требует только k умножений и k сложений для любого массива. Который может поместиться в памяти. Более того, если какой-либо коэффициент имеет фиксированную степень 2, то умножение может быть заменено сдвигом битов.

Коэффициенты ck должны быть выбраны таким образом. Чтобы каждый допустимый индексный кортеж соответствовал адресу отдельного элемента.

Если минимальное допустимое значение для каждого индекса равно 0, то B-это адрес элемента. Все индексы которого равны нулю. Как и в одномерном случае. Индексы элементов могут быть изменены путем изменения базового адреса B. Таким образом. Если двумерный массив имеет строки и столбцы. Индексированные от 1 до 10 и от 1 до 20 соответственно. То замена B на B + c1 − 3c2 это приведет к тому. Что они будут перенумерованы от 0 до 9 и от 4 до 23 соответственно. Используя эту функцию, некоторые языки (например, FORTRAN 77) указывают, что индексы массива начинаются с 1, как в математической традиции, в то время как другие языки (например, Fortran 90, Pascal и Algol) позволяют пользователю выбирать минимальное значение для каждого индекса.

Векторы допинга

Формула адресации полностью определяется размерностью d, базовым адресом Bи приращениями c1, c2,…, ck. Часто бывает полезно упаковать эти параметры в запись. Называемую дескриптором массива, вектором шага или вектором допинга. Размер каждого элемента. А также минимальные и максимальные значения. Допустимые для каждого индекса. Также могут быть включены в вектор допинга. Вектор допинга является полным дескриптором массива и представляет собой удобный способ передачи массивов в качестве аргументов процедурам. Много полезной нарезки массива операции (такие как выбор подмассива. Замена индексов или изменение направления индексов) могут быть выполнены очень эффективно путем манипулирования вектором допинга.]

Компактные макеты

Часто коэффициенты выбираются таким образом. Чтобы элементы занимали смежную область памяти. Однако в этом нет необходимости. Даже если массивы всегда создаются с непрерывными элементами. Некоторые операции среза массива могут создавать из них несмежные суб-массивы.

Иллюстрация основного порядка строк и столбцов

Существует два систематических компактных макета для двумерного массива. Например, рассмотрим матрицу

A=[123456789].{\displaystyle A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}

В схеме расположения основных строк (принятой C для статически объявленных массивов) элементы в каждой строке хранятся в последовательных позициях. И все элементы строки имеют более низкий адрес. Чем любой из элементов последовательной строки:

1 2 3 4 5 6 7 8 9

В порядке следования столбцов (традиционно используемом Fortran) элементы в каждом столбце являются последовательными в памяти. И все элементы столбца имеют более низкий адрес. Чем любой из элементов последовательного столбца:

1 4 7 2 5 8 3 6 9

Для массивов с тремя или более индексами последнем индексе. первому индексу.

В системах . Использующих кэш процессора или виртуальную память, сканирование массива намного быстрее. Если последовательные элементы хранятся в последовательных позициях в памяти. А не разрозненно. Многие алгоритмы. Использующие многомерные массивы. Будут сканировать их в предсказуемом порядке. Программист (или сложный компилятор) может использовать эту информацию для выбора между основным расположением строк или столбцов для каждого массива. Например, при вычислении продукта A·B из двух матриц лучше всего хранить A в порядке строки-майора и B в порядке столбца-майора.

Изменение размера

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

Некоторые структуры данных массива не перераспределяют хранилище. А хранят количество используемых элементов массива. Называемое числом или размером. Это фактически делает массив динамическим массивом с фиксированным максимальным размером или емкостью; строки Pascal являются примерами этого.

Нелинейные формулы

Иногда используются более сложные (нелинейные) формулы. Для компактного двумерного треугольного массива, например. Формула адресации является многочленом степени 2.

И хранение, и выбор принимают (детерминированный наихудший случай) постоянное время. Массивы занимают линейное (O(n)) пространство по числу элементов n, которые они содержат.

В массиве с размером элемента k и на машине с размером строки кэша B байт итерация по массиву из n элементов требует минимального потолка(nk/B) пропусков кэша. Поскольку его элементы занимают смежные ячейки памяти. Это примерно в разы больше. Чем количество пропусков кэша. Необходимых для доступа к n элементам в случайных местах памяти. Как следствие. Последовательная итерация по массиву на практике заметно быстрее. Чем итерация по многим другим структурам данных, свойство. Называемое локальностью ссылки (это, однако. Не означает. Что использование совершенного хэша или тривиальный хэш внутри одного и того же (локального) массива. Не будет еще быстрее — и достижим в постоянном времени). Библиотеки предоставляют низкоуровневые оптимизированные средства для копирования диапазонов памяти (например, memcpy), которые могут использоваться для перемещения смежных блоков элементов массива значительно быстрее. Чем это может быть достигнуто при индивидуальном доступе к элементам. Ускорение таких оптимизированных процедур зависит от размера элемента массива. Архитектуры и реализации.

С точки зрения памяти массивы представляют собой компактные структуры данных без накладных расходов на каждый элемент. Могут быть накладные расходы на каждый массив (например. Для хранения границ индекса). Но это зависит от языка. Также может случиться так. Что элементы. Хранящиеся в массиве. Требуют меньше памяти. Чем те же элементы. Хранящиеся в отдельных переменных. Потому что несколько элементов массива могут храниться в одном слове; такие массивы часто называют упакованными массивами. Крайним (но часто используемым) случаем является битовый массив, где каждый бит представляет собой один элемент. Один октет таким образом. Он может содержать до 256 различных комбинаций до 8 различных условий в наиболее компактной форме.

Доступ к массивам со статически предсказуемыми шаблонами доступа является основным источником параллелизма данных.

Сравнение с другими структурами данных

Динамические массивы или растущие массивы похожи на массивы. Но добавляют возможность вставлять и удалять элементы; добавление и удаление в конце особенно эффективно. Однако они резервируют линейное (Θ(n)) дополнительное хранилище. Тогда как массивы не резервируют дополнительное хранилище.

Ассоциативные массивы обеспечивают механизм для массивоподобной функциональности без огромных накладных расходов на хранение. Когда значения индекса разрежены. Например, массив. Содержащий значения только в индексах 1 и 2 миллиарда. Может извлечь выгоду из использования такой структуры. Специализированные ассоциативные массивы с целочисленными ключами включают в себя массивы Patricia tries, Judy arraysи деревья van Emde Boas.

Сбалансированные деревья требуют O(log n) времени для индексированного доступа. Но также позволяют вставлять или удалять элементы за O(log n) время,в то время как растущие массивы требуют линейного (Θ(n)) времени для вставки или удаления элементов в произвольном положении.

Связанные списки допускают постоянное удаление и вставку времени в середине. Но требуют линейного времени для индексированного доступа. Их использование памяти. Как правило, хуже. Чем массивы. Но все же линейно.

Двумерный массив, хранящийся в виде одномерного массива одномерных массивов (строк).

Вектор Илиффа является альтернативой многомерной структуре массива. Он использует одномерный массив ссылок на массивы с одним измерением меньше. В частности. Для двух измерений эта альтернативная структура будет представлять собой вектор указателей на векторы. По одному для каждой строки(указатель на c или c++). Таким образом. Элемент в строке i и столбце j массива A будет доступен с помощью двойной индексации (A[i][j] в типичной нотации). Эта альтернативная структура допускает зубчатые массивы, где каждая строка может иметь разный размер—или. В общем случае. Где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Он также сохраняет одно умножение (на приращение адреса столбца). Заменяя его битовым сдвигом (для индексации

Размерность массива — это количество индексов. Необходимых для выбора элемента. Таким образом. Если массив рассматривается как функция от множества возможных комбинаций индексов. То это размерность пространства. В котором его область является дискретным подмножеством. Таким образом. Одномерный массив-это список данных. Двумерный массив-это прямоугольник данных, трехмерный массив-это блок данных и т. Д.

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

Посмотрите массив в Викисловаре, свободном словаре.
  1. ^
  2. ^ b c d e Bjoern Andres; Ullrich Koethe; Thorben Kroeger; Hamprecht (2010). arXiv:1008.2909 [cs.DS].
  3. ^ b c d Гарсия, Рональд; Ламсдейн, Эндрю (2005). Программное обеспечение: Практика и опыт. 35 (2): 159-188. doi:10.1002/spe.630. ISSN 0038-0644.
  4. ^ Дэвид Р. Ричардсон (2002), Книга о структурах данных. iUniverse, 112 страниц. ISBN 0-595-24039-9, ISBN 978-0-595-24039-5.
  5. ^ b Veldhuizen. Todd L. (декабрь 1998). Массивы в Blitz++ (PDF). Вычисления в объектно-ориентированных параллельных средах. Конспект лекций по информатике. 1505. Springer Berlin Heidelberg. pp. 223–230. doi:10.1007/3-540-49372-7_24. ISBN 978-3-540-65387-5. Архивирован из оригинала (PDF) 9 ноября 2016 года.
  6. ^ Дональд Кнут, Искусство компьютерного программирования, т. 3. Эддисон-Уэсли
  7. ^ Levy, Henry M. (1984), Capability-based Computer Systems, Digital Press, p. 22, ISBN 9780932376220.
  8. ^ . http://www.configure-all.com/: Компьютерное программирование Советы по веб-программированию. Архивирован с оригинала 13 апреля 2011года . Извлечено 8 апреля 2011года . В большинстве компьютерных языков индекс массива (подсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и так далее. В массиве имен ниже вы можете увидеть индексы и значения.
  9. ^ Перейти вверх к: a b c Крис Окасаки (1995). Материалы Седьмой Международной конференции по функциональным языкам программирования и компьютерной архитектуре: 86-95. doi:10.1145/224164.224187.
  10. ^ День 1 Keynote — Bjarne Stroustrup: Стиль C++11 на GoingNative 2012 on channel9.msdn.com с минуты 45 или минуты 44
  11. ^ Хруст чисел: Почему вы никогда, никогда. НИКОГДА больше не должны использовать linked-list в своем коде в kjellkod.wordpress.com
  12. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Манро, ДЖИ; Демейн, ЭД (1999), Изменяемые размеры массивов в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF), Факультет компьютерных наук Университета Ватерлоо
  13. ^ .
  14. ^ . processing.org. Извлечено 1 мая 2020года .