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.

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


 

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

50553. Исследование изохорного процесса 122.5 KB
  Изучение характеристик изохорного процесса при подводе тепла к газу. Уравнение процесса имеет вид: или Регистрируя изменение давление и температуры в ходе процесса можно построить его кривую в координатах Р Т а также определить константу и построить расчетную кривую. По результатам опыта строится кривая процесса в координатах Р Т.
50555. Инструкция по работе с программой RASTR 121 KB
  Для перемещения по меню используйте: а клавиши перемещения курсора ENTER – для входа в выбранную команду ESC – для выхода. б функциональные клавиши – нажатие клавиши lt одновременно с выделенной цветом буквой горизонтального меню приводит к попаданию в это меню где бы Вы ни находились. Нажатие выделенной цветом буквы вертикального меню приводит к началу выполнения этой команды используйте клавиши на которые нанесены русские буквы независимо от регистра.
50558. ИНФОРМАЦИОННЫЕ СИСТЕМЫ ОРГАНИЗАЦИОННОГО УПРАВЛЕНИЯ 55.5 KB
  Информационные системы организационного управления Информационная система комплекс включающий вычислительное и коммуникационное оборудование программное обеспечение лингвистические средства и информационные ресурсы а также системный персонал и обеспечивающий поддержку динамической информационной модели некоторой части реального мира для удовлетворения информационных потребностей пользователей Система целое составленное из частей множество элементов находящихся в отношениях и связях друг с другом которое образует определенную...
50559. Исследование трансформатора. Методические указания 436.5 KB
  У однофазного трансформатора рис. У трехфазного трансформатора рис. При холостом ходе вторичная обмотка трансформатора разомкнута U20=E2 т.
50561. Определение скорости пули при помощи крутильного баллистического маятника 58.5 KB
  Экспериментальное определение постоянной упругих сил кручения момента инерции баллистического маятника. Экспериментальное определение с помощью баллистического маятника скорости пули. Определение периода колебаний упругих сил кручения и момента кручения баллистического маятника...