Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Комп’ютерні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Національний університет “Львівська політехніка”
Кафедра САП
Звіт
до лабораторної роботи № 7
ДЕРЕВА І ГРАФИ
В МОВІ ПРОГРАМУВАННЯ С
з курсу “Проблемно-орієнтоване програмування”
для студентів спеціальності "Комп’ютерні системи проектування"
Львів 2013
ТЕОРЕТИЧНІ ВІДОМОСТІ
Дерева. Основні поняття
Дерева являють собою найбільш важливі нелінійні структури, що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев, серед яких особливою "популярністю" користуються бінарні (двійкові) дерева. Вони застосовуються у різноманітних алгоритмах (програмах): наприклад, деякі компілятори з мов високого рівня використовують їх для аналізу й обчислення арифметичних виразів. Ще однією причиною популярності бінарних дерев є простота їхньої організації.
Дерево - це неорієнтований зв'язний граф без циклів. Визначимо формальне дерево як скінченну множину Т, яка складається з одного або більше вузлів, таких, що:
є один позначений вузол, який називається коренем даного дерева;
інші вузли (крім кореня) містяться в m >= 0 множинах Т1, Т2, ..., Тm, які попарно не перетинаються, і кожна з яких у свою чергу є деревом.
Дерева Т1, Т2, ..., Тm називаються піддеревами даного дерева.
Це визначення є рекурсивним, тобто воно визначає дерево в термінах самих же дерев. З нього слідує, що кожний вузол дерева є коренем деякого піддерева, що міститься в цьому дереві. Число таких піддерев у даному вузлі називають його ступенем. В бінарних деревах є також листя. Це вузли з нульовим степенем. Всі інші (некінцеві) вузли називають вузлами розгалуження.
Корінь - це такий вузол, з якого йдуть зв'язки до всіх інших элементів дерева. Дерева на папері зображують так: спочатку малюють корінь, потім від нього малюють зв’язки до вузлів-нащадків, від них зв'язки до їхніх нащадків і т. д. Ще однією характеристикою дерева є його висота. Це шлях максимальної довжини від листка до кореня.
Бінарні дерева
Двійковим або бінарним деревом називають неорієнтований граф наступного виду
Рівень 1 (корінь)
Рівень 2 (вузли)
Рівень 3 (вузли)
Рівень 4 (листя)
Рис. 1.
У бінарному дереві кожний вузол має тільки два піддерева. У кожного вузла є ліве й праве піддерево. Вузол і його піддерева називають взагалі по-різному, наприклад: батько, син і брат; або: батько з "лівим" і "правим" синами.
Більш формально бінарне дерево можна визначити як скінченну множину вузлів, яка або пуста, або складається з кореня з одним/двома бінарними деревами, що не перетинаються.
На мові С вузол бінарного дерева можна описати у вигляді наступної структури:
struct node
{ іnt key; // Ключ
... // Дані
struct node *left; // Посилання на ліве пiддерево/вузол
struct node *rіght; // Посилання на праве пiддерево/вузол
};
Для обходу дерева використовують ключі. Ключ - спеціальна змінна, яка полегшує доступ до вузлів дерева. Звичайно, це ціле число, що зберігається в кожному вузлі дерева і задовольняює деяким умовам. Наприклад, таким: нехай всі ключі в лівому піддереві поточного вузла менші ключа в ньому, а всі ключі в правому піддереві - більші або рівні поточному.
При роботі з бінарними деревами потрібно вміти додати, видалити, знайти в них вузол з необхідною інформацією, або створити довільне дерево.
Побудова зворотного польського запису
Однією з головних причин, що лежать в основі появи мов програмування високого рівня, є завдання, що вимагають великих обсягів обчислень. Тому до мов програмування ставляться вимоги максимального наближення форми запису обчислень до природної мови математики. У цьому зв'язку однією з перших областей системного програмування сформувалося дослідження способів трансляції виразів. Тут отримані численні результати, однак найбільше поширення одержав метод трансляції за допомогою зворотного польського запису, що запропонував польський математик Я. Лукашевич.
Нехай задано простий арифметичний вираз:
. (1)
Представимо цей вираз у вигляді дерева, у якому вузлам відповідають операції, а листю - операнди. Побудову почнемо з кореня, у якості якого вибирається операція, що виконується останньою. Лівій вітці відповідає лівий операнд операції, а правій вітці - правий. Дерево виразу (1) показане на Рис. 6.
Зробимо обхід дерева, під яким будемо розуміти формування рядка символів із символів вузлів і віток дерева. Обхід будемо робити від самої лівої вітки вправо й вузол переписувати у вихідний рядок тільки після розгляду всіх його віток. Результат обходу дерева має вигляд:
(2)
Характерні риси виразу (2) полягають у проходженні символів операцій за символами операндів і у відсутності дужок. Такий запис називається зворотним польським записом.
Зворотний польський запис володіє рядом позитивних властивостей, які перетворюють його в ідеальну проміжну мову при трансляції.
По-перше, обчислення виразу, записаного у зворотному польському записі, може проводитися шляхом однократного перегляду, що є досить зручним при генерації об'єктного коду програм.
Наприклад, обчислення виразу (2) може бути проведене в такий спосіб:
N
Аналізований рядок
Дія
1
AB+CD+* E-
rl=A+B
2
Rl CD+* E -
r2=C+D
3
r1 r2*E -
r1=r1 * r2
4
r1 E -
r1=r1 -E
5
r1
Тут r1, r2 – додаткові змінні.
Таблиця 1.
По-друге, одержання зворотного польського запсу з
Операція
Пріорітет
вихідного виразу може здійснюватися досить просто.
)
0
Для цього вводиться поняття стекового пріоритету
(
1
операцій (Табл. 1).
Проглядається вхідний рядок символів зліва направо,
+ -
2
операнди нерепиуються у вихідний рядок, а знаки
* /
3
операцій заносяться в стек на основі наступних міркувань:
а) якщо стек порожній, то операція з вхідного рядка записується в стек;
б) операція виштовхує зі стека всі операції з більшим або рівним пріоритетом у вихідний рядок;
в) якщо черговий символ з вхідного рядка є відкриваюча дужка, то вона проштовхується в стек;
г) закриваюча кругла дужка виштовхує всі операції зі стека до найближчої відкриваючої дужки, самі дужки у вихідний рядок не переписуються, а видаляються.
Процес одержання зворотного польського запису виразу (1) представлений у Табл. 2
Таблиця 2.
Символ, що переглядається
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Вхідний рядок
(
А
+
В
)
*
(
C
+
D
)
-
Е
Стан стека
(
(
+ (
+ (
*
(*
(*
+ (*
+ (*
*
-
-
Вихідний рядок
А
B
+
C
D
+
*
Е
-
2.3. Знаходження найкоротшого шляху на графі
Нехай нам дана частина карти дорожньої мережі, і потрібно знайти найкращий маршрут від початкової вершини до кінцевої. Його можуть визначати багато факторів, такі, як відстань у кілометрах, час проходження маршруту з урахуванням обмеження швидкості, число міст, які необхідно відвідати з метою доставки вантажів. Існує безліч інших задач, які можна звести до відшукання найкоротшого шляху на мережі. Наприклад, знайти найменшу кількість часу, необхідну для будівництва будинку, або обчислити мінімальну вартість модернізації устаткування для підвищення продуктивності на якому-небудь підприємстві. Також можна виділити кілька типів задач про найкоротший шлях:
1. між двома заданими вершинами в мережі;
2. між даною вершиною й всіма іншими вершинами мережі;
3. між кожною парою вершин у мережі;
4. між двома заданими вершинами для шляхів, що проходять через задану вершину;
5. перший, другий, третій і так далі найкоротші
шляхи в мережі.
Рис. 7.
Кожній дузі (х, у) вихідного графа G поставимо у відповідність число а(х, у) (Рис. 7). Якщо в графі G відсутня деяка дуга (х, у), покладемо а(х, у) рівним безмежності. Будемо називати число а(х, у) довжиною дуги (х, у), хоча а(х, у) може також інтерпретувати відповідні витрати й відповідний ваговий коефіцієнт. Визначимо довжину шляху як суму довжин окремих дуг, що становлять цей шлях. Для будь-яких двох вершин s і t графа G можуть існувати кілька шляхів, що з'єднують вершину s з вершиною t. Розглянемо алгоритм, що визначає шлях, що веде з вершини s у вершину t, і має мінімально можливу довжину. Цей шлях називається найкоротшим шляхом між вершинами s і t.
Алгоритм Дейкстри
Описаний далі алгоритм дозволяє знаходити в графі найкоротший шлях при додатних довжинах дуг і вважається одним з найбільш ефективних алгоритмів рішення задачі. Головна ідея полягає в послідовному визначенні найближчих до s вершин (тобто визначається 1- а найближча до s вершина, потім - 2- а, 3- я й так далі доти, поки наступна найближча вершина не виявиться вершиною t). Припустимо, що нам відомо m вершин, найближчих до вершини s (близькість будь-якої вершини х до вершини s визначається довжиною найкоротшого шляху, що веде з s у х). Нехай також відомі самі найкоротші шляхи, що з'єднують вершину s з виділеними m вершинами. Покажемо тепер, як може бути визначена (m+1)-a найближча до s вершина.
Зафарбуємо (виділимо) вершину s і m найближчих до неї вершин. Побудуємо для кожної незафарбованої вершини y шляхи, що безпосередньо з'єднують за допомогою дуг (х, у) кожну зафарбовану вершину х з у. Виберемо із цих шляхів найкоротший і будемо вважати його умовно найкоротшим шляхом з вершини s у вершину у. Та вершина, для якої умовно найкоротший шлях має найменшу довжину, і буде (m+1)-ою найближчою до s вершиною. Починаючи з m =0, описана процедура повинна повторюватися доти, поки не буде отриманий найкоротший шлях, що веде з вершини s до вершини t.
Тепер формально опишемо алгоритм Дейкстри:
Крок 1. Перед початком виконання алгоритму всі вершини й дуги не зафарбовані. Кожній вершині в ході виконання алгоритму приписується число d(х), рівне довжині найкоротшого шляху з s в х, що включає тільки зафарбовані вершини. Покладемо d(s) = 0 і d(x) рівним безмежності для всіх х, відмінних від s. Зафарбуємо вершину s і покладемо y=s (y - остання з зафарбованих вершин).
Крок 2. Для кожної незафарбованої вершини х у такий спосіб перерахуємо величину d(x):
d(x) = mm{d(x), d(y) + a(x, y)}. (3)
Якщо d(x) дорівнює безмежності, для всіх незафарбованих вершин х, закінчити процедуру алгоритму: у вхідному графі відсутні шляхи з вершини s у незабарвлені вершини. У протилежному випадку зафарбувати ту з вершин х, для якої величина d(x) є найменшою. Крім того, зафарбувати дугу, що веде в обрану на даному кроці вершину х (для цієї дуги досягався мінімум відповідно до виразу (3)). Покладаємо y= х.
Крок 3. Якщо y = t, закінчити процедуру: найкоротший шлях з вершини s у вершину t знайдений (це єдиний шлях з s в t, складений із зафарбованих дуг). У протилежному випадку перейти до кроку 2.
Відзначимо, що кожний раз, коли зафарбовуюється деяка вершина (не рахуючи вершини s), зафарбовується й деяка дуга, що заходить у дану вершину. Таким чином, на будь-якому етапі алгоритму в кожну вершину заходить не більш ніж одна зафарбована дуга. Крім того, зафарбовані дуги не можуть утворювати у вихідному графі цикл, тому що в алгоритмі не може зафарбовуватися дуга, кінцеві вершини якої вже зафарбовані. Отже, зафарбовані дуги утворять у вхідному графі орієнтоване дерево з коренем у вершині s. Це дерево називається орієнтованим деревом найкоротших шляхів.
Єдиний шлях від вершини s до будь-якої вершини х, що належить дереву найкоротших шляхів, є найкоротшим шляхом між зазначеними вершинами. Якщо найкоротшому шляху з вершини s у вершину х в дереві найкоротших шляхів належить вершина y, то частина цього шляху, укладена між х i y, є найкоротшим шляхом між цими вершинами. Дійсно, якби між х i y існував більш короткий шлях, тo згаданий вище шлях між вершинами s і х не міг би бути найкоротшим.
Алгоритм Дейкстри можна розглядати як процедуру нарощування орієнтованого дерева з коренем у вершині s. Коли у цій процедурі нарощування досягається вершина t, процедура може бути зупинена.
Для визначення найкоротших шляхів з вершини s в усі вершини вхідного графа процедуру нарощування дерева варто продовжувати доти, поки всі вершини графа не будуть включені в орієнтоване дерево найкоротших шляхів. При цьому для вхідного графа було б отримане покриваюче орієнтоване дерево (за умови, що в цьому графі міститься хоча б одне таке дерево). Отже, для одержання дерева найкоротших шляхів від вершини s до всіх інших вершин, третій крок алгоритму повинен бути скоректований у такий спосіб: якщо всі вершини виявляються зафарбованими, закінчити процедуру (для будь-якої вершини х є єдиний шлях з s в х, що складається з зафарбованих дуг, і цей шлях є найкоротшим шляхом між відповідними вершинами); у протилежному випадку перейти до кроку 2.
Алгоритм Форда
Початкове припущення в алгоритмі Дейкстри складалося в невід’ємності дуг вхідного графа. Якби деякі з довжин дуг були від’ємними, то алгоритм Дейкстри міг би невірно вказати найкоротший шлях. Для приклада розглянемо граф на рис. 8.
1-а і 2-а вершини є початковою й кінцевою вершинами графа відповідно. Довжини переходу між вершинами зазначені на рисунку. У цьому графі найкоротшим шляхом, що з'єднує вершини 1 і 2, є шлях 1 -> 3 -> 4 -> 6 -> 5 -> 2, довжина цього шляху дорівнює 2 + 1 + 4 – 5 - 2 = 0. Алгоритм Дейкстри помилково вкаже шлях 1-> 3 -> 4 -> 2, довжина якого дорівнює 5.
Рис. 8.
Алгоритм Дейкстри може бути узагальнений на випадок, коли деякі з дуг мають від’ємні довжини. Ідея відповідного узагальнення належить Фордові. Необхідна модифікація алгоритму Дейкстри полягає в наступному:
на кроці 2 алгоритму перерахунок величин d(x) за допомогою співвідношення (3) відбувається для всіх вершин, а не тільки для незафарбованих. Отже, числа d(x) можуть зменшуватися як для зафарбованих, так і для незафарбованих вершин;
якщо для деякої зафарбованої вершини х відбувається зменшення величини d(x), то із цієї вершини і ідентичній їй зафарбованій дузі фарбування знімається;
процедура алгоритму закінчується тільки тоді, коли всі вершини зафарбовані і коли після виконання кроку 2 жодне із чисел d(x) не змінюється.
ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ(1 варіант)
1. Використовуючи рекурсивну функцію, скласти програму додавання нового елемента до дерева.
КОД ПРОГРАМИ
#include <stdio.h>
#include <conio.h>
struct TTree {
int k;
TTree *left;
TTree *right;
TTree() { left = right = NULL; }
} *Tree = NULL;
void AddElem(TTree *tree, int k)
{
if (!tree) {
Tree = new TTree();
Tree->k = k;
} else if (k > tree->k)
if (tree->left) AddElem(tree->left,k);
else {
tree->left = new TTree();
tree->left->k = k;
}
else if (k < tree->k)
if (tree->right) AddElem(tree->right,k);
else {
tree->right = new TTree();
tree->right->k = k;
}
else return;
}
void FreeTree(TTree *tree)
{
if (!tree) return;
FreeTree(tree->left);
FreeTree(tree->right);
delete tree;
}
void PrintTree(TTree *tree, int n = 0)
{
for (int i = 0; i < n; i++)
printf("\t");
if (tree) printf("%d\n",tree->k);
else { printf("NULL\n"); return; }
PrintTree(tree->left,n+1);
PrintTree(tree->right,n+1);
}
int main(){
printf("Input number of elements\n");
int n,elem;
if (!scanf("%d",&n)) scanf("%*s");
printf("Input %d elements\n",n);
for (int i = 0; i < n; i++) {
if (!scanf("%d",&elem)) scanf("%*s");
else AddElem(Tree,elem);
}
printf("Tree:\n");
PrintTree(Tree);
FreeTree(Tree);
getch();
return 0;
}
РЕЗУЛЬТАТ ВИКОНАННЯ
ВИСНОВОК
На даній лабораторній роботі я навчився працювати з бінарними деревами.
29.09.2014 20:09-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора