Система моделювання методів обходу бінарних дерев

 

Анотація


Даний дипломний проект призначений створенню системи моделювання методів обходу бінарних дерев.

У даному проекті було розглянуто питання обґрунтування необхідності створення програмного продукту, зроблений пошук аналогів створюваної системи. Обрано засоби реалізації для проектування програмного засобу, в результаті був створений та протестований готовий програмний продукт.

Створена програма дозволяє будувати повні бінарні дерева вказаної кількості рівнів та виконувати обхід дерев за одним із трьох методів. Система буде корисна викладачу предмету «Алгоритми та структури даних» та студентам під час вивчення теми «бінарні дерева та методи їх обходу», для кращого розуміння матеріалу лекції.

Обсяг пояснювальної записки: 25 листів, кількість додатків: 3, загальна кількість листів 48.

При написанні дипломного проекту була використана спеціалізована література по створенню алгоритмічних моделей системи та програмуванню на Borland Delphi 7.0.


ЗМІСТ


СПИСОК СКОРОЧЕНЬ ТА УМОВНИХ ПОЗНАЧЕНЬ

ВСТУП

. ПОСТАНОВКА ЗАДАЧІ

. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ

. ОПИС АЛГОРИТМУ

. ВИБІР ЗАСОБІВ РЕАЛІЗАЦІЇ

.1 МОВА ПРОГРАМУВАННЯ І СЕРЕДОВИЩЕ РОЗРОБКИ

.2 ВИБІР ТЕХНІЧНИХ ЗАСОБІВ

.3 ВИСНОВКИ

. ОПИС СПРОЕКТОВАНОЇ СИСТЕМИ

.1 СТРУКТУРА ДАНИХ

.2 СТРУКТУРА МОДУЛІВ СИСТЕМИ

.3 РОБОТА СИСТЕМИ

.4 ВИСНОВКИ

ВИСНОВОК

СПИСОК ЛІТЕРАТУРИ

ДОДАТКИ


СПИСОК СКОРОЧЕНЬ ТА УМОВНИХ ПОЗНАЧЕНЬ


ПКПерсональний компютерRADШвидка розробка застосунківIDEІнтегроване середовище розробкиОСОпераційна системаПЗПрограмне забезпеченняHTMLМова розмітки гіпертекстуCSSКаскадна таблиця стилів

ВСТУП


З розвитком інформаційних технологій (ІТ), стає все більший попит на ринку праці на професію програміст. На цю спеціальність навчають як в коледжах, так і у вищих навчальних закладах. Ця спеціальність повязана з автоматизацію різних галузей за допомогою програмного забезпечення(ПЗ). А в основі будь якого ПЗ, стоїть алгоритм, послідовність дій яка приводить до певного результату.

Предмет «Алгоритми і структури даних» розпочинають вивчати на перших курсах у коледжі та в університеті, і саме цей предмет відіграє важливу роль в подальшому розвитку студента в цій галузі. Але цей предмет для більшості є в значній мірі незрозумілим по різним причинам, однією з таких причин є відсутність візуального прикладу який би моделював той матеріал лекції, і ті приклади що були наведені на дошці.

В основному саме для полегшення сприйняття однієї із теми предмету «Бінарні дерева та методи їх підходу» призначений програмний продукт розроблений у даній дипломній роботі.

За допомогою нього на мою думку студенти зможуть краще сприймати матеріал лекції, переглянувши візуальний приклад який моделює матеріал із лекції про побудову і методи обходу бінарних дерев.


1. ПОСТАНОВКА ЗАДАЧІ


Потрібно створити програмний додаток за допомогою якого можна створювати бінарне дерево та виконувати обхід по дереві за вибраним методом.

Програмний додаток повинен відповідати вказаним критеріям:

створювати повне бінарне дерево вказаної кількості рівнів;

візуально відображати метод обходу бінарного дерева;

надавати довідку користувачеві про створення та методи обходу дерева;

мати зручний, графічний інтерфейс;

працювати під управлінням ОС Windows XP/7.

Проаналізувавши ринок програмного забезпечення, ми не знайшли програми яка б відповідала поставленим критеріям. Так як більшість програм мають командний інтерфейс і не володіють хорошою візуальністю при створенні бінарного дерева, та моделюванні методу його обходу.

Тому виникла потреба у розроблені такого програмного додатку який буде відповідати вказаним критеріям.


2. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ


Після отримання критерій щодо створюваного програмного продукту приступили до аналізу предметної області.

Дерева

У повсякденному житті ми дуже часто зустрічаємо приклади дерев, і вже напевно знайомі з цією концепцією.

Наприклад, люди часто використовують генеалогічне дерево для зображення структури свого роду, як ми побачимо, багато термінів, пов'язаних з деревами, взято саме звідси наприклад.

Другий приклад - це структура великої організації; використання деревоподібної структури для представлення її «ієрархічної структури» нині широко використовується в багатьох комп'ютерних завданнях.

Третій приклад - це граматичне дерево; спочатку воно служило для граматичного аналізу комп'ютерних програм, а нині широко використовується і для граматичного аналізу літературної мови.

Бінарні дерева

Найпростіші з дерев вважаються бінарні дерева.

Бінарне дерево - це кінцева множина елементів, яка або порожня, або містить один елемент, званий коренем дерева, а інші елементи множини діляться на дві непересічні підмножини, кожна з яких сама є бінарним деревом. Ці підмножини називаються лівим і правим піддеревом вихідного дерева.

