Список структур данных
Это список известных структур данных . Более широкий список терминов см. в списке терминов, относящихся к алгоритмам и структурам данных . Для сравнения времени выполнения подмножества этого списка см. сравнение структур данных .
Типы данных [ править ]
Примитивные типы [ править ]
- Логическое значение , истинное или ложное .
- Характер
- Представление с плавающей запятой конечного подмножества рациональных чисел .
- Включая числа с плавающей запятой одинарной и двойной точности 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 Сравнение нескольких структур данных.