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

 

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

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

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

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

1) прямой или префиксный {узел, левое поддерево, правое поддерево};

2) обратный или постфиксный {левое поддерево, правое поддерево, узел};

3) симметричный или инфиксный {левое поддерево, узел, правое поддерево};

Чтобы вывести элементы в порядке их возрастания, дерево поиска обходят в симметричном порядке. Для вывода в обратном порядке в процессе обхода необходимо поменять порядок посещения поддеревьев.

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

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

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

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

 

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

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

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

Граф.

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

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

 

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

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

5. Файлы

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

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

Сложность типовых операций при работе
с линейными структурами данных

Структуры данных оказывают существенное влияние на методы решения задач и сложность типовых алгоритмов. Можно привести оценки сложности основных операций с линейными структурами данных, таких как добавление, удаление и поиск элемента по индексу или ключу. Элементарными операциями, в данном случае, являются операции сравнения, перебора, вычисления адреса или перестановки элементов набора структуры данных. В сводной таблице, помимо верхней оценки сложности, также приведены соответствующие перечисленным структурам данных компоненты библиотеки BCL. Таким образом, основные линейные структуры данных уже есть в готовом виде и доступны всем разработчикам программного обеспечения на платформе Microsoft.NET Framework.

 

Структура	Вставка	Удаление	Поиск	Компонент BCL
Массив	-	-	O(1)	Базовый тип Array
Список	O(N)	O(N)	O(N)	List< T>
Связанный список	O(1)	O(1)	O(N)	LinkedList< T>
Стек	O(1) (добавление в конец)	O(1) (удаление последнего)	O(N)	Stack< T>
Очередь	O(1) (добавление в конец)	O(1) (удаление первого)	O(N)	Queue< T>
Хэш-таблица	O(1)	O(1)	O(1)	Dictionary< TKey, TValue

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. I. Какое из данных утверждений выражает основную идею текста?
2. IDEF1X - методология моделирования данных, основанная на семантике, т.е. на трактовке данных в контексте их взаимосвязи с другими данными.
3. II. Особенности технологии баз и банков данных.
4. II. СПОСОБЫ И ПРИЗНАКИ ИЗМЕНЕНИЯ МАРКИРОВОЧНЫХ ДАННЫХ
5. IХ. Органы управления, контрольно-ревизионный орган и консультативно-совещательные структуры РСМ
6. OLAP-технология и многомерные модели данных
7. V. Составьте и запишите предложения из данных слов.
8. XXIX. МЫ И ЭТОТ МИР – ПОЛЕВЫЕ СТРУКТУРЫ.
9. Автоматическое заполнение данных
10. Адаптивные структуры управления
11. Административно-правовые нормы: понятие, структура, виды. Дискуссионность по понятию структуры правовой нормы.
12. Акт приёма-передачи базы данных