Кожен елемент бінарного дерева називається вузлом дерева.

На рис. 2.1 зображений загальноприйнятий спосіб зображення бінарного дерева.


Рисунок 2.1 - Бінарне дерево


Це дерево складається з семи вузлів, А-корінь дерева. Його ліве піддерево має корінь В, а праве - корінь С. Це зображується двома гілками, що виходять із А: лівим - до В і правим - до С. Відсутність гілки позначає пусте піддерево - такий вузол називають листом.

Бінарні дерева з корінням D, E, F і G мають порожні ліві і праві піддерева і являються листами дерева.

Властивість 1. Строго бінарне дерево з n листами завжди містить 2n-1 вузлів.

Рівень вузла в бінарному дереві може бути визначений таким чином. Корінь дерева має рівень 0, і рівень будь-якого іншого вузла дерева має рівень на 1 більше рівня свого батька.

Наприклад, в бінарному дереві на рис. 1 вузол B - вузол рівня 1, а вузол D - рівня 2.

Глибина бінарного дерева - це максимальний рівень листа дерева, що дорівнює довжині найдовшого шляху від кореня до листа дерева.

Стало бути, глибина дерева на рис. 2.2 дорівнює 3.

Повне бінарне дерево рівня N - це дерево, в якому кожен вузол рівня N є листом і кожен вузол рівня менше N-1 має непусті ліве і праве піддерево (рис. 2.2).


Рисунок 2.2 - Повне бінарне дерево

Структура бінарного дерева при реалізації

Структура бінарного дерева побудована з вузлів.

Вузол дерева містить поле даних і два поля з покажчиками.

Поля покажчиків називаються лівим покажчиком і правим покажчиком, оскільки вони вказують на ліве і праве піддерево, відповідно. Значення nil є ознакою порожнього дерева.

Тоді бінарне дерево можна буде представити в наступному вигляді рис 2.3.


Рисунок 2.3 - Структура бінарного дерева


Тоді дерево що зображено на рис 2.1. Можна зобразити в наступному вигляді рис. 2.4.


Рисунок 2.4 - Структура бінарного дерева у вигляді реалізації


Методи обходу бінарних дерев

Над бінарним деревом є операція - його проходження, тобто потрібно обійти все дерево, зазначивши кожен вузол один раз.

Існує 3 основних методи обходу бінарного дерева:

.в прямому порядку;

.в симетричному порядку;

.у зворотному порядку.

Методи обходу дерева детально описані в розділі Опис алгоритму.


3. ОПИС АЛГОРИТМУ


Як було сказано вище, існує 3 основні методи обходу бінарного дерева:

в прямому порядку;

в симетричному порядку;

у зворотному порядку.

Прямий метод

Алгоритм обходу бінарного дерева у прямому порядку має наступний вигляд:

1.Потрапити в корінь;

2.Пройти в прямому порядку ліве піддерево;

.Пройти в прямому порядку праве піддерево.

На рис. 3.1 змодельований прямий метод обходу дерева.


Результат обходу: 1-2-4-5-3-6-7

Рисунок 3.1 - Прямий метод обходу


Зворотній метод

Алгоритм обходу бінарного дерева у зворотному порядку наступний:

.Пройти в зворотному порядку ліве піддерево;

.Пройти в зворотному порядку праве піддерево;

.Потрапити в корінь.

На рис. 3.2 змодельований зворотній метод обходу дерева.

Результат обходу: 4-5-2-6-7-3-1

Рисунок 3.2 - Зворотній метод обходу


Симетричний метод

Алгоритм обходу бінарного дерева у симетричному порядку наступний:

.Пройти в симетричному порядку ліве піддерево;

.Потрапити в корінь;

.Пройти в симетричному порядку праве піддерево.

На рис. 3.3 змодельований симетричний метод обходу дерева.


Результат обходу: 4-2-5-1-6-3-7

Рисунок 3.3 - Симетричний метод обходу


Кожен з вище описаних методів виконується з використанням рекурсії.

Рекурсією називається ситуація, коли підпрограма викликає сама себе. Саме три кроки що описані в кожному методі, використовують рекурсію для виконання обходу всього дерева. Без використання рекурсії за допомогою вищеописаних алгоритмів можна було б пройти лише бінарне дерево що складається з трьох вузлів, а така задача виконується дуже рідко. Тому рекурсія допомагає нам обійти всі вузли дерева за вказаними правилами.


4. ВИБІР ЗАСОБІВ РЕАЛІЗАЦІЇ


.1 МОВА ПРОГРАМУВАННЯ І СЕРЕДОВИЩЕ РОЗРОБКИ


Для розробки нашого дипломного проекту на тему «Система моделювання методів обходу бінарних дерев» ми скористаємось середовищем швидкої розробки (RAD) Delphi 7 фірми Borland.

В Delphi 7, нам найбільш подобається швидкість та простота розробки додатку, без затрати часу на підготовчі дії такі як ініціалізацію(реєстрацію класу вікна, організацію обробки повідомлень і т.д.). При створенні проекту на Delphi ми більшу увагу приділяємо алгоритмам. Ми обрали Delphi за його набір компонентів для роботи з малюванням, ці компоненти знадобляться для створення та відображені бінарного дерева, та моделюванні методів його обходу. А також за можливість встановлення нових компонентів для покращення інтерфейсу користувача.

Основною перевагою при виборі для нас стало:

швидкість розробки програми (RAD);

висока продуктивність розробленого додатка;

