Есть ли разница между "структурой данных" и "типом данных"?

Два вопроса, которые часто появляются на экзамене Uni, где я изучаю, - это:

Определить типы данных. Классифицировать и объяснять типы данных Определить структуры данных. Классификация и объяснение структур данных

Как бы то ни было, они не то же самое?
Подумайте, что вы делаете Tree<E> в Java. Вы объявили бы свой класс для Tree<E>, добавили бы к нему методы и где-то вы сделали бы Tree<String> myTree = new Tree<>();, чтобы создать объект дерева.

Структура данных ваших данных теперь является типом данных.
Скажем, если вас задали вопрос: Какой тип переменной myTree? Ответ будет Tree<E>. Теперь ваша структура данных является типом данных.

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

Это мое понимание. Является ли понимание неправильным?

Ответ 1

Я хотел бы исправить следующее: вы создали класс, называемый "Дерево" и объект, называемый "myTree", а не переменная называется "myTree" datatype "Дерево". Это разные вещи.

Ниже приведено определение типа данных:

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

Теперь согласно Википедии существуют различные определения типа "type" в типе данных.

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

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

Также написано, что:

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

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

Что касается структур данных:

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

Многие учебники используют эти слова взаимозаменяемо. С более сложными типами это может привести к путанице.

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

Другой пример: существует так много деревьев, как b-tree, дерево двоичного поиска, дерево AA и т.д. Все они по существу относятся к типу дерева, но каждый из них имеет собственную структуру данных.

Обратитесь: Список структур данных для огромного списка доступных структур.

Ответ 2

Различие между абстрактными и конкретными структурами данных. Некоторые учебники CS относятся к абстрактным структурам данных как к "типам данных", что запутывает, поскольку не все типы данных являются структурами данных. Они используют "структуру данных", чтобы конкретно обозначать конкретную структуру данных.

Абстрактная структура данных, также называемая абстрактным типом данных, является интерфейсом структуры данных. Java часто представляет их с использованием интерфейсов; примеры: List, Queue, Map, Deque, Set. (Но есть и другие, не представленные на Java, такие как сумки/мультимножества, мультиплексы, графики, стеки и очереди приоритетов.) Они отличаются поведением и тем, как вы используете структуру данных. Например, набор характеризуется запрещением дубликатов, а не порядком записи, тогда как список позволяет дублировать и запоминать заказ. Очередь имеет ограниченный интерфейс, который позволяет добавлять только один конец и удалять из другого.

Конкретная структура данных представляет собой реализацию абстрактной структуры данных. Примерами являются ArrayList и LinkedList. Это и реализация списков; в то время как их интерфейс списка тот же, программист может по-прежнему заботиться о своих различных характеристиках производительности. Обратите внимание, что LinkedList также реализует Queue.

Ответ 3

Кроме того, существуют структуры данных в языках программирования, которые не имеют системы типов. Например, вы можете modell a Map в LISP или иметь словарь в Python. Было бы неверно говорить о типе здесь, так как тип ИМХО имеет смысл только в отношении некоторой системы типов или как абстрактное понятие, такое как "совокупность всех значений, которые населяют t".

Итак, кажется, что data structure имеет коннотацию конкретной реализации некоторого абстрактного типа. Если мы говорим о каком-либо объекте на языке программирования с системой типов OTOH, мы, вероятно, сказали бы, что "у него есть тип XY".