Иерархические структуры данных

Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент (или ссылками на нижестоящие элементы) и (необязательно) порядковым номером в линейной последовательности своего уровня (иерархические списки).

Дерево – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла определяет размерность (степень) дерева.

Выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска. Каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора. Все его «левые» потомки являются меньшими элементами, а «правые» – большими. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него, которую называют путем.

Иерархический список представляет собой комбинацию линейного списка и дерева. Каждый элемент такого списка может быть началом списка следующего подуровня иерархии. Пример иерархического списка – структура интернет форумов: последовательность сообщений образует линейный список, в то время как сообщения, являющиеся ответами на другие сообщения, порождают новые потоки обсуждения.

Сетевые структуры данных

Элемент в сетевой структуре характеризуется набором связей с другими - соседними элементами. В таких структурах ни начальный, ни корневой элементы явно не выделены.

Двоичное (бинарное) дерево.

Иерархический список.

Граф – динамическая сетевая структура данных, представленная набором вершин и ребер – связей между вершинами. Каждая вершина может быть связана с любым числом других вершин или с самой собой.

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

Граф.

Ориентированный граф.

4. Табличные структуры данных

Элемент в табличной структуре данных характеризуется двумя индексами: строки и столбца, на пересечении которых он находится. Примерами табличных структур данных являются двумерные массивы и таблицы реляционной базы данных.

Табличные структуры данных.

5. Файлы

Файл (последовательность) – это однородная структура, состоящая из элементов одного и того же (базового) типа. Он похож на массив, но отличается тем, что число его элементов не указывается при объявлении и, вообще говоря, может меняться при выполнении программы. Это приводит к тому, что под последовательность невозможно выделить память фиксированного размера.

Вообще, файл – это динамическая структура данных, размер которой может меняться в процессе выполнения программы (его размер может быть равен нулю, что соответствует пустому файлу). В каждый момент времени может быть доступен только один элемент файла. Существует несколько видов файлов: текстовые, типизированные и др.