infa_1 / 5.Линейные и нелинейные структуры данных

5. Линейные и нелинейные структуры данных

Структуры данных:

-линейные: картезианские (прямоугольные), строчные, списковые;

-нелинейные (деревья (древовидные), графы (графовые), сплетения (плексы)).

Линейная – структура, в которой связи между элементами не зависят от выполнения какого-либо условия. К ним относятся матрица, вектор и множество.

Полустатические линейные структуры: стек, очередь, дек.

Стек – это последовательность, в которой включение и исключение элемента осуществляется с одной стороны этой последовательности. Он функционирует по принципу LIFO (Last Input First Output).

Очередь – это последовательность, в которую элементы включаются с одной стороны, а исключаются с другой – FIFO (First Input First Output).

Дек – линейная структура (последовательность), в которой операции включения/исключения элемента могут выполняться как с одного, так и с другого конца.

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

Нелинейные структуры данных – это структуры данных, у которых связи между элементами зависят от выполнения определенных условий.

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

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

Дерево, из каждой вершины которого выходит только по 2 ребра, называется бинарным.

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

Многосвязная структура обладает следующими свойствами:

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

2. каждый элемент может иметь связь с любым количеством других элементов

3. каждая связь (ребро или дуга) может иметь направление и вес.

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

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