83721

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

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

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

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

Украинкский

2015-03-16

221.77 KB

11 чел.

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

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

Кафедра САПР

Звіт

до лабораторної роботи № 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. АНАЛІЗ РЕЗУЛЬТАТІВ ТА ВИСНОВКИ

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


 

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

52419. Числа Фібоначчі та їх основні властивості 839.5 KB
  Числа Фібоначчі та їх основні властивості Методичні розробки для факультативних занять Зміст Передмова. Що таке числа Фібоначчі. Деякі найпростіші властивості чисел Фібоначчі. Властивості чисел ФібоначчіНарайани.
52420. Действия с рациональными числами 408 KB
  На нашем уроке работает Зеленый патруль 1 задание Деревья способствуют очищению воздуха поглощая углекислый газ и выделяя кислород. 2 задание. Каждый получает карточку с заданием. Координатная прямая проектируется не экран 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 Я У К Ь Д Л...
52421. Розвязування вправ з теми «Дії над раціональними числами» 130 KB
  Розвивати вміння учнів знаходити суму, різницю та добуток раціональних чисел, працювати з різними видами чисел; виховувати увагу, спостережливість при виконанні завдань.
52422. Дії з натуральними числами 63 KB
  Обладнання: сніжинка переможець проведеного напередодні конкурсу ялинка іграшкиналіпки картина Святий Миколай. Головним його атрибутом є новорічна ялинка. 4м і 6м Яка гарна ялинка виходить У кожного вдома теж буде ялинка. Назва роботи Урокгра математики в 5 класі Новорічна ялинка П.
52423. Загальна характеристика Членистоногих 115.5 KB
  Загальна характеристика Членистоногих Мета уроку: ознайомити із загальними рисами типу; відмітити ускладнення організації членистоногих порівняно з кільчаками; зясувати їхнє походження; розкрити різноманітність членистоногих їхню роль у природі та житті людини; формувати навички роботи з текстом підручника вміння виділяти головне порівнювати робити висновки; розвивати пізнавальні пошукові та творчі можливості учнів під час створення проектів розвивати вміння презентувати власну роботу; формувати основи екологічного мислення Тип уроку:...
52424. Chocolate is good for you 94.5 KB
  INTRODUCTION t the lesson we re going to tlk with you bout chocolte nd its role nd plce in our life.CHOCOLTE: Wlk round the clss nd tlk to other students bout chocolte. studies fntstic news reserch diet hert ttcks milk chocolte risks suffering stroke nutrition blood pressure weight gin clories sweets snck Hve cht bout the topics you liked.
52425. Чорнобиль не має минулого. Історія Чорнобильської трагедії крізь призму української літератури 72.5 KB
  Історія Чорнобильської трагедії крізь призму української літератури Мета: розширити знання дітей про Чорнобильську трагедію розповісти про ліківідаторів аварії на Чорнобильській АЕС розкрити трагедію ЧАЕС через твори українських письменників; розвивати вміння школярів аналізувати та узагальнювати навчальну інформацію вміння виразно декламувати артистичні здібності; виховувати співчуття до чужого болю любов до рідного краю природи; виховувати людяність доброту згуртованість. Драч Чорнобильська мадонна М. І тихо ступає життя у полин...
52427. Чорнобиль – найбільша трагедія світу 50 KB
  Досліджуючи солі урану він виявив що уран випромінює невидимі промені. фізик і хімік Петербурзької Академії наук невидимі промені назвала радіоактивними а явище випромінювання радіоактивністю. У забруднених зонах спостерігаються масові аномалії тому що радіонукліди потрапивши в організм людини випромінюють радіоактивні промені які руйнують клітини. випромінювання це потік позитивно заряджених частинок з масою атома Гелію промені це потік негативно заряджених електронів це потік електромагнітних хвиль подібних до звичайного...