В чем разница между абстрактным типом данных и логической структурой данных?

Мне трудно провести различие между абстрактным типом данных (ADT) и логической структурой данных (LDS). Единственная разница, о которой я могу думать, заключается в том, что ADT имеют определенные операции, тогда как LDS больше о том, как хранятся данные. Но стек может быть ADT, поскольку мы знаем, какие операции должны быть запрещены, чтобы называть что-то «стеком», а также его можно назвать LDT, поскольку мы знаем, как данные должны быть «структурированы», чтобы называть это «стеком». '. И ADT, и LDS являются «абстрактными» в том смысле, что мы не говорим о том, как они реализованы. Так правильно ли, что ADT и LDS — это разные названия одного и того же, но в зависимости от того, откуда мы родом, мы можем называть это ADT или LDS?

Сравнение структур данных: Массивы и объекты в Javascript
Сравнение структур данных: Массивы и объекты в Javascript
Итак, вы изучили основы JavaScript и хотите перейти к изучению структур данных. Мотивация для изучения/понимания Структур данных может быть разной,...
1
0
18
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Абстрактный тип данных (ADT) — это математическая модель вместе с некоторыми операциями, которые выполняются с этой моделью. Например, АТД стека состоит из последовательности целых чисел (скажем) вместе с операциями push, pop, isempty, makeemptystack и top. ADT похож на интерфейс в Java и является спецификацией. Структуры данных о том, как эти спецификации реализованы. Например, операции АТД стека могут быть реализованы с использованием структуры данных массива или структуры данных связанного списка. АТД очереди может быть реализован с использованием структуры данных кругового массива таким образом, что все операции АТД могут выполняться за время O(1).

В реальной задаче вы столкнулись бы только с подмножеством возможных операций, составляющих ваш АТД, и вам нужно найти структуру данных, которая эффективно реализовывала бы именно это подмножество операций. Например, в некоторых приложениях вы хотите поддерживать набор целых чисел, и единственные операции, которые вы будете выполнять с этим набором, — это найти значение наименьшего элемента в наборе, удалить наименьший элемент в наборе и вставить новый элемент в набор. (Приложения включают алгоритм кратчайшего пути Дейкстры, алгоритм минимального остовного дерева Прима и кодирование Хаффмана.) Набор с этими тремя операциями MIN, EXTRACTMIN и INSERT определяет ADT очереди с минимальным приоритетом. Структура данных, которая может эффективно реализовать все эти три операции — за время O(log n) — это minheap. Другие структуры данных, такие как связанные списки, несортированные массивы, отсортированные массивы, потребовали бы O(n) времени для одной или нескольких из этих операций и, следовательно, менее эффективны для этого конкретного АТД.

Другие вопросы по теме