69756

Поняття про графи і дерева

Лекция

Информатика, кибернетика и программирование

Графом називають скінченну множину точок - вершин графа, для деяких пар якої налагоджені зв’язки - ребра графа. Розглянемо використання графів для зображення динамічних структур. Нехай є деяка структура, що складається з записів, пов’язаних між собою системою вказівок...

Украинкский

2014-10-09

39 KB

0 чел.

Поняття про графи і дерева

Графом називають скінченну множину точок - вершин графа, для деяких пар якої налагоджені зв'язки - ребра графа. Розглянемо використання графів для зображення динамічних структур. Нехай є деяка структура, що складається з записів, пов'язаних між собою системою вказівок, причому кожен запис може містити вказівки на декілька інших записів. Тепер зіставимо вершини графа із записами, а ребра - з вказівками, поставивши у відповідність цій структурі граф. Ребра такого графа будуть характеризуватися напрямами, що відповідають тим вказівкам, які вони відображають. Такий граф називається орієнтованим. З будь-якого графа завжди можна виділити дерево - сукупність (підмножину) ребер графа, що пов'язує всі вершини, однак не утворює замкнутих контурів (циклів). Дерева можна вибирати багатьма способами.

Для зображення таблиці використовуватимемо двійкові дерева. Двійкове дерево характеризується тим, що з кожної вершини виходить не більше двох стрілок, і є одна вершина - корінь дерева, в який не напрямлена жодна стрілка. У всі ж інші вершини напрямлено по одній стрілці. Приклад двійкового дерева показаний на рис. 1.

51

35 84

96

32 65

102

62          91

Рис. 1. Двійкове дерево.

Ліва і права стрілки не є взаємозамінними, тому наступні два двійкові дерева різні (рис. 2).

Рис. 2. Незбіжні елементи двійкового дерева.

Під час формування дерева записів ліва стрілка відповідає вказівці на запис з меншим ключем, права - на запис з більшим ключем.

1. Зображення таблиці двійковим деревом. У цьому випадку кожна вершина дерева - це запис, що містить чотири поля: ключ запису, вказівку на ліву вершину, вказівку на праву вершину і вказівку на текст запису, який зберігається окремо (як прийнято для таблиць).

Двійкове дерево наведемо у вигляді таких описів типу:

type

Tekst={iм'я або задання типу запису з текстом};

RT=^Tekst;

L=^Node; Node=record

Key: Char;

Left, Right: L;

TXT: RT;

end;

2. Шукання запису в дереві. Опишемо логічну функцію шукання запису в дереві за ключем з побічним ефектом - вказівкою на вершину, що містить відшуканий запис. Формальні параметри функції: k - ключ; Tree - вказівка на дерево, у якому ведуть шукання; Res - вказівна змінна, що містить вказівку на знайдений вузол.

program Form9;

type

Tekst=Char;

RT=^Tekst;

L=^Node;

Node=record

Key: Char;

Left,

Right: L;

TXT: RT;

end;

function SeekTree(k: Char; Tree: L; var Res: L): Boolean;

var p, q: L;

b: Boolean;

begin

b:=false;

p:=Tree;

If p<>nil then repeat

if p^.key=k then b:=True else

if p^.key<k then p:=p^.Right else p:=p^.Left

until b or (p=nil);

SeekTree:=b;

Res:=p;

end;

begin 

end.

Наведена функція побудована на ітеративному методі.


 

А также другие работы, которые могут Вас заинтересовать

31805. Технология принятия решений в условиях поведенческого риска 23 KB
  Формируется когда существуют др лица принимающие решение и основное ЛПР опасается их т.к либо интересы основного ЛПР столкнулись с интересами др ЛПР либо сущ различия в позициях точках зрения традиций основного лица и др ЛПР либо ЛПР считает природу в кот принимаемое решение неопределенной непредсказуемой и поэтому агрессивной.
31806. Формы разработки и реализации управленческих решений 36.5 KB
  Указание решение носящее методический технологический характер. Акт решение широкого круга государственных и общественных организаций. Приказ письменный или устный это решение руководителя обличенного властью в организации или крупном ее подразделении. Распоряжение это решение руководителя не наделенного административными функциями.
31807. Сущность, функции, виды и методы контроля управленческого решения 30 KB
  Контроль организации исполнения УР – система наблюдения проверки оценки и коррекции положения дел на основе критерия. Виды контроля: 1Постоянный – ежедневно 2Регулярный – еженедельно 3Промежуточный – ежемесячно 4Переодический – составление отчета 5Детальный 6Факторный Контроль как функция управления. Контроль УР как на стадии разработки так и на стадии реализации является важнейшей функцией управления. Контроль может осуществляться в двух вариантах: по результатам и по упреждению.
31808. Сущность и виды ответственности руководителей за принятие управленческого решения 30.5 KB
  Ответственность – мера соответствия действий человека групп людей или обва взаимным требованиям нормам. Ответственность это необходимость обязанность отдавать комулибо отчет в своих действиях поступках. Ответственность может быть официальная и личная чувство ответственности как черта характера. Виды ответственности: 1Внутрифирменная: аадминистративная выговор бэкономическая лишение премии впрофессиональная понижение в должности 2Внешняя: аюридическая арест бсоциальная вморальная Юридическая ответственность частично или...
31809. Планирование и прогнозирование в процессе принятия управленческих решений 25 KB
  Метод прогнозирования – способ исследования объекта прогноза направленный на разработку прогнозов. Состояние объекта в будущем определяется закономерностями выявленным по частным результатам опыта его проведения в прошлом и настоящем. Осущся от имеющегося уровня знаний а конечные результаты развития объекта составляют содержание прогноза. Ориентирован на то что задается цель развития объекта в будущем а содержанием прогнозов становится определение частных путей.
31810. Экспертные методы прогнозирования решения 27 KB
  Экспертные методы базируются на информации которую поставляют специалистыэксперты в процессе систематизированных процедур выявления и обобщения этого мнения. Например при проведении экспертного опроса участникам представляют цифровую информацию об объекте или фактографические прогнозы либо наоборот при экстраполяции тенденции наряду с фактическими данными используют экспертные оценки. Экспертные методы разделяются на два подкласса. Прямые экспертные оценки строятся по принципу получения и обработки независимого обобщенного мнения...
31811. Фактографические методы прогнозирования решения 26 KB
  Фактографические методы прогнозирования решения. Фактографические методы базируются на фактически имеющемся информационном материале об объекте прогнозирования и его прошлом развитии. Экспертные методы базируются на информации которую поставляют специалистыэксперты в процессе систематизированных процедур выявления и обобщения этого мнения. Комбинированные методы выделены в отдельный класс чтобы можно было относить к нему методы со смешанной информационной основой в которых в качестве первичной информации используются фактографическая и...
31812. Комплексные системы прогнозирования решения 30.5 KB
  Позволяет: Выбрать объект прогноза выявить внутренние закономерности его развития написать сценарий сформулировать задачи и генеральную цель прогноза провести анализ иерархии и декомпозицию цели принять внутреннюю и внешнюю структуру объекта прогнозирования провести анкетирование выполнить математическую обработку данных анкетного опроса количественно оценить структуру верифицировать результаты разработать алгоритм распределения ресурсов провести распределение ресурсов оценить распределение ресурсов Методика примечательна тем что сочетает...
31813. Модели процесса принятия решений 27 KB
  2политические – система предпочтений лица принимающего решение 3организационные – в большинстве организаций есть организованные анархии процесс принятия решений в которых обладает особенностями. 4 Три типа ППР 1Сначала думаю: определение проблемы диагностика проектирование решениевыбор 2Сначала вижу: подготовка инкубирование проектирование верификация 3Сначала делаю: действие выбор закрепление 5 Классификация процессов взаимодействия руководителя со своими подчиненными: 1 Вы решаете задачу самостоятельно используя ту...