- 0
Фундаментальные структуры данных
В процессе изучения нового языка столкнулся с совершенно новыми для себя структурами данных. В попытках понять окончательно запутался.
Разъясните, что представляет из себя каждая из структур, без привязки к конкретному языку. И чем они отличаются друг от друга.
- Список
- Массив
- Вектор
- Хэш-таблица
Может какие забыл?
3 ответа:
-
- 2
Позволю себе уточнить коллегу.
Список - собственно связь элементов любого типа, в том числе и списков. Списки бывают односвязные, двусвязные и многосвязные (когда помимо предыдущего и следующего добавляются, к примеру, наследник и родитель). Иными словами - нет связи - нет списка, см. Массив. Доступ к спискам последовательный, в отличие от массива. Соответственно быстродействие по доступу O(n), в то время как у массива O(1).
Хеш-табличку легче всего себе представить как массив значений "ключ = значение", где ключ (внимание) является а) уникальным для всего пространства ключей данной таблицы, б) является хешируемым в математическом смысле, т.е. в реальности каждому ключу (если он уже сам по себе не хэш) приводится в соответствие некоторое число, причём операция ключ -> число всегда даёт один и тот же результат, обратное строго говря неверно. Порядок элементов в хеш-табличке зависит от внутренней реализации и не может быть предсказан (не зная алгоритма реализации, понятное дело).
Вектор в С++ понимании не просто массив, а массив с автоматическим аллокатором.
-
- 0
массив - упорядоченное множество однотипных элементов, с доступом к элементу по его индексу (номеру);
список - в общем случае - набор элементов любого типа, в том числе и списков. Связный список - упорядоченный список, в котором каждый элемент хранит ссылку на следующий и/или предыдущий элемент списка.
хэш-таблица - одна из возможных реализаций ассоциативного массива. То есть массива, обращение к элементам в котором может быть не по целочисленному индексу, а по индексу любого типа, строковому, например;
вектор - смотря что имеется ввиду. Вектор, который std::vector в C++ - фактически обычный массив. А если имеется ввиду вектор в математическом смысле - то это 2х, 3х или 4х-мерный массив, для которого определены соответствующие математические операции.
Как-то так вкратце. Вики в помощь.
-
- 0
Рекомендую почитать Никлауса Вирта "Алгоритмы и структуры данных". В этой книге описываются не только составные типы данных, но и операции, которые можно с ними совершать, плюсы и минусы, рекомендации к применению. Предупреждаю, что все примеры на Паскале, но они достаточно просты для понимания.
