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.

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


 

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

14439. Проведення першої примірки, виявлення дефектів, їх усунення 223.5 KB
  Тема: Проведення першої примірки виявлення дефектів їх усунення. Мета: Навчити проводити першу примірку виявляти дефекти та усувати їх. Виховувати любов до праці уважність під час трудових завдань. Розвивати просторову уяву вміння працювати самостійно використо...
14440. Обробка спідниці після примірки 128 KB
  Тема: 2.3.6 Обробка спідниці після примірки. Мета: Навчити обробляти виточки складки бічні зрізи. Виховувати любов до праці уважність під час трудових завдань. Розвивати точність вміння працювати самостійно використовуючи роздатковий матеріал. Інструменти...
14441. Обробка нижнього зрізу спідниці 654 KB
  Тема: 2.3.7. Обробка нижнього зрізу спідниці. Мета: Навчити обробляти низ спідниці відповідно до виду тканини. Виховувати любов до праці бережливе ставлення до інструменту уважність під час трудових завдань. Розвивати точність вміння працювати самості
14442. Кінцева обробка спідниці 98 KB
  Тема:2.3.8 Кінцева обробка спідниці. Мета: Навчити виконувати кінцеву обробку виробу. Виховувати любов до праці бережливе ставлення до інструменту уважність під час трудових завдань. Розвивати естетичний смак вміння працювати самостійно використовуючи роздатковий ...
14443. Остаточна обробка виробу. Волого - теплова обробка. Контроль якості готового виробу 133 KB
  Тема. Остаточна обробка виробу. Волого теплова обробка. Контроль якості готового виробу. Мета. Навчити виконувати остаточну обробку виробу. Виховувати любов до праці бережливе ставлення до інструменту уважність під час трудових завдань. Розвивати вміння пра...
14444. В’язання спицями 279 KB
  Тема. Вязання спицями Мета. Ознайомити учнів з одним із видів декоративноужиткового мистецтва вязанням інструментами і матеріалами для вязання спицями. Організацією робочого місця. Правилами безпечної праці та санітарногігієнічні вимоги. Прийомами роботи спиця...
14445. Добавляння й убавлення петель 416 KB
  Тема. Добавляння й убавлення петель Мета. Ознайомити учнів з способами добавлення і убавлення петель. Основні поняття: спиця пряжа трафарет петля. Очікувані результати навчальної діяльності: проводити добавлення і убавлення петель. Інструменти і матеріали: с...
14446. Технологія вишивання мережок 85.5 KB
  Тема. Технологія вишивання мережок. Мета: ознайомити учнів із технологією виконання мережок навчити виконувати мережки одинарний прутик подвійний прутик; виховувати акуратність і точність під час виконання вишивальних робіт. Обладнання: зразки швів виробів
14447. Технологія вишивання мережок. Розробка композиції виробу 74.5 KB
  Тема. Технологія вишивання мережок. Розробка композиції виробу. Мета: розширити знання учнів про технологію виконання мережок навчити виконувати мережку роздільний прутик; формуй ти художній смак почуття стилю й кольору під час розробку композиції вишивки підбору ...