Список структур данных
Это список известных структур данных . Более широкий список терминов см. в списке терминов, относящихся к алгоритмам и структурам данных . Для сравнения времени выполнения подмножества этого списка см. сравнение структур данных .
Типы данных
[ редактировать ]Примитивные типы
[ редактировать ]- Логическое значение , истинное или ложное .
- Характер
- Представление с плавающей запятой конечного подмножества рациональных чисел .
- Включая числа с плавающей запятой одинарной и двойной точности IEEE 754. , среди прочего,
- с фиксированной точкой Представление рациональных чисел
- Integer , прямое представление целых или неотрицательных целых чисел.
- Ссылка , которую иногда ошибочно называют указателем или дескриптором, представляет собой значение, которое ссылается на другое значение, возможно, включая себя.
- Символ , уникальный идентификатор
- Перечислимый тип , набор символов
- Комплекс , представление комплексных чисел
Составные типы или непримитивные типы
[ редактировать ]- Массив — последовательность элементов одного типа, хранящихся в памяти подряд.
- Запись (также называемая структурой или структурой ), набор полей.
- Тип продукта (также называемый кортежем), запись, в которой поля не имеют имен.
- String — последовательность символов, представляющая текст.
- Union — данные, которые могут быть одним из набора типов.
- Теговое объединение (также называемое вариантом , дискриминируемым объединением или типом суммы ), объединение с тегом, указывающим, к какому типу относятся данные.
Абстрактные типы данных
[ редактировать ]- Контейнер
- Список
- Кортеж
- Ассоциативный массив, Карта
- Мультикарта
- Набор
- Мультисет (сумка)
- Куча
- Очередь (пример: Приоритетная очередь )
- Двусторонняя очередь
- График (пример: Дерево , Куча )
Некоторые свойства абстрактных типов данных:
 | Эта статья требует внимания эксперта в области компьютерных наук . Конкретная проблема заключается в следующем: необходимы дополнительные функции. ( июнь 2022 г. ) |
