Динамическая структура данных. Что это?

Question

[GreySS]

В требованиях к одной вакансии(junior) Динамическая структура данных.
Цитата из Прата С. 189 стр.: "Инструментом для этого, опять-таки, послужит операция new. С ее помощью можно создавать динамические структуры. Динамические здесь снова означает выделение памяти во время выполнения, а не во время
компиляции. Кстати, поскольку классы очень похожи на структуры, вы сможете использовать изученные приемы как для структур, так и для классов.". С этим ясно. Так же яндексом выводится очень много задач/примеров, где дсд применяется к Стеку. В итоге получаем структуры и стек. Что еще можно отнести к дсд?

Answer 1

[Станислав Макаров]

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

Что еще можно отнести к дсд?

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

Так же яндексом выводится очень много задач/примеров, где дсд применяется к Стеку. В итоге получаем структуры и стек.

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

Comments

[abcd0x00]

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

[Станислав Макаров]

abcd0x00 вы понимаете, что я придерживаюсь цитаты из книги?) Я могу дать наверное штук 5 разных определений динамичности применительно к структуре данных, говоря о работе со стеком процессора/кучей C++, о переменности числа элементов, об известном или неизвестном во время компиляции размере структуры и так далее. Но что человеку моё определение, если он по Прата читает, и там написано "Динамические здесь снова означает выделение памяти во время выполнения, а не во время компиляции.". Очевидно, у утверждения есть контекст)

[abcd0x00]

Станислав Макаров: а почему динамическая память называется динамической памятью? Наверное, просто так из космоса идея прилетела. Есть два противоположных значения: статическое и динамическое. Вот берёшь массив элементов - это статическая структура данных (в языках через массив реализуют вектор, он так и называется - вектор, а вектор уже из математики берётся как понятие). А если в массиве элементов количество элементов может меняться, то это динамический вектор. И вот его обычно реализуют отдельно.

И вот в книжке по C++ тебе могут написать что-то про вектор (про vector), но фактически это динамический вектор, потому что вектор реализован в C++ через массив элементов.

Answer 2

[Mercury13]

Инструментом для этого, опять-таки, послужит операция new.

Это и есть критерий ДСД. Всё, где используется динамическая память,— динамическая структура данных.

Так же яндексом выводится очень много задач/примеров, где дсд применяется к Стеку. В итоге получаем структуры и стек.

Почему только?
По организации: одиночный объект, массив, разные виды деревьев, связанный список и комбинации всего этого…
По семантике: одиночный объект, индексный массив, ассоциативный массив, список, стек, очередь, pimpl (указатель на реализацию), динамическая строка…
Например, ассоциативный массив (семантика) можно реализовать как дерево поиска (двоичное дерево), а можно как хэш-таблицу (расширяемый динамический массив + куча связанных списков).
Очередь (семантика) может быть кольцевым списком (динамический массив, возможно, расширяемый), может — расширяемым массивом из динамических массивов (так работает std::deque из C++), может — связанным списком.
Стандартный подход к строке — динамический массив. Но что делать, если мы, например, клеим и клеим к строке что-то в конец? Или пишем текстовый редактор, где можно вписывать текст в середину? Тоже хитрые структуры.
Задача Яндекса — проверить испытуемого за несколько минут. Сложную задачу вряд ли за это время разгрызёшь. Потому и любят простые структуры данных.

Answer 3

[abcd0x00]

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

Стек, очередь, дек, последовательность, множество, нагруженное множество, Л1-список, Л2-список, динамический вектор, дерево, хеш-таблица и другие - это всё динамические структуры данных.

А вот просто вектор, матрица - это нединамические структуры данных, потому что количество элементов в них фиксировано.