Абстрактный тип данных и структура данных

Мне довольно сложно понять эти термины. Я искал в Google и прочитал немного в Википедии, но я все еще не уверен. Я определил, что:

Абстрактный тип данных - это определение нового типа, описываются его свойства и операции.

Структура данных - это реализация ADT. Многие ADT могут быть реализованы как одна и та же структура данных.

Если я не ошибаюсь, массив как ADT означает набор элементов и как структуру данных, как она хранится в памяти. Стек - это ADT с операциями push, pop, но можем ли мы сказать о структуре данных стека, если я имею в виду, что в своем алгоритме я использовал стек, реализованный в виде массива? И почему куча не ADT? Это может быть реализовано в виде дерева или массива.

Проще говоря, ADT (абстрактный тип данных) - это скорее логическое описание, а структура данных - конкретная.

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

Структура данных - это реальная, конкретная вещь . Это может быть реализовано и использовано в алгоритме.

ADT для интерфейса ( что он делает ), как структура данных для класса ( как он это делает ).

Несколько примеров:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Я думаю, вы поняли.

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

Основное различие между абстрактным типом данных (ADT) и конкретным типом данных заключается в том, что последние позволяют нам смотреть на конкретное представление, тогда как первые скрывают представление от нас. ADT может быть чистым ADT или обновляемым ADT. Чистый ADT - это тот, в котором все операции являются чистыми функциями. Это означает, что операции не имеют побочных эффектов. В частности, они не изменяют и не обновляют входные аргументы. Они просто используют эти аргументы для генерации вывода, которые являются свежими значениями ADT (или других типов). Большинство конкретных типов чистые. Например, никакая операция над целыми числами фактически не изменяет целое число. Вместо этого все операции, такие как «+», производят новые выходные данные.

Обновляемый ADT - это тот, где некоторые операции фактически изменяют значения ADT. Например, предположим, у нас была операция с именем pop, которая взяла стек в качестве аргумента и изменила его. («На месте», «разрушительно»), удалив элемент с наивысшим приоритетом. Эта операция будет считаться нечистой, и тогда весь ADT будет нечистым. ADT может быть пользовательским ADT.

Мы знаем, что абстрактный тип данных - это тип данных, который удовлетворяет следующим двум условиям:

1. Представление или определение типа и операций содержатся в одной синтаксической единице.

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

Пользовательский абстрактный тип данных должен обеспечивать:

1. Определение типа, которое позволяет программным модулям объявлять переменные типа, но скрывает представление этих переменных.

2. Набор операций для манипулирования объектами типа.

Примером определенного пользователем абстрактного типа данных является структура. «C» предоставляет четыре основных типа: int, char, float и double. Тем не менее, «C» также предоставляет программисту возможность определять свои собственные типы. Структура является одним из таких примеров. Структура представляет собой совокупность различных частей, где каждая часть имеет некоторый существующий тип.

struct abc

{int x;

float y;

};

Приведенное выше определение структуры не создает никаких переменных, а создает новый тип. Переменные этого типа могут создаваться аналогично переменным встроенного типа.

struct abc a;

Ключевое слово typedef позволяет нам создавать новые имена типов для наших новых типов.

Например:

typedef struct abc AB;

где AB - это имя нового типа, которое теперь можно использовать для создания новых типов.

AB b;

Структуры данных. Ниже приведены характерные особенности структур данных:

1. Он содержит элементы данных компонента, которые могут быть атомарными или другой структурой данных (все еще домен).

2. Набор операций над одним или несколькими компонентами.

3. Определяет правила относительно того, как компоненты связаны друг с другом и со структурой в целом (утверждения).

Структуры данных:

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

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

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

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

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

Я думаю, что настоящая путаница возникает, когда кто-то называет свои DS как ADT, например, некоторые люди будут называть свои вышеупомянутые DS как «Словарь» вместо DictImplementation, что совершенно законно, это просто вызывает некоторую путаницу.

Ссылка: Skiena: Руководство по разработке алгоритма