83721

ДЕРЕВА І ГРАФИ В МОВІ ПРОГРАМУВАННЯ С

Лабораторная работа

Информатика, кибернетика и программирование

Дерева. Основні поняття Дерева являють собою найбільш важливі нелінійні структури що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев серед яких особливою популярністю користуються бінарні двійкові дерева.

Украинкский

2015-03-16

221.77 KB

8 чел.

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Кафедра САПР

Звіт

до лабораторної роботи № 7

з курсу:

“Проблемно-орієнтоване програмування”

на тему:

ДЕРЕВА І ГРАФИ

В МОВІ ПРОГРАМУВАННЯ С


Виконав:

студент групи КН – 25

Ступницький С

Прийняв:

Дупак Б.П.

Львів 2014

1. МЕТА РОБОТИ

Мета роботи - навчитися використовувати логічну структуру дерев для програмування задач з використанням графів.

2.1. Дерева. Основні поняття

Дерева являють собою найбільш важливі нелінійні структури, що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев, серед яких особливою "популярністю" користуються бінарні (двійкові) дерева. Вони застосовуються у різноманітних  алгоритмах (програмах): наприклад, деякі компілятори з мов високого рівня використовують їх для аналізу й обчислення арифметичних виразів. Ще однією причиною популярності бінарних дерев є простота їхньої організації.

Дерево - це неорієнтований зв'язний граф без циклів. Визначимо формальне дерево як скінченну множину Т, яка складається з одного або більше вузлів, таких, що:

  1. є один позначений вузол, який називається коренем даного дерева;
  2. інші вузли (крім кореня) містяться в m >= 0 множинах Т1, Т2, ..., Тm, які попарно не перетинаються, і кожна з яких у свою чергу є деревом.

Дерева Т1, Т2, ..., Тm називаються піддеревами даного дерева.

Це визначення є рекурсивним, тобто воно визначає дерево в термінах самих же дерев. З нього слідує, що кожний вузол дерева є коренем деякого піддерева, що міститься в цьому дереві. Число таких піддерев у даному вузлі називають його ступенем. В бінарних деревах є також листя. Це вузли з нульовим степенем. Всі інші (некінцеві) вузли називають вузлами розгалуження.

Корінь - це такий вузол, з якого йдуть зв'язки до всіх інших элементів дерева. Дерева на папері зображують так: спочатку малюють корінь, потім від нього малюють зв’язки до вузлів-нащадків, від них зв'язки до їхніх нащадків і т. д. Ще однією характеристикою дерева є його висота. Це шлях максимальної довжини від листка до кореня.

2.1.1. Бінарні дерева

Двійковим або бінарним деревом називають неорієнтований граф наступного виду

Рівень 1 (корінь)

Рівень 2 (вузли)

Рівень 3 (вузли)

Рівень 4 (листя)

Рис. 1.

У бінарному дереві кожний вузол має тільки два піддерева. У кожного вузла є ліве й праве піддерево. Вузол і його піддерева називають взагалі по-різному, наприклад: батько, син і брат; або: батько з "лівим" і "правим" синами.

Більш формально бінарне дерево можна визначити як скінченну множину вузлів, яка або пуста, або складається з кореня з одним/двома бінарними деревами, що не перетинаються.

3. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

23.Скласти програму упорядкування елементів дерева по зростанню з використанням рекурсивної функції.

Текст програми: 

#include "stdafx.h"

#include <iostream>

#include <cstdlib>

using namespace std;

class BinaryTree

{

private:

struct Binary

{

 Binary* leftCh;

 Binary* rightCh;

 int data;

};

Binary* root;

public:

BinaryTree()

{

 root = NULL;

}

bool Empty() const { return root == NULL; }

void print_inorder();

void inorder(Binary*);

void insert(int);

};

void BinaryTree::insert(int d)

{

 }

Binary* tree = new Binary;

Binary* parent;

tree->data = d;

tree->leftCh = NULL;

tree->rightCh = NULL;

parent = NULL;

// is this a new tree?

if (Empty()) root = tree;

else

{

 //Note: ALL insertions are as leaf nodes

 Binary* curr;

 curr = root;

 // Find the Node's parent

 while (curr)

 {

  parent = curr;

  if (tree->data > curr->data) curr = curr->rightCh;

  else curr = curr->leftCh;}

 if (tree->data < parent->data)

  parent->leftCh = tree;

 else

  parent->rightCh = tree;

}

}

void BinaryTree::print_inorder()

{

inorder(root);

}

void BinaryTree::inorder(Binary* p)

{

if (p != NULL)

{

 if (p->leftCh) inorder(p->leftCh);

 cout << " " << p->data << " ";

 if (p->rightCh) inorder(p->rightCh);

}

else return;

}

int main()

{

BinaryTree b;

int x, xx, xxx;

cout << "Elements of a B-tree: ";

cin >> xx;

cout << "\nEnter a data : ";

for (xxx = 1; xxx <= xx; ++xxx)

{

 cin >> x;

 b.insert(x);

}

cout << endl;

cout << "       Inorder      " << endl;

cout << " -------------------" << endl;

b.print_inorder();

 cout << endl;

}

Результат:

5. АНАЛІЗ РЕЗУЛЬТАТІВ ТА ВИСНОВКИ

На цій лабораторній роботі я  навчився використовувати логічну структуру дерев для програмування задач з використанням графів.


 

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

15846. Кино и семиотика реальности 126.5 KB
  Имманентная биография Кино и семиотика реальности Пьера Паоло Пазолини €œДавайте внимательно просмотрим шестнадцатимиллиметровую пленку на которой заснят момент убийства президента Кеннеди. Эта пленка есть типичнейший планэпизод. Самый типичный из всех возможн...
15847. Эйзенштейн сегодня 93.5 KB
  Н.Клейман О.Косолапов Н.Сиривля ЭЙЗЕНШТЕЙН СЕГОДНЯ1 Наталья Сиривля. Со дня смерти Эйзенштейна прошло уже почти пятьдесят лет но мы до сих пор не в состоянии освоить его наследие. Отношение к нему все время меняется: мы то низвергаем его то вновь водружаем на пьеде
15848. Проблема постмодерна и фильм Питера Гринауэя «Брюхо архитектора» 154.5 KB
  Г. С. Кнабе Проблема постмодерна и фильм Питера Гринауэя Брюхо архитектора Кнабе Г.С. Древо познания древо жизни. М.: РГГУ 2006 с. 331344 Предметом настоящих заметок будет духовная и социокультурная ситуация в которой сегодня находится большая ч
15849. КИНО — ИСКУССТВО ИЗОБРАЗИТЕЛЬНОЕ 56.5 KB
  Aлександр Княжинский €œКИНО ИСКУССТВО ИЗОБРАЗИТЕЛЬНОЕ€1 Из лекции во ВГИКе Давайте начнем с самого начала... Первое к чему я вас призываю никогда не натаскивайте в павильон где вам предстоит снимать много реквизита. Что обычно происходит в процессе съемки Ас...
15850. Взрывобезопасность. Взрывозащищенное (Ex) оборудование 488 KB
  Вид взрывозащиты – специальные меры, предусмотренные в электрооборудовании с целью предотвращения воспламенения окружающей взрывоопасной среды; совокупность средств взрывозащиты электрооборудования, установленная нормативными документами.
15851. Психоанализ о кино и кино о психоанализе 86 KB
  Ксения Корбут Психоанализ о кинои кино о психоанализе Данная статья представляет собой краткий обзор психоаналитических размышлений о кино и предназначается для тех кто не только любит кино но и хочет знать как же оно воздействует на зрителей. Иначе говоря кому инт...
15852. Язык-это баланс, а фильм-сюрприз 51.5 KB
  Дэвид Кроненберг Язык это баланс а фильм сюрприз1 Журнал Стюдио Studio Франция ведет рубрику Урок кино предназначенную для массового читателя и начинающих кинематографистов. В ней выступают многие крупные режиссеры излагающие свои вз
15853. Режиссер - это хозяин 135 KB
  Дэвид Линч РЕЖИССЕР ЭТО ХОЗЯИН1 В юности я хотел стать художником. Но во время занятий живописью я снял маленький мультфильм для того чтобы показывать его без перерыва нонстоп то есть в виде кольца на объемном так называемом скульптурном эк...
15854. Титаник. Спецэффекты в фильме 627.5 KB
  Титаник. Спецэффекты в фильме Автор: Дмитрий Мороз Титаник корабльлегенда изза своего катастрофического крушения навеки оставшийся в памяти простых смертных. Титаник фильм снятый за умопомрачительные 200 млн. долларов и ставший в итоге самой кассовой картин...