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.

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


 

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

15641. ЭСТЕТИЧЕСКИЕ ВЗГЛЯДЫ А.К. ВОРОНСКОГО 211.5 KB
  ЭСТЕТИЧЕСКИЕ ВЗГЛЯДЫ А.К. ВОРОНСКОГО В автобиографической книге За живой и мертвой водой Александр Константинович Воронский с мягким юмором рассказал о начале своей литературной работы. Фельетон написанный голодным подпольщиком 1911 неожиданная удача напечатали...
15642. КРИТИКА В КОНТЕКСТЕ ЭСТЕТИКИ (О ДЕЯТЕЛЬНОСТИ И ТВОРЧЕСТВЕ А. ЛЕЖНЕВА) 226.5 KB
  КРИТИКА В КОНТЕКСТЕ ЭСТЕТИКИ О ДЕЯТЕЛЬНОСТИ И ТВОРЧЕСТВЕ А. ЛЕЖНЕВА В начале 20х годов когда жизнь многих людей меняла свой ход никого не могло удивить появление из безвестности нового литературного имени – А. Лежнева. Никто не знал что Абрам Захарович Горелик А. Л...
15643. Энвайронементализм (экологическое направление) 185 KB
  Лекция 22. Энвайронементализм экологическое направление 1. Географический подход в археологии. Этногеография дала импульс не только диффузионизму в археологии но и упору на географический фактор хотя географический детерминизм имеет и более
15644. Инвазионизм и библейская археология 220.5 KB
  Лекция 23. Инвазионизм и библейская археология 1. Миграционизм как инвазионизм. Миграция вообще предстает в исходном пункте как эмиграция в конечном – как иммиграция а если в новую страну передвинулся целый народ или армия то такая иммиграция описывается как вторж...
15645. Комбинационизм в археологии 279.5 KB
  Лекция 26. Комбинационизм. Незамеченное течение. В трансмиссионизме постепенно всё большее место занимала констатация не самих заимствований а их воздействия на остальную культуру на местные ее элементы причем в воспринимающих очагах под воздейст...
15646. Эмпирические школы в археологии 480.5 KB
  24 Лекция 31. Эмпирические школы. 1. Введение. В археологической литературе иногда встречаются указания на эмпирическую школу но всякий раз оказывается что под этим названием фигурируют разные группы ученых разного времени и в разных странах. То ест
15647. Автономная археология в историческом синтезе и эмергентизм 424 KB
  Лекция 33. Автономная археология в историческом синтезе и эмергентизм 1. На руинах археологии обитания. В 1947 г. на конференции в Гамбурге собравшимся немецким археологам было сказано: Сегодня наша преистория прежде всего стоит перед задачей привести в порядок сп
15648. Реболлинг (восстановление шариковых выводов) BGA компонентов (чипов) 446.5 KB
  Реболлинг восстановление шариковых выводов BGA компонентов чипов Рис.1 Примеры выполненных трафаретов для восстановления шариков BGA Рис.2 Восстановленные шариковые выводы BGA чипа Необходимое оборудование Сушка рекомендуется для подсушки ком
15649. ДОМАШНИЙ АРЕСТ КАК МЕРА ПРЕСЕЧЕНИЯ В УГОЛОВНОМ ПРОЦЕССЕ 36.95 KB
  ДОМАШНИЙ АРЕСТ КАК МЕРА ПРЕСЕЧЕНИЯ В УГОЛОВНОМ ПРОЦЕССЕ А. АЛЕКСАНДРОВ Александров Александр профессор Нижегородской академии МВД России доктор юридических наук профессор. Федеральный закон от 7 декабря 2011 г. N 420ФЗ содержит новую редакцию ст. 107 УПК РФ рег