Структура данных массива - Array data structure

Эта статья посвящена структуре на уровне байтового макета. Для абстрактный тип данных, видеть Тип данных массива. Для других типов массивов см. Множество.

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

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

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

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

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

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

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

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

История

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

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

Приложения

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

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

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

Массивы могут использоваться для определения частичного или полного поток управления в программах, как компактная альтернатива (иначе повторяющимся) множественным ЕСЛИ заявления. В этом контексте они известны как таблицы управления и используются вместе со специально созданным интерпретатором, чей поток управления изменяется в соответствии со значениями, содержащимися в массиве. Массив может содержать подпрограмма указатели (или относительные номера подпрограмм, на которые может воздействовать ВЫКЛЮЧАТЕЛЬ операторы), которые направляют путь исполнения.

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

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

Есть три способа индексирования элементов массива:

0 (индексация с нуля )

Первый элемент массива индексируется индексом 0.^[8]

1 (индексирование на основе одного)

Первый элемент массива индексируется индексом 1.

п (индексирование на основе n)

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

Использование индексации с нулевым отсчетом является выбором многих влиятельных языков программирования, включая C, Ява и Лисп. Это приводит к более простой реализации, где нижний индекс относится к смещению от начальной позиции массива, поэтому первый элемент имеет нулевое смещение.

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

Количество индексов, необходимых для определения элемента, называется размерностью, размерностью или классифицировать массива.

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

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

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

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

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

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

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

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

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

В общем, в k-мерный массив, адрес элемента с индексами я₁, я₂, ..., я_k является

B + c₁ · я₁ + c₂ · я₂ + … + c_k · я_k.

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

Это означает, что массив a имеет 2 строки и 3 столбца, а массив имеет целочисленный тип. Здесь мы можем сохранить 6 элементов, они будут храниться линейно, но начиная с первой строки, затем продолжая со второй строки. Вышеупомянутый массив будет сохранен как₁₁, а₁₂, а₁₃, а₂₁, а₂₂, а₂₃.

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

Коэффициенты c_k должен быть выбран так, чтобы каждый допустимый кортеж индекса отображался на адрес отдельного элемента.

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

Допинговые векторы

Формула адресации полностью определяется размером d, базовый адрес B, а приращения c₁, c₂, ..., c_k. Часто бывает полезно упаковать эти параметры в запись, называемую массивом дескриптор или же шаг вектор или же наркотик вектор.^[2][3] Размер каждого элемента, а также минимальные и максимальные значения, разрешенные для каждого индекса, также могут быть включены в вектор допинга. Вектор допинга - это полный ручка для массива, и это удобный способ передать массивы в качестве аргументов в процедуры. Много полезного нарезка массива операции (такие как выбор подматрицы, перестановка индексов или изменение направления индексов на противоположное) могут выполняться очень эффективно, манипулируя вектором допинга.^[2]

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

Основная статья: Порядок строк и столбцов

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

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

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

${displaystyle mathbf {A} ={egin{bmatrix}1&2&34&5&67&8&9end{bmatrix}}.}$

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

1

2

3

4

5

6

7

8

9

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

1

4

7

2

5

8

3

6

9

Для массивов с тремя или более индексами "основной порядок строк" помещает в последовательные позиции любые два элемента, чьи индексные кортежи отличаются только на единицу в последний индекс. «Старший порядок столбцов» аналогичен первый индекс.

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

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

Основная статья: Динамический массив

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

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

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

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

Эффективность

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

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

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

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

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

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

	Связанный список	Множество	Динамический массив	Сбалансированное дерево	Случайный список доступа	Дерево хешированных массивов
Индексирование	Θ (п)	Θ (1)	Θ (1)	Θ (журнал n)	Θ (журнал n)[9]	Θ (1)
Вставить / удалить в начале	Θ (1)	Нет данных	Θ (п)	Θ (журнал n)	Θ (1)	Θ (п)
Вставить / удалить в конце	Θ (1) когда последний элемент известен; Θ (п) когда последний элемент неизвестен	Нет данных	Θ (1) амортизированный	Θ (журнал п)	Нет данных [9]	Θ (1) амортизированный
Вставить / удалить в середине	время поиска + Θ (1)[10][11]	Нет данных	Θ (п)	Θ (журнал п)	Нет данных [9]	Θ (п)
Потраченное впустую пространство (средний)	Θ (п)	0	Θ (п)[12]	Θ (п)	Θ (п)	Θ (√п)

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

