Структуры данных: деревья, сети, графы, таблицы структуры данных

СТРУКТУРЫ ДАННЫХ:

• деревья, сети, графы, таблицы

СТРУКТУРЫ ДАННЫХ

• Данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками – элементным составом, структурой, назначением.
• Такие структурированные системы данных называют структурами данных.

ГРАФЫ

• Граф – это средство для наглядного представления состава и структуры системы.
• Граф состоит из ВЕРШИН, связанных ДУГАМИ (если линия направленная) или РЕБРАМИ (если линия не имеет направления). Две дуги, направленные в противоположные стороны можно заменить ребром.
• Граф, в котором все линии направленные, называется ориентированным.
• Две вершины, соединенные дугой или ребром, называются смежными.

МОСКОВСКИЙ МЕТРОПОЛИТЕН

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

ГРУППЫ КРОВИ ЧЕЛОВЕКА

• Связи несимметричны
• Граф ориентированный
• Петля, линия выходящая и входящая в одну и ту же вершину

• I

• IV

• III

• II

ВЗВЕШЕННЫЙ (РАЗМЕЧЕННЫЙ) ГРАФ

• Репкино

• Кошкино

• Мышкино

• Дедкино

• 14

• 5

• 12

• 4

ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ (ДЕРЕВЬЯ)

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

ГРАФ ИЕРАРХИЧЕСКОЙ СИСТЕМЫ (АДМИНИСТРАТИВНАЯ СТРУКТУРА РФ)

• Корень дерева

• Ветви

• 1 уровень

• 2 уровень

• 3 уровень

УСТРОЙСТВО ШАРИКОВОЙ РУЧКИ

• Шариковая ручка

• Стержень

• Колпачок

• Корпус

• Нижняя часть

• Верхняя часть

• Трубочка

• Наконечник

• Паста

ИЕРАРХИЧЕСКАЯ СИСТЕМА ХРАНЕНИЯ ФАЙЛОВ

ТАБЛИЦЫ

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

ТАБЛИЦЫ ТИПА «ОБЪЕКТ-СВОЙСТВО»

Дата	Осадки	Температура, С	Давление, мм рт. ст.	Влажность, %
15.03.2007	Снег	-3,5	746	67
16.03.2007	Без осадков	0	750	63
17.03.2007	Туман	1	740	100
18.03.2007	Дождь	3,4	745	96
19.03.2007	Без осадков	5,4	760	87

• Таблица 1. ПОГОДА

ТАБЛИЦЫ ТИПА «ОБЪЕКТ-ОБЪЕКТ»

Ученик	Предмет
	Рус.яз	Матем	Химия	Физика	История	Музыка
Иванов И.	4	3	4	3	4	5
Петров П.	4	5	4	3	5	4
Сидоров С.	3	5	4	5	3	4
Яшин Я.	5	5	5	5	5	5

Ученик	Предмет
	Рус.яз	Матем	Химия	Физика	История	Музыка
Иванов И.	1	0	0	1	1	1
Петров П.	0	1	0	1	0	1
Сидоров С.	1	1	1	0	0	0
Яшин Я.	1	1	1	1	1	1

• Таблица двоичная матрица (качественная связь между объектами)