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.

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


 

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

46795. Поведение потребителя в рыночной экономике 30.67 KB
  Они выдвинули субъективнопсихологическую концепцию стоимости и цены товара которую противопоставили трудовой теории стоимости. Потребитель может выразить свое желание приобрести некоторое благо посредством количественной оценки его полезности. Он рассматривал предельную полезность не как единственное основание цен а как лишь один из факторов который через свое влияние на спрос воздействует и на изменение цен. Парето считал необходимым отказаться от абсолютного измерения предельных полезностей и сконцентрировать внимание на предпочтении...
46796. What is a Sole Proprietorship? 30.77 KB
  With more than 17 million operating in the United States, nearly 70 percent of businesses operate as sole proprietorships. In addition to the relative simplicity compared to large corporations, opening a sole proprietorship is a low-cost method of entering into the business world. From consultants and free lancers to independent contractors, nearly anyone can create a sole proprietorship
46797. Маркетинговая среда. Анализ рынка 30.83 KB
  Маркетинговая среда фирмы совокупность активных субъектов и сил действующих за пределами фирмы и влияющих на возможности руководства службой маркетинга устанавливать и поддерживать с целевыми клиентами отношения успешного сотрудничества. Изучение мотивации является необходимым этапом в маркетинговых исследованиях – ведь цель маркетинга заключается в обеспечении наиболее полного удовлетворения потребностей и спроса покупателей. К микросреде маркетинга относятся те субъекты рынка с которыми фирма имеет возможность взаимодействовать напрямую...
46798. Расчеты посредством чеков 30.9 KB
  судебного постановления кот санкционирует исполнение суд решения придает ему принудительную силу. Возможна проверка решения по существу если оно вынесено против своего гражданина. Условие выдачи экзекватуры: решение не д противоречить публичному порядку места исполнения решения и должник надлежащим образом был извещен о времени и месте судебного разбирательства.В РФ решения иных судов признаются и исполняются если это предусмотрено междун договором.
46799. Политическая коммуникация: сущность и особенности 31 KB
  Три основных типа политического общения: Побудительное приказ указ Информирование населения Фактическое Функции: Распространение политических ценностей Интеграция и регулирование политических отношений Формирование общественного политического мнения Распространение политической культуры и её развитие у конкретного индивида Политикокультурный обмен Подготовка общественности к участию в политике Три способа политической коммуникации: Коммуникация через печать и электронные СМИ из центра в регионы Коммуникация через организации население и...
46800. Оператор SELECT. Группировка результатов запроса. Вычисление итогов. Примеры итоговых функций. Отбор результатов по результатам вычисления итогов (выражение HAVING) 28.5 KB
  Оператор SELECT. Отбор результатов по результатам вычисления итогов выражение HVING В общем случае для создания вычисляемого производного поля в списке SELECT следует указать некоторое выражение языка SQL. SELECT Товар. SELECT Фирма Фамилия LeftИмя1.
46801. Формы ведения бухгалтерского и налогового учета организацией- аутсорсинга 31 KB
  Формы ведения БУ и НУ: полное ведение БУ и НУ оргции ведение ьу и ну отдго участка Ведение БУ вклт: учет инфо в ден выражении об имущве обязвах их движнии на основании первичных докв систематизация первичных докв составление сводных регистров БУ учет труда и расчет зп составление финн отчти Составление отчетов во внебюд фонды формирование учетной политики для целей бу Ведение НУ вклт: систематизация первичный уч довв формирование уч политики для целей НУ составление анал регистров ну расчет налог базы ...