Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М. - презентация

1 Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М.

2 Граф - отображает элементный состав системы и структуру связей Описание некоторой местности: «Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино. Д Р КМ Б Это не карта местности. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом. Составными частями графа являются вершины и ребра. вершины ребра Неориентированный граф

3 Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин Д Р КМ Б Неориентированный граф (сеть) Как добраться из Р в М ? 1)Р-К-Б-М 2) Р-К-Д-Б-М Для сетей также характерно наличие замкнутых путей, который называются циклами Цикл К-Д-Б-К

4 Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Граф с такими свойствами называется ориентированным. Существует четыре группы крови человека. При переливании не все группы совместимы. Данный граф показывает возможные варианты переливания крови. Например, из графа видно,что кровь I группы можно переливать любому человеку. IV I IIIII Направленные линии называют дугами (в отличии от ребер неориентированных графов). Линию, выходящую и входящую в одну и ту же вершину называют петлей. Ориентированный граф Дуги Петли

5 Иерархическая структура Директор Заместители директора Учителя Ученики Система административного управления, между элементами которой установлены отношения подчиненности.

6 Граф иерархической структуры - Между любыми двумя его вершинами существует единственный путь. Дерево Деревья не содержат циклов и петель Главная вершина - корень Ветви дерева Порожденные вершины Листья – не имеют порожденных вершин

7 Примеры иерархических структур - деревьев Владимир Рюрик Игорь Святослав Олег Ярополк Мстислав Тмутараканский ГлебЯрославБорис Святополк Изяслав Полоцкий

8 Таблицы Средства ЭОРКол-во учителей в % Интерактивные лекции 63% Виртуальные экскурсии 93% Виртуальные лаборатории 41% Конструкторы формул/графиков 33% Игровые модули 67% Контрольные модули 96% Тренажеры для оттачивания различных навыков 81% В какой форме представлена информация? Табличный способ представления данных является универсальным

9 Таблица типа "объект-свойство" Датаосадкитемп 15.03снег дождь- 20 Таблица типа "объект-объект" Ученикрусскийалгебра Иванов44 Сидоров53 Таблица типа «двоичная матрица» УченикТанцыЛегкая атлетика Сидорова10 Иванов01

10 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Какая связь между графом и таблицей ? Попробуйте представить информацию о дорожной связи между поселками в форме таблицы.

11 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Если сеть является неориентированным графом, то матрица смежности симметрична относительно главной диагонали. Матрица смежности

12 Попробуйте представить информацию о группах крови в форме таблицы. Начальная вершина Конечная вершина IIIIIIIV I1111 II0101 III00110 IV0001 У матрицы, отражающий ориентированный граф, симметричности не будет

13 Зачем мы переводили графы в табличную форму? Вам понятнее граф или таблица? С точки зрения человека, граф гораздо нагляднее и понятнее представляет структуру системы, чем таблица. А компьютеру какую форму обрабатывать легче? Для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии (базы данных, электронные таблицы) работают с таблицами и поэтому в компьютерном моделировании чаще работают с табличным представлением.

14 Подведем итоги Структуры данных ГрафыТаблицы ДеревьяСетиТипы таблиц Элементы дереваЭлементы сети Объект-свойство Объект-объект Двоичная матрица КореньВетвиЛистьяВершиныРебра Единственность пути между вершинами Множественность путей между вершинами

15 Выполните задания 1. Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».

16 Выполните задания 2. Нарисуйте произвольную структуру глобальной компьютерной сети в виде графа, в котором вершины обозначают серверы, а ребра – линии связи. Опишите эту сеть в виде двоичной матрицы смежности.

17 Выполните задания 3. Нарисуйте родословное дерево своей семьи (только по мужской линии или только по женской) с наибольшим числом известных вам уровней. Полученной дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.