Кратное содержание теории

Дерево - одна из самых распространнных структур., используемых для представления

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

Между узлами существует отношение типа "исходный-порождённый". Корень - узел, не имеющий исходного (отца).Все узлы, кроме корня, имеют только один исходный (исх.отца).

Есть деревья, состоящие из одного корня. Каждый узел может иметь несколько порождённых (сыновей). Отношение "исходный-порождённый" действует только так: не бывает отношения "порождённый-исходный", т.к потомок узла никогда не станет его предком.

Древовоидная структура очень часто представляется в списковой форме.

Граф обычно определяется как некоторое множество точек (называемых вершинами) и

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

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

Для задания графов существует несколько классов матриц, основные из которых класс матриц инциденции и класс матриц смежности.

Упражнения:

1. Для заданного графа вывести все пары связных вершин, сосчитать их количество.

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

3. Сосчитать количество ребер заданного графа.

4. Сосчитать количество ребер заданного ориентированного графа.

5. Создать программу поиска в графе вершины, из которой исходит наибольшее число ребер.

6. Для заданного графа найти и вывести кратчайший путь между заданными вершинами.

ЛАБОРАТОРНАЯ РАБОТА №14

Динамические структуры данных. Организация данных в списковые структуры

Цель работы: Изучение и создание списковых структур данных