Что такое ADT? (Абстрактный тип данных)

Question

В настоящее время я изучаю абстрактные типы данных (ADT), но я не понимаю концепцию вообще. Может кто-нибудь объяснить мне, что это на самом деле? И что такое коллекция, сумка и список ADT? простыми словами?

Answer 1

Абстрактный тип данных (ADT) - это тип данных, в котором определяется только поведение, но не реализация.

Противоположностью ADT является Конкретный тип данных (CDT), где он содержит реализацию ADT.

Примеры:
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector являются ADT. Каждый из этих ADT имеет много реализаций, т.е. CDT. Контейнер - это ADT высокого уровня, прежде всего ADT.

Пример из реальной жизни:
Book is Abstract (Телефонная книга является реализацией)

Answer 2

В статье Википедии о типе данных Abstact есть, что сказать.

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

В более конкретном плане, вы можете взять Java List интерфейс в качестве примера. Интерфейс явно не определяет какое-либо поведение, потому что нет конкретного List учебный класс. Интерфейс определяет только набор методов, которые другие классы (например, ArrayList а также LinkedList) необходимо реализовать, чтобы считаться List,

Коллекция - это еще один абстрактный тип данных. В случае с Java Collection интерфейс, это даже более абстрактный, чем List, поскольку

List интерфейс помещает дополнительные условия, помимо указанных в Collection интерфейс, на контрактах iterator, add, remove, equals, а также hashCode методы.

Сумка также называется мультимножеством.

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

В Java Bag - это коллекция, которая реализует очень простой интерфейс. Вам нужно только иметь возможность добавлять предметы в сумку, проверять ее размер и перебирать предметы, которые в ней содержатся. См. Bag.java для примера реализации (из 4-го издания Sedgewick & Wayne's Algorithms).

Answer 3

Обозначение абстрактного типа данных (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 вводит определения значений, а ключевое слово условие используется для указания любых условий для вновь определенного типа данных. В этом определении условие указывает, что знаменатель не может быть 0. Условие определения требуется, но условие может быть необязательным для каждого ADT.

2) Определение оператора:-

Каждый оператор определяется как абстрактный узел из трех частей.

1) Заголовок

2) Необязательные предварительные условия

3) Дополнительные постусловия

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

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 относится к любому классу, который реализует интерфейс коллекции. Коллекция в общем смысле - это просто группа объектов.

Имидж коллекций

Answer 4

Одно из самых простых объяснений, приведенных на вики-странице Brilliant:

Абстрактные типы данных, обычно сокращенно ADT, представляют собой способ классификации структур данных на основе того, как они используются, и поведения, которое они обеспечивают. Они не определяют, как структура данных должна быть реализована или размещена в памяти, а просто предоставляют минимальный ожидаемый интерфейс и набор поведений. Например, стек - это абстрактный тип данных, который определяет линейную структуру данных с поведением LIFO (последний пришел, первый ушел). Стеки обычно реализуются с использованием массивов или связанных списков, но излишне сложная реализация с использованием двоичного дерева поиска по-прежнему является допустимой реализацией. Чтобы было ясно, неправильно говорить, что стеки являются массивами или наоборот. Массив можно использовать как стек. Точно так же стек может быть реализован с использованием массива.

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

Пример для ADT: List - может быть реализован с использованием Array и LinkedList, Queue, Deque, Stack, Associative array, Set.

https://brilliant.org/wiki/abstract-data-types/?subtopic=types-and-data-structures&chapter=abstract-data-types

Answer 5

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

Answer 6

Фактически абстрактные типы данных:

• Концепции или теоретическая модель, логически определяющая тип данных
• Задает набор данных и набор операций, которые могут быть выполнены с этими данными.
• Ничего не сказано о том, как будут реализованы операции
• "Существовать как идея, но не иметь физической идеи"

Например, давайте посмотрим спецификации некоторых абстрактных типов данных,

1. Список абстрактных типов данных: initialize(), get (), insert(), remove () и т. Д.
2. Тип абстрактных данных стека: push(), pop(), peek(), isEmpty(), isNull () и т. Д.
3. Абстрактный тип данных очереди: enqueue(), dequeue(), size(), peek () и т. Д.

Answer 7

ADT - это набор значений данных и связанных операций, которые точно не зависят от какой-либо конкретной реализации. Сила ADT в том, что реализация скрыта от пользователя. Объявляется только интерфейс. Это означает, что ADT имеет различные способы.

Answer 8

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

Answer 9

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

Answer 10

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

Чтобы упростить процесс решения проблем, мы объединяем структуры данных с их операциями и называем это "абстрактный тип данных". (АТД).

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

ADT состоят из двух типов:

1. Декларация данных.

2. Декларация об операции.

Answer 11

Просто абстрактный тип данных - это не что иное, как набор операций, а набор данных используется для эффективного хранения некоторых других данных в машине. Нет необходимости в каком-либо объявлении перикулярного типа. Это просто требует внедрения ADT.

Answer 12

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

Answer 13

ADT - это тип данных, в котором сбор данных и операции работают с этими данными. Он больше фокусируется на концепции, чем на реализации. Вам решать, какой язык вы будете использовать, чтобы сделать его видимым на земле. Пример: Стек - это ADT, а массив - это не Stack, потому что мы можем реализовать его на многих языках, Python c C++ java и многие другие, в то время как массив построен в типе данных

Answer 14

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

Answer 15

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

из кода завершено 2 книга

Answer 16

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

Аналогичным образом ADT дает вам обзор типов данных: что они / могут быть сохранены и какие операции вы можете выполнять с этими типами данных. Но в нем не говорится, как это реализовать. Это ADT. Он только определяет логическую форму ваших типов данных.

Другая аналогия: в машине или велосипеде вы знаете, только когда вы нажимаете на тормоз, ваше транспортное средство останавливается. Но знаете ли вы, как байк останавливается при нажатии на тормоз ??? Нет, это означает, что детали реализации скрыты. Вы знаете только, что делает тормоз, когда вы нажимаете, но не знаете, как это происходит.

Answer 17

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

https://runestone.academy/runestone/books/published/pythonds/Introduction/WhyStudyDataStructuresandAbstractDataTypes.html

Answer 18

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

Answer 19

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

Answer 20

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

1. Декларация данных.
2. Декларация об операции.

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

Answer 21

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

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