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

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


 

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

11414. Запросы определения данных SQL 59.5 KB
  Лабораторная работа № 2. Запросы определения данных SQL. Задание: 1. Определить схемы разработанных отношений на SQLсервере. Обосновать выбор типов данных атрибутов отношений. 2. Определить произвольный двух или трехзначный атрибут пол статус и т.д. и ввести его в одн
11415. Запросы выборки данных SQL 41.5 KB
  Лабораторная работа № 3. Запросы выборки данных SQL. Задание: Создать запросы: 1. На выборку всех кортежей отношения 2. На выборку всех значений нескольких атрибутов отношения. 3. Запрос на выборку значений нескольких атрибутов с назначением альтернативных име
11416. Работа с РБД в MS Access 87 KB
  Лабораторная работа № 4. Работа с РБД в MS Access. Задание: 1. Создать формы для ввода данных. 2. Визуализировать схему данных. 3. Создать отчеты для вывода результатов запросов. Access: запросы формы отчеты макросы. Запрос это объект базы данных являющийся основн
11417. Оценка информационной меры Харкевича в СИИ 139.5 KB
  Лабораторная работа N 7 Оценка информационной меры Харкевича в СИИ Задание на ЛР дать навыки количественной оценки семантической меры Харкевича путем построения моделей при синтезе экспертных систем в среде нейросетевого конструктора. Применить на практике д...
11418. Секундомер в Visual Basic 34.5 KB
  Секундомер 1.Нарисовать кнопку на листе 2.Установить указатель мыши на кнопке и нажать правую кноп...
11419. ИССЛЕДОВАНИЕ МИКРОТРАНСФОРМАТОРА 50.52 KB
  ИССЛЕДОВАНИЕ МИКРОТРАНСФОРМАТОРА 4. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 4.1. Опыты холостого хода и с нагрузкой Собрать цепь по рис. 1. Собранную цепь показать преподавателю или лаборанту. Рис. 1 Таблица 1 U1 ...
11420. ВИДЫ И ЦЕЛИ ТЕРМИЧЕСКОЙ ОБРАБОТКИ СТАЛИ. ОПРЕДЕЛЕНИЕ ТЕМПЕРАТУРЫ КРИТИЧЕСКИХ ТОЧЕК МЕТОДОМ ПРОБНЫХ ЗАКАЛОК 159.5 KB
  Учебноисследовательская работа № 6 ВИДЫ И ЦЕЛИ ТЕРМИЧЕСКОЙ ОБРАБОТКИ СТАЛИ. ОПРЕДЕЛЕНИЕ ТЕМПЕРАТУРЫ КРИТИЧЕСКИХ ТОЧЕК МЕТОДОМ ПРОБНЫХ ЗАКАЛОК 6.1. Цель работы Данная работа предполагает: изучение фазовых превращений в сплавах железа при нагреве и охлажден
11421. ВИЗНАЧЕННЯ ПОСТІЙНОЇ ПЛАНКА ЗА СПЕКТРОМ АТОМА ВОДНЮ 191.5 KB
  Лабораторна робота №5 ВИЗНАЧЕННЯ ПОСТІЙНОЇ ПЛАНКА ЗА СПЕКТРОМ АТОМА ВОДНЮ Мета роботи: Вивчення методу визначення постійної Планка за спектром водню. Прилади та обладнання: універсальний монохроматор УМ2 ртутнокварцова лампа джерело живлення Спектр1 газороз...
11422. ИЗМЕРЕНИЯ БАЛЛИСТИЧЕСКИМ ГАЛЬВАНОМЕТРОМ 720 KB
  Лабораторная работа № 6 ИЗМЕРЕНИЯ БАЛЛИСТИЧЕСКИМ ГАЛЬВАНОМЕТРОМ Часть I ОПРЕДЕЛЕНИЕ ЕМКОСТИ КОНДЕНСАТОРА БАЛЛИСТИЧЕСКИМ МЕТОДОМ ЦЕЛЬ РАБОТЫ: Приобрести практические навыки работы с баллистическим гальванометром. Овладеть методикой градуировки галь...