Если Linked List и Array являются фундаментальными структурами данных, то каким типом структуры данных являются дерево, хеш-таблица, куча и т. Д.?

Question

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

Спасибо.

Answer 1

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

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

Но AFIAK, как и многие вещи в компьютерной науке, не формализовано, что математически может означать «фундаментальная структура данных».

Answer 2

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

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

--- n-арное дерево обычно реализуется как серия связанных узлов (например, список), но каждый узел содержит массив дочерних ссылок. Для бинарного дерева вы обычно не видите массив явно, потому что потомкам обычно дают имена слева и справа.

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

--- Наборы, как правило, являются деревьями или хеш-таблицами и, таким образом, транзитивно определяются в терминах массивов и списков

--- Стеки, очереди, векторы и т. Д. - это просто массивы со специальной семантикой.

Я согласен с другими авторами, что у CS на самом деле нет «учебного» определения фундаментальных структур данных, но вы легко можете увидеть, что это «фактическая» правда.

Интересный вопрос, кстати ...

Answer 3

Я бы не согласился. Основным типом данных является массив слов. Это то, что обеспечивают все современные чипы оперативной памяти. Все остальное - абстракция, созданная программами. Связанный список? При этом используется одно слово на узел для «следующего указателя», возможно одно слово для «предыдущего указателя», а затем несколько слов для данных узла. Хеш-таблицы - это еще одна абстракция поверх этого массива слов.

Даже массивы байтов являются абстракцией; они реализуются путем субадресации каждого байта. Это сокращение обычно обеспечивается процессором.

Answer 4

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

Но это интересный вопрос, так как я могу придумать полезные определения. В конце концов, структуры данных, которые мы строим в HLL, построены из что-то . (Простое сокращение всех структур данных до «является языком и платформой Turing-complete» кажется глупым.)

Итак, я могу придумать два разумных использования этого термина:

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

• Он может описывать структуры данных, встроенные в данный язык

Answer 5

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

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

Редактировать: ОК, Java и C ++. Я предполагаю, что все контейнеры библиотеки C ++, такие как Vector и Queue, будут основаны на скромном массиве, но в Java может быть встроено больше типов. Я думаю, это зависит от того, как вы определяете "фундаментальный".