Список структур данных
Это список известных структур данных . Более широкий список терминов см. в списке терминов, относящихся к алгоритмам и структурам данных . Сравнение времени выполнения для подмножества этого списка см. в сравнении структур данных .
Типы данных
Примитивные типы
- Логическое значение , истина или ложь .
- Характер
- Представление с плавающей точкой конечного подмножества рациональных чисел .
- Включая , среди прочего , числа с плавающей точкой IEEE 754 одинарной и двойной точности.
- Представление рациональных чисел с фиксированной точкой
- Целое число , прямое представление целых чисел или неотрицательных целых чисел.
- Ссылка , иногда ошибочно называемая указателем или дескриптором, — это значение, которое ссылается на другое значение, возможно, включая само себя.
- Символ , уникальный идентификатор
- Перечислимый тип , набор символов
- Комплекс , представление комплексных чисел
Составные типы или непримитивные типы
- Массив — последовательность элементов одного типа, хранящихся последовательно в памяти.
- Запись ( также называемая структурой ), набор полей
- Тип продукта (также называемый кортежем), запись, в которой поля не поименованы
- Строка , последовательность символов, представляющая текст
- Объединение , данные, которые могут быть одним из множества типов
- Тегированное объединение (также называемое вариантом , дискриминированным объединением или типом суммы ), объединение с тегом, указывающим, к какому типу относятся данные
Абстрактные типы данных
- Контейнер
- Список
- Кортеж
- Ассоциативный массив, Карта
- Мультикарта
- Набор
- Мультисет (сумка)
- Куча
- Очередь (пример приоритетной очереди )
- Двусторонняя очередь
- Граф (пример Дерево , Куча )
Некоторые свойства абстрактных типов данных:
 | Эта статья требует внимания эксперта по информатике . Конкретная проблема: необходимы дополнительные функции. ( Июнь 2022 г. ) |
| Структура | Заказали? | Уникальность? |
|---|---|---|
| Список | да | нет |
| Ассоциативный массив | нет | только ключи (индексы) |
| Набор | нет | да |
| Куча | да | нет |
| Мультикарта | нет | нет |
| Мультисет (сумка) | нет | нет |
| Очередь | да | нет |
«Упорядоченный» означает, что элементы типа данных имеют некий явный порядок, где элемент может считаться «до» или «после» другого элемента. Этот порядок обычно определяется порядком, в котором элементы добавляются в структуру, но элементы могут быть переупорядочены в некоторых контекстах, таких как сортировка списка. С другой стороны, для структуры, которая не упорядочена, нельзя делать никаких предположений о порядке элементов (хотя физическая реализация этих типов данных часто будет применять некоторый произвольный порядок). «Уникальность» означает, что дублирующие элементы не допускаются. В зависимости от реализации типа данных попытка добавить дублирующий элемент может быть либо проигнорирована, либо перезаписать существующий элемент, либо вызвать ошибку. Обнаружение дубликатов основано на некотором встроенном (или, альтернативно, определяемом пользователем) правиле сравнения элементов.
Линейные структуры данных
Структура данных называется линейной, если ее элементы образуют последовательность.
Массивы
- Множество
- Ассоциативный массив
- Битовый массив
- Битовое поле
- Битборд
- Растровое изображение
- Круговой буфер
- Контрольный стол
- Изображение
- Вектор наркотика
- Динамический массив
- Буфер разрыва
- Дерево хешированного массива
- Таблица поиска
- Матрица
- Параллельный массив
- Сортированный массив
- Разреженная матрица
- Вектор Илиффа
- Массив переменной длины
Списки
- Двусвязный список
- Список массивов
- Связанный список, также известный как односвязный список
- Список ассоциаций
- Самоорганизующийся список
- Пропустить список
- Развернутый связанный список
- VList
- Список Conc-tree
- Список связанных XOR
- Молния
- Двусвязный список ребер, также известный как полуребро
- Список отличий
- Бесплатный список
Деревья
Деревья являются подмножеством направленных ациклических графов .
Двоичные деревья
- Дерево АА
- АВЛ-дерево
- Двоичное дерево поиска
- Двоичное дерево
- декартово дерево
- Список Conc-tree
- Бинарное дерево «левый потомок — правый брат»
- Дерево статистики заказа
- Пагода
- Рандомизированное двоичное дерево поиска
- Красно-черное дерево
- Веревка
- Дерево козла отпущения
- Самобалансирующееся двоичное дерево поиска
- Раскидистое дерево
- Т-дерево
- Дерево танго
- Связанное двоичное дерево
- Верхнее дерево
- Треп
- Дерево WAVL
- Сбалансированное по весу дерево
- Почтовое дерево
B-деревья
Кучи
- Куча
- Мин-макс куча
- Двоичная куча
- B-куча
- Слабая куча
- Биномиальная куча
- Куча Фибоначчи
- AF-куча
- куча Леонардо
- 2–3 кучи
- Мягкая куча
- Сопряжение кучи
- Левая куча
- Треп
- Бип
- Косая куча
- Тройная куча
- D-арная куча
- очередь Бродала
Деревья бит-слайсов
В этих структурах данных каждый узел дерева сравнивает битовый срез ключевых значений.
- Дерево счисления
- Дерево суффиксов
- Массив суффиксов
- Сжатый массив суффиксов
- FM-индекс
- Обобщенное суффиксное дерево
- B-дерево
- массив Джуди
- Трие
- X-быстрый три
- Y-быстрый trie
- дерево Меркла
Многоканальные деревья
- Троичное дерево поиска
- Троичное дерево
- К-арное дерево
- И-или дерево
- (а,б)-дерево
- Ссылка/вырезка дерева
- SPQR-дерево
- Стопка спагетти
- Структура данных Disjoin-set (структура данных Union-find)
- Дерево слияния
- Анфилада
- Экспоненциальное дерево
- Фенвиковое дерево
- Дерево Ван Эмде Боаса
- Розовое дерево
Деревья разбиения пространства
Это структуры данных, используемые для разделения пространства или двоичного разделения пространства .
- Сегмент дерева
- Интервальное дерево
- Дерево диапазонов
- Корзина
- дерево КД
- Неявное дерево kd
- Мин/макс kd дерево
- Расслабленное дерево kd
- Адаптивное дерево kd
- Квадтри
- Октодерево
- Линейное октодерево
- Z-порядок
- UB-дерево
- R-дерево
- R+ дерево
- R* дерево
- Гильбертово R-дерево
- X-дерево
- Метрическое дерево
- Дерево покрытия
- М-дерево
- VP-дерево
- BK-дерево
- Иерархия ограничивающего интервала
- Иерархия ограничивающего объема
- BSP-дерево
- Быстрое исследование случайного дерева
Деревья, специфичные для приложений
- Абстрактное синтаксическое дерево
- Дерево разбора
- Дерево решений
- Альтернативное дерево решений
- Минимаксное дерево
- Дерево Expectiminimax
- Дерево пальцев
- Дерево выражений
- Лог-структурированное дерево слияния
- Дерево PQ
Структуры на основе хэша
- Фильтр запроса приблизительного членства
- Скетч «Количество мин.»
- Распределенная хэш-таблица
- Двойное хеширование
- Динамическая идеальная хеш-таблица
- Массив хэшей, отображенный в виде trie-дерева
- Список хэшей
- Хэш-таблица
- Хэш-дерево
- Hash-trie
- Коорде
- Префиксное хэш-дерево
- Роллинг хэш
- МинХэш
- Ctrie
Графики
Многие графовые структуры данных используются в информатике и смежных областях:
- График
- Список смежности
- Матрица смежности
- Графически-структурированный стек
- Граф сцены
- Дерево решений
- Диаграмма решения с подавлением нуля
- График И-инвертора
- Направленный граф
- Направленный ациклический граф
- Пропозициональный ориентированный ациклический граф
- Мультиграф
- Гиперграф
Другой
- Карта освещения
- Крылатый край
- Четырехгранный
- Таблица маршрутизации
- Таблица символов
- Таблица деталей
- E-график
Смотрите также
- Список алгоритмов
- Чисто функциональная структура данных
- Блокчейн — это основанная на хэше цепочечная структура данных, которая может сохранять историю состояний с течением времени.
Внешние ссылки
- Tommy Benchmarks Сравнение нескольких структур данных.