| Структура | Заказал? | Уникальность? |
|---|---|---|
| Список | да | нет |
| Ассоциативный массив | нет | только ключи (индексы) |
| Набор | нет | да |
| Куча | да | нет |
| Мультикарта | нет | нет |
| Мультисет (сумка) | нет | нет |
| Очередь | да | нет |
«Упорядоченный» означает, что элементы типа данных имеют какой-то явный порядок, при котором элемент можно считать «до» или «после» другого элемента. Этот порядок обычно определяется порядком, в котором элементы добавляются в структуру, но в некоторых контекстах элементы можно переупорядочивать, например при сортировке списка. С другой стороны, для неупорядоченной структуры нельзя делать никаких предположений относительно порядка элементов (хотя физическая реализация этих типов данных часто применяет некоторый произвольный порядок). «Уникальность» означает, что дублирование элементов не допускается. В зависимости от реализации типа данных попытка добавить дубликат элемента может быть либо проигнорирована, либо перезаписана, либо вызвать ошибку. Обнаружение дубликатов основано на некотором встроенном (или, альтернативно, определяемом пользователем) правиле сравнения элементов.
Линейные структуры данных
[ редактировать ]Структура данных называется линейной, если ее элементы образуют последовательность.
Массивы
[ редактировать ]- Множество
- Битовый массив
- Битовое поле
- Битборд
- Растровое изображение
- Круговой буфер
- Таблица управления
- Изображение
- Вектор допинга
- Динамический массив
- Буфер разрыва
- Дерево хешированного массива
- Таблица поиска
- Матрица
- Параллельный массив
- Сортированный массив
- Разреженная матрица
- Вектор Илиффа
- Массив переменной длины
Списки
[ редактировать ]- Двусвязный список
- Список массивов
- Связанный список, также известный как односвязный список.
- Список ассоциаций
- Самоорганизующийся список
- Пропустить список
- Развернутый связанный список
- Список в.
- Список дерева соглашений
- Xor связанный список
- Молния
- Двусвязный список ребер, также известный как полуребро.
- Список различий
- Бесплатный список
Деревья
[ редактировать ]Деревья — это подмножество ориентированных ациклических графов .
Бинарные деревья
[ редактировать ]- АА-дерево
- АВЛ-дерево
- Бинарное дерево поиска
- Бинарное дерево
- Декартово дерево
- Список дерева соглашений
- Бинарное дерево левого дочернего элемента и правого родственного элемента
- Дерево статистики заказа
- Пагода
- Рандомизированное двоичное дерево поиска
- Красно-черное дерево
- Веревка
- Дерево козла отпущения
- Самобалансирующееся двоичное дерево поиска
- Распространение дерева
- Т-образное дерево
- Дерево танго
- Резьбовое двоичное дерево
- Верхнее дерево
- Треп
- WAVL-дерево
- Дерево со сбалансированным весом
- Почтовое дерево
B-деревья
[ редактировать ]Кучи
[ редактировать ]- Куча
- Мин-макс куча
- Двоичная куча
- B-куча
- Слабая куча
- Биномиальная куча
- Куча Фибоначчи
- Куча АФ
- Леонардо куча
- 2–3 кучи
- Мягкая куча
- Куча сопряжения
- Левая куча
- Треп
- Бип
- Косая куча
- Тройная куча
- D-ичная куча
- Широкая очередь
Бит-срезы деревьев
[ редактировать ]В этих структурах данных каждый узел дерева сравнивает битовый срез значений ключей.
- Радикс-дерево
- Суффиксное дерево
- Суффиксный массив
- Сжатый массив суффиксов
- FM-индекс
- Обобщенное суффиксное дерево
- B-дерево
- Массив Джуди
- Три
- X-быстрая попытка
- Y-быстрая попытка
- Дерево Меркла
Многосторонние деревья
[ редактировать ]- Тернарное дерево поиска
- Тройное дерево
- K-арное дерево
- И-или дерево
- (a,b)-дерево
- Связать/вырезать дерево
- SPQR-дерево
- Стопка спагетти
- Структура данных непересекающегося набора (структура данных поиска объединения)
- Дерево слияния
- Сервант
- Экспоненциальное дерево
- Дерево Фенвика
- Ван Эмде Боас уходит в отставку
- Розовое дерево
Деревья пространственного разделения
[ редактировать ]Это структуры данных, используемые для разделения пространства или разделения двоичного пространства .
- Дерево сегментов
- Дерево интервалов
- Дерево диапазона
- Бин
- Кд дерево
- Неявное дерево kd
- Мин/макс дерево kd
- Расслабленное дерево КД
- Адаптивное дерево kd
- Четырехдерево
- Октри
- Линейное октодерево
- Z-порядок
- UB-дерево
- R-дерево
- R+ дерево
- Р* дерево
- Гильбертово R-дерево
- X-дерево
- Метрическое дерево
- Покровное дерево
- М-дерево
- VP-дерево
- БК-дерево
- Иерархия граничных интервалов
- Иерархия ограничивающих объемов
- BSP-дерево
- Быстрое исследование случайного дерева
Деревья, специфичные для приложения
[ редактировать ]- Абстрактное синтаксическое дерево
- Дерево разбора
- Дерево решений
- Альтернативное дерево решений
- Минимаксное дерево
- Ожидаемо-минимаксное дерево
- Пальцевое дерево
- Дерево выражений
- Дерево слияний с лог-структурой
- Дерево качества обслуживания
Структуры на основе хеша
[ редактировать ]- Приблизительный фильтр запроса на членство
- Эскиз счета-минуты
- Распределенная хеш-таблица
- Двойное хеширование
- Динамическая идеальная хеш-таблица
- Дерево, отображаемое хеш-массивом
- Хэш-список
- Хэш-таблица
- Хэш-дерево
- Хэш-три
- Шнуры
- Префиксное хеш-дерево
- Роллинг хеша
- Минхеш
- Cтрие
Графики
[ редактировать ]Многие структуры данных на основе графов используются в информатике и смежных областях:
- График
- Список смежности
- Матрица смежности
- Стек с графовой структурой
- Граф сцены
- Дерево решений
- Диаграмма принятия решений с подавлением нуля
- И-инверторный граф
- Ориентированный граф
- Ориентированный ациклический граф
- Пропозициональный ориентированный ациклический граф
- Мультиграф
- Гиперграф
Другой
[ редактировать ]- Карта освещения
- Крылатый край
- Четырехгранный
- Таблица маршрутизации
- Таблица символов
- Стол поштучный
- Электронный график
См. также
[ редактировать ]- Список алгоритмов
- Чисто функциональная структура данных
- Блокчейн — структура данных, основанная на хеш-цепочке, которая может сохранять историю состояния с течением времени.
Внешние ссылки
[ редактировать ]- Tommy Benchmarks Сравнение нескольких структур данных.