83721

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

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

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

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

Украинкский

2015-03-16

221.77 KB

10 чел.

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

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

Кафедра САПР

Звіт

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

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


 

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

40985. Трудові спори і порядок розв’язання 183.5 KB
  Поняття трудових спорів та їх класифікація При здійсненні відносин людей під час трудової діяльності між працівниками і власниками підприємств або уповноваженими ними органами можуть виникати й часто виникають різного роду непорозуміння. Перебудова виробничих і трудових відносин нові форми застосування і використання праці істотно вплинули не тільки на індивідуальні трудові відносини а й на структуру і зміст організаційноуправлінських відносин що виникають між власником підприємства або уповноваженою ним особою з одного боку і трудовим...
40986. 4-х комнатный жилой дом мансардного типа 103.5 KB
  Расширился ассортимент, и повысилось качество применяемых в отечественном строительстве отделочных материалов — всех видов керамической плитки, покрытий для пола и стен, а также керамических санитарных и санитарно-технических изделий.
40987. Мова і культура 148.5 KB
  Однак з іншого боку у самій матерії мови у ряду істотних характеристик мовної структури позначилася біологічна природа людини. Психофізіологічні можливості знакової діяльності людини зумовили багаторівневу організацію мови визначили кількісні параметри окремих рівнів наприклад обсяг фонологічної системи що коливається в різних мовах в інтервалі від 10 до 100 одиниць; обсяг словника в інтервалі від 10 тисяч до півмільйона слів; вияв надмірності в мові. Культура визначає план змісту мови. У молекулярній біології і семіотиці був виявлений...
40988. Стратегии позиционирования в маркетинге, стратегия эффективного позиционирования, проблемы разработки стратегии позиционирования 233 KB
  Целью данной работы является детальное изучение понятия позиционирования в маркетинге и рассмотрение стратегий позиционирования. Для достижения поставленной цели мною решались следующие задачи: раскрытие понятия позиционирования, выявления ключевых концепций и идей позиционирования
40989. ПОЛІТИЧНА ЛІНГВІСТИКА. МОВНА ПОЛІТИКА 115.5 KB
  Потрыбно постійно памятати що будьяке рішення щодо мови це політичне рішення яке має прийматися при одночасному врахуванні обєктивних комунікативних потреб й механізму групової ідентифікації. Крисін ставлять перед собою і таке завдання: регулювати розвиток і функціонування мови мов не покладаючись цілком на самоплин мовного життяâ. На нашу думку не самі соціолінгвісти регулюють розвиток і функціонування мови чи мов у суспільстві а держава її владні інститути. Сьогодні вже можна говорити про чітко окреслену...
40990. Психологія стресу та його наслідки 80.5 KB
  Функції природа та фази стресу. Методи подолання стресу. Стан стресу може виникати під впливом найрізноманітніших життєвих умов починаючи із повсякденних турбот і закінчуючи екстремальними ситуаціями так званими ударами долі .
40991. Проектирование 2-х этажного пятикомнатного жилого дома 121 KB
  Однако на сегодняшний день ситуация на рынке малоэтажного строительства еще весьма неоднозначна. С одной стороны, есть огромный неудовлетворенный потенциальный спрос на загородное жилье у горожан, уставших от городского шума, плохой экологии и тесноты. С другой стороны, наблюдается явное несоответствие спроса и предложения на рынке.
40992. ПЛАНУВАННЯ НАВЧАЛЬНОГО ПРОЦЕСУ З ІНОЗЕМНОЇ МОВИ 153 KB
  Система планування в середній школі охоплює послідовне планування в межах усього курсу навчання чвертей циклу уроків та окремого уроку виходячи з конкретних цілей кожного відрізка навчального процесу. Вчитель повинен усвідомити призначення кожного елемента уроку його взаємодію з іншими елементами уроку. Підготовча робота вчителя до уроку здійснюється послідовно і включає: аналіз змісту матеріалу визначення типу уроку формулювання цілей уроку поетапний розподіл навчального матеріалу визначення часу на його опрацювання розробку...
40993. ЭКОНОМИЧЕСКАЯ ЭФФЕКТИВНОСТЬ ПРОИЗВОДСТВА КАРТОФЕЛЯ НА ПРИМЕРЕ СПК «КУШЛИКИ» 1.33 MB
  Дать организационно-экономическую характеристику СПК «Кушлики»; изучить экономическую эффективность отрасли картофелеводства и пути его повышения; дать характеристику экономической эффективности картофелеводства на примере СПК «Кушлики»; предложить мероприятия по повышению экономической эффективности производства картофеля.