Ассоциативные массивы предоставить механизм для функций, подобных массиву, без огромных накладных расходов на хранилище, когда значения индекса разрежены. Например, массив, содержащий значения только с индексами 1 и 2 миллиарда, может выиграть от использования такой структуры. Специализированные ассоциативные массивы с целочисленными ключами включают Патрисия пытается, Джуди массивы, и деревья ван Эмде Боаса.

Сбалансированные деревья требуется O (журнал п) время для индексированного доступа, но также разрешить вставку или удаление элементов в O (журнал п) время,^[13] тогда как для растущих массивов требуется линейный (Θ (п)) пора вставлять или удалять элементы в произвольной позиции.

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

An Илифф вектор является альтернативой многомерной структуре массива. Он использует одномерный массив Рекомендации в массивы на одну размерность меньше. В частности, для двух измерений эта альтернативная структура была бы вектором указателей на векторы, по одному для каждой строки (указатель на c или c ++). Таким образом, элемент в строке я и столбец j массива А будет доступна двойная индексация (А[я][j] в типичных обозначениях). Эта альтернативная структура позволяет зубчатые массивы, где каждая строка может иметь разный размер - или, в общем, допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Он также сохраняет одно умножение (на приращение адреса столбца), заменяя его битовым сдвигом (для индексации

Измерение

Размерность массива - это количество индексов, необходимых для выбора элемента. Таким образом, если массив рассматривается как функция на множестве возможных комбинаций индексов, это измерение пространства, в котором его домен является дискретным подмножеством. Таким образом, одномерный массив - это список данных, двумерный массив - это прямоугольник данных,^[14] трехмерный массив блок данных и т. д.

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

Смотрите также

• Портал компьютерного программирования

• Динамический массив
• Параллельный массив
• Массив переменной длины
• Битовый массив
• Нарезка массива
• Смещение (информатика)
• Порядок строк и столбцов
• Шаг массива

Рекомендации

1. Блэк, Пол Э. (13 ноября 2008 г.). "множество". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий. Получено 22 августа 2010.
2. Бьорн Андрес; Ульрих Кете; Торбен Крегер; Хампрехт (2010). «Гибкие во время выполнения многомерные массивы и представления для C ++ 98 и C ++ 0x». arXiv:1008.2909 [cs.DS ].
3. Гарсия, Рональд; Ламсдэйн, Эндрю (2005). «MultiArray: библиотека C ++ для общего программирования с массивами». Программное обеспечение: практика и опыт. 35 (2): 159–188. Дои:10.1002 / spe.630. ISSN  0038-0644.
4. Дэвид Р. Ричардсон (2002), Книга о структурах данных. iUniverse, 112 страниц. ISBN  0-595-24039-9, ISBN  978-0-595-24039-5.
5. Велдхёйзен, Тодд Л. (декабрь 1998 г.). Массивы в Blitz ++ (PDF). Вычисления в объектно-ориентированных параллельных средах. Конспект лекций по информатике. 1505. Springer Berlin Heidelberg. С. 223–230. Дои:10.1007/3-540-49372-7_24. ISBN  978-3-540-65387-5. Архивировано из оригинал (PDF) 9 ноября 2016 г.
6. Дональд Кнут, Искусство программирования, т. 3. Эддисон-Уэсли
7. Леви, Генри М. (1984), Компьютерные системы на основе возможностей, Цифровая пресса, стр. 22, ISBN  9780932376220.
8. «Примеры кода массива - Функции массива PHP - Код PHP». http://www.configure-all.com/: Компьютерное программирование. Советы по веб-программированию. Архивировано из оригинал 13 апреля 2011 г.. Получено 8 апреля 2011. В большинстве компьютерных языков индекс массива (подсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и так далее. В массиве имен ниже вы можете увидеть индексы и значения.
9. Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре: 86–95. Дои:10.1145/224164.224187.
10. Основной доклад дня 1 - Бьярн Страуструп: стиль C ++ 11 в GoingNative 2012 на channel9.msdn.com с 45 минут или фольги с 44
11. Обработка чисел: почему вы никогда и НИКОГДА не должны использовать связанный список в своем коде снова в kjellkod.wordpress.com
12. Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF), Департамент компьютерных наук, Университет Ватерлоо
13. "Счетные B-деревья".
14. "Двумерные массивы Processing.org". processing.org. Получено 1 мая 2020.