Войти
В информатике, тип массива - это тип данных, который представляет собой набор элементов (значений или переменных ), каждый из которых выбирается по одному или несколько индексов (идентифицирующих ключей), которые могут быть вычислены во время выполнения во время выполнения программы. Такой набор обычно называется переменной массива, значением массива или просто массивом . По аналогии с математическими понятиями вектор и матрица, типы массивов с одним и двумя индексами часто называют векторным типом и матричным типом, соответственно.
Языковая поддержка для типов массивов может включать в себя определенные встроенные типы данных массива, некоторые синтаксические конструкции (конструкторы типов массивов), которые программист может использовать для определения таких типов. и объявляют переменные массива и специальную нотацию для индексации элементов массива. Например, в языке программирования Pascal объявление type MyTable = array [1..4,1..2] целого числаопределяет новый тип данных массива с именем MyTable. Объявление var A: MyTableзатем определяет переменную Aэтого типа, которая представляет собой совокупность восьми элементов, каждый из которых является целочисленной переменной, идентифицируемой двумя индексами. В программе на языке Pascal эти элементы обозначены A [1,1], A [1,2], A [2,1],… А [4,2]. Специальные типы массивов часто определяются стандартными библиотеками языка..
Динамические списки также более распространены и их легче реализовать, чем динамические массивы. Типы массивов отличаются от типов record в основном потому, что они позволяют вычислять индексы элементов во время времени выполнения, как в Pascal assignment A [I, J]: = A [NI, 2 * J]. Среди прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольно много элементов переменной массива.
В более теоретических контекстах, особенно в теории типов и в описании абстрактных алгоритмов, термины «массив» и «тип массива» иногда относятся к абстрактный тип данных (ADT), также называемый абстрактным массивом, или может относиться к ассоциативному массиву, математической модели с основными операциями и поведением типичного типа массива в большинство языков - в основном это набор элементов, которые выбираются индексами, вычисляемыми во время выполнения.
В зависимости от языка типы массивов могут перекрываться (или быть идентифицированы) с другими типами данных, которые описывают совокупные значения, например списки и строки. Типы массивов часто реализуются с помощью структур данных массива, но иногда и другими способами, такими как хэш-таблицы, связанные списки или деревья поиска.
Язык программирования Superplan Хайнца Рутисхаузера (1949–1951) включал многомерные массивы. Однако Рутисхаузер, описывая, как должен быть построен компилятор для своего языка, не реализовал его.
Языки ассемблера и низкоуровневые языки, такие как BCPL, обычно не имеют синтаксической поддержки массивов.
Из-за важности структур массивов для эффективных вычислений самые ранние языки программирования высокого уровня, включая FORTRAN (1957), COBOL (1960) и Algol 60 (1960) обеспечил поддержку многомерных массивов.
Структура данных массива может быть математически смоделирована как абстрактная структура данных (абстрактный массив) с двумя операциями
Эти операции требуются для удовлетворения аксиом
для любого состояния массива A, любого значения V и любых кортежей I, J, для которых определены операции.
Первая аксиома означает, что каждый элемент ведет себя как переменная. Вторая аксиома означает, что элементы с разными индексами ведут себя как непересекающиеся переменные, так что сохранение значения в одном элементе не влияет на значение любого другого элемента.
Эти аксиомы не накладывают никаких ограничений на набор допустимых кортежей индекса I, поэтому эту абстрактную модель можно использовать для треугольных матриц и других массивов необычной формы.
Чтобы эффективно реализовывать переменные таких типов, как структуры массивов (с индексацией, выполняемой арифметикой указателя ), многие языки ограничивают индексы для целочисленных типов данных (или других типов, которые можно интерпретировать как целые числа, например, байтов и перечислимые типы ), и требуют, чтобы все элементы имели одинаковые тип данных и размер хранилища. Большинство этих языков также ограничивают каждый индекс конечным интервалом целых чисел, который остается фиксированным на протяжении всего времени существования переменной массива. В некоторых скомпилированных языках, на самом деле, диапазоны индексов могут быть известны во время компиляции.
С другой стороны, некоторые языки программирования предоставляют более либеральные типы массивов, которые позволяют индексировать произвольными значения, такие как числа с плавающей запятой, строки, объекты, ссылки и т. д. Такие значения индекса не могут быть ограничены интервал, а тем более фиксированный интервал. Таким образом, эти языки обычно позволяют создавать произвольные новые элементы в любое время. Этот выбор исключает реализацию типов массивов как структур данных массива. То есть эти языки используют синтаксис, подобный массиву, для реализации более общей семантики ассоциативного массива, и поэтому должны быть реализованы с помощью хэш-таблицы или какой-либо другой структуры данных поиска.
Количество индексов, необходимых для указания элемента, называется размерностью, размерностью или рангом типа массива. (Эта номенклатура конфликтует с концепцией размерности в линейной алгебре, где это количество элементов. Таким образом, массив чисел с 5 строками и 4 столбцами, следовательно, 20 элементов, как говорят, имеет размерность 2 в вычислительном контексте, но представляет матрица размером 4 на 5 или 20. Кроме того, в компьютерных науках значение "ранга" аналогично его значению в тензорной алгебре, но не понятию линейной алгебры ранга матрицы.)
Многие языки поддерживают только одномерные массивы. В этих языках многомерный массив обычно представлен вектором Илиффа, одномерный массив ссылается на на массивы на одно измерение меньше. В частности, двумерный массив будет реализован как вектор указателей на его строки. Таким образом, доступ к элементу в строке i и столбце j массива A будет осуществляться путем двойной индексации (A [i] [j] в типичной записи). Этот способ эмуляции многомерных массивов позволяет создавать зубчатые массивы, где каждая строка может иметь разный размер - или, в общем, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов..
Такое представление многомерных массивов широко распространено в программном обеспечении C и C ++. Однако C и C ++ будут использовать формулу линейной индексации для многомерных массивов, объявленных с постоянным размером времени компиляции, например на int A [10] [20]или int A [m] [n]вместо традиционного int ** A.
Большинство языков программирования, поддерживающих массивы, поддерживают операции сохранения и выбора и имеют специальный синтаксис для индексации. В ранних языках использовались круглые скобки, например A (i, j), как в FORTRAN; другие выбирают квадратные скобки, например A [i, j]или A [i] [j], как в Algol 60 и Pascal (в отличие от использования круглых скобок для вызовов функций ).
Типы данных массивов чаще всего реализуются как структуры массивов: с индексами, ограниченными целочисленными (или полностью упорядоченными) значениями, диапазонами индексов, фиксированными во время создания массива, и полилинейной адресацией элементов. Так было в большинстве языков «третьего поколения» и до сих пор остается в большинстве языков системного программирования, таких как Ada, C и C ++. Однако в некоторых языках типы данных массивов имеют семантику ассоциативных массивов с индексами произвольного типа и созданием динамических элементов. Так обстоит дело с некоторыми языками сценариев, такими как Awk и Lua, а также с некоторыми типами массивов, предоставляемыми стандартными библиотеками C ++.
Некоторые языки (например, Pascal и Modula) выполняют проверку границ при каждом доступе, вызывая исключение или прерывая программу при любом индекс вне допустимого диапазона. Компиляторы могут разрешить отключение этих проверок в целях безопасности ради скорости. Другие языки (например, FORTRAN и C) доверяют программисту и не выполняют никаких проверок. Хорошие компиляторы могут также проанализировать программу, чтобы определить диапазон возможных значений, которые может иметь индекс, и этот анализ может привести к исключению проверки границ.
Некоторые языки, такие как C, предоставляют только массивы с отсчетом от нуля, для которых минимальное допустимое значение для любого индекса равно 0. Этот выбор удобен для реализации массива и вычислений адресов. С помощью такого языка, как C, можно определить указатель на внутреннюю часть любого массива, который будет символически действовать как псевдомассив, вмещающий отрицательные индексы. Это работает только потому, что C не проверяет индекс на соответствие границам при использовании.
Другие языки предоставляют только типы массивов на основе одного, где каждый индекс начинается с 1; это традиционное математическое соглашение для матриц и математических последовательностей . Некоторые языки, такие как Pascal и Lua, поддерживают типы массивов на основе n, минимальные допустимые индексы которых выбираются программистом. Относительные достоинства каждого выбора были предметом горячих споров. Индексирование с нуля имеет естественное преимущество перед индексированием с единицей в том, что позволяет избежать одноразовых или ошибок ограждения.
См. сравнение языков программирования (массив) для базовые индексы, используемые различными языками.
Связь между числами, появляющимися в объявлении массива, и индексом последнего элемента этого массива также зависит от языка. Во многих языках (например, C) следует указывать количество элементов, содержащихся в массиве; тогда как в других (таких как Pascal и Visual Basic.NET ) нужно указать числовое значение индекса последнего элемента. Излишне говорить, что это различие несущественно в языках, где индексы начинаются с 1, таких как Lua.
Некоторые языки программирования поддерживают программирование массивов, где операции и функции, определенные для определенных типов данных, неявно расширяются до массивов элементов этих типов. Таким образом, можно написать A + B, чтобы сложить соответствующие элементы двух массивов A и B. Обычно эти языки обеспечивают как поэлементное умножение, так и стандартное матричное произведение из линейная алгебра, и какая из них представлена оператором *, зависит от языка.
Языки, обеспечивающие возможности программирования массивов, получили распространение со времени появления инноваций в этой области APL. Это основные возможности предметно-ориентированных языков, таких как GAUSS, IDL, Matlab и Mathematica. Они являются основным средством для новых языков, таких как Julia и последних версий Fortran. Эти возможности также предоставляются через стандартные библиотеки расширений для других языков программирования общего назначения (таких как широко используемая библиотека NumPy для Python ).
Многие языки предоставляют встроенный тип данных string со специальной нотацией («строковые литералы ») для построения значения этого типа. В некоторых языках (например, C) строка представляет собой просто массив символов или обрабатывается примерно так же. Другие языки, такие как Pascal, могут предоставлять совершенно разные операции для строк и массивов.
Некоторые языки программирования предоставляют операции, которые возвращают размер (количество элементов) вектора или, в более общем смысле, диапазон каждого индекса массива. В C и C ++ массивы не поддерживают функцию размера, поэтому программистам часто приходится объявлять отдельную переменную для хранения размера и передавать ее процедурам как отдельный параметр.
Элементы вновь созданного массива могут иметь неопределенные значения (как в C) или могут быть определены как имеющие конкретное значение «по умолчанию», такое как 0 или нулевой указатель (как в Java).
В C ++ объект std :: vector поддерживает операции сохранения, выбора и добавления с характеристиками производительности, описанными выше. У векторов можно запросить их размер и изменить его размер. Также поддерживаются более медленные операции, такие как вставка элемента в середину.
Операция нарезки массива берет подмножество элементов объекта типа массива (значение или переменная), а затем собирает их как другой объект типа массива, возможно, с другими индексами. Если типы массивов реализованы как структуры массивов, многие полезные операции нарезки (такие как выбор подмассивов, замена индексов или изменение направления индексов) могут быть выполнены очень эффективно, манипулируя вектором допинга из структура. Возможные срезы зависят от деталей реализации: например, FORTRAN позволяет срезать один столбец матричной переменной, но не строку, и обрабатывать его как вектор; тогда как C позволяет вырезать строку из матрицы, но не столбец.
С другой стороны, другие операции нарезки возможны, когда типы массивов реализованы другими способами.
Некоторые языки допускают динамические массивы (также называемые изменяемым размером, расширяемым или расширяемым): переменные массива, диапазоны индексов которых могут быть расширены в любое время после создания, без изменение значений его текущих элементов.
Для одномерных массивов эта возможность может быть предоставлена как операция «append(A, x)», которая увеличивает размер массива A на единицу, а затем устанавливает значение последний элемент x. Другие типы массивов (например, строки Паскаля) предоставляют оператор конкатенации, который можно использовать вместе с нарезкой для достижения этого эффекта и многого другого. В некоторых языках присвоение значения элементу массива автоматически расширяет массив, если необходимо, для включения этого элемента. В других типах массивов срез может быть заменен массивом другого размера »с соответствующим перенумерованием последующих элементов - как в назначении списка Python« A [5: 5] = [10,20,30] », которое вставляет три новых элементы (10, 20 и 30) перед элементом «A [5]». Массивы с изменяемым размером концептуально аналогичны спискам, и эти два понятия являются синонимами в некоторых языках.
Расширяемый массив может быть реализован как массив фиксированного размера со счетчиком, который записывает, сколько элементов фактически используется. Операция appendпросто увеличивает счетчик; пока не будет использован весь массив, когда Операция добавленияможет быть определена как неудачная. Это реализация динамического массива с фиксированной емкостью, как в типе stringязыка Паскаля. В качестве альтернативы, Операция добавленияможет перераспределить базовый массив большего размера и скопировать старые элементы в новую область.
 | В Викиучебнике есть книга по теме: Структуры данных / Массивы |
 | Найдите массив в Викисловаре, бесплатном словаре. |
 | Викискладе есть носители, относящиеся к структуре данных массива. |
