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.

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


 

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

81565. Трансмембранная передача сигнала. Участие мембран в активации внутриклеточных регуляторных систем - аденилатциклазной и инозитолфосфатной в передаче гормонального сигнала 109.02 KB
  Важное свойство мембран - способность воспринимать и передавать внутрь клетки сигналы из внешней среды. \"Узнавание\" сигнальных молекул осуществляется с помощью белков-рецепторов, встроенных в клеточную мембрану клеток-мишеней или находящихся в клетке. Клетку-мишень определяют по способности избирательно связывать данную сигнальную молекулу
81566. Коллаген: особенности аминокислотного состава, первичной и пространственной структуры. Роль аскорбиновой кислоты в гидоксилировании пролина и лизина 108.5 KB
  В межклеточном матриксе молекулы коллагена образуют полимеры называемые фибриллами коллагена. Фибриллы коллагена обладают огромной прочностью и практически нерастяжимы. Молекулы коллагена состоят из трёх полипептидных цепей называемых αцепями. Первичная структура αцепей коллагена необычна так как каждая третья аминокислота в полипептидной цепи представлена глицином около 1 4 аминокислотных остатков составляют пролин или 4гидроксипролин около 11 аланин.
81567. Особенности биосинтеза и созревания коллагена. Проявления недостаточности витамина С 106.89 KB
  Синтез и созревание коллагена сложный многоэтапный процесс начинающийся в клетке а завершающийся в межклеточном матриксе. Синтез и созревание коллагена включают в себя целый ряд посттрансляционных изменений: гидроксилирование пролина и лизина с образованием гидроксипролина Hyp и гидроксилизина Hyl; гликозилирование гидроксилизина; частичный протеолиз отщепление сигнального пептида а также N и Сконцевых пропептидов; образование тройной спирали. Синтез полипептидных цепей коллагена.
81568. Особенности строения и функции эластина 103.27 KB
  Эластин содержит довольно много пролина и лизина но лишь немного гидроксипролина; полностью отсутствует гидроксилизин. В образовании этих сшивок участвуют остатки лизина двух трёх или четырёх пептидных цепей. Предполагают что эти гетероциклические соединения формируются следующим образом: вначале 3 остатка лизина окисляются до соответствующих εальдегидов а затем происходит их соединение с четвёртым остатком лизина с образованием замещённого пиридинового кольца. Окисление остатков лизина в εальдегиды осуществляется медьзависимой...
81569. Гликозаминогликаны и протеогликаны. Строение и функции. Роль гиалуроновой кислоты в организации межклеточного матрикса 192.62 KB
  Протеогликаны высокомолекулярные соединения состоящие из белка 510 и гликозаминогликанов 9095. Протеогликаны отличаются от большой группы белков которые называют гликопротеинами. Гликозаминогликаны и протеогликаны являясь обязательными компонентами межклеточного матрикса играют важную роль в межклеточных взаимодействиях формировании и поддержании формы клеток и органов образовании каркаса при формировании тканей.
81570. Адгезивные белки межклеточного матрикса: фибронектин и ламинин, их строение и функции. Роль этих белков в межклеточных взаимодействиях и развитии опухолей 104.14 KB
  К первой группе белков с выраженными адгезивными свойствами относят фибронектин ламинин нидоген фибриллярные коллагены и коллаген IV типа; их относят к белкам зрелой соединительной ткани. Фибронектин. Фибронектин один из ключевых белков межклеточного матрикса неколлагеновый структурный гликопротеин синтезируемый и выделяемый в межклеточное пространство многими клетками.
81571. Структурная организация межклеточного матрикса. Изменения соединительной ткани при старении, коллагенозах. Роль коллагеназы при заживлении ран. Оксипролинурия 112.48 KB
  Роль коллагеназы при заживлении ран. Коллаген IX типа антипараллельно присоединяется к фибриллам коллагена II типа. Его глобулярный НК4домен основный он не связан с фибриллами коллагена II типа и поэтому к нему может присоединяться такой компонент матрикса как гиалуроновая кислота. Микрофибриллы которые образуются тетрамерами коллагена VI типа присоединяются к фибриллам коллагена II типа и к гиалуроновой кислоте.
81572. Важнейшие белки миофибрилл: миозин, актин, актомиозин, тропомиозин, тропонин, актинин. Молекулярная структура миофибрилл 116.56 KB
  Молекулярная масса миозина скелетных мышц около 500000 для миозина кролика 470000. Молекула миозина имеет сильно вытянутую форму длину 150 нм. Легкие цепи находящиеся в головке миозиновой молекулы и принимающие участие в проявлении АТФазнойактивности миозина гетерогенны по своему составу. Количество легких цепей в молекуле миозина у различных видов животных и в разных типах мышц неодинаково.
81573. Биохимические механизмы мышечного сокращения и расслабления. Роль градиента одновалентных ионов и ионов кальция в регуляции мышечного сокращения и расслабления 107.85 KB
  В настоящее время принято считать что биохимический цикл мышечного сокращения состоит из 5 стадий: 1 миозиновая головка может гидролизовать АТФ до АДФ и Н3РО4 Pi но не обеспечивает освобождения продуктов гидролиза. Актомиозиновая связь имеет наименьшую энергию при величине угла 45 поэтому изменяется угол миозина с осью фибриллы с 90 на 45 примерно и происходит продвижение актинана 1015 нм в направлении центра саркомера; 4 новая молекула АТФ связывается с комплексом миозинFактин; 5 комплекс миозинАТФ обладает низким...