Описание тега data-structures
Структуры данных в программном обеспечении встречаются повсеместно. Хеш-таблицы, сбалансированные деревья и динамические массивы являются важными строительными блоками для больших и сложных систем, и почти все программисты в какой-то момент сталкивались с ними. Более сложные структуры, такие как двоичные кучи, могут ускорить сложные системы, а более простые концепции, такие как стеки и очереди, позволяют более элегантно и лаконично кодировать алгоритмы.
Конечно, это только верхушка айсберга, когда дело касается структур данных. В течение последних лет теоретики постоянно разрабатывали все более совершенные структуры данных, многие из которых широко используются в современном программном обеспечении, а многие полезны только с теоретической точки зрения.
Структуры данных тесно связаны с алгоритмами. Часто хороший выбор структуры данных может привести к заметному улучшению времени выполнения алгоритма. Например, алгоритм Дейкстры с наивной реализацией очереди с приоритетами работает за квадратичное время, но с быстрой кучей Фибоначчи можно показать, что он работает вO(m + n lg n).
Ниже приведен (совсем не полный) список некоторых из наиболее популярных структур данных и их вариантов:
- Динамические массивы
- Динамический стол
- Многоуровневый вектор
- Дерево хешированных массивов
- Расширяемый массив
- Связанные списки
- Односвязные списки
- Двусвязные списки
- Списки, связанные XOR
- Пропустить списки
- Хеш-таблицы
- Связанные хеш-таблицы
- Хеш-таблицы линейного зондирования
- Квадратичные хеш-таблицы зондирования
- Двойные хеш-таблицы
- Хеш-таблицы с кукушкой
- Идеальные хеш-таблицы
- Динамические идеальные хеш-таблицы
- Бинарные деревья
- Красные / черные деревья
- Деревья интервалов
- Деревья двоичного поиска
- Сегментные деревья
- Деревья АВЛ
- Деревья AA
- Раскидистые деревья
- Деревья козлов отпущения
- Treap
- Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Куча Фибоначчи
- дерево ван Эмде Боас
- Косая биномиальная куча
- Бродальская очередь
- Корневые деревья
- Трие
- Патрисия дерево
- Тернарное дерево поиска
- Многонаправленные деревья
- B дерево
- B+ дерево
- B* дерево
- Геометрические деревья
- Quadtree
- Octree
- kd-Tree
- BSP-дерево
- R-дерево
- Геометрические конструкции
- Крылатый край
- Quadedge
- Структуры сетевых подключений
- Непересекающийся лес
- Связать / вырезать дерево
- Верхнее дерево
- Графики
- DAG
- Направленный граф
- Ненаправленный граф
- Гиперграф
Ссылки: