83721

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

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

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

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

Украинкский

2015-03-16

221.77 KB

9 чел.

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

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

Кафедра САПР

Звіт

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

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


 

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

68823. Привод (Электродвигатель: АИР 100L6) 866 KB
  Наиболее распространены горизонтальные редукторы. Как горизонтальные, так и вертикальные редукторы могут иметь колеса с прямыми, косыми и круговыми зубьями. Корпус чаще всего выполняют литым чугуном, реже сварным стальным. Валы монтируются на подшипниках качения или скольжения.
68824. Перетворення вхідної граматики у LL(1)-граматику 93 KB
  Аналогічне ствердження має місце відносно ліворекурсивного циклу приклад якого дають правила 1. У наведеному прикладі правила 2 3 4 6 утворюють ліворекурсивний цикл який завжди можна вилучити перетворив одне з правил наприклад 6 у ліву рекурсію. Для С існують два правила 4 та 5.
68825. Застосування ДМП-автомату для реалізації висхідного аналізу 179 KB
  Для реалізації висхідного аналізу використовується ДМП-автомат, який працює за таким принципом. Якщо вхідний рядок приймається, то у кожному такті конкатенація символів, що знаходяться у магазині, і символів, що належать до ще непрочитаної частини вхідного рядка, утворює...
68826. Порівняння LL- та LR-методів розбору 180 KB
  Генерація коду проміжний код транслююча граматика Кінцевою ціллю компіляції є отримання програми у машинному коді. Часто генерація коду здійснюється паралельно з побудовою дерева. У разі коли для отримання машинного коду виконуються декілька проходів треба передавати уявлення дерева з одного проходу у інший.
68827. Генерація машинного коду 79.5 KB
  Для перевірки подібних обмежень у компіляторах застосовують таблиці символів у яких запамятовують для кожного ідентифікатора його тип а можливо і іншу інформацію. У момент читання прикладної реалізації компілятор здійснює пошук відповідної інформації у таблиці.
68828. Використання бінарних дерев при роботі з таблицею символів 163 KB
  Кожний елемент містить змістовну частину і два покажчики на інші вершини. Вершини А С F що не мають ненульових покажчиків називають листями. Окремим випадком дерева є пусте дерево і дерево що складається з однієї вершини. Якщо у дереві є покажчик від вершини А до В то В називають прямим нащадком або сином А.
68829. Розподіл пам’яті 79.5 KB
  Етап розподілу памяті майже не залежить від мови програмування та машини. Якщо у тексті вхідної програми зустрічається опис ідентифікатору що дозволяє визначити необхідний обєм памяті для його зберігання то компілятор спеціальним чином виділяє потрібну память.
68830. Компоненти лінгвістичного забезпечення САПР 60.5 KB
  Звичайно у засобах лінгвістичного забезпечення САПР виділяють три основні групи: мови програмування мови проектування та мови керування. Мови програмування використовують для розробки програм САПР.
68831. Формальні мови 88.5 KB
  Форма уявлення інформації визначається мовою тому у поданій дисципліні розглядаються питання повязані з переходом від однієї мови до іншої при представленні деякої інформації. Формальні мови Природні мови англійська російська українська та ін. Позбавитись цих недоліків природних мов дозволило...