низькі вимоги розробленого додатка до ресурсів комп'ютера.

Для створення красивого дизайну Delphi - програми призначений AlphaControls - це набір стандартних і деяких унікальних компонентів, підтримуючих скіни AlphaSkins, чим забезпечують красивий інтерфейс додатка. Перевагою є те, що для жителів країн СНД всі компоненти є безкоштовними незалежно від того - комерційний проект чи ні.

Delphi - це інтегроване середовище швидкої розробки 32-х бітного програмного забезпечення для роботи під управлінням ОС Microsoft Windows. Середовище підтримує розробку Windows - застосунків на мові програмування Delphi, яка є наступницею мови Object Pascal.

В склад Delphi входять засоби, необхідні для розробки, тестування та встановлення програм, включаючи велику за обсягом бібліотеку компонентів (VCL - Visual Components Library), засоби візуального проектування, шаблони програм і форм. Середовище проектування Delphi є відкритою системою і дозволяє використовувати як компоненти VCL, так і компоненти від сторонніх розробників, саме завдяки цієї можливості ми використали набір допоміжних компонентів AlphaControls.в основному використовується для розробки настільних додатків <#"justify">.2 ВИБІР ТЕХНІЧНИХ ЗАСОБІВ


Для повноцінної роботи системи моделювання методів обходу бінарних дерев потрібно, щоб компютер відповідав наступним характеристикам (табл. 4.1):


Таблиця 4.1 - Мінімальні вимоги до апаратного забезпечення

№п/пНазваЗначення1.Процесор із тактовою частотою700МГц2.Оперативна пам'ять128 Мб.3.Вільного місця на жорсткому диску50 Мб.4.Встановлена Операційна Система(ОС)Windows XP/7

.3 ВИСНОВКИ


Після отримання критерій по розробці програмного продукту та аналізу предметної області, перейшли до вибору засобів реалізації, для створення програмного продукту.

Проаналізувавши всі доступні та вивчені нами IDE, ми обрали Delphi 7 за його набір компонентів для роботи з малюванням, а також можливість встановлення нових компонентів для покращення інтерфейсу користувача.

Основною перевагою для нас стало:

швидкість розробки програми (RAD);

висока продуктивність розробленого додатка;

низькі вимоги розробленого додатка до ресурсів комп'ютера.

В результаті вибраних засобів реалізації сформовано таблицю мінімальних характеристик для повноцінної роботи системи моделювання методів обходу бінарних дерев.


5. ОПИС СПРОЕКТОВАНОЇ СИСТЕМИ


.1 СТРУКТУРА ДАНИХ


У системі бінарне дерево зберігається у вигляді динамічного масиву елементи якого (вузли) є змінними типу TNode(рис. 5.1).


Рисунок 5.1 - діаграма класу


На рис. 5.1 зображено діаграму класу, на якій видно що клас TNode спадкується від класу TImage(картинки) та має додатково 4 поля, та метод конструктора.

Поле value призначене для збереження значення що містить вузол, при обході у шлях обходу записується саме це значення.

Поле r, l вказівники на правого і лівого нащадка в дереві, містять значення індексу під яким нащадок зберігається у масиві.

Поле prt вказівник на предка (індекс у динамічному масиві).


.2 СТРУКТУРА МОДУЛІВ СИСТЕМИ


Спроектована система має один модуль.

Головний модуль.

Виконує побудову та обхід дерева за вказаним методом обходу.

На рис 5.2 зображено головний модуль на етапі розробки. Для створення інтерфейсу модуля були використанні наступні компоненти:

Image - який в нашому додатку грає роль полотна на якому відбувається будування дерева і модулювання методів обходу. Також вузли дерева спадкуються від класу TImage.

GroupBox - призначена для групування елементів керування які призначенні для виконання однієї задачі.

SpinEdit - лічильник, призначений для вказання висоти бінарного дерева, що створюється.

RadioButton - залежний перемикач призначений для вибору методу обходу бінарного дерева(в один момент дерево можна обійти лише одним методом)

BitBtn - командна кнопка, всього використовується дві, перша призначена для створення дерева з вказаними параметрами, друга для запуску вибраного методу обходу.


Рисунок 5.2 - Головний модуль на етапі розробки


Memo - текстова область призначення для відображення результуючої інформації про дерево, вибраний метод обходу та пройдений шлях.

WebLabel - посилання, в нашому додатку на html-сторінку допомоги.

StatusBar - стрічка стану відображає стан додатку при використанні системи.

Веб-сторінка інструкція користувача

Надає інформацію про користування системою.

Для створення структури документа були використанні такі теги:

div - є блоковим елементом і призначений для виділення фрагмента документа з метою зміни виду вмісту. Як правило, вигляд блоку управляється за допомогою стилів. Щоб не описувати кожен раз стиль всередині тегу, можна виділити стиль в зовнішню таблицю стилів, а для тегу додати атрибут class або id з ім'ям селектора.

h1,...,h6 - тег <h1> являє собою найбільш важливий заголовок першого рівня, а тег <h6> служить для позначення заголовка шостого рівня і є найменш значним. Типово, заголовок першого рівня відображається найбільшим шрифтом жирного накреслення, заголовки подальшого рівня за розміром менше. Теги <h1>,..., <h6> відносяться до блокових елементів, вони завжди починаються з нового рядка, а після них інші елементи відображаються на наступному рядку. Крім того, перед заголовком і після нього додається порожній простір.

p - Визначає текстовий абзац. Тег <p> є блоковим елементом, завжди починається з нового рядка, абзаци тексту йдуть один за одним розділяються між собою відбиванням. Величиною відбиття можна керувати за допомогою стилів. Якщо закриває тегу немає, вважається, що кінець абзацу збігається з початком наступного блокового елемента.

ol - тег <ol> встановлює нумерований список. Кожен елемент списку повинен починатися з тегу <li>. Якщо до тегу <ol> застосовується таблиця стилів, то елементи <li> успадковують ці властивості.

img - тег <img> призначений для відображення на веб-сторінці зображень в графічному форматі GIF, JPEG або PNG. Цей тег має єдиний обов'язковий атрибут src, який визначає адресу файлу з картинкою. Якщо необхідно, то малюнок можна зробити посиланням на інший файл, помістивши тег <img> в контейнер <a>.

a - Тег <a> є одним з важливих елементів HTML і призначений для створення посилань. Залежно від присутності атрибутів name або href тег <a> встановлює посилання або якір. Якорем називається закладка всередині сторінки, яку можна вказати в якості мети посилання. При використанні посилання, яка вказує на якір, відбувається перехід до закладки всередині веб-сторінки. Для створення посилання необхідно повідомити браузеру, що є посиланням, а також вказати адресу документа, на який слід зробити посилання. Як значення атрибута href використовується адреса документа (URL, Universal Resource Locator, універсальний покажчик ресурсів), на який відбувається перехід. Адреса посилання може бути абсолютним і відносним. Абсолютні адреси працюють скрізь і всюди незалежно від імені сайту або веб-сторінки, де прописана посилання. Відносні посилання, як випливає з їх назви, побудовані щодо поточного документа або кореня сайту.

Для стильового оформлення використовувалися наступні властивості css.

margin - встановлює величину відступу від кожного краю елемента. Відступом є простір від кордону поточного елемента до внутрішньої межі його батьківського елементу.

padding - Встановлює значення полів навколо вмісту елемента. Полем називається відстань від внутрішнього краю рамки елемента до уявного прямокутника, що обмежує його вміст

background-color - визначає колір фону елемента. Хоча ця властивість не успадковує властивості свого батька, через те, що початкове значення встановлюється прозорим, колір фону дочірніх елементів збігається з кольором фону батьківського елементу.

position - встановлює спосіб позиціонування елемента щодо вікна браузера або інших об'єктів на веб-сторінці.align - Визначає горизонтальне вирівнювання тексту в межах елемента.

font-family - Встановлює сімейство шрифту, яке буде використовуватися для оформлення тексту вмісту. Список шрифтів може включати одне або кілька назв, розділених комою. Якщо в імені шрифту містяться прогалини, наприклад, Trebuchet MS, воно повинно полягати в одинарні або подвійні лапки. Коли браузер зустрічає перший шрифт у списку, він перевіряє його наявність на комп'ютері користувача. Якщо такого шрифту немає, береться наступне ім'я зі списку і також аналізується на присутність. Тому кілька шрифтів збільшує ймовірність, що хоча б один з них буде виявлений на клієнтському комп'ютері. Закінчують список зазвичай ключовим словом, яке описує тип шрифту - serif, sans-serif, cursive, fantasy або monospace.

font-size - Визначає розмір шрифту елемента. Розмір може бути встановлений кількома способами. Набір констант (xx-small, x-small, small, medium, large, x-large, xx-large) задає розмір, який називається абсолютним. По правді кажучи, вони не зовсім абсолютні, оскільки залежать від налаштувань браузера та операційної системи. Зрештою, розмір шрифту сильно залежить від значення властивості font-size у батька елемента. Сам розмір шрифту визначається як висота від базової лінії до верхньої межі кегельного майданчика.


.3 РОБОТА СИСТЕМИ


При запуску програми користувачу відображається форма програми (рис. 5.3)


Рисунок 5.3 - форма при запуску програми


Інтерфейс програми можна умовно поділити на три області, які на рис. 5.3 виділені прямокутними областями різного кольору.

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

По середині знаходиться робоча область в якій відображається створене дерево, та моделюється один із методів обходу.

Знизу розташована текстова область, в якій розміщені результати створення дерева, вибраний метод і шлях обходу.

Перед створенням дерева, панель «методи обходу бінарного дерева» є недоступною, що є логічним, якщо немає створеного дерева немає, що обходити. Для створення дерева потрібно вказати його висоту, та натиснути кнопку створити (рис. 5.4).


Рисунок 5.4 - Створення бінарного дерева


В робочій області відображається створене дерево по вказаних параметрах(рис. 5.5).


Рисунок 5.5 - відображення бінарного методу


Після створення дерева панель «Методи обходу бінарного дерева» стає активною, і уже можна вибрати метод і виконати за ним обхід (рис. 5.6).

Рисунок 5.6 - Вибір методу обходу


При натисненні кнопки «обхід дерева» у робочій області відбуватиметься моделювання обходу бінарного дерева за вказаним методом (рис. 5.7).


Рисунок 5.7 - Моделювання обходу дерева вибраним методом


Після обходу бінарного дерева у текстову область записується результати обходу (рис. 5.8).


Рисунок 5.8 - результати виконання обходу дерева

бінарний дерево програмування модуль

Для недосвідчених користувачів є можливість скористатися довідкою системи яка розроблена у вигляді веб-сторінки. Для того щоб викликати допомогу наприклад по створенні бінарного дерева, потрібно натиснути на посилання «допомога» яка містить адресу на файл index.html що знаходиться за шляхом: binary tree method\help\index.html. В результаті запуститься веб-браузер для перегляду сторінки допомоги (рис 5.9).

