Ağacvari strukturlar

:

Ağacvari strukturlar

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

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

Такие структурированные системы данных называют структурами данных.

Графы

Граф – это средство для наглядного представления состава и структуры системы.

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

Граф, в котором все линии направленные, называется ориентированным.

Две вершины, соединенные дугой или ребром, называются смежными.

Московский метрополитен

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

Группы крови человека

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

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

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