Войти
В информатике, аннотация тип данных(ADT) - это математическая модель для типов данных. Абстрактный тип данных определяется своим поведением (семантика ) с точки зрения пользователя данных, в частности, с точки зрения возможных значений, возможных операций с данными этого типа и поведения эти операции. Эта математическая модель контрастирует со структурами данных , которые являются конкретными представлениями данных и являются точкой зрения разработчика, а не пользователя.
Формально ADT можно определить как «класс объектов, логическое поведение которых определяется набором значений и набором операций»; это аналог алгебраической структуры в математике. Что подразумевается под «поведением», варьируется в зависимости от автора, при этом двумя основными типами формальных спецификаций поведения являются аксиоматическая (алгебраическая) спецификация и абстрактная модель; они соответствуют аксиоматической семантике и операционной семантике абстрактной машины соответственно. Некоторые авторы также включают вычислительную сложность («стоимость») как с точки зрения времени (для вычислительных операций), так и с точки зрения пространства (для представления значений). На практике многие распространенные типы данных не являются ADT, поскольку абстракция не идеальна, и пользователи должны знать о таких проблемах, как арифметическое переполнение, которые возникают из-за представления. Например, целые числа часто хранятся как значения фиксированной ширины (32-битные или 64-битные двоичные числа) и, таким образом, испытывают целочисленное переполнение, если максимальное значение превышено.
ADT - это теоретическая концепция в информатике, используемая при разработке и анализе алгоритмов, структур данных и программных систем, и не соответствуют конкретным функциям компьютера. languages - основные компьютерные языки напрямую не поддерживают официально указанные ADT. Однако различные языковые функции соответствуют определенным аспектам ADT, и их легко спутать с собственно ADT; к ним относятся абстрактные типы, непрозрачные типы данных, протоколы и разработка по контракту. Впервые ADT были предложены Барбарой Лисков и Стивеном Н. Зиллесом в 1974 году в рамках разработки языка CLU.
Например, целые числа представляют собой ADT, определяемые как значения..., −2, −1, 0, 1, 2,..., и операциями сложения, вычитания , умножение и деление вместе с больше чем, меньше чем и т. д., которые ведут себя согласно знакомой математике (с вниманием к целочисленному делению ), независимо от того, как целые числа представлены компьютером. Явно «поведение» включает в себя соблюдение различных аксиом (ассоциативность и коммутативность сложения и т. Д.) И предварительных условий для операций (не может делиться на ноль). Обычно целые числа представлены в структуре данных как двоичные числа, чаще всего как дополнение до двух, но могут быть десятичными числами с двоичным кодом или единицами. дополнение, но пользователь абстрагируется от конкретного выбора представления и может просто использовать данные как типы данных.
ADT состоит не только из операций, но также из значений базовых данных и ограничений на операции. «Интерфейс» обычно относится только к операциям и, возможно, к некоторым ограничениям на операции, особенно к предварительным условиям и постусловиям, но не к другим ограничениям, таким как отношения между операциями.
Например, абстрактный стек , который представляет собой структуру «последним пришел - первым ушел», может быть определен тремя операциями: push, который вставляет данные предмет в стек; pop, который удаляет из него элемент данных; и peekили top, который обращается к элементу данных наверху стека без удаления. Абстрактная очередь , которая является структурой «первым пришел - первым обслужен», также будет иметь три операции: enqueue, которая вставляет элемент данных в очередь; dequeue, который удаляет из него первый элемент данных; и front, который обращается к первому элементу данных в очереди и обслуживает его. Не было бы никакого способа различать эти два типа данных, если не введено математическое ограничение, которое для стека указывает, что каждый всплывающий элемент всегда возвращает последний отправленный элемент, который еще не был извлечен. При анализе эффективности алгоритмов, использующих стеки, можно также указать, что все операции выполняются одинаково, независимо от того, сколько элементов данных было помещено в стек, и что стек использует постоянный объем памяти. для каждого элемента.
Абстрактные типы данных - это чисто теоретические сущности, используемые (среди прочего) для упрощения описания абстрактных алгоритмов, для классификации и оценки структур данных, а также для формального описания системы типов языков программирования. Однако ADT может быть реализован с помощью конкретных типов данных или структур данных многими способами и на многих языках программирования; или описан на языке формальных спецификаций. ADT часто реализуются как модули : интерфейс модуля объявляет процедуры, которые соответствуют операциям ADT, иногда с комментариями, которые описывают ограничения. Эта стратегия сокрытия информации позволяет изменять реализацию модуля, не нарушая клиентские программы.
Термин абстрактный тип данных также можно рассматривать как обобщенный подход к ряду алгебраических структур, таких как решетки, группы и кольца. Понятие абстрактных типов данных связано с концепцией абстракции данных, важной в объектно-ориентированном программировании и методологиях проектирования по контракту для разработки программного обеспечения..
Абстрактный тип данных определяется как математическая модель объектов данных, составляющих тип данных, а также функций, которые работают с этими объектами. Для их определения нет стандартных соглашений. Можно провести широкое разделение между «императивным» и «функциональным» стилями определения.
В философии языков императивного программирования абстрактная структура данных рассматривается как изменяемая сущность, что означает, что она может находиться в разных состояния в разное время. Некоторые операции могут изменить состояние ADT; поэтому порядок, в котором оцениваются операции, важен, и одна и та же операция с одними и теми же объектами может иметь разные эффекты, если выполняется в разное время - точно так же, как инструкции компьютера или команды и процедуры императивного языка. Чтобы подчеркнуть эту точку зрения, принято говорить, что операции выполняются или применяются, а не оцениваются. Императивный стиль часто используется при описании абстрактных алгоритмов. (Подробнее см. Искусство компьютерного программирования Дональда Кнута )
Определения ADT в императивном стиле часто зависят от понятие абстрактной переменной, которую можно рассматривать как простейший нетривиальный ADT. Абстрактная переменная V - это изменяемый объект, который допускает две операции:
с ограничением, что
Как во многих языках программирования операция store(V, x) часто обозначается как V ← x (или аналогичная запись), а fetch(V) подразумевается всякий раз, когда переменная V используется в контексте, где требуется значение. Так, например, V ← V + 1 обычно понимается как сокращение для store(V, fetch(V) + 1).
В этом определении неявно предполагается, что сохранение значения в переменной U не влияет на состояние отдельной переменной V. Чтобы сделать это предположение явным, можно добавить ограничение, которое
В более общем смысле определения ADT часто предполагают, что любая операция, изменяющая состояние одного экземпляра ADT, не влияет на состояние любого другого экземпляра (включая другие экземпляры тот же ADT) - если аксиомы ADT не подразумевают, что два экземпляра связаны (с псевдонимом ) в этом смысле. Например, при расширении определения абстрактной переменной для включения абстрактных записей операция, которая выбирает поле из переменной записи R, должна давать переменную V, которая связана с этой частью R.
Определение абстрактной переменной V может также ограничивать сохраненные значения x членами определенного набора X, называемого диапазоном или типом V. Как и в языках программирования, такие ограничения могут упростить описание и анализ алгоритмов и улучшить их читаемость.
Обратите внимание, что это определение ничего не говорит о результате оценки fetch(V), когда V не инициализирован, то есть перед выполнением любой операции storeна V. Алгоритм, который делает это, обычно считается недействительным, потому что его действие не определено. (Однако есть несколько важных алгоритмов, эффективность которых сильно зависит от предположения, что такая выборкаявляется допустимой и возвращает произвольное значение в диапазоне переменной.)
Некоторым алгоритмам необходимо создавать новые экземпляры некоторого ADT (например, новые переменные или новые стеки). Для описания таких алгоритмов обычно включают в определение ADT операцию create(), которая возвращает экземпляр ADT, обычно с аксиомами, эквивалентными
Эта аксиома может быть усилена, чтобы исключить также частичное совпадение имен с другими экземплярами. С другой стороны, эта аксиома по-прежнему позволяет реализациям create() выдавать ранее созданный экземпляр, который стал недоступен для программы.
В качестве другого примера, определение абстрактного стека в императивном стиле может указывать, что состояние стека S может быть изменено только с помощью операций
с ограничением,
Поскольку присваивание V ← x по определению не может изменить состояние S, это условие означает, что V ← pop(S) восстанавливает S в состояние, которое было до push(S, x). Из этого условия и из свойств абстрактных переменных следует, например, что последовательность
где x, y и z - любые значения, а U, V, W - попарно различные переменные, эквивалентно
Здесь неявно предполагается, что операции с экземпляром стека не изменяют состояние любого другого экземпляра ADT, включая другие стеки; то есть
Определение абстрактного стека обычно включает также логическую -значную функцию empty(S) и Операция create(), которая возвращает экземпляр стека, с аксиомами, эквивалентными
Иногда ADT определяется так, как если бы во время выполнения алгоритма существовал только один его экземпляр, и все операции были применены к этому экземпляру, который явно не обозначен. Например, приведенный выше абстрактный стек можно было бы определить с помощью операций push(x) и pop(), которые работают с единственным существующим стеком. Определения ADT в этом стиле можно легко переписать, чтобы допустить несколько сосуществующих экземпляров ADT, добавив явный параметр экземпляра (например, S в предыдущем примере) к каждой операции, которая использует или изменяет неявный экземпляр.
С другой стороны, некоторые ADT не могут быть осмысленно определены без использования нескольких экземпляров. Это тот случай, когда одна операция принимает в качестве параметров два разных экземпляра ADT. В качестве примера рассмотрите возможность дополнения определения абстрактного стека операцией compare(S, T), которая проверяет, содержат ли стеки S и T одинаковые элементы в одинаковом порядке.
Другой способ определения ADT, более близкий к духу функционального программирования, - это рассмотрение каждого состояния структуры как отдельной сущности. В этом представлении любая операция, изменяющая ADT, моделируется как математическая функция, которая принимает старое состояние в качестве аргумента и возвращает новое состояние как часть результата. В отличие от императивных операций эти функции не имеют побочных эффектов. Следовательно, порядок, в котором они оцениваются, не имеет значения, и одна и та же операция, применяемая к одним и тем же аргументам (включая одни и те же состояния ввода), всегда будет возвращать одни и те же результаты (и состояния вывода).
В функциональном представлении, в частности, нет способа (или необходимости) определять «абстрактную переменную» с семантикой императивных переменных (а именно, с fetchи хранитьопераций). Вместо того, чтобы сохранять значения в переменных, их передают в качестве аргументов функциям.
Например, полное определение абстрактного стека в функциональном стиле может использовать три операции:
В a определения функционального стиля нет необходимости в операции create. Действительно, нет понятия «экземпляр стека». Состояния стека можно рассматривать как потенциальные состояния одной структуры стека, а два состояния стека, которые содержат одинаковые значения в одном порядке, считаются идентичными состояниями. Это представление фактически отражает поведение некоторых конкретных реализаций, таких как связанные списки с хэш-кодами.
Вместо create(), определение абстрактного объекта в функциональном стиле. стек может предполагать наличие специального состояния стека, пустого стека, обозначенного специальным символом, например Λ или «()»; или определите операцию bottom(), которая не принимает аргументов и возвращает это особое состояние стека. Обратите внимание, что аксиомы подразумевают, что
В определении стека в функциональном стиле не требуется предикат empty: вместо этого может проверить, пуст ли стек, проверяя, равен ли он Λ.
Обратите внимание, что эти аксиомы не определяют эффект top(s) или pop(s), если s не является состоянием стека, возвращаемым нажмите. Поскольку pushоставляет стек непустым, эти две операции не определены (следовательно, недопустимы), когда s = Λ. С другой стороны, аксиомы (и отсутствие побочных эффектов) подразумевают, что push(s, x) = push(t, y) тогда и только тогда, когда х = у и s = t.
Как и в некоторых других разделах математики, принято также считать, что состояния стека - это только те состояния, существование которых может быть доказано с помощью аксиом за конечное число шагов. В приведенном выше примере абстрактного стека это правило означает, что каждый стек представляет собой конечную последовательность значений, которая становится пустым стеком (Λ) после конечного числа pops. Сами по себе аксиомы, приведенные выше, не исключают существования бесконечных стеков (которые могут быть выталкиватьвечно, каждый раз приводя к другому состоянию) или круговых стеков (которые возвращаются в то же состояние после конечного числа pops). В частности, они не исключают такие состояния s, что pop(s) = s или push(s, x) = s для некоторого x. Однако, поскольку невозможно получить такие состояния стека с помощью данных операций, предполагается, что они «не существуют».
Помимо поведения в терминах аксиом, в определение операции ADT также можно включить их алгоритмическую сложность. Александр Степанов, разработчик стандартной библиотеки шаблонов C ++ , включил гарантии сложности в спецификацию STL, аргументируя это:
Причина введения понятия абстрактных типов данных заключалась в том, чтобы позволить взаимозаменяемые программные модули. У вас не может быть взаимозаменяемых модулей, если эти модули не имеют аналогичного сложного поведения. Если я заменю один модуль другим модулем с таким же функциональным поведением, но с другими компромиссами сложности, пользователь этого кода будет неприятно удивлен. Я мог бы сказать ему все, что мне нравится об абстракции данных, и он все равно не захотел бы использовать код. Утверждения сложности должны быть частью интерфейса.
— Александр СтепановПреимущества абстрактной типизации данныхИнкапсуляция
Абстракция дает обещание, что любая реализация ADT имеет определенные свойства и способности; знание этого - все, что требуется для использования объекта ADT.
Локализация изменения
Код, использующий объект ADT, не нужно будет редактировать, если реализация ADT изменилась. Поскольку любые изменения в реализации должны по-прежнему соответствовать интерфейсу, и поскольку код, использующий объект ADT, может ссылаться только на свойства и возможности, указанные в интерфейсе, изменения могут быть внесены в реализацию, не требуя каких-либо изменений в коде, в котором используется ADT..
Гибкость
Различные реализации ADT, имеющие все одинаковые свойства и возможности, эквивалентны и могут использоваться в некоторой степени взаимозаменяемо в коде, который использует ADT. Это дает большую гибкость при использовании объектов ADT в различных ситуациях. Например, разные реализации ADT могут быть более эффективными в разных ситуациях; каждый из них можно использовать в той ситуации, в которой они предпочтительны, тем самым повышая общую эффективность.
Типичные операцииНекоторые операции, которые часто указываются для ADT (возможно, под другими именами), это
- compare(s, t), который проверяет, соответствуют ли состояния двух экземпляров эквивалент в некотором смысле;
- hash(s), который вычисляет некоторую стандартную хеш-функцию из состояния экземпляра;
- print(s) или show(s), который создает удобочитаемое представление состояния экземпляра.
В определениях ADT императивного стиля часто можно встретить также
- create(), который создает новый экземпляр ADT;
- инициализировать(s), который подготавливает вновь созданный экземпляр s для дальнейших операций или сбрасывает его в какое-то «начальное состояние»;
- copy(s, t), который помещает экземпляр s в состояние, эквивалентное состоянию t;
- clone(t), которое выполняет s ← create(), copy(s, t) и возвращает s;
- free(s) или destroy(s), который освобождает память и другие ресурсы, используемые s.
Операция freeобычно не актуальна или м многозначительно, поскольку ADT - это теоретические объекты, которые не «используют память». Однако это может быть необходимо, когда нужно проанализировать хранилище, используемое алгоритмом, использующим ADT. В этом случае нужны дополнительные аксиомы, которые определяют, сколько памяти использует каждый экземпляр ADT в зависимости от его состояния, и сколько из нее возвращается в пул бесплатно.
ПримерыНекоторые распространенными ADT, которые оказались полезными в большом количестве приложений, являются
- Контейнер
- Список
- Набор
- Multiset
- Карта
- Multimap
- График
- Дерево
- Стек
- Очередь
- Приоритетная очередь
- Двусторонняя очередь
- Двусторонняя приоритетная очередь
Каждый из этих ADT может быть определен многими способами и вариантами, не обязательно эквивалентными. Например, абстрактный стек может иметь или не иметь операцию count, которая сообщает, сколько элементов было отправлено, но еще не извлечено. Этот выбор имеет значение не только для клиентов, но и для реализации.
- Абстрактный графический тип данных
В 1979 году было предложено расширение ADT для компьютерной графики: абстрактный графический тип данных (AGDT). Его представили Надя Магненат Тельманн и Даниэль Тельманн. AGDT предоставляют преимущества ADT со средствами для структурированного построения графических объектов.
РеализацияРеализация ADT означает предоставление одной процедуры или функции для каждой абстрактной операции. Экземпляры ADT представлены некоторой конкретной структурой данных , которой манипулируют эти процедуры в соответствии со спецификациями ADT.
Обычно есть много способов реализовать один и тот же ADT, используя несколько различных конкретных структур данных. Таким образом, например, абстрактный стек может быть реализован с помощью связанного списка или массива .
. Чтобы клиенты не зависели от реализации, ADT часто упаковывается как непрозрачный тип данных в одном или нескольких модулях , интерфейс которых содержит только сигнатуру (количество и типы параметров и результатов) операций. Реализация модуля, а именно тела процедур и используемая конкретная структура данных, затем может быть скрыта от большинства клиентов модуля. Это позволяет изменить реализацию, не затрагивая клиентов. Если реализация раскрыта, она известна как прозрачный тип данных.
При реализации ADT каждый экземпляр (в определениях императивного стиля) или каждое состояние (в определениях функционального стиля) обычно представлены каким-либо дескриптором .
Современные объектно-ориентированные языки, такие как C ++ и Java, поддерживают абстрактные типы данных. Когда класс используется как тип, это абстрактный тип, который относится к скрытому представлению. В этой модели ADT обычно реализуется как класс, и каждый экземпляр ADT обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций ADT как методы этого класса. Однако такой подход нелегко инкапсулировать несколько вариантов представления, найденных в ADT. Это также может подорвать расширяемость объектно-ориентированных программ. В чисто объектно-ориентированной программе, использующей интерфейсы как типы, типы относятся к поведению, а не к представлениям.
Пример: реализация абстрактного стека
В качестве примера приведем реализацию абстрактного стека выше на языке программирования C.
Интерфейс императивного стиля
Интерфейс императивного стиля может быть таким:
typedef struct stack_Rep stack_Rep; // тип: представление экземпляра стека (непрозрачная запись) typedef stack_Rep * stack_T; // тип: дескриптор экземпляра стека (непрозрачный указатель) typedef void * stack_Item; // тип: значение хранится в стеке экземпляр (произвольный адрес) stack_T stack_create (void); // создает новый пустой экземпляр стека void stack_push (stack_T s, stack_Item x); // добавляет элемент вверху стека stack_Item stack_pop (stack_T s); // удаляет верхний элемент из стека и возвращает его bool stack_empty (stack_T s); // проверяет, пуст ли стекЭтот интерфейс можно использовать следующим образом:
#include// включает интерфейс стека stack_T s = stack_create (); // создает новый экземпляр пустого стека int x = 17; stack_push (s, & x); // добавляет адрес x наверху стека void * y = stack_pop (s); // удаляет адрес x из стека и возвращает его if (stack_empty (s)) {} // что-то делает, если стек пуст Этот интерфейс можно реализовать разными способами. Реализация может быть произвольно неэффективной, поскольку формальное определение ADT, приведенное выше, не указывает, сколько места может использовать стек и сколько времени должна занимать каждая операция. Он также не указывает, продолжает ли состояние стека s существовать после вызова x ← pop(s).
На практике формальное определение должно указывать, что пространство пропорционально количеству элементов, выдвинутых, но еще не извлеченных; и что каждая из вышеперечисленных операций должна завершаться за постоянный промежуток времени, независимо от этого числа. Чтобы соответствовать этим дополнительным спецификациям, реализация может использовать связанный список или массив (с динамическим изменением размера) вместе с двумя целыми числами (количество элементов и размер массива).
Интерфейс функционального стиля
Определения ADT функционального стиля больше подходят для языков функционального программирования, и наоборот. Однако можно предоставить интерфейс функционального стиля даже в императивном языке, таком как C. Например:
typedef struct stack_Rep stack_Rep; // тип: представление состояния стека (непрозрачная запись) typedef stack_Rep * stack_T; // тип: дескриптор состояния стека (непрозрачный указатель) typedef void * stack_Item; // тип: значение состояния стека (произвольный адрес) stack_T stack_empty (void); // возвращает состояние пустого стека stack_T stack_push (stack_T s, stack_Item x); // добавляет элемент наверху состояния стека и возвращает результирующее состояние стека stack_T stack_pop (stack_T s); // удаляет верхний элемент из состояния стека и возвращает результирующее состояние стека stack_Item stack_top (stack_T s); // возвращает верхний элемент состояния стека.Библиотеки ADT
Многие современные языки программирования, такие как C ++ и Java, поставляются со стандартными библиотеками, которые реализуют несколько общих ADT, например перечисленные выше.
Встроенные абстрактные типы данных
Спецификация некоторых языков программирования намеренно нечетко описывает представление определенных встроенных типов данных, определяя только операции, которые могут быть выполнены с ними. Следовательно, эти типы можно рассматривать как «встроенные ADT». Примерами являются массивы на многих языках сценариев, таких как Awk, Lua и Perl, которые можно рассматривать как реализацию абстрактного списка.
См. Также
- Концепция (обобщенное программирование)
- Формальные методы
- Функциональная спецификация
- Обобщенный алгебраический тип данных
- Начальная алгебра
- Принцип подстановки Лискова
- Теория типов
- Стены и зеркала
ПримечанияЦитатыСсылкиДополнительная литература
- Митчелл, Джон К. ; Плоткин, Гордон (июль 1988 г.). «Абстрактные типы имеют экзистенциальный тип» (PDF). Транзакции ACM по языкам и системам программирования. 10(3): 470–502. doi : 10.1145 / 44501.45065.
Внешние ссылки
- СМИ, связанные с абстрактными типами данных на Wikimedia Commons
- Абстрактный тип данных в NIST Словарь алгоритмов и структур данных