Для зручності у верху сторінки розміщенні посилання (якоря) на інформацію про роботу системи яка описана нижче. Для того щоб наприклад переглянути методи обходу бінарного дерева які моделює система потрібно натиснути на пункт «Методи обходу». Після того як ми ознайомилися з можливостями системи, та інструкціями по її використанню, можна закрити браузер і застосувати отримані теоретичні знання на практиці.


Рисунок 5.9 - веб-сторінка інструкція користувача, п. створення дерева


.4 ВИСНОВКИ


При отриманні необхідної інформації про предметну область бінарні дерева, приступив до реалізації структури бінарного дерева на мові програмування object pascal. В результаті реалізовано збереження структури даних бінарного дерева у вигляді динамічного масиву який зберігає вузли дерева які є екземплярами спроектованого класу. Розроблений інтерфейс програми засобами IDE Delphi 7.

Описано структуру модулів та виконаний аналіз роботи розробленого додатку.


ВИСНОВОК


Після отримання критерій по розробці програмного продукту приступив до аналізу предметної області. Проаналізувавши предметну область «бінарні дерева» перейшов до вибору засобів реалізації, для створення програмного продукту, в результаті обрано IDE Delphi 7.

При отриманні необхідної інформації про предметну область бінарні дерева, спроектовано структуру бінарного дерева на мові програмування object pascal. Реалізовано три основних алгоритми обходу дерева, у прямому, зворотному та симетричному порядку.

Розроблено та описано структуру модуля, виконаний аналіз роботи розробленого додатку.

В результаті розроблено систему моделювання методів обходу бінарних дерев, яка відповідає поставленим до ПЗ критеріям. Володіє зазначеним в критеріях функціональністю, має зручний та зрозумілий інтерфейс, при роботі потребує невелику кількість ресурсів. За допомогою цієї системи можна будувати бінарні дерева, різної кількості рівнів та виконувати по них обхід одним із трьох основних методів.

Даний програмний продукт може бути використаний при роботі викладачем предмету «Алгоритми і структури даних» для візуалізації матеріалу лекції про бінарні дерева та методи їх обходу.


СПИСОК ЛІТЕРАТУРИ


1.Брауде Е. Технология разработки программного обеспечения / Е. Брауде - СПб Питер, 2004 - 655 с.: ил.

2.Хоменко А.Д. Delphi 7/ Под общ. ред. А.Д. Хоменко. - СПб.: БХВ-Петербург, 2008. - 1216 с.: ил.

.Макгрегор Д. Тестирование объектного ориентированного программного обеспечения. Практическое пособие: Пер. с англ. / Д. Макгрегор, Д.Сайкс, - К.: ООО ТИД «ДС», 2002. - 432 с.

4.Електронний ресурс. Структури даних. Бінарні дерева. - режим доступу до статті. : #"justify">ДОДАТОК А


Система моделювання методів обходу бінарних дерев

Специфікація

.ТБЕК.3 234.006-01

Листів 2

Розробник: Савченко О.О.

Керівник: Бойко С.В.

Тальне 2013


ПозначенняНайменуванняПримітка482.ТБЕК.3 234-01 12 01Текст програми482.ТБЕК.3 234-01 34 01Інструкція користувачеві

ДОДАТОК Б


СИстема моделювання методів обходу бінарних дерев

Текст програми

482.ТБЕК.3 234-01 12 01

Листів 14

Розробник Савченко О.О.

Тальне 2013

АНОТАЦІЯ

В даному документі представлена частина тексту програми, за допомогою якої створюється бінарне дерево, та моделюється три методи обходу дерева.

Документ складається із 14 сторінок.

Main; {Головний модуль}, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, sSkinManager, StdCtrls, sRadioButton, sLabel, sEdit, sSpinEdit,, sBitBtn, sGroupBox, ExtCtrls, sPanel, sSpeedButton, ComCtrls,, Math, sMemo;= class(TImage) //Клас вузла що спадкується від класу TImagevalue: integer; //значення вузлаl:integer; //вказівник на лівого нащадкаr:integer; //вказівник на правого нащадкаPrt: integer; //вказівник на предкаCreate(i: Integer);;= class(TForm): TsStatusBar;: TsPanel;: TsGroupBox;: TsLabel;: TsSkinManager;: TsGroupBox;: TsRadioButton;: TsRadioButton;: TsSpinEdit;: TsRadioButton;: TsBitBtn;: TsBitBtn;: TImage;: TsLabel;: TsPanel;: TsLabel;: TsMemo;: TsWebLabel;: TsWebLabel;DrawTree(T : array of TNode); //процедура малювання дереваpObhod(i : integer); //прямий метод обходуsObhod(i : integer); //симетричний методzObhod(i : integer); //зворотній методDelay(Value: Cardinal); //процедура затримкиbtnCreateTreeClick(Sender: TObject); //процедура створення дереваseHeightTreeChange(Sender: TObject); //обрахунок кількості вузлівbtnBypassTreeClick(Sender: TObject); //виконання обходу дерева

{ Private declarations }

{ Public declarations };: TForm1;: array of TNode; //дерево, i:integer;: String; //шлях обходу одного із методів

{$R *.dfm}

//Реалізація процедури прямий метод обходуTForm1.pObhod(i:integer);resultLine:String;i<>-1 then //якщо вузол не лист (-1)strPath='' then strPath:=IntToStr(Tree[i].value) //записуємо значення першого вузлаstrPath:=strPath+' - '+IntToStr(Tree[i].value); //будуємо шлях обходу(4000); //затримка[i].Picture.LoadFromFile('img\p'+IntToStr(i+1)+'.png'); //змінюємо вигляд пройденого вузла(Tree[i].l); //резурсивно обходимо в прямому порядку ліве піддерево(Tree[i].r); //резурсивно обходимо в прямому порядку праве піддерево;;

//Реалізація процедури симетричний метод обходуTForm1.sObhod(i:integer);i<>-1 then //якщо вузол не лист (-1)(Tree[i].l); //проходимо в симетричному порядку ліве піддерево(4000); //затримкаstrPath='' then strPath:=IntToStr(Tree[i].value)strPath:=strPath+' - '+IntToStr(Tree[i].value); //записуємо шлях обходу[i].Picture.LoadFromFile('img\s'+IntToStr(i+1)+'.png'); //змінюємо вигляд вузла який відвідали(Tree[i].r); //проходимо в симетричному порядку праве піддерево;;

//Реалізація процедури зворотній метод обходуTForm1.zObhod(i:integer);i<>-1 then(Tree[i].l); //обхід в зворотному порядку ліве піддерево(Tree[i].r); //обхід в зворотному порядку ліве піддерево[i].Picture.LoadFromFile('img\z'+IntToStr(i+1)+'.png'); //змінюємо вигляд вузла який відвідали(4000);strPath='' then strPath:=IntToStr(Tree[i].value) //записуємо шлях обходуstrPath:=strPath+' - '+IntToStr(Tree[i].value);;;

//Реалізація процедури затримки (застосовується під час проходу по дереву для того щоб користувач міг переглянути як саме виконується обхід)TForm1.Delay(Value: Cardinal);, N: Cardinal;:= 0;N <= (Value div 10) do(1, True);.ProcessMessages;(N);;:= GetTickCount;.ProcessMessages;:= GetTickCount;(N - F >= (Value mod 10)) or (N < F);;

//Реалізація конструктора нашого класу TNodode(вузла)TNode.Create(i: integer); //конструктор вузлаCreate(nil);.Picture.LoadFromFile('img\'+IntToStr(i+1)+'.png'); //завантажуємо зображення.Width:=30; //ширина вузла.Height:=30; //висота вузла;

//Реалізація процедури малювання дереваTForm1.DrawTree(T:array of TNode); //малюємо деревоi,n,x,h,mid,ShiftH,StepH,W:integer;(Image1.Canvas.Handle, 0, 0, Image1.ClientWidth, Image1. Client Height, WHITENESS);:=high(T);:=Image1.Width;:=W div 2;i:=0 to h doi>0 then n:=trunc(ln(i+1)/ln(2))n:=0;:=i-round(power(2,n))+1;:=(W div (round(power(2,n))+1));n=0 then ShiftH:=0ShiftH:=(StepH div 2)+StepH*(x-round(power(2,n)/2));[i].Left:= (W div 2) + ShiftH+Image1.Left-10; //розміщення вузлів по осі x[i].Top:=n*50+10+Image1.Top+10; //розміщення вузлів по осі y;.Canvas.Pen.Color:=clGray;i:=1 to h do //малювання гілок дерева.Canvas.MoveTo(T[i].Left+14,T[i].Top+15);.Canvas.LineTo(T[T[i].Prt].Left+14,T[T[i].Prt].Top+15);;;;

//Реалізація процедури створення дереваTForm1.btnCreateTreeClick(Sender: TObject);i,n,x,p:integer;seHeightTree.Value>5 then seHeightTree.Value:=5;seHeightTree.Text='' then seHeightTree.Value:=2;not(sGroupBox2.Enabled) then sGroupBox2.Enabled:=true;Length(Tree)>0 then //якщо дерево вже створенеi:=0 to Length(Tree)-1 do //проходження по всьому дереву[i].Free; //видалити вузли:=round(power(2,seHeightTree.Value))-1; //кількість вузлів(Tree,NodesCount); //створення дерева що містить NodesCount вузлівi:=0 to NodesCount-1 do[i]:=TNode.Create(i); //створення вузла і завантаження його зображення[i].Parent:=Image1.Parent;;[0].value:=1;[0].l:=1;[0].r:=2;i:=1 to NodesCount-1 do // присвоєння кожному елементу номера батьківського вузла:=trunc(ln(i)/ln(2));:=i-round(power(2,n));:=trunc(round(power(2,n-1))+ ((x-1)/2));p<0 then p:=0;[i].Prt:=p;i<(Power(2,(seHeightTree.Value-1))-1) then //якщо поточний вузол знаходиться на перед останьому рівні[i].l := Tree[i-1].l+2; // то присоїти його нащадкам індекси елементів на останьому рівні[i].r := Tree[i].l+1;[i].value:=i+1;// якщо вузоз знаходится на останьому рівні позначаємо його як лист (-1)[i].l:=-1;[i].r:=-1;[i].value:=i+1;;;(Tree); //малюємо дерево;

//Реалізація процедури визначення вузлів у дереві вказаної висотиTForm1.seHeightTreeChange(Sender: TObject);.Caption:='Вузлів: '+floattostr(Power(2,seHeightTree.Value)-1);;

//Реалізація процедури яка розпочинає обхід дерева по вказаному методуTForm1.btnBypassTreeClick(Sender: TObject);:=''; //шлях на початку пустий.Lines.Clear; //очищуємо поле результатуradioDirectMethod.Checked then //якщо вибраний прямий метод.Panels.Items[0].Text:='Режим: обходу дерева';.Panels.Items[1].Text:='Метод: Прямий';.Lines.Add('Бінарне дерево');.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');.Lines.Add('метод обходу: [ прямий ]');.Enabled:=false;(0); //виконуємо обхід прямим методом.Enabled:=true;.Panels.Items[0].Text:='';.Panels.Items[1].Text:='';.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходуradioFeedbackMethod.Checked then //якщо вибраний зворотній метод.Panels.Items[0].Text:='Режим: обходу дерева';.Panels.Items[1].Text:='Метод: Зворотній';.Lines.Add('Бінарне дерево');.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');.Lines.Add('метод обходу: [ зворотній ]');.Enabled:=false;(0); //виконуємо обхід зворотнім методом.Enabled:=true;.Panels.Items[0].Text:='';.Panels.Items[1].Text:='';.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходуradioSymmetricMethod.Checked then //якщо вибраний симетричний метод.Panels.Items[0].Text:='Режим: обходу дерева';.Panels.Items[1].Text:='Метод: Симетричний';.Lines.Add('Бінарне дерево');.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');.Lines.Add('метод обходу: [ симетричний ]');.Enabled:=false;(0); //виконуємо обхід симетричним методом.Panels.Items[0].Text:='';.Panels.Items[1].Text:='';.Enabled:=true;.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходу;;..html {Сторінка довідки користувача}

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "#"justify"><html xmlns="#"justify"><head>

<title>Допомога | СММОБД</title>

<meta http-equiv="content-type" content="text/html; charset=utf-8" />

<link rel="stylesheet" type="text/css" href="style.css" />

</head>

<body>

<div id="holder">

<div id="header">

<h1>Сторінка допомоги</h1>

<h2>Система моделювання методів обходу бінарних дерев</h2>

</div>

<div id="menu"></div>

<div id="undermenu"></div>

<div id="content">

<!-- Document starts. -->

<h1>Допомога</h1>

<ul>

<li><a href="#createtree" name="hcreate_tree">Створення дерева</a></li>

<li><a href="#methods">Методи обходу</a></li>

<li><a href="#pmetod">Прямий метод</a></li>

<li><a href="#zmetod">Зворотній метод</a></li>

<li><a href="#smetod">Симетричний метод</a></li>

</ul>

<h3 id="intro"><a name="createtree">Створення дерева</a></h3>

<p>

<h3 id="dancingwithpenuines"><a href="#hcreate_tree" name="methods">Методи обходу</a></h3>

<p>

<p>

<div align="center"><img src="methods.png"></div>

<h3 id="mouthofthelion"><a href="#hcreate_tree" name="pmetod">Прямий метод</a></h3>

<p>

<ol>

<li>Потрапити в корінь</li>

<li>Пройти в прямому порядку ліве піддерево</li>

<li>Пройти в прямому порядку праве піддерево.</li>

</ol>

<p>

<div align="center"><img src="methods.png"></div>

<p>

<div align="center"><img src="pmetod.png"></div>

<h3 id="coughinghairballs"><a href="#hcreate_tree" name="zmetod">Зворотній метод</a></h3>

<p>

<ol>

<li>Пройти в зворотному порядку ліве піддерево</li>

<li>Пройти в зворотному порядку праве піддерево</li>

<li>Потрапити в корінь</li>

</ol>

<p>

<div align="center"><img src="pzmetod.png"></div>

<p>

<div align="center"><img src="zmetod.png"></div>

<h3 id="end"><a href="#hcreate_tree" name="smetod">Симетричний метод</a></h3>

<p>

<ol>

<li>Пройти в симетричному порядку ліве піддерево</li>

<li>Потрапити в корінь</li>

<li>Пройти в симетричному порядку праве піддерево</li>

<p>

<div align="center"><img src="psmetod.png"></div>

<p>

<div align="center"><img src="smetod.png"></div>

</ol>

<!-- Document ends. -->

</div>

</div>

</body>

</html>.css {стилі довідки користувача}

/* Styles the body. */{: #777675 url(bg.png) repeat-x;: 12px arial, sans-serif;: #000;: 0; padding: 0;bottom: 50px;

}

/* The design-holder. */

#holder{: relative;: 50%; top: 0;: 750px; height: auto;left: -375px; margin-bottom: 50px;bottom: 25px;color: #F5F7F9;left: 2px #436C78 solid; border-right: 2px #436C78 solid; border-bottom: 2px #436C78 solid;

}

/* Gives all the below id's the same values. */

#header, #menu, #undermenu, #content, #footer{: relative;: 0; top: 0;: 100%;

}

/* The header (with homepage name..). */

#header{: 160px;: url(menu-top-bg.png) repeat-x;

}

/* "Homepage name..." text above (bright coloured). */

#header h1{: absolute;: 20px; bottom: 40px;: 0;: 1.4em georgia, serif;: #fff;index: 1;

}

/* "Homepage name..." text below (dark coloured). */

#header h2{: absolute;: 21px; bottom: 19px;: 0;: 1.4em georgia, serif;: #3E515E;index: 0;

}

/* Fixes the links colours and such in the menu. */

#menu a{ color:#7A96A7; text-decoration:none; font-weight:bold; margin-left:10px; margin-right: 10px; }

#menu a:hover{ color:#000; text-decoration:none; margin-left:10px; margin-right: 10px; }

/* The fade-thingie below the menu. */

#undermenu{: 24px;: url(menu-bottom-bg.png) repeat-x;

}

/* The content holder */

#content{: auto;color: transparent;

}

/* Styles the 'p'-tag. */{: 25px 30px 10px 30px;: 0;align: justify;indent: 15px;: 1em arial, sans-serif;height: 1.5em;: #3E515E;

}

/* Use this (with the 'h4'-tag as header) if you want to quote something. */

.quote{: 0 30px 10px 50px;: italic 0.8em verdana, sans-serif;color: #fff;: 5px;indent: 0;: 1px #aaa dotted;

}

/* Use this if you don't want first lines on all paragraph to be moved 15px inn */

.noindent{indent: 0;

}

/* The biggest font. */{: 2em "times new roman", serif;: 25px 0 0 30px;: 0;: #3E515E;

}

/* The font below the biggest font. */{: 0.8em georgia, serif;: -3px 0 0 35px;: 0;: #aaa;

}

/* Use this for paragraph titles. */{: 1.4em verdana, serif;decoration: underline;: 20px 0 0 30px;: 0;: #3E515E;

}

/* Use this on all paragraphs (but not #quote) wich are part of the article/documentation/etc.. */

.text{: 15px 30px 10px 30px;

}

/* The title to be used when displaying a quote with '#quote'. */{: 1.2em georgia, serif;: 0 0 0 50px;: 0;: #3E515E;

}

/* Italic text. */{: 1em arial, sans-serif;style: italic;: #000;

}

/* Bold text. */{weight: bold;: #3E515E;

}

/* The list ('li') holder. */{color: #fff;

}

/* Lists. */{: 0 0 0 5px;: 0;

}

/* Styles all links on the page (without the menu, wich allready have been styled). */{: #000;weight: bold;decoration: underline;

}

/* Same as above, exept this is the hover (mouse-over) effect. */:hover{: #3E515E;decoration: none;

}


ДОДАТОК В


Система моделювання методів обходу бінарних дерев

Інструкція користувачеві

.ТБЕК.3 234-01 34 01

Листів 7

Розробник Савченко О.О.

Тальне 2013

АНОТАЦІЯ

Даний документ містить відомості про призначення системи, а також інформацію, необхідну для розуміння функцій програми та її експлуатації.

Розглянуто основні принципи, можливості та загальні методи користування програмою.

Документ складається із 7 сторінок.

Запуск додатку

Для запуску додатку потрібно двічі натиснути праву кнопку миші по піктограмі додатку(рис В.1).


Рисунок В.1 - Піктограма додатку


При запуску програми для користувача відображається вікно програми що зображене на рис. В.2.


Рисунок В.2 - Вікно програми


Праворуч розташовані основні функції програми, знизу текстова область в якій відображаються результати створення та обходу дерева вибраним методом.

По середині розміщена робоча область в якій буде відображатися створене бінарне дерево.

Для прикладу створимо повне бінарне дерево кількість рівнів якого рівна 4 та обійдемо його за допомогою прямого методу обходу. Всі дії розбиті на два етапи.

Перший етап. Побудова дерева

Для цього у правій частині за допомогою лічильника встановлюємо значення 4 (рис. В.3). Система підказує нам, що при висоті у 4 рівні дерево матиме 15 вузлів.


Рисунок В.3 - Створення бінарного дерева

Після натиснення кнопки «Створити», система побудує бінарне дерево із вказаними параметрами (рис. В.4).


Рисунок В.4 - Бінарне дерево 4 рівнів


Другий етап. Обхід дерева вибраним методом

Після того як побудоване дерево переходимо до вибору методу обходу (рис. В.5)


Рисунок В.5 - Вибір методу обходу бінарного дерева


Для того щоб дізнатися більше про методи обходу потрібно натиснути на посилання під назвою допомога, відкриється браузер який вказаний по замовчуванню, із завантаженою сторінкою інструкції користувача на якій описані методи обходу бінарних дерев (рис В.6).

Рисунок В.6 - веб-сторінка інструкції користувача


Щоб нам наприклад переглянути допомогу про прямий метод обходу потрібно натиснути на посилання «Прямий метод» яке є якорем на описаний нижче метод (рис В.7).


Рисунок В.7 - веб-сторінка допомоги, опис прямого методу

Після того як ми вибрали метод обходу потрібно натиснути кнопку «Обхід дерева» розпочнеться обхід дерева, у стрічці стану відобразиться режим і метод обходу (рис. В.8).


Рисунок В.8 - Стрічка стану при обході бінарного дерева


А в полі результату відобразиться інформація про дерево і вибраний метод обходу (рис В.9).


Рисунок В.9 - інформація про створене дерево


При цьому в робочій області користувач переглядає візуально як відбуватиметься обхід дерева. Система при перегляді вузла дерева позначає його іншим кольором і після невеликої затримки переходить до наступного вузла дерева(рис В.10а, рис. В.10б).


Рисунок В.10а - Початок обходу дерева прямим методом

Рисунок В.10б - Закінчення обходу дерева прямим методом


По закінченню обходу дерева поле для виведення результату матиме наступний вигляд (рис. В.11).


Рисунок В.11 - Результат обходу дерева прямим методом


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


Анотація Даний дипломний проект призначений створенню системи моделювання методів обходу бінарних дерев. У даному проекті було розглянуто питання обґр

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