В настоящее время я изучаю абстрактные типы данных (ADT), но я вообще не понимаю концепции. Может кто-нибудь объяснить мне, что это на самом деле? Также что такое сбор, сумка и список ADT? простыми словами?
Что такое ADT? (Абстрактный тип данных)
Ответы (20)
Абстрактный тип данных (ADT) - это тип данных, в котором определяется только поведение, но не реализация.
Напротив ADT находится конкретный тип данных (CDT), где он содержит реализацию ADT.
Примеры: Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector
- ADT. Каждый из этих ADT имеет множество реализаций, например CDT. Контейнер - это ADT высокого уровня, прежде всего, из всех ADT.
Пример из реальной жизни:
книга является абстрактной (телефонная книга - это реализация)
В статье Википедии Тип данных Abstact есть что сказать.
В информатике абстрактный тип данных (ADT) - это математическая модель для определенного класса структур данных, которые имеют схожее поведение; или для определенных типов данных одного или нескольких языков программирования, которые имеют аналогичную семантику. Абстрактный тип данных определяется косвенно, только операциями, которые могут быть выполнены с ним, и математическими ограничениями на эффекты (и, возможно, стоимость) этих операций.
Говоря несколько более конкретно, вы можете взять _1 _ интерфейс в качестве примера. Интерфейс вообще не определяет явно какое-либо поведение, потому что нет конкретного List
класса. Интерфейс определяет только набор методов, которые другие классы (например, ArrayList
и LinkedList
) должны реализовать, чтобы считаться List
.
Коллекция - еще один абстрактный тип данных. В случае интерфейса Java Collection
это даже более абстрактно, чем List
, поскольку
Интерфейс
List
налагает дополнительные условия, помимо тех, которые указаны в интерфейсеCollection
, на контракты методовiterator
,add
,remove
,equals
иhashCode
.
Пакет также известен как мультимножество.
В математике понятие мультимножества (или мешка) является обобщением понятия множества, в котором членам разрешено появляться более одного раза. Например, существует уникальный набор, который содержит элементы a и b и никаких других, но есть много мультимножеств с этим свойством, например мультимножество, которое содержит две копии a и одну из b, или мультимножество, которое содержит три копии оба а и Б.
В Java Bag будет коллекцией, реализующей очень простой интерфейс. Вам нужно только иметь возможность добавлять предметы в сумку, проверять ее размер и перебирать элементы, которые она содержит. См. Bag.java для примера реализации (из 4-е издание алгоритмов).
По-настоящему абстрактный тип данных описывает свойства своих экземпляров без привязки к их представлению или конкретным операциям. Например, абстрактный (математический) тип Integer - это дискретный, неограниченный, линейно упорядоченный набор экземпляров. Конкретный тип дает конкретное представление для экземпляров и реализует определенный набор операций.
Фактически абстрактные типы данных:
- Концепции или теоретическая модель, логически определяющая тип данных
- Определяет набор данных и набор операций, которые могут быть выполнены с этими данными.
- Ничего не сказано о том, как будут реализованы операции
- Существуют как идея, но не имеют физической идеи
Например, давайте посмотрим спецификации некоторых абстрактных типов данных,
- Список абстрактных типов данных: initialize (), get (), insert (), remove () и т. Д.
- Тип абстрактных данных стека: push (), pop (), peek (), isEmpty (), isNull () и т. Д.
- Абстрактный тип данных очереди: enqueue (), dequeue (), size (), peek () и т. Д.
Одно из простейших объяснений, приведенных на вики-странице Brilliant:
Абстрактные типы данных, обычно сокращенно ADT, представляют собой способ классификации структур данных на основе того, как они используются и поведения, которое они обеспечивают. Они не определяют, как структура данных должна быть реализована или размещена в памяти, а просто предоставляют минимальный ожидаемый интерфейс и набор поведений. Например, стек - это абстрактный тип данных, который определяет линейную структуру данных с поведением LIFO (последний пришел, первый ушел). Стеки обычно реализуются с использованием массивов или связанных списков, но излишне сложная реализация с использованием двоичного дерева поиска по-прежнему является допустимой реализацией. Чтобы было ясно, неправильно говорить, что стеки являются массивами или наоборот. Массив можно использовать как стек. Точно так же стек может быть реализован с использованием массива.
Поскольку абстрактные типы данных не определяют реализацию, это означает, что также неправильно говорить о временной сложности данного абстрактного типа данных. Ассоциативный массив может иметь среднее время поиска O (1), а может и не иметь. Ассоциативный массив, реализованный с помощью хеш-таблицы, имеет среднее время поиска O (1).
Пример для ADT: List - может быть реализован с использованием Array и LinkedList, Queue, Deque, Stack, Associative array, Set.
ADT - это набор значений данных и связанных операций, которые совершенно не зависят от какой-либо конкретной реализации. Сильная сторона ADT заключается в том, что реализация скрыта от пользователя. Объявлен только интерфейс. Это означает, что ADT может использоваться различными способами.
Абстрактный тип данных - это математический модуль, который включает данные с различными операциями. Детали реализации скрыты, поэтому она называется абстрактной. Абстракция позволила вам организовать сложность задачи, сосредоточив внимание на логических свойствах данных и действий.
В языках программирования тип - это некоторые данные и связанные с ними операции. ADT - это определяемая пользователем совокупность данных и операции над этими данными, которая характеризуется инкапсуляцией, данные и операции представлены или в объявленном списке в единой синтаксической единице и информации скрытие, пользователю ADT, интерфейса ADT, видны только соответствующие операции, точно так же, как и обычный тип данных в языке программирования. Это абстракция, потому что внутреннее представление данных и реализация операций не имеют значения для пользователя ADT.
Обозначение абстрактного типа данных (ADT)
Абстрактный тип данных можно определить как математическую модель с набором определенных на ней операций. Простым примером является набор целых чисел вместе с операциями объединения, пересечения, определенными на множестве.
ADT являются обобщениями примитивного типа данных (целое число, символ и т. Д.), И они инкапсулируют тип данных в том смысле, что определение типа и все операции с этим типом локализованы в одном разделе программы. Они рассматриваются как примитивный тип данных за пределами раздела, в котором определены ADT и его операции.
Реализация ADT - это перевод в операторы языка программирования объявления, которое определяет переменную как принадлежащую этому ADT, а также процедуру на этом языке для каждой операции. этого ADT. Реализация ADT выбирает структуру данных для представления ADT.
Полезным инструментом для определения логических свойств типа данных является абстрактный тип данных. По сути, тип данных - это набор значений и набор операций с этими значениями. Этот набор и эти операции образуют математическую конструкцию, которая может быть реализована с использованием конкретной структуры данных аппаратного и программного обеспечения. Термин «абстрактный тип данных» относится к основной математической концепции, определяющей тип данных.
Определяя абстрактный тип данных как математическое понятие, мы не заботимся об эффективности пространства или времени. Это проблема реализации. Фактически, определение ADT вообще не связано с деталями реализации. Может оказаться невозможным даже реализовать конкретный ADT на конкретном оборудовании или с помощью определенной программной системы. Например, мы уже видели, что целое число ADT не является универсальным.
Чтобы проиллюстрировать концепцию ADT и моего метода спецификации, рассмотрим ADT RATIONAL, который соответствует математической концепции рационального числа. Рациональное число - это число, которое можно выразить как частное двух целых чисел. Операции с рациональными числами, которые мы определяем, - это создание рационального числа из двух целых чисел, сложение, умножение и проверка на равенство. Ниже приводится начальная спецификация этого ADT.
/* Value defination */
abstract typedef <integer, integer> RATIONAL;
condition RATIONAL [1]!=0;
/*Operator defination*/
abstract RATIONAL makerational (a,b)
int a,b;
preconditon b!=0;
postcondition makerational [0] =a;
makerational [1] =b;
abstract RATIONAL add [a,b]
RATIONAL a,b;
postcondition add[1] = = a[1] * b[1]
add[0] = a[0]*b[1]+b[0]*a[1]
abstract RATIONAL mult [a, b]
RATIONAL a,b;
postcondition mult[0] = = a[0]*b[a]
mult[1] = = a[1]*b[1]
abstract equal (a,b)
RATIONAL a,b;
postcondition equal = = |a[0] * b[1] = = b[0] * a[1];
ADT состоит из двух частей: -
1) Определение значения
2) Определение операции
1) Определение значения: -
Определение значения определяет набор значений для ADT и состоит из двух частей:
1) Пункт определения
2) Условие
Например, определение значения для ADT RATIONAL гласит, что значение RATIONAL состоит из двух целых чисел, второе из которых не равно 0.
Ключевое слово abstract typedef вводит определения значений, а ключевое слово condition используется для указания любых условий для вновь определенного типа данных. В этом определении условие указывает, что знаменатель не может быть равен 0. Пункт определения является обязательным, но условие может быть необязательным для каждого ADT.
2) Определение оператора: -
Каждый оператор определяется как абстрактное соединение из трех частей.
1) Заголовок
2) Необязательные предварительные условия
3) Необязательные постусловия
Например, определение оператора ADT RATIONAL включает в себя операции создания (создание), сложение (сложение) и умножение (mult), а также проверку на равенство (равно). Давайте сначала рассмотрим спецификацию умножения, так как она самая простая. Он содержит заголовок и пост-условия, но без предварительных условий.
abstract RATIONAL mult [a,b]
RATIONAL a,b;
postcondition mult[0] = a[0]*b[0]
mult[1] = a[1]*b[1]
Заголовок этого определения - это первые две строки, которые похожи на заголовок функции C. Ключевое слово abstract указывает, что это не функция C, а определение оператора ADT.
Постусловие указывает, что делает операция. В постусловии имя функции (в данном случае mult) используется для обозначения результата операции. Таким образом, mult [0] представляет числитель результата, а mult 1 представляет знаменатель результат. То есть указывает, какие условия выполняются после выполнения операции. В этом примере постусловие указывает, что неумератор результата рационального умножения равен целому произведению числителей двух входных данных, а знаменатель равен целому произведению двух знаменателей.
Список
В информатике список или последовательность - это абстрактный тип данных, который представляет собой счетное количество упорядоченных значений, где одно и то же значение может встречаться более одного раза. Экземпляр списка - это компьютерное представление математической концепции конечной последовательности; (потенциально) бесконечный аналог списка - это поток. Списки являются основным примером контейнеров, поскольку они содержат другие значения. Если одно и то же значение встречается несколько раз, каждое вхождение считается отдельным элементом.
Список имен также используется для нескольких конкретных структур данных, которые можно использовать для реализации абстрактных списков, особенно связанных списков.
Изображение списка
Сумка
Сумка - это набор объектов, из которого вы можете добавлять объекты в сумку, но не можете удалить их после добавления в сумку. Таким образом, с помощью структуры данных пакета вы можете собрать все объекты, а затем перебрать их. Когда вы программируете на Java, у вас все в порядке.
Изображение сумки
Коллекция
Коллекция в смысле Java относится к любому классу, реализующему интерфейс Collection. Коллекция в общем смысле - это просто группа объектов.
Изображение коллекций
Прежде чем определять абстрактные типы данных, давайте рассмотрим различные представления о типах данных, определенных системой. Все мы знаем, что по умолчанию все примитивные типы данных (int, float и т. Д.) Поддерживают базовые операции, такие как сложение и вычитание. Система предоставляет реализации для примитивных типов данных. Для определяемых пользователем типов данных нам также необходимо определить операции. Реализация этих операций может быть осуществлена тогда, когда мы действительно хотим их использовать. Это означает, что обычно определяемые пользователем типы данных определяются вместе с их операциями.
Чтобы упростить процесс решения проблем, мы объединяем структуры данных с их операциями и называем этот «абстрактный тип данных». (ADT).
Обычно используемые ADT'ы включают: связанный список, стеки, очереди, двоичное дерево, словари, непересекающиеся множества (объединение и поиск), хеш-таблицы и многие другие.
ADT бывают двух типов:
1. Объявление данных.
2. Декларация об эксплуатации.
Простой абстрактный тип данных - это не что иное, как набор операций, и набор данных используется для эффективного хранения некоторых других данных в машине. Нет необходимости в объявлении какого-либо специального типа. Это просто требует реализации ADT.
Для решения проблем мы объединяем структуру данных с их операциями. ADT состоит из двух частей:
- Объявление данных.
- Декларация об эксплуатации.
Обычно используемые ADT - это связанные списки, стеки, очереди, очереди приоритетов, деревья и т. Д. При определении ADT нам не нужно беспокоиться о деталях реализации. Они появляются на экране только тогда, когда мы хотим их использовать.
Абстрактный тип данных подобен определяемому пользователем типу данных, с которым мы можем выполнять функции, не зная, что находится внутри типа данных и как с ними выполняются операции. Поскольку информация не разглашается, то она абстрагируется. например. Список, массив, стек, очередь. В Stack мы можем выполнять такие функции, как Push, Pop, но мы не уверены, как это реализовано за кулисами.
ADT - это набор объектов и операций, и нигде в определениях ADT нет упоминания о том, как этот набор операций реализован. Программистам, которые используют коллекции, нужно только знать, как создавать экземпляры и получать доступ к данным некоторым заранее определенным образом, не беспокоясь о деталях реализации коллекций. Другими словами, с точки зрения пользователя, коллекция является абстракцией, и по этой причине в информатике некоторые коллекции называются абстрактными типами данных (ADT). Пользователь озабочен только изучением его интерфейса или набора операций, которые он выполняет ... еще
Проще говоря: абстрактный тип данных - это набор данных и операций, которые работают с этими данными. Эти операции описывают данные для остальной части программы и позволяют остальной части программы изменять данные. Слово «данные» в «абстрактном типе данных» используется нечетко. ADT может быть графическим окном со всеми затрагивающими его операциями, файловыми и файловыми операциями, таблицей страховых ставок и операциями с ней или чем-то еще.
из кода закончите 2 книги
Абстрактный тип данных - это набор значений и любые операции над этими значениями. Например, поскольку String не является примитивным типом данных, мы можем включить его в абстрактные типы данных.
ADT - это тип данных, в котором сбор данных и операции работают с этими данными. Он фокусируется больше на концепции, чем на реализации. Вам решать, какой язык вы используете, чтобы сделать его видимым на земле. Пример: Стек - это ADT, а массив - это не Stack, потому что мы можем реализовать его на многих языках, Python c c ++ java и многие другие, в то время как массив построен в типе данных
Абстрактный тип данных, иногда сокращенно ADT, представляет собой логическое описание того, как мы просматриваем данные и операции, которые разрешены, независимо от того, как они будут реализованы. Это означает, что нас интересует только то, что данные представляют, а не то, как они в конечном итоге будут построены.
Абстракции предоставляют вам только информацию (служебную информацию), но не реализацию. Например: когда вы идете снимать деньги в банкомате, вы просто знаете одну вещь: вставьте свою карту банкомата в автомат, нажмите опцию снятия, введите сумму, и ваши деньги исчезнут, если есть деньги. Это только то, что вы знаете о банкоматах. Но знаете ли вы, как вы получаете деньги ?? Какая бизнес-логика творится за этим? Какая база данных вызывается? Какой сервер в каком месте вызывается ?? Нет, вы знаете только служебную информацию, т.е. вы можете снимать деньги. Это абстракция.
Аналогичным образом ADT дает вам обзор типов данных: что они / могут быть сохранены и какие операции вы можете выполнять с этими типами данных. Но не объясняется, как это реализовать. Это ADT. Он только определяет логическую форму ваших типов данных.
Другая аналогия: в автомобиле или велосипеде вы знаете, только когда вы нажимаете на тормоз, ваше транспортное средство останавливается. Но знаете ли вы, как байк останавливается при нажатии на тормоз ??? Нет, это означает, что детали реализации скрыты. Вы знаете только, что делает тормоз, когда вы нажимаете, но не знаете, как это происходит.
Термин «тип данных» означает тип данных, которые может содержать конкретная переменная - это может быть целое число, символ, число с плавающей запятой или любой диапазон простого представления хранилища данных. Однако, когда мы строим объектно-ориентированную систему, мы используем другие типы данных, известные как абстрактный тип данных, которые представляют более реалистичные сущности.
Например: нас может заинтересовать представление типа данных «банковский счет», который описывает, как все банковские счета обрабатываются в программе. Абстракция - это снижение сложности, игнорирование ненужных деталей.