Рис. 3.2. Иллюстрация понятия «очередь»

↑

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

Рис. 3.2. Иллюстрация понятия «очередь»

Подумайте, какая связь между стеком и следующими объектами:

Почему стек является структурой типа LIFO (от англ. Last In, Firts Out — последним пришёл, первым ушёл)?
Почему очередь является структурой типа FIFO (от англ. First In, First Out — первым пришёл, первым ушёл)?

Примеры нелинейных структур данных вам также хорошо известны — это графы и деревья (рис. 3.3).

Граф — это множество элементов (вершин графа) вместе с набором отношений между ними.

Рис. 3.3. Примеры графовых структур

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

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

Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром. Линия направленная (со стрелкой) называется дугой. При этом вершина, из которой дуга исходит, называется начальной, а вершина, куда дуга входит, — конечной. Граф называется неориентированным, если его вершины соединены рёбрами. Вершины ориентированного графа соединены дугами. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.

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

Одной из разновидностей графа является дерево.

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

Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.

Деревья используются для представления родственных связей (генеалогическое дерево), для определения выигрышной стратегии в играх и т. д.

Ещё одной знакомой вам структурой данных являются таблицы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.

Оформляют таблицы в соответствии с рисунком 3.4.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры