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.

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


 

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

7944. Поняття суспільство,суспільне, соціальне, соціум. Суспільство як самоорганізована система 53.5 KB
  Поняття суспільство,суспільне, соціальне, соціум. Суспільство як самоорганізована система У переважній більшості суспільствознавчої літератури (як у минулому, так і тепер) подається тлумачення, що поняття суспільство і соціум є тотожними та рівн...
7945. Поняття про природу. Природа як об’єкт знання та пізнання. 68 KB
  Етимологічно, тобто відповідно до первісного значення слова, поняття природа є похідним від слів при роді (тобто родовій общині, формі спільноти людей, повязаних між собою кровною спорідненістю), при родах, при породіллі (тобто при народженні, адже природа породжує людину). Але це поняття і в літературі, і в буденній мові вживається неоднозначно
7946. Роль природно-історичного середовища і спадковості у формуванні та розвитку людини 46.5 KB
  Тема уроку: Роль природно-історичного середовища і спадковості у формуванні та розвитку людини. Мета уроку: З’ясувати роль природно-історичного середовища і спадковості у формуванні та розвитку людини, сформувати природні, соціокультурні та дух...
7947. Сутність людини та сенс людського життя 22.85 KB
  Тема Сутність людини та сенс людського життя Мета: Проаналізувати та визначити основні поняття сутності людини та сенсу людського життя розвивати вміння критично аналізувати різні точки зору на певну проблему виховувати толерантне ставлення до пра...
7948. Ценообразование. Конспект лекций 526.5 KB
  В конспекте лекций изложены основные подходы к ценообразованию на современном этапе, рассмотрены вопросы государственного регулирования цен и ценовой политики предприятия. Содержание Введение...
7949. Понятие внутренней картины болезни и здоровья 283.5 KB
  Понятие внутренней картины болезни и здоровья. Определение понятия внутренняя картина болезни. Внутренняя картина болезни = понятие, введенное отечественным терапевтом Романом Альбертовичем Лурией. Лурия Роман Альбертович, (1874-1944гг)...
7950. Педагогика. Ответы на государственный экзамен 745 KB
  № 1. Предмет и задачи педагогической науки. Методы научно-педагогического исследования. 3 № 2. Закономерности и принципы целостного пед процесса. 6 №3. Сущность воспитания. Современные подходы к воспитанию (В) 9 № 4. Биологическое и соц. в ра...
7951. Педагогическая психология. Учебное пособие 1.49 MB
  В основе пособия - деятельностная теория учения, изложение ее сопровождается различными практическими ситуациями. Приводятся возрастные особенности младших школьников рассматривается учение как один из видов деятельности выявляются его мотивы, за...
7952. Педагогическая психология. Учебник 1.96 MB
  Педагогическая психология Содержание ЧАСТЬ. ПЕДАГОГИЧЕСКАЯ ПСИХОЛОГИЯ: СТАНОВЛЕНИЕ, СОВРЕМЕННОЕ СОСТОЯНИЕ Глава. Педагогическая психология - междисциплинарная отрасль научного знания. Общенаучная характеристика педагогической психологии...