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.

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


 

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

19577. Информационные системы. Домашняя бухгалтерия 1.58 MB
  Тема моей курсовой работы – домашняя бухгалтерия. В рамках обычной семьи совершаются различные действия с деньгами, такие как их поступление, хранение и трата. В семье несколько человек, а значит счетов, с которых производятся операции
19578. Ветеранов третьей мировой не будет 92 KB
  В этой фразе Мондейл Уолтер рассматривал проблему итогов глобальных проблем современности и будущего человечества, а конкретно – третья мировая война и наличие человеческого населения после ее окончания.
19579. Загальні відомості про способи отримання деталей заданої форми із різних матеріалів: різання, пиляння, штампування, лиття 115.5 KB
  Тема: Загальні відомості про способи отримання деталей заданої форми із різних матеріалів: різання пиляння штампування лиття. Мета: 1 ознайомити учнів з основними способами отримання деталей заданої форми із різних матеріалів і назвами інструментів. Забезпечити за
19580. РАЗРАБОТКА КОМПЛЕКСА МАРКЕТИНГА ДЛЯ ИП «БЕЛОВ Ю.В.» 273.93 KB
  В настоящее время большинство компаний в той или иной форме регулярно осуществляют рыночные исследования. Содержание понятия «маркетинг» определяется стоящими перед ним задачами
19581. ОЦЕНКА ФИНАНСОВОГО СОСТОЯНИЯ ОРГАНИЗАЦИИ 91.5 KB
  Методы и инструментарий финансового анализа. Общая оценка финансового состояния организации и изменений его финансовых показателей за отчетный период. Анализ платежеспособности и финансовой устойчивости организации. Анализ кредитоспособности и ликвидности баланса организации. Анализ эффективности использования оборотных средств.
19582. РОЗРОБКА HTML5 ДОДАТКУ ДЛЯ ВІЗУАЛІЗАЦІЇ ТА МАНІПУЛЯЦІЇ СІТКАМИ ЕЛЕМЕНТІВ 991 KB
  HTML еволюціонує, забезпечуючи поліпшену і складнішу стандартну графіком, що сприяє підвищенню якості взаємодії з користувачами. Це дає веб- розробникам можливість використовувати веб- технології на основі стандартів для створення інтерактивних сайтів і додатків зі складною графікою
19583. Техніка. Історія розвитку техніки. Основні види техніки 38.5 KB
  Тема.2.1.1 Техніка. Історія розвитку техніки. Основні види техніки. Мета: ознайомити з історією розвитку техніки та засобів праці значенням машин у сучасному виробництві та побуті; розвивати інтерес до техніки розширювати технічний кругозір творчі здібності; виховува...
19584. Мозг и психика 115 KB
  Сознание и мышление человека, его идеалы и духовные потребности, планы и образы окружающей действительности, какие бы возвышенные чувства у нас ни вызывали, прозаически связаны с функционированием вещественного, материального органа — мозга
19585. Обоснование плана развития растениеводства на предприятии ООО «Зелёные линии - Калуга 260 KB
  Целью курсовой работы является изучение состояния отрасли овощеводства ООО «Зелёные линии - Калуга», разработка мероприятий по совершенствованию производства культур, обоснование затрат на их реализацию.