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

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


 

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

11221. Фонетическое слово, синтагма, фраза, фоноабзац, текст. СЛОГ 93.5 KB
  Лекция 9 Фонетическое слово синтагма фраза фоноабзац текст. СЛОГ На предыдущей лекции мы выяснили что слог представляет собой симбиозную фонетикофонологическую единицу. Просодические единицы такие как например ударение и тон влияют в большей степени на сло
11222. Фоностилистическая дифференциация речи. Предмет и задачи фоностилистики 121 KB
  ЛЕКЦИЯ 14. Фоностилистическая дифференциация речи. Предмет и задачи фоностилистики. Как мы убедились в предыдущих лекциях произношение не может быть однородным. Оно меняется под воздействием многочисленных факторов. Поскольку эти факторы никак не влияют на переда...
11223. Discuss different opinions of the threat of population growth on our planet 24 KB
  Discuss different opinions of the threat of population growth on our planet. From the very start I want to admit that population growth as well as other global problems in the world is an urgent one. For decades the population explosion has been giving people nightmares. The worlds population increases by 3 every second and by a billion every decade. With figures such as these the gloom is understandable. There school of thought that the battle to feed all the humanity is over....
11224. Talk about the problems a newly-independent state is confronted with 23.5 KB
  Talk about the problems a newlyindependent state is confronted with. Chinese people say that the worst thing is to live in the time of changes. With the rich choice of possible way of further development comes a bunch of problems as well. Its especially true for newlyindependent states. Id like to illustrate this on the example of Samoa. For centuries time stood still in Samoa. The people worked at banana plantations and respected the customs that the family chiefs presented abso...
11225. Talk on how parents feel about their children travelling on their own for the first time 23.5 KB
  Talk on how parents feel about their children travelling on their own for the first time. It goes without saying that parents is always get worried when their children go abroad to visit new places and get to know other ways of living. Without any doubt traveling is necessary for all of us as it broadens our minds and horizons its kind of relaxation and a wonderful opportunity to get away from it all. When children go on a journey they relax their body refresh their spirits and renew ...
11226. Talk about stereotyped ideas that people may have about the way of life in oyher countries 24.5 KB
  Talk about stereotyped ideas that people may have about the way of life in oyher countries. Nobody wants to be average. So generalizations about nations arent usually welcomed though sometimes they are quiet accurate. The dangers may go even deeper when someone tries to generalize from his own limited experience. The Americans for instance are the nation about which numerous stereotyped ideas exist. They are created as a rule by the people who have never been to the USA but n...
11227. Talk about madame tussaud’s as one of london’s famous museums 24.5 KB
  Talk about madame tussauds as one of londons famous museums. It often comes as a shock for Londoners that Madame Tussauds museum is one of the capital top tourist attractions. Many find it gruesome and frightening. Others maintain that its collection of wax statues has no artistic merit. Yes despite this criticism Madam Tussauds has become a world famous. Millions of tourists from overseas and from other parts of Britain wouldnt consider their trip to the capital worthwhile with...
11228. TAIK ABOUT HOLYWOOD AND THE EPICS PRODUCED THERE IN THE 1930S AND 1940S 23.5 KB
  TAIK ABOUT HOLYWOOD AND THE EPICS PRODUCED THERE IN THE 1930S AND 1940S. Nowadays for million if people theres nothing better than watching a good film and the vast majority of films are produced in Hollywood. But what we really know about this really know about this greatstar factory To tell the truth everything we read about the great days of Hollywood in the 30s and 40s seems like exaggeration. The studious always said their film were superb and colossal because vast s...