Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Пошук бінарних дерев
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2025
Тип роботи:
Курсовий проект
Предмет:
Основи програмування та алгоритмічні мови
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЦЕНТРАЛЬНА СПІЛКА СПОЖИВЧИХ ТОВАРИСТВ УКРАЇНИ
Кіровоградський кооперативний коледж фаховий економіки і права
імені М.П.Сая
Спеціальність: 121 Інженерія програмного забезпечення
ЗАВДАННЯ
на курсовий проект з дисципліни
Основи програмування та алгоритмічні мови
Студенту 2 курсу групи ІПЗ9 -19-26 Якун Павло Костянтинович
Тема: Розробка прогами «Пошук бінарних дерев»
Зміст курсового проекту
ВСТУП…………………………………………………………………………...3
РОЗДІЛ 1 Теоретичні відомості………………………………………………4
1.1 Відомості про бінарні дерева……………………………………………….4
1.2 Поняття мови прогамування…………………………………………..........9
1.3 Мова програмування Паскаль ……………………………………………15
1.4 Компілятори Pascal АВС.NET та Turbo Pascal…………………………..18
РОЗДІЛ 2 Практична частина………………………………………………22
2.1 Опис алгоритму……………………………………………………….........22
2.2 Опис програми………………………………………………………...........24
РОЗДІЛ 3 Методи вдосконалення створеної програми………………….25
ВИСНОВКИ……………………………………………………………………30
ДОДАТКИ:
Додаток А – Блок-схема алгоритму
Додаток В – Лістинг програми
Дата видачі „ “ 20 р. Дата захисту „ “ 20 р.
Керівник ___________/_____________/ Студент ___________
(підпис) (підпис)
Зміст
ВСТУП…………………………………………………………………………...3
РОЗДІЛ 1 Теоретичні відомості………………………………………………4
1.1 Відомості про бінарні дерева……………………………………………….4
1.2 Поняття мови прогамування…………………………………………..........9
1.3 Мова програмування Паскаль ……………………………………………15
1.4 Компілятори Pascal АВС.NET та Turbo Pascal…………………………..18
РОЗДІЛ 2 Практична частина………………………………………………22
2.1 Опис алгоритму……………………………………………………….........22
2.2 Опис програми………………………………………………………...........24
РОЗДІЛ 3 Методи вдосконалення створеної програми………………….25
ВИСНОВКИ……………………………………………………………………30
ДОДАТКИ:
Додаток А – Блок-схема алгоритму
Додаток В – Лістинг програми
ВСТУП
В сучасному житті більшість людей щоденно використовує комп'ютер для відпочинку та у своїй професійній діяльності. Розроблена в даному курсовому проекті програма дуже добре підходить для організацій, які у своєму професійному середовищі використовують велику кількість інформації.
Об'єктом розробки в курсовому проекті є структура даних – бінарне дерево пошуку.
Метою роботи є вивчення даної структури, а потім розробка програми на мові програмування Pascal.
В ході курсового проекту була розроблена інформаційна система даних на мові програмування Pascal, яка описує структуру бінарного дерева пошуку і дозволяє виконувати з ним основні операції (пошук, видалення та додавання елементу).
Організація даних за допомогою бінарного дерева дозволяє суттєво скоротити час знаходження потрібного елемента. Пошук елемента в лінійних структурах зазвичай реалізується шляхом послідовного перебору всіх елементів, присутніх в даній структурі. Пошук по дереву не потребує перебору всіх елементів, тому займає менше часу.
В даному курсовому проекті головною метою є розробка інформаційної структури на мові програмування Pascal, яка представляє собою організацію даних у вигляді бінарного дерева. Також в програму закладений принцип зручності і простоти, що означає відсутність у користувача певних навичок, за виключенням простої комп'ютеної етики.
Актуальністю створюваної програми є скорочення часу роботи, раціональний розподіл часу, що дозволяє виконати більший обсяг роботи за короткий проміжок часу.
РОЗДІЛ 1 Теоретичні відомості
1.1 Відомості про бінарні дерева
Масиви і зв'язані списки визначають колекції об'єктів, доступ до яких здійснюється послідовно. Такі структури даних називають лінійними (Linear) списками, оскільки вони мають унікальні перший та останній елементи та у кожного внутрішнього елемента є тільки один спадкоємець. Лінійний список є абстракцією, що дозволяє маніпулювати даними, що подаються різним чином - масивами, стеками, чергами і зв'язаними списками.
У багатьох програмах виявляється нелінійний порядок об'єктів, де елементи можуть мати декількох спадкоємців. Наприклад, у генеалогічному дереві батько може мати декількох нащадків (дітей). На рисунку 1.1 показано генеалогічне дерево Мономаховичів. Такий спосіб упорядкування називають ієрархічним.
/
Рисунок 1.1 – Генеалогічне дерево Мономаховичів
Бінарне (двійкове) дерево – це упорядковане дерево, кожна вершина якого містить не більше двох піддерев. Бінарне дерево є рекурсивною структурою, так як кожне його піддерево є бінарним деревом і кожен його вузол, в свою чергу, є коренем дерева.
Вузли дерева, які мають нащадків, називаються листям.
Схематично бінарне дерево зображено на рисунку1.2:
/
Рисунок 1.2 – Схематичне зображення бінарного дерева
Бінарне дерево пошуку може бути або порожнім, або воно має таку властивість, що кореневий елемент має більше значення вузла, ніж будь-який елемент в лівому піддереві, і менше або рівне, ніж елементи в правому піддереві. Вказана властивість називається характеристичним властивістю двійкового дерева пошуку і виконується для будь-якого вузла такого дерева, включаючи коріння.
Основні операції над двійковими деревами
Пошук.
Для пошуку вузла із заданим ключем в бінарному дереві пошуку використовується процедура , яка отримує параметри покажчика на корінь бінарного дерева і ключ k, а повертає покажчик на вузол з цим ключем (якщо такий існує; в іншому випадку повертається значення NIL).
Процедура пошуку починається з кореня дерева і проходить вниз по дереву. Для кожного вузла х на шляху вниз його ключ key[x] порівнюється з переданим як параметр ключем k. Якщо ключі однакові, пошук завершується. Якщо k менше key[х], пошук триває в лівому піддереві х; якщо більше — то пошук переходить в праве піддерево. Ту ж процедуру можна записати ітеративно, «розгортаючи» рекурсію в цикл while.
Додавання нових вузлів.
Для вставки нового вузла v у дерево потрібно скористатися процедурою, яка отримує параметр вузла z, у якого key[z] = v, left[z] = NIL і right[z] = NIL, після чого вона таким чином змінює саме дерево і деякі поля z, що z виявляється вставленим в відповідну позицію в дереві.
Видалення вузлів.
Процедура видалення даного вузла z з бінарного дерева пошуку отримує як аргумент покажчик на z. Процедура розглядає три можливі ситуації:
Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NIL.
Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.
Якщо у вузла z два дочірніх вузла, то ми знаходимо наступний за ним вузол у, у якого немає лівого дочірнього вузла, прибираємо його з позиції, де він перебував раніше, шляхом створення нового зв'язку між його батьком і нащадком, і замінюємо ним вузол Z.
Класифікація бінарних дерев
За ступенем.
Ступенем вузла в дереві називається кількість дуг, яке з нього виходить (рисунок 1.3). Ступінь дерева дорівнює максимальному ступені вузла, що входить до дерево. Виходячи з визначення ступеня зрозуміло, що ступінь вузла бінарного дерева не перевищує числа два. При цьому листям в дереві є вершини, мають ступінь нуль.
/
Рисунок 1.3 – Ступені бінарного дерева
За повнотою.
Неповне бінарне дерево складається тільки з вузлів, що мають ступінь два або ступінь нуль. Повне бінарне дерево містить вузли зі ступенем рівної одному (рисунок 1.4).
/
Рисунок 1.4 – Повне та неповне бінарне дерево
Представлення бінарних дерев
1. Подання дерева у вигляді списку.
Бінарні дерева досить просто можуть бути представлені у вигляді списків (рисунок 1.5). Списочно подання бінарних дерев засноване на елементах, відповідних вузлів дерева. Кожен елемент має поле даних і два поля покажчиків. Один покажчик використовується для зв'язування елемента з правим нащадком, а інший з лівим. Листя має порожні покажчики нащадків.
/
Рисунок 1.5 – Подання бінарного дерева у вигляді списку
2. У вигляді масиву.
У вигляді масиву найпростіше представляється повне бінарне дерево, оскільки воно завжди має строго певне число вершин на кожному рівні (рисунок 1.6). Вершини можна пронумерувати зліва направо послідовно за рівнями і використовувати ці номери в якості індексів в одновимірному масиві.
/
Рисунок 1.6 – Подання бінарного дерева у вигляді масиву
1.2 Поняття мови програмування
Мова програмування (англ. Programming language) — це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.
Більш строге визначення: мова програмування — це система позначень для опису алгоритмів та структур даних, певна штучна формальна система, засобами якої можна виражати алгоримти. Мову програмування визначає набір лексичних, синтаксичних і семантичних правил, що задають зовнішній вигляд програми і дії, які виконує виконавець (комп'ютер) під її управлінням.
З часу створення перших програмованих машин було створено понад дві з половиною тисячі мов програмування. Щороку їх кількість поповнюється новими. Деякими мовами вміє користуватись тільки невелике число їх власних розробників, інші стають відомі мільйонам людей. Професійні програмісти зазвичай застосовують в своїй роботі декілька мов програмування.
Історія
Власне перші мови програмування з'явилися задовго до появи перших комп'ютерів. Ще в 19-му столітті існували «програмовані» ткацькі верстати та піаніно-програвачі, спосіб програмування нагадує так званіпредметно-орієнтовані мови програмування. На початку 20-го століття починають використовуватисьперфокарти, та механічна обробка даних. В 1930 −1940 рр. виникає лямбда-числення та машина Тюринга, які застосовували математичну абстракцію для опису алгоритмів. Лямбда-числення згодом здійснило вплив на проектування мов програмування.
В 1940-х роках створюються перші електричні, двійкові комп'ютери. Вважається, що першу мову програмування високого рівня — Планкалькюль (нім. Plankalkül) розробив німець Конрад Цузе в період1943–1945 років, але в той час вона не була реалізована і не одержала уваги. Реалізацією мови зайнялися і здійснили лише в 1998—2000 роках.
У кінці 40-их — початку 50-их застосовувалися інтерпретовані системи кодування, коли певні команди мови програмування кодувалися числами, які вже інтерпретувалися машинним кодом. Ці системи називалися «автоматичним програмуванням» і були простішими для програмування, ніж машинні коди, але могли мати значно меншу (до 50 разів) швидкодію, через що часто надавали перевагу машинним кодам. До таких систем належали — Short Code для BINAC (1949) і UNIVAC I (1952), Speedcoding для IBM 701, розроблена Джоном Бекусом у 1954.
Першою широковживаною компільованою мовою стала розроблена групою Джона Бекуса Фортран, анонсована у 1954 році і випущена у 1957 для IBM 704. Основним призначенням Фортрану були швидкі наукові обчислення, оголошувалося, що швидкодія згенерованого компілятором коду майже не відрізнятиметься від написаного вручну машинного коду.
У 1964 році було створено спрощену мову BASIC (Beginners All-purpose Symbolic Instruction Code) для навчання програмуванню студентів, які переважно спеціалізувалися у вільних мистецтвах, а не технічних науках.
У стислі терміни до 1965 року було розроблено мову PL/I, яка поєднувала можливості Фортран, ALGOL і COBOL, і виявилась заскладною, хоча і була у широкому вжитку у 1970-их у наукових і бізнес задачах, також її підмножини (PL/C, PL/CS) використовувалися для навчання програмуванню.
На початку 1960-их було створено перші мови із динамічною типізацією — APL і SNOBOL.
У 1971 році Вірт опублікував опис мови Pascal, яка у 70-их стала загальновживаною для навчання студентів.
У 1972 році Деніс Річі розробив у Bell Labs мову C. Тоді ж у Марселі створено інтерпретатор мови Пролог — першої і найвідомішої мови логічного програмування. Алан Кей у Xerox PARC розробив першу широко вживану об'єктно-орієнтовану мову — Smalltalk.
У 1973 Робін Мілнер в Единбурзькому університеті створив ML.
У 1975 Міністерство оборони США утворило міжнародну групу для створення нової мови програмування для власних потреб, конкурс у 1979 виграла мова Ада.
У 1981 випущено dBASE II.
У 1986 році опублікована мова Objective-C і створено Erlang. Тоді ж Borland і Apple незалежно створили об'єктно-орієнтоване розширення мови Pascal — Object Pascal.
У 1995 році Sun Microsystems випустила Java, Netscape — JavaScript, тоді ж створено PHP і Ruby.
У 1996 році створено OCaml.
У 2001 році створено C#.
У 2002 році створено F#. У 2003 році створено Scala.
Класифікація мов програмування
Мови програмування класифікують за такими критеріями:
Рівень абстракції.
Мови програмування високого рівня оперують сутностями ближчими людині, такими як об'єкти, змінні, функції. Мови програмування нижчого рівня оперують сутностями ближчими машині: байти, адреси, інструкції. Текст програми на мові високого рівня зазвичай набагато коротший ніж текст такої самої програми на мові низького рівня, проте програма має більший розмір.
Область застосування.
Універсальні та спеціалізовані. Спеціалізовані мови теж бувають Тьюрінг-повні, та все ж їх область застосування обмежена, як наприклад у мови shell.
Підтримувані парагдими програмування.
Об'єктно-орієнтовані, логічні, функційні, структурні.
Імперативні мови базуються на ідеї змінної, значення якої змінюється присвоєнням. Вони називаються імперативними (лат. imperative — наказовий), оскільки складаються із послідовностей команд, які звичайно містять присвоєння змінних, де вираз може посилатися на значення змінних присвоєних попередніми командами.
Способи реалізації мов
Мови можуть бути реалізовані як компільовані та інтерпретовані.
Програма на компільованій мові за допомогою компілятора (особливої програми) перетвориться (компілюється) в машинний код (набір інструкцій) для даного типу процесора і далі збирається в виконавчий модуль, який може бути запущений на виконання як окрема програма. Іншими словами, компілятор переводить вихідний текст програми з мови програмування високого рівня в двійкові коди інструкцій процесора.
Якщо програма написана на скриптовій мові, то інтерпретатор безпосередньо виконує (інтерпретує) вихідний текст без попереднього перекладу. При цьому програма залишається мовою оригіналу і не може бути запущена без інтерпретатора. Процесор комп'ютера, в зв'язку з цим, можна назвати інтерпретатором для машинного коду.
Поділ на компільовані і інтерпретовані мови є умовним. Так, для будь-якої традиційно компілючої мови, як, наприклад, Паскаль, можна написати інтерпретатор. Крім того, більшість сучасних «чистих» інтерпретаторів не виконують конструкції мови безпосередньо, а компілюють їх в деяке високорівневе проміжне представлення (наприклад, з розіменуванням змінних і розкриттям макросів).
Для будь-якої інтерпритуючої мови можна створити компілятор — наприклад, мова Лісп, початково інтерпретована, може компілюватися без обмежень. Створюваний під час виконання програми код може так само динамічно компілюватися під час виконання.
Як правило, скомпільовані програми виконуються швидше і не вимагають для виконання додаткових програм, так як вже переведені на машинну мову. Разом з тим, при кожній зміні тексту програми потрібно її перекомпіляція, що уповільнює процес розробки. Крім того, скомпільована програма може виконуватися тільки на тому ж типі комп'ютерів і, як правило, під тією ж операційною системою, на яку був розрахований компілятор. Щоб створити виконуваний файл для машини іншого типу, потрібна нова компіляція.
Інтерпретовані мови володіють деякими специфічними додатковими можливостями, крім того, програми на них можна запускати відразу ж після зміни, що полегшує розробку. Програма на скриптовій мові може бути найчастіше запущена на різних типах машин та операційних систем без додаткових зусиль.
Однак інтерпретовані програми виконуються помітно повільніше, ніж компільовані, крім того, вони не можуть виконуватися без програми-інтерпретатора.
Деякі мови, наприклад, Java та C#, перебувають між компільованими і інтерпретованими. А саме, програма компілюється не в машинну мову, а в машинно-незалежний код низького рівня, байт-код. Далі байт-код виконується віртуальною машиною. Для виконання байт-коду зазвичай використовується інтерпретація, хоча окремі його частини для прискорення роботи програми можуть бути трансльовані в машинний код безпосередньо під час виконання програми за технологією компіляції «на льоту» (Just-in-time compilation, JIT). Для Java байт-код виповнюється віртуальною машиною Java (Java Virtual Machine, JVM), для C # — Common Language Runtime.
Подібний підхід у деякому сенсі дозволяє використовувати плюси як інтерпретаторів, так і компіляторів. Слід згадати, що є мови, які мають і інтерпретатор, і компілятор (Форт (Forth)).
Покоління мов програмування
Інколи в літературі та в інтернеті згадують про 5 поколінь мов програмування, щоправда, даний поділ є спірним і суперечним. В професійній літературі по програмуванню доволі рідко згадують про покоління мов програмування, а більше зосереджуються на функціональній класифікації мов програмування. Крім того саме віднесення певних мов до різних поколінь різниться у різних авторів.
Поділ на покоління мов програмування почав поширюватись з появою високорівневих мов програмування і до того не застосовувався. Високорівневі мови програмування почали вважатися третім поколінням, асемблерні мови — другим, а машинний код — першим поколінням. Сучасні спроби класифікація мов на четверте і п'яте покоління проводяться різними авторами по різному по різних ознаках і різниця між мовами третього, четвертого та п'ятого покоління часто доволі нечітка. Крім того багато компаній розробники мов програмування та середовищ програмування для них використовують маркетинговий хід проголошуючи певну мову (мову та інтегроване середовище розробки для неї) п'ятим поколінням.
1.3 Мова прорамування Паскаль
Для написання програми пошуку бінарних дерев я використала мову програмування Pascal, так як на ній найзручніше створювати програми такого типу.
Pascal — алгоритмічна мова програмування універсального призначення. Існують діалекти мови з підтримкою об'єктно-орієнтованого програмування.
Історія виникнення та особливості
Першим компілятором мови Pascal є ETH Pascal, створений у 1970-му. Назва ETH походить від назви інституту німецькою Eidgenössische Technische Hochschule Zürich (українською Федеральна вища технічна школа Цюріха), де він був розроблений. Творцем мови є Ніклаус Вірт. Наприкінці того ж року Вірт оприлюднив перший офіційний опис мови, синтаксису та семантики. Нова версія мови побачила світ у 1972 році. Тоді ж Вірт та його англійський колега Чарльз Ентоні Гоар випустили аксіоматичний опис мови Pascal.
У 1969 році Вірт доручає розробку компілятора одному зі своїх студентів (Е. Марм'є). На той момент Марм'є володів лише Фортраном (Fortran) і писав компілятор виключно на цій мові. Після написання компілятор Pascal був переписаний на самому собі. Як згадував потім Вірт, вибір Фортрана був серйозною помилкою, бо він не міг адекватно представляти складні структури даних компілятора Pascal, що лише заплутувало програму.
Наступна спроба створення компілятору почалася з чіткого формулювання на описі (1970 року) самого Паскалю. Синтаксичний аналіз нового однопрохідного компілятору реалізовувався за допомогою рекурсії. Тепер команду розробників склали: У. Амман, Е. Марм'є, Р. Шилд. Після того як компілятор був написаний на ще невідомій мові, Шилд поїхав додому, де він протягом двох тижнів вручну транслював програму у допоміжну низькорівневу мову. Отже, в середині 1970 року компілятор ETH Pascal був готовий.
ETH Pascal був цікавий насамперед тим, що став він однією з перших реалізацій мов високого рівня написаних на самій собі, на два роки випередивши компілятор Сі. У 1973 році була створена абстрактна Pascal-машина (P-машина), яка виконувала спеціальний P-код. Щоб вирішити проблему сумісності компілятора, Вірт вирішив скористатися перевіреними часом методами інтерпретаціі. Найвідомішими з них рішеннями, які передували P-коду, можна назвати реалізацію мови Snobol-4 (Р. Грісуолдом, у 1967 році), де як код абстрактної машини використовувалася мова SIL (System Implementation Language).
Початкова мета розробки мови диктувалася потребою інструмента «для навчання програмуванню як систематичній дисципліні». Pascal належить до Algol-подібних мов програмування, оскільки використовує семантику Algol-ла. Однак Pascal мав суттєве удосконалення — жорстку типізацію. Це означало, що присвоювання можна було виконувати лише для змінних, що належать до одного типу (одночасно вказувались правила, за якими типи вважались однаковими). Це удосконалення суттєво покращило стиль програмування, оскільки значну частину помилок вдавалось виявити ще на етапі компіляції — що збільшує надійність програм.
Однак мова розроблялась як дослідницький проект і первісний Pascal був мало придатний для написання великих проектів, оскільки програму не можна було скласти з кількох програмних частин — просто не було передбачено такої можливості. Але ця мова програмування швидко завоювала популярність у навчальних закладах при вивченні програмування. А коли з'явились діалекти мови де можливим було окреме компілювання програмних частин — Pascal став засобом написання великих програмних систем.
Існує ряд об'єктивних причин, які обумовили видатний успіх мови Pascal. Серед них у першу чергу потрібно вказати такі:
Мова в природній і елегантній формі відбила найважливіші сучасні концепції технології розробки програм.
Завдяки своїй компактності, концептуальній цілісності й ортогональності понять, а також вдалому оригінальному опису, запропонованому автором мови, Pascal виявився дуже легким для вивчення й освоєння.
Незважаючи на відносну простоту мови, вона виявилась придатною для дуже широкого спектру застосунків, у тому числі для розробки дуже великих і складних програм, наприклад, операційних систем.
Pascal дуже технологічний для реалізації практично усіх, у тому числі і нетрадиційних, машинних архітектур. Стверджується, що розробка Pascal-транслятора «майже» не перевищує за трудомісткістю гарної дипломної роботи випускника ВНЗу.
Мова Pascal стандартизована в багатьох країнах, а у 1983 році було прийнято міжнародний стандарт (ISO 7185:1983).
1.4 Компілятори Pascal АВС.NET та Turbo Pascal
Pascal АВС.NET – це мова програмування нового покоління Паскаль, що включає класичний Pascal. Вона реалізована на платформі Microsoft.NET і включає в себе всі сучасні мовні засоби: класи, перегрузку операцій, інтерфейси, обробку виключень, узагальнені класи та підпрограми, засоби паралельного програмування.
Pascal АВС.NET є мультипарадігменною мовою: на ній можна програмувати в структурному, об'єктно-орієнтованому та функціональному стилях.
Pascal АВС.NET - це також просте і потужне інтегроване середовище розробки, яке підтримує технологію IntelliSense, що включає засоби автиоформатування, вбудований відгадчик та вбудований дизайнер форм.
Крім того, консольний компілятор PascalABC.NET функціонує на Linux і MacOS під Mono.
Історія виникнення
У 2003 році на факультеті математики, механіки і комп'ютерних наук ПФУ була створена навчальне середовище програмування Pascal ABC. Система була інтегрована оболонку з вбудованим інтерпретатором мови програмування Паскаль, близького до мови Delphi. Незважаючи на неповну реалізацію мови, вона стала вдалою заміною застарілій системі Turbo Pascal в первісному навчанні програмуванню. Як навчальну систему її використовували в багатьох регіонах СНД. В каталозі Soft@Mail.ru програма Pascal ABC в 2006 році визнавалася програмою тижні.
/
Рисунок 1.7 – Зовніший вигляд програми на Pascal АВС.NET
У 2005-2006 роках система була повністю перероблена: змінена її архітектура - на повноцінний компілятор мови, близької до Delphi, з розширеннями, пов'язаними з платформою .NET. Нова система отримала назву PascalABC.NET. У червні 2009 року з'явилася перша стабільна версія PascalABC.NET 1.2.
У вересні 2009 р з'явилася веб-середовище розробки WDE, що не вимагає установки PascalABC.NET на локальний комп'ютер і дозволяє запускати програми на PascalABC.NET безпосередньо з вікна браузера. Ключовою особливістю WDE є те, що програма запускається на сервері, а на клієнтський комп'ютер в інтерактивному режимі передаються лише дані вводу-виводу. Для зареєстрованих користувачів доступний особистий файловий архів програм з можливістю навігації, а також з можливістю надавати іншим користувачам доступ до опублікованих програмами на читання в стилі Google Docs. У серпні 2010 р в WDE з'явилася можливість створювати прості графічні додатки.
Особливості PascalABC.NET
Всі типи – класи;
Стандартний тип BigInteger;
Стандартний тип Complex;
Двовимірні динамічні масиви;
Інтерфейси .NET;
Підключення просторів імен .NET в розділі uses;
Узагальнені класи, інтерфейси, підпрограми та процедурні змінні;
Автоматичне прибирання сміття для об'єктів;
Атрибути;
Методи розширення;
Підтримка некерованого коду через external;
Стандартні модулі
Оскільки в PascalABC.NET можна користуватися всіма бібліотеками платформи .NET, то стандартні модулі нечисленні і орієнтовані на навчання:
Модуль растрової графіки GraphABC;
Модуль векторної графіки ABCObjects;
Модуль FormsABC для створення простих віконних додатків без дизайнера форм;
Модулі виконавців Робот і креслярем (шкільна інформатика);
Тurbo Pascal — інтегроване середовище розробки програмного забезпечення для платформ DOS та Windows 3.x та мова програмування в цьому середовищі, діалект мови Паскаль від фірми Borland.
Переваги та недоліки Тurbo Pascal
Переваги:
Зручне середовище розробки, що включає функціональний налагоджувач, доступний в будь-який момент.
Контекстна довідкова система, за якою можна вивчати мову, не звертаючись до сторонніх джерел.
Висока швидкість компіляції та виконання скомпільованих програм.
Вбудована можливість використовувати вставки мовою асемблера.
Недоліки:
Компілятор розрахований на реальний режим DOS, застосування якого сходить нанівець. Проте в останніх версіях компілятора і середовища введена підтримка захищеного режиму разом з відповідним зневаджувачем (TD).
У модулі CRT є помилка (некоректний підрахунок кількості циклів для функції delay, не розрахований на швидкі процесори, процесори зі змінною частотою і багатозадачні середовища), через яку при запуску програми на комп'ютерах з тактовою частотою понад 200 MHz відразу відбувалося аварійне завершення з повідомленням «Runtime error 200 at …».
Цікаві факти
В Turbo / Borland Pascal 7.0 вбудовано пасхальне яйце: якщо в інтегрованому середовищі через меню «Help» відкрити панель «About» і натиснути клавіші Alt+I, то в панелі будуть прокручуватися імена розробників.
Алгоритм розмальовки у вбудованому редакторі трохи відрізняється від того, як розуміє синтаксис компілятор. А саме, конструкція (*) сприймається редактором як закінчений коментар, а компілятором — як початок коментаря. Це може використовуватися, щоб усередині коментарів вставляти синтаксично розфарбовані ділянки, наприклад, демонстрація способу використання. Або, наприклад, існують Паскаль-віруси, які записують своє тіло після 80-ї колонки, використовуючи (*), щоб старий текст виглядав без змін. Область розповсюдження таких вірусів обмежена місцями, де запускаються програми у середовищі Turbo Pascal, зате в самих цих місцях боротися з Паскаль-вірусами було нетривіально. Антивіруси тих часів були безсилі проти цих перших представників макровірусів.
РОЗДІЛ 2 Реалізація проекта
2.1 Опис алгоритму
Найпростіший спосіб побудови бінарного дерева полягає у створенні симетричної структури із наперед відомою кількістю вузлів. Усі вузли-нащадки, що створюються, рівномірно розподіляються зліва та справа кожного вузла-предка. При цьому досягається мінімально можлива глибина для заданої кількості вузлів дерева. Рівномірний розподіл вузлів можна визначити рекурсивно:
Перший вузол вважати коренем дерева;
Створити ліве піддерево із заданою кількістю вузлів;
Створити праве піддерево із заданою кількістю вузлів.
Для початку потрібно ввести змінні, які будуть використовуватися у програмі. Вводимо змінні n,i,x.
Далі розробляємо процедуру abbToTree, яка буде створювати та відображати дерево. Якщо дерево порожнє, то створюємо нове дерево, якщо ж ні, то визначаємо чи менший покажчик на корінь дерева за х. Якщо так, то спочатку створюємо праве піддерево, я кщо ж ні, тоді створюємо ліве піддерево.
Після цього створюємо процедуру getDepthOfTree, яка буде здійснювати знаходження ключового значення в бінарному дереві пошуку. Якщо дерево порожнє, то пошук припиняється, якщо ж ні, то визначаємо глибину дерева і виконуємо пошук ключового значення.
2.2 Опис програми
Створимо бінарне дерево із заданою користувачем кількістю вузлів. Оскільки структура дерева визначена рекурсивно, то для його створення та відображення можна розробити рекурсивні підпрограми.
Процедура створення дерева отримує один цілочисловий параметр ТNode, що визначає кілъкістъ вузлів дерева та повертає покажчик на його корінь. Якщо кількість вузлів дорівнює нулю, дерево порожне, а отже, виконано умову завершення рекурсії і має повертатися значення nil. Якщо кількістъ вузлів дерева відрізняєтъся від нуля, необхідно виділити пам'ять для кореня дерева, за наведеними вище формулами обчислити кількістъ вузлів у лівому та правому піддеревах і двічі рекурсивно викликати процедуру для створення піддерева.
Дерево відображатиме процедура abbToTree .
Procedure addToTree(var root : TNode; depth , x : integer);
Begin
if root = Nil then begin
new(root);
root^.left := Nil;
root^.right := Nil;
root^.depth := depth;
root^.info := x;
end else if (root^.info > x) then
addToTree(root^.left , depth + 1 , x)
else
addToTree(root^.right , depth + 1 , x);
End;
Розробимо процедуру знаходження ключового значення в бінарному дереві пошуку. До процедури передається ключове значення і покажчик на корінь дерева, а повертається покажчик на вузол, значення якого дорівнює шуканому. Пошук починається з кореня дерева і триває доти, доки шукане значення не буде знайдено або доки всі вузли дерева не будуть перевірені.
Procedure getDepthOfTree(root : TNode);
Begin
if root = Nil then exit;
if root^.depth > depth then
depth := root^.depth;
getDepthOfTree(root^.left);
getDepthOfTree(root^.right);
End.
РОЗДІЛ 3 Методи вдосконалення створеної програми
Для вдосконалення розробленої програми можна було використати мову програмування Delphi.
Мова програмування Delphi
Delphi — мова програмування, що ґрунтується на діалекті мови Pascal від компанії Borland. До версії 7.0 мала назву Object Pascal. Окрім того Delphi - середовище розробки (IDE) для однойменної мови.
Delphi - це нащадок Турбо Паскаля, який був випущений для операційної системи Cp/m в 1983 році. У лютому 1994 року Турбо Паскаль був перенесений на операційну систему MS-DOS. На ранньому етапі розвитку комп'ютерів IBM РС, Турбо Паскаль був однією з найбільш популярних мов розробки програмного забезпечення - головним чином тому, що це був цілком серйозний компілятор, який, включаючи компілятор, редактор і відгадчик. Середовище мало змогу працювати на машині з 64 Kb оперативної пам'яті.
Під Windows – Турбо Паскаль був перенесений фірмою Borland в 1990 році. А найостанніша версія Borland Pascal 7.0 (що має тепер таку назву), не рахуючи Delphi, вийшла в світ в 1992 році. Розробка Delphi почалася в 1993 році. Після проведення beta-тестування Delphi показали на "Software Development '95".
Спочатку на Delphi можна було програмувати під MS Windows 3.1. Починаючи з версії 2.0 на Delphi можна створювати програми під будь-яку з 32-бітних версій MS Windows.
В 2000 році була спроба створити варіант Delphi під операційну систему на базі ядра Linux, така модифікація Delphi мала назву Kylix. Було випущено 3 версії Kylix, проте експеримент виявився невдалим і 2003 року проект був заморожений.
2003 року була створена модифікація мови під платформу Microsoft.NET, що отримала назву Delphi.NET. Цей варіант мови послідовно розвивається в версіях Delphi 8, 2005, 2006, 2007.
Частково Delphi підтримується також у відкритому проекті FreePascal, що потенційно дозволяє створювати програми під велику кількість платформ.
Інтегроване середовище Delphi складається з чотирьох основних елементів: головне вікно, вікно інспектора об’єктів, вікно форми та вікно модуля (вікно коду).
Головне вікно має заголовок Delphi 7.0 – Project1. Це вікно містить головне меню, панель кнопок швидкого доступу і палітру компонент.
Головне меню (рисунок 3.1) – стандартне меню в стилі Windows. Це меню дозволяє керувати всіма аспектами роботи в Delphi. Рядок меню можна налаштувати за власним бажанням, наприклад, додати власні елементи до пункту меню інструментів Tools.
/
Рисунок 3.1 – Головне меню в Delphі
Кнопки і гарячі клавіші (рисунок 3.2). Кнопки використовуються для швидкого доступу до найнеобхідніших пунктів меню. Вони розташовані в лівій частині екрану на панелі швидкого доступу. Серед них є кнопки для компіляції і запуску програм, для перегляду вихідного коду рядок за рядком тощо. Для того, щоб з’ясувати призначення кнопки досить навести на неї вказівник миші і прочитати підказку. Панель швидкого доступу за замовчанням містить 14 кнопок, але її склад можна налогодити відповідно до вимог користувача. Більша частина найнеобхідніших функцій середовища Delphi також має гарячі клавіші, які можна натиснути замість відповідної кнопки чи то пункту меню.
/
Рисунок 3.2 – Гарячі клавіші в Delphi
Палітра компонентів (рисунок 3.3) – це каталог візуальних і невізуальних об’єктів, які можна включати до власних форм и програм. У Delphi компоненти об’єднані в кілька основних груп: стандартна, додаткова, група Windows 95, група доступу до даних, група управлінняданими, група Windows 3.1, діалогова група, системна група, група звітів, OCX група і група взірців. Кожна з цих груп представлена на окремій сторінці палітри компонент. Щоб з’ясувати призначення компонента, досить лише виділити його і натиснути F1.
/
Рисунок 3.2 – Палітра компонентів Delphi
Вікно, яке знаходиться у центрі, називається формою. Під час розробки форма являє собою вікно програми. У цьому вікні проходить основна частина роботи по проектуванню програми. Деякі елементи у вікні форми (лінії сітки, невізуальні компоненти) не будуть видимими під час виконання програми. Але, оскільки Delphi – це середовище програмування типу WYSIWYG (What – You – See – Is – What – You – Get, що бачите, те й отримаєте), то більша частина того, що ми бачимо під час проектування є тим, що ми побачимо і під час виконання програми. Є можливість змінити різні його властивості, наприклад, прибрати кнопки максимізації та мінімізації вікна тощо.
Вікно коду працює аналогічно до простого текстового редактора. Можна використовувати клавіші PgUp i PgDn, клавіші курсору, мишу, можна виділити, скопіювати, вставити текст за допомогою меню EDIT і відповідних гарячих клавіш.
Вгорі вікна коду є закладка. Вона належить до файлу, який зараз редагується. Якщо відкрити декілька файлів, кожен з них будемати свою закладку.
Інспектор об’єктів або Object Inspector як правило знаходиться в лівій частині екрану і містить інформацію про виділений об’єкт. Інспектор об’єктів складається з таких елементів: комбінованої панелі (Combo box) вибору об’єкту, сторінки властивостей (Properties Page) та сторінки подій (Events Page) вибраного об’єкту.
У інспекторі об’єктів описані всі властивості об’єкту, і його використовують для зміни цих властивостей. Наприклад, можна змінити заголовок кнопки, клацнувши на ній мишкою, а потім записавши нову назву в полі Caption інспектора об’єктів.
Крім
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора