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.

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


 

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

36010. Правовые основы природопользования. Российское природоохранное законодательство 36 KB
  Кодекс о недрах 2008 Водный кодекс 1998 в редакции 2009 г.; Кодекс о земле 1999 в редакции [2008 г.; Лесной кодекс 2000 в редакции 2008 г.; Налоговый кодекс 2009; законы: Об охране окружающей среды 1992 в редакции 2009 г.
36011. Понятие о современном русском литературном языке. Литературный язык и его признаки. Разновидности общенационародного языка, лежащие за границами литературного языка 36 KB
  Литературный язык и его признаки. Разновидности общенационародного языка лежащие за границами литературного языка. Понятие о современном русском литературном языке.
36012. Метод обучения 36 KB
  Пятая группа: исследовательские методы. Эти методы предполагали самостоятельную работу учеников направленную на познание информации при помощи индивидуального разрешения проблемы. Сюда входили и методы организации и осуществления познавательной деятельности учащихся через выполнение логических операций. Также сюда входили методы самоуправления учебной деятельности ребят организация их самостоятельной работы.
36013. Тепловые процессы и аппараты 4.31 MB
  Основы передачи тепла и основные закономерности. Перенос энергии в форме тепла, происходящей между телами, имеющими различную температуру, называется теплообменом. Движущей силой любого процесса теплообмена является разность температур более нагретого и менее нагретого тел
36014. Специфика строения и физиологии клеток растений 35.5 KB
  фотосинтез протекает при участии фотосинтезирующих пигментов обладающих уникальным свойством преобразования энергии солнечного света в энергию химической связи в виде аТФ. Строение хлоропласта: во внутренней мембране тилакоидов гран содержатся фотосинтетические пигменты а также белки цепи переноса электронов и молекулы фермента АТФсинтетазы. К ней относятся: поглощение хлорофиллом квантов света образование молекулы АТФ и фотолиз воды. При достижении критической величины разности потенциалов сила электрического поля начинает...
36015. Динамика экосистем. Экологические сукцессии 35.5 KB
  Экологические сукцессии. Затем по мере появления растений растущих более медленно скорость сукцессии снижается. Постепено по мере смыкания крон березы светолюбивые виды характерные для начальных стадий сукцессии начинают исчезать и уступают место теневыносливым. Антропогенные сукцессии сукцессии происходящими в результате воздействия человека на природные экосистемывыпас скота рубка лесов распашка земель.
36017. Оператор SELECT. Переименование атрибутов и отношений в операторе SELECT. Ключевое слово WHERE. Сортировка результатов запросы по значению атрибута 31 KB
  Раздел WHERE используется совместно с SQL DML операторами в следующей форме: SQLDMLвыражение FROM TBLE_NME WHERE predicte Все записи для которых значением предиката раздела WHERE является истина будут задействованы или возвращены в SQL DML выражении или запросе. Типы предикатов используемых в предложении WHERE: сравнение с использованием реляционных операторов = равно не равно = не равно больше меньше = больше или равно = меньше или равно BETWEEN IN LIKE CONTINING IS NULL EXIST NY LL SELECT first_nme lst_nme dept_no FROM...
36018. Происхождение кириллицы. Буквенный состав русского алфавита, значение букв и принцип функционирования русской графики 35.5 KB
  Кирилл взял славянские буквы и 8 греческих и написал кириллицу. Черноризец Хребр черты и резы своеобразные русские буквы. Глаголица 43 буквы кириллица 38. На тот момент в ней было по видимому 43 буквы.