Тип данных массива - Array data type

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

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

Языковая поддержка для типов массивов может включать определенные встроенный типы данных массивов, некоторые синтаксические конструкции (конструкторы типов массивов) что программист может использовать для определения таких типов и объявления переменных массива, а также специальные обозначения для индексации элементов массива.[1] Например, в Язык программирования Паскаль, декларация тип MyTable = массив [1..4,1..2] целых чисел, определяет новый тип данных массива, называемый MyTable. Декларация var A: MyTable затем определяет переменную А этого типа, который представляет собой совокупность восьми элементов, каждый из которых является целочисленной переменной, идентифицируемой двумя индексами. В программе на языке Pascal эти элементы обозначены А [1,1], А [1,2], A [2,1],… A [4,2].[2] Специальные типы массивов часто определяются стандартом языка. библиотеки.

Динамические списки также более распространены и проще в реализации, чем динамические массивы. Типы массивов отличаются от записывать типов главным образом потому, что они позволяют вычислять индексы элементов в время выполнения, как в Паскале назначение A [I, J]: = A [N-I, 2 * J]. Помимо прочего, эта функция позволяет использовать один итеративный утверждение для обработки произвольного количества элементов переменной массива.

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

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

История

Хайнц Рутисхаузер Русский язык программирования Superplan (1949–1951) включал многомерные массивы. Однако Рутисхаузер, описывая, как должен быть построен компилятор для своего языка, не реализовал его.

Языки ассемблера и языки низкого уровня, такие как BCPL[3] обычно не имеют синтаксической поддержки массивов.

Из-за важности структур массивов для эффективных вычислений самые ранние языки программирования высокого уровня, включая FORTRAN (1957), КОБОЛ (1960), и Алгол 60 (1960), обеспечили поддержку многомерных массивов.

Абстрактные массивы

Структуру данных массива можно математически смоделировать как абстрактная структура данных (ан абстрактный массив) с двумя операциями

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

Эти операции необходимы, чтобы удовлетворить аксиомы[4]

получать(набор(А,я, V), я) = V
получать(набор(А,я, V), J) = получать(А, J) если я ≠ J

для любого состояния массива А, любое значение V, и любые кортежи я, J для которого определены операции.

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

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

Реализации

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

С другой стороны, некоторые языки программирования предоставляют более либеральные типы массивов, которые позволяют индексировать произвольными значениями, такими как числа с плавающей запятой, струны, объекты, Рекомендации и т. д. Такие значения индекса не могут быть ограничены интервалом, тем более фиксированным интервалом. Таким образом, эти языки обычно позволяют создавать произвольные новые элементы в любое время. Этот выбор исключает реализацию типов массивов как структур данных массива. То есть эти языки используют синтаксис, подобный массиву, для реализации более общего ассоциативный массив семантика, и поэтому должна быть реализована хеш-таблица или какой-то другой структура данных поиска.

Языковая поддержка

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

Количество индексов, необходимых для определения элемента, называется измерение, размерность, или же классифицировать типа массива. (Эта номенклатура противоречит концепции размерности в линейной алгебре,[5] где это количество элементов. Таким образом, массив чисел с 5 строками и 4 столбцами, а значит, 20 элементами, как говорят, имеет размерность 2 в вычислительном контексте, но представляет собой матрицу с размером 4 на 5 или 20 в математике. Кроме того, в информатике значение слова «ранг» похоже на его смысл в тензорной алгебре но не к концепции линейной алгебры ранг матрицы.)

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

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

Это представление для многомерных массивов довольно распространено в программном обеспечении C и C ++. Однако C и C ++ будут использовать формулу линейной индексации для многомерных массивов, объявленных с постоянным размером времени компиляции, например к int A [10] [20] или же int A [m] [n]вместо традиционного int ** A.[6]

Обозначение индексации

Большинство языков программирования, поддерживающих массивы, поддерживают хранить и Выбрать операции и имеют специальный синтаксис для индексации. В ранних языках использовались круглые скобки, например А (я, j), как в FORTRAN; другие выбирают квадратные скобки, например A [i, j] или же A [i] [j], как в Algol 60 и Pascal (в отличие от использования круглых скобок для вызовы функций ).

Типы индексов

Типы данных массивов чаще всего реализуются как структуры массивов: с индексами, ограниченными целыми (или полностью упорядоченными) значениями, диапазонами индексов, фиксированными во время создания массива, и полилинейной адресацией элементов. Так было в большинстве "третье поколение" языков, и до сих пор остается в большинстве языки системного программирования Такие как Ада, C, и C ++. Однако в некоторых языках типы данных массивов имеют семантику ассоциативных массивов с индексами произвольного типа и созданием динамических элементов. Так бывает в некоторых языки сценариев Такие как Awk и Lua, а также некоторых типов массивов, предусмотренных стандартными C ++ библиотеки.

Проверка границ

Некоторые языки (например, Паскаль и Модула) выполняют проверка границ при каждом доступе, повышая исключение или прерывание программы, когда какой-либо индекс выходит за пределы допустимого диапазона. Компиляторы могут разрешить отключение этих проверок в целях безопасности ради скорости. Другие языки (например, FORTRAN и C) доверяют программисту и не выполняют никаких проверок. Хорошие компиляторы могут также анализировать программу, чтобы определить диапазон возможных значений, которые может иметь индекс, и этот анализ может привести к исключение проверки границ.

Происхождение индекса

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

Другие языки предоставляют только на одной основе типы массивов, где каждый индекс начинается с 1; это традиционное соглашение в математике для матриц и математических последовательности. Некоторые языки, такие как Pascal и Lua, поддерживают n-основанный типы массивов, минимальные допустимые индексы которых выбирает программист. Относительные достоинства каждого выбора были предметом горячих споров. Индексация с отсчетом от нуля имеет естественное преимущество перед индексированием с отсчетом от единицы, поскольку позволяет избежать один за другим или же ошибки столбов забора.[7]

Видеть сравнение языков программирования (массив) для базовых индексов, используемых в различных языках.

Самый высокий индекс

Связь между числами, появляющимися в объявлении массива, и индексом последнего элемента этого массива также зависит от языка. Во многих языках (например, C) следует указывать количество элементов, содержащихся в массиве; тогда как в других (таких как Паскаль и Visual Basic .NET ) следует указать числовое значение индекса последнего элемента. Излишне говорить, что это различие несущественно в языках, в которых индексы начинаются с 1, например Lua.

Алгебра массивов

Некоторые языки программирования поддерживают программирование массива, где операции и функции, определенные для определенных типов данных, неявно расширяются до массивов элементов этих типов. Таким образом, можно написать А+B добавить соответствующие элементы двух массивов А и B. Обычно эти языки предоставляют как поэлементное умножение и стандарт матричный продукт из линейная алгебра, и какой из них представлен * Оператор зависит от языка.

Языки, обеспечивающие возможности программирования массивов, получили распространение после появления инноваций в этой области APL. Это основные возможности предметно-ориентированные языки Такие какГАУСС, IDL, Matlab, и Mathematica. Они являются основным средством работы с новыми языками, такими как Юля и последние версии Фортран. Эти возможности также предоставляются через стандартные библиотеки расширений для других языков программирования общего назначения (например, широко используемых NumPy библиотека для Python ).

Типы строк и массивы

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

Запросы диапазона индекса массива

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

Элементы вновь созданного массива могут иметь неопределенные значения (как в C) или могут быть определены как имеющие конкретное значение «по умолчанию», такое как 0 или нулевой указатель (как в Java).

В C ++ объект std :: vector поддерживает хранить, Выбрать, и добавить операции с рабочими характеристиками, рассмотренными выше. У векторов можно запросить их размер и изменить его размер. Также поддерживаются более медленные операции, такие как вставка элемента посередине.

Нарезка

An нарезка массива операция принимает подмножество элементов объекта типа массива (значение или переменная), а затем собирает их как другой объект типа массива, возможно, с другими индексами. Если типы массивов реализованы как структуры массивов, многие полезные операции нарезки (такие как выбор подмассива, замена индексов или изменение направления индексов) могут быть выполнены очень эффективно, манипулируя наркотик вектор конструкции. Возможные срезы зависят от деталей реализации: например, FORTRAN позволяет срезать один столбец матричной переменной, но не строку, и обрабатывать его как вектор; тогда как C позволяет вырезать строку из матрицы, но не столбец.

С другой стороны, возможны другие операции нарезки, если типы массивов реализованы другими способами.

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

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

Для одномерных массивов это средство может быть предусмотрено как операция "добавить(А,Икс) ", что увеличивает размер массива А на единицу, а затем устанавливает значение последнего элемента равным Икс. Другие типы массивов (например, строки Паскаля) предоставляют оператор конкатенации, который можно использовать вместе с нарезкой для достижения этого эффекта и многого другого. В некоторых языках присвоение значения элементу массива автоматически расширяет массив, если необходимо, для включения этого элемента. В других типах массивов срез может быть заменен массивом другого размера, «с соответствующим перенумерованием последующих элементов - как при назначении списка Python»А[5: 5] = [10,20,30] ", который вставляет три новых элемента (10,20 и 30) перед элементом"А[5] ". Массивы с изменяемым размером концептуально аналогичны списки, а в некоторых языках эти два понятия являются синонимами.

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

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

Связанные типы

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

  1. ^ а б Роберт В. Себеста (2001) Концепции языков программирования. Эддисон-Уэсли. 4-е издание (1998 г.), 5-е издание (2001 г.), ISBN  9780201385960
  2. ^ К. Йенсен и Никлаус Вирт, Руководство пользователя и отчет PASCAL. Springer. Издание в мягкой обложке (2007 г.) 184 стр., ISBN  978-3540069508
  3. ^ Джон Митчелл, Концепции языков программирования. Издательство Кембриджского университета.
  4. ^ Лукхам, Судзуки (1979), "Проверка операций с массивами, записями и указателями в Паскале". Транзакции ACM по языкам и системам программирования 1 (2), 226–244.
  5. ^ увидеть определение матрицы
  6. ^ Брайан В. Керниган и Деннис М. Ричи (1988), Язык программирования C. Прентис-Холл, стр. 81.
  7. ^ Эдсгер В. Дейкстра, "Почему нумерация должна начинаться с нуля "

внешняя ссылка