Контрольная работа по "Информатике"

Структуры данных формируются с помощью  типов данных, ссылок и операций над ними в выбранном языке  программирования.

Различные виды структур данных подходят для  различных приложений; некоторые  из них имеют узкую специализацию для определённых задач. Например, Б-деревья обычно подходят для создания баз данных, в то время как хэш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет адреса компьютеров.

При разработке программного обеспечения  сложность реализации и качество работы программ существенно зависит  от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++.

Фундаментальными строительными  блоками для большей части  структур данных являются массивы, записи (см. конструкцию struct в языке Си и  конструкцию record в языке Паскаль), размеченные объединения (см. конструкцию union в языке Си) и ссылки. Например, структура данных двусвязный список, может быть построена с помощью записей и зануляемых ссылок, а именно, каждая запись будет предоставлять блок данных (узел, node), содержащий ссылки на «левый» и «правый» узлы, а также сами хранимые данные.

Список структур данных

• Линейные структуры данных (Linear data structures)
• Список (List)
• Массив (Array)
• Битовые поля (Bitmaps)
• Изображения (Images)
• Поля высот (Heightfields)
• Фильтр Блума (Bloom filter)
• Параллельный массив (Parallel array)
• Дерево Фенвика
• Разреженная таблица
• Связный список (Linked list)
• Список с пропусками (Skip list)
• Развёрнутый связный список (Unrolled linked list)
• XOR-связный список (Xor linked list)
• V-список (VList)
• Ассоциативный массив (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)
• Граф (Graph)
• Список рёбер (Adjacency list)
• Представление графа в разорванном виде (Disjoint-set data structure)
• Представление графа в виде стеков (Graph-structured stack)
• Сценограф (Scene graph)
• Деревья
• 2-3 дерево
• Дерево отрезков
• Красно-чёрное дерево
• BSP дерево
• 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)
• Куча (Heap)
• Двоичная куча (Binary heap)
• Биномиальная куча (Binomial heap)
• Фибоначчиева куча (Fibonacci heap)
• Сливаемая куча (Mergable heap)
• 2-3-куча (2-3 heap)
• Мягкая куча (Soft heap)
• Дерево разбора (Parse tree)
• Квад-дерево (Quadtree) и Окт-дерево (Octree)
• Суффиксное дерево (Suffix tree)
• Префиксное дерево (Trie)
• Патриция (дерево) (Patricia trie)
• Другие структуры данных
• Помеченное объединение (Tagged union)
• Объединение (Union)
• Таблица (Table)

Попытка классификации  некоторых из них на основании  особенностей:

«Упорядоченная» не означает — отсортированная, только то, что исходный порядок  «сохранён». Другие структуры, такие  как «связный список» и «стек» не могут легко быть определены таким образом, потому что существуют специальные операции ассоциирующиеся с ними.