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.

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


 

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

29231. Анимизм, фетишизм, тотемизм, магия как базовые формы культуры 37.5 KB
  Отсюда магические обряды размножения тотема ритуальное поедание его мяса в обычных условиях запрещенного рассказывание мифов пляски маскированных танцоров подражающих тотему. magéia колдовство чародейство волшебство обряды связанные с верой в способность человека сверхъестественным путём воздействовать на людей животных явления природы а также на воображаемых духов и богов. Магические обряды распространённые у всех народов мира чрезвычайно разнообразны. Широко были распространены магические обряды при начале пахоты сева...
29232. СЛОВО об АНТИЧНОСТИ 40.5 KB
  Три вещи связывали древних с их землей: храмы могилы и предки. Слово родина у древних было прилагательным и сочеталось со словом земля то была отцовская земля это слово доходило до сердца. Слово свобода к примеру имело для древних тот же глубинный смысл что и ответственность . Свобода теперь имеет моральный смысл у древних же совершенно политический Древние которых все их государственное устройство заставляло быть рационалистами были одухотворены поэзией.
29233. Синкретизм первобытной культуры 62 KB
  Синкретизм первобытной культуры. Синкретизм основное качество культуры характеризующее процесс перехода от биологической формы бытия животных к социокультурной форме существования человека разумного. Синкретизм этого первого исторического состояния культуры естествен и закономерен так как на начальном уровне целостность системы проявляется в её аморфности нерасчленённости. С этим отождествлением связан и характерный для первобытной культуры тотемизм с языка индейского племени оджибве его род вера в первопредка которым может быть...
29234. Проблема «Восток-Запад» в культуре 38.5 KB
  Отличия Западной и Восточной культуры: 1. Для западной культуры характерен ускоренный прогресс науки и техники быстрое изменение предметного мира. На Западе сформировалась сильная рационалистическая традиция которая проявлялась во всех видах культуры.
29235. Культура и глобальные проблемы современности 36 KB
  Одно из самых напряженных противоречий политической и духовной жизни человечества обнаружившееся в конце ХХ столетия и обозначившее рубеж между завершавшимся вторым и рождавшимся третьим тысячелетиями столкновение процессов и движений получивших название глобализма и антиглобализма. Вообще говоря само противостояние позиций обозначенных этими новыми понятиями отнюдь не ново оно пронизывает всю историю человечества. Речь идет о едином для всего человечества техникотехнологическом уровне производства о...
29236. Николай Яковлевич Данилевский (1822-1885) 44.5 KB
  В наше время особенно актуальна мысль Данилевского о том что необходимым условием расцвета культуры является политическая независимость. Отрицая существование единой мировой культуры Данилевский выделял 10 культурноисторических типов египетский китайский ассировавилонский индийский иранский и др. Арнольд Джозеф Тойнби 1889 1975 английский историк и социолог автор 12томного Исследования истории 1934 1961 труда в котором он стремился осмыслить развитие человечества в духе круговорота цивилизаций употребляя этот термин в...
29237. Первобытность и цивилизация 48 KB
  Кочевой образ жизни оказывался на периферии культуры. Новый хозяйственный и административный уклад принципиально меняет содержание духовной культуры: нравственная нейтральность этическая невменяемость Г. Все восточные культуры единообразны не однообразны пластичны жизнестойки. Восточные культуры способны создавать величайшие культурные ценности при сравнительно низком развитии индивидуального я и вообще самодеятельнотворческого начала.
29238. Индо-буддистский тип культуры 30.5 KB
  это учение было изложено в четырех сборниках: Ригведа Книга гимнов Яджурведа Книга жертв Самаведа Книга песен Артхарваведа Книга жрецов .
29239. Теория модернизации 36 KB
  Термин модернизация относится не ко всему периоду социального прогресса а только к одному его этапу современному. Органическая модернизация является моментом собственного развития страны и подготовлена всем ходом предшествующей эволюции. Такая модернизация начинается не с экономики а с культуры и изменения общественного сознания. Неорганическая модернизация являет собой ответ на внешний вызов со стороны более развитых стран.