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.

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


 

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

56119. «Сміхові» вправи в системі здоров’язберігаючих технологій 69.5 KB
  Сміх йде від здоровя. Тому діти і сміються таким тотальним сміхом. Одним з малорозвинених напрямків здоровязберігаючих технологій є напрямок вправ зі сміхом.
56121. Тренінгове заняття «Що я знаю про СНІД» 87.5 KB
  Мета: сформувати у підлітків розуміння власної відповідальності за ризик інфікування ВІЛ та ІПСШ; сприяти зміні мотивації статевої поведінки підлітків на користь репродуктивного здоровя та індивідуального захисту від ВІЛ; систематизувати знання про шляхи передачі ВІЛ...
56122. ПРОФІЛАКТИКА ВІЛ/СНІДу 70.5 KB
  Мета уроку: Розглянути теоретичні основи та практичні способи профілактики ВІЛ-інфекції СНІДу; ознайомити учнів з розповсюдженням ВІЛ СНІД в Україні; Навчити учнів оцінювати ступінь ризику захворювання; Розвивати вміння аналізувати робити висновки...
56123. ЕКОНОМІКА ПІДПРИЄМСТВА 248 KB
  Мета заняття: Навчальна: економічно обґрунтоване визначення величини затрат для виробництва і збуту продукції. Методичне забезпечення: Роздатковий матеріал 2 компоненти: вправа для розпізнання термінів; економічний...
56124. Собівартість продукції, її структура. Витрати на виробництво продукції 135.5 KB
  Вивчення теми «Собівартість продукції, її структура. Витрати на виробництво продукції» в рамках усієї дисципліни сприяє формування у студентів вмінь та знань щодо структури собівартості, витрат на виробництво продукції...
56125. Содержание понятия нормирование труда 57 KB
  Нормирование труда - это установление норм затрат труда на изготовление единицы продукции или выработки количества продукции в единицу времени различают следующие основные виды норм: нормы времени; нормы выработки...