СпиÑок Ñтруктур данных
Материал из Википедии — Ñвободной Ñнциклопедии
Ðто — ÑпиÑок Ñтруктур данных. Ð”Ð»Ñ Ð±Ð¾Ð»ÐµÐµ широкого ÑпиÑка Ñм. ÑпиÑок терминов, отноÑÑщихÑÑ Ðº алгоритмам и Ñтруктурам данных.
- Линейные Ñтруктуры данных (Linear data structures)
- СпиÑок (List)
- МаÑÑив (Array)
- Битовые Ð¿Ð¾Ð»Ñ (Bitmaps)
- Ð˜Ð·Ð¾Ð±Ñ€Ð°Ð¶ÐµÐ½Ð¸Ñ (Images)
- ÐŸÐ¾Ð»Ñ Ð²Ñ‹Ñот (Heightfields)
- Параллельный маÑÑив (Parallel array)
- Дерево отрезков
- Битовые Ð¿Ð¾Ð»Ñ (Bitmaps)
- СвÑзанный ÑпиÑок (Linked list)
- СпиÑок Ñ Ð¿Ñ€Ð¾Ð¿ÑƒÑками (Skip list)
- Развёрнутый ÑвÑзанный ÑпиÑок (Unrolled linked list)
- Xor-ÑвÑзанный ÑпиÑок (Xor linked list)
- V-ÑпиÑок (VList)
- МаÑÑив (Array)
- ÐÑÑоциативный маÑÑив (Associative array a.k.a. dictionary or map) — также извеÑтен как Ñловарь или карта
- Хеш-таблица (Hash table)
- Стек (Stack a.k.a. LIFO Last in, first out) — также извеÑтен как ЛИФО
- Очередь (Queue a.k.a. FIFO First in, first out) — также извеÑтен как ФИФО
- ÐŸÑ€Ð¸Ð¾Ñ€Ð¸Ñ‚ÐµÑ‚Ð½Ð°Ñ Ð¾Ñ‡ÐµÑ€ÐµÐ´ÑŒ (Priority queue) — иногда выполнÑетÑÑ Ð² виде кучи, Ñм. ниже
- Дек (Deque) — двуÑвÑÐ·Ð½Ð°Ñ Ð¾Ñ‡ÐµÑ€ÐµÐ´ÑŒ
- Буферное окно (Buffer gap)
- СпиÑок (List)
- Граф (Graph)
- СпиÑок рёбер (Adjacency list)
- ПредÑтавление графа в разорванном виде (Disjoint-set data structure)
- ПредÑтавление графа в виде Ñтеков (Graph-structured stack)
- Сценограф (Scene graph)
- ДеревьÑ
- M-Way Tree
- B-дерево
- Двоичное дерево поиÑка (Binary search tree)
- СамобаланÑирующееÑÑ Ð´ÐµÑ€ÐµÐ²Ð¾ поиÑка (Self-balancing binary search tree)
- ÐВЛ-дерево (AVL tree)
- КраÑно-чёрное дерево (Red-black tree)
- Дерево Ñо штрафами (Scapegoat tree)
- КоÑое дерево (Splay tree)
- Дерево ван Емде БоаÑа (van Emde Boas tree)
- Дерево оÑтатков (Radix tree)
- Интервальное дерево (Interval tree)
- СамобаланÑирующееÑÑ Ð´ÐµÑ€ÐµÐ²Ð¾ поиÑка (Self-balancing binary search tree)
- Куча (Heap)
- Ð”Ð²Ð¾Ð¸Ñ‡Ð½Ð°Ñ ÐºÑƒÑ‡Ð° (Binary heap)
- Ð‘Ð¸Ð½Ð¾Ð¼Ð¸Ð°Ð»ÑŒÐ½Ð°Ñ ÐºÑƒÑ‡Ð° (Binomial heap)
- ФибоначчиевÑÐºÐ°Ñ ÐºÑƒÑ‡Ð° (Fibonacci heap)
- 2-3-куча (2-3 heap)
- ÐœÑÐ³ÐºÐ°Ñ ÐºÑƒÑ‡Ð° (Soft heap)
- Дерево разбора (Parse tree)
- Квад-дерево (Quadtree) и Окт-дерево (Octree)
- Дерево ÑуффикÑов (Suffix tree)
- Бор ПрефикÑное дерево (Trie)
- Бор (Patricia trie)
- M-Way Tree
- Другие Ñтруктуры данных
- Помеченное объединение (Tagged union)
- Объединение (Union)
- Таблица (Table)
Попытка клаÑÑификации некоторых из них на оÑновании оÑобенноÑтей:
| Структура | УпорÑÐ´Ð¾Ñ‡ÐµÐ½Ð½Ð°Ñ | Ð£Ð½Ð¸ÐºÐ°Ð»ÑŒÐ½Ð°Ñ | Данных на вершину |
|---|---|---|---|
| Сумка | нет | нет | 1 |
| МножеÑтво | нет | да | 1 |
| СпиÑок | да | нет | 1 |
| ÐÑÑоциативный маÑÑив | нет | да | 2 |
«УпорÑдоченнаÑ» не означает — отÑортированнаÑ, только то, что иÑходный порÑдок «Ñохранён». Другие Ñтруктуры, такие как «ÑвÑзанный ÑпиÑок» и «Ñтек» не могут легко быть определены таким образом, потому что ÑущеÑтвуют Ñпециальные операции аÑÑоциирующиеÑÑ Ñ Ð½Ð¸Ð¼Ð¸.
