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

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


 

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

12853. Автопортрет отрядное мероприятие. Знакомство детей в пионерлагере 21 KB
  АВТОПОРТРЕТ. Задача: познакомить детей друг с другом. Период смены: организационный. Возраст детей: кроме старших. Продолжительность: 4060 мин. Количество детей: весь отряд. Место проведения: отрядное место. Оборудование: 5 карточек. Делим отряд на 5 г...
12854. СТРАШНЫЙ СУД Карточная групповая профориентационная игра 182 KB
  СТРАШНЫЙ СУД Карточная групповая профориентационная игра Эта игра помогает подростку увидеть свои возможности и в соответствии с ними выбирать профессиональные и жизненные цели. Игра имеет диагностические психокоррекционные и прогностические аспекты. ОБЩЕЕ
12855. ИГРА Профконсультация 208.5 KB
  ИГРА Профконсультация Целью игры профконсультация является специально организованная помощь школьников друг другу при выборе профессии под наблюдением и контролем психолога. Игра имеет разные варианты которые имеют отдельные описания. В некоторых вариантах иг
12856. БУДЬ ГОТОВ! Активизирующая профориентационная методика 118 KB
  БУДЬ ГОТОВ Активизирующая профориентационная методика Цель этой методики повысить у старшеклассников уровень осознания своей готовности к различным видам профессионального труда.Эту методику можно использовать при работе с классом группой а можно в индивидуа...
12857. ИГРА УГАДАЙ ПРОФЕССИЮ 35 KB
  ИГРА УГАДАЙ ПРОФЕССИЮ ЦЕЛЬ ИГРЫ. Знакомство школьников с научной схемой анализа профессий. Игра используется при изучении тем Профессиограмма Формула профессии а также при знакомстве с конкретными профессиями различных отраслей народного хозяйства. УСЛОВИЯ ИГ
12858. Психологическая игра Звездные планеты 35.5 KB
  Психологическая игра Звездные планеты Цель игры: поставить перед детьми проблему по созданию новых планет. Психологическая цель: обучить детей совместной практической деятельности. Задачи: Развивать навыки сотрудничества и умение соревноваться со сверстниками п...
12859. СЦЕНАРИЙ ДЛЯ СВОБОДНОГО ПЛАВАНИЯ 89 KB
  СЦЕНАРИЙ ДЛЯ СВОБОДНОГО ПЛАВАНИЯ Существуют истории финал которых заранее не известен. Есть только многочисленные дороги распутья перекрестки и изредка камни с кратким описанием последствий: направо пойдешь... налево пойдешь... Остается только догадываться что ждет...
12860. НАЧИНАЕМ РАЗГОВОР Игра для учащихся пятых классов 37.5 KB
  НАЧИНАЕМ РАЗГОВОР Игра для учащихся пятых классов В одном из номеров Школьного психолога за этот год читатели имели возможность познакомиться с моделью психологопедагогического сопровождения школьников на этапе перехода из начальной школы в среднюю см. ст
12861. ПЕРВЫЙ КЛАССНЫЙ ЧАС В 5 КЛАССЕ 31.5 KB
  ПЕРВЫЙ КЛАССНЫЙ ЧАС В 5 КЛАССЕ Возраст 10 11 12 лет. Дети этого возраста обучаются у нас в пролицейском отделении. Поступают после начальной школы и переходят от нас во взрослый лицей через 3 года. Поступают из всех школ района умные замечательные с огромным желанием...