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. АНАЛІЗ РЕЗУЛЬТАТІВ ТА ВИСНОВКИ

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


 

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

34873. Класифікація населення україни.Рівень безробіття 24.5 KB
  Рівень безробіття 1. Рівень безробіття безробіття робоча сила. У звязку з тим що добровільне безробіття є і Д нормальним явищем то повна зайнятість припускає що економіка ніколи не V функціонує при 100 зайнятості робочої сили. Повна зайнятість це зайнятість яка складає менше 100 наявної робочої сили що припускає фрикційну та структурну форми безробіття.
34874. Сутність і показники інфляції 23 KB
  сутність і показники інфляції Інфляція це підвищення загального рівня цін. Дефляція зворотне явище тобто зниження загального рівня цін. В економічній літературі дискусійним є питання про те чи всяке підвищення цін є інфляційним. Більшість економістів вважають що будьяке підвищення цін означає інфляцію.
34875. Види інфляції 23.5 KB
  По причині виникнення :1) Інфляція попиту –виникає в результаті перевищення спроса попиту над пропозицією 2)Інфляція іздержок -виникає в результаті збільшення іздержок виробництва і зменшення пропозиції в результаті збільшення заробітної плати і збільшенням уін на ресурси (крива пропозиції буде відхилятися вліво).
34876. Сутність і функції грошей 24.5 KB
  Сутність і функції грошей Гроші це загальний еквівалент що виконує основні функції: міра ітості засіб обігу і засіб заощадження. Гроші як загальний еквівалент виникли ще в VII 111 і до нашої ери і виступали у вигляді товару що виражає вартість всіх і ч товарів що дозволяло легко порівнювати товари між собою. Цю функцію гроші виконують безпосередньо і виступають у якості посередника в товарному обігу. У 1690 року в Північній Америці з'явилися замінники золота у вигляді паперових грошей коли гроші вільно...
34877. Види і засоби, що замінюють гроші 23.5 KB
  Вексель письмове зобовязання боржника сплатити визначену суму грошей у визначений термін. Звичайний вексель має такі реквізити: 1 найменування; 2 визначену суму платежів; 3 зазначення терміну платежу; 4 найменування того кому має бути здійснено платіж; 5 місце дату складання векселю і підпис того хто його видав. Вексель може розпочати самостійний рух якщо він передається від одного власника держателя до іншого шляхом особливого передатного напису індосаменту. Вексель можна передати банку отримавши із певною знижкою борг...
34878. Поняття кредит . Види кредиту 20.5 KB
  Позички торговим і промисловим підприємствам. Позички під застану нерухомості. Споживчі позички приватним особам що повертаються вроздріб. Позички під цінні папери даються для придбання акцій та інших цінних паперів.
34879. Функції центрального банку 21 KB
  функції центрального банку Центральний банк головний банк що регулює грошовий обії країни і визначає основи кредитної політики держави. Особливість функціонування центрального банку Сучасні центральні банки характеризуються двоїстістю положення: з однієї сторони їхня діяльність повинна бути погоджена з економічною політикою держави з іншого боку вони повинні мати самостійність у проведенні фінансовокредитної політики держави.