- •Лабораторна робота №1
- •3 Теоретичний матеріал
- •4 Варіанти завдань для виконання
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №2
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №3
- •3 Теоретичний матеріал
- •4 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №4
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №5
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №6
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №7
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
5 Хід виконання практичної роботи
У задачі нас цікавить набір символів, для кожного з яких ми зберігаємо число - кількість входжень цього символу в текст.
#include <iostream> // підключення основних команд
#include <fstream> // підключення роботи над файлами
#include <string> // підключення строкової змінної
#include <Windows.h> // підключення будь-якої мови
ifstream a; // змінна файлу з якого зчитує
ofstream b; // змінна файлу в которй записує
string stroka; // змінна запам'ятовуюча рядок
Таким чином, нам залишилося лише розписати основну програму в складі:
1. Ініціалізація вхідного файлу.
2. Побудова дерева .
3. Вибір виду відображення результатів, висновок.
Питання до захисту :
Перерахуйте подібності та відмінності динамічних структур типу «лінійний список», «стек», «дерево».
Відповідь:____________________________________________________
_____________________________________________________________
Написати процедуру, яка визначає глибину дерева.
Відповідь:____________________________________________________
_____________________________________________________________
Який тип інформації зручно представляти за допомогою бінарних дерев?
Відповідь:____________________________________________________
_____________________________________________________________
Чому пошук на бінарних деревах не дає виграшу по складності в порівнянні з лінійними структурами?
Відповідь:____________________________________________________
_____________________________________________________________
Роботу виконав Роботу перевірив
Лабораторна робота №7
«Реалізація алгоритмів обмінних сортувань в С++»
1 Тема роботи: Реалізація алгоритмів обмінних сортувань при написанні програм в середовищі Delphi.
2 Мета роботи: Формування знань і умінь по вивченню методів внутрішніх сортувань. Придбання навичок реалізації алгоритмів сортування.
3 Теоретичний матеріал
Алгоритм сортування - це алгоритм для впорядкування елементів у списку. У випадку, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в решті полях зберігаються які-небудь дані, ніяк не впливають на роботу алгоритму.
Класифікація алгоритмів сортування
Стійкість (stability) - стійка сортування не змінює взаємного розташування рівних елементів.
Природність поведінки - ефективність методу при обробці вже впорядкованих або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
Використання операції порівняння. Алгоритми, що використовують для сортування порівняння елементів між собою, називаються заснованими на порівняннях. Мінімальна трудомісткість гіршого випадку для цих алгоритмів становить O (n logn), але вони відрізняються гнучкістю застосування. Для спеціальних випадків (типів даних) існують більш ефективні алгоритми.
Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:
Внутрішня сортування оперує масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь комірці. Дані зазвичай упорядковуються на тому ж місці без додаткових витрат.
Існує три групи методів внутрішнього сортування (сортування включенням, сортування вибором, обмінна сортування).
У сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.
Зовнішня сортування оперує запам'ятовуючими пристроями великого об'єму, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми 'бачимо' тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і призводить до спеціальних методів впорядкування, зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних на носії виробляється набагато повільніше, ніж операції з оперативною пам'яттю.
Доступ до носія здійснюється послідовним чином: в кожний момент часу можна вважати або записати тільки елемент, наступний за поточним.
Обсяг даних не дозволяє їм розміститися в ОЗУ.
Також алгоритми класифікуються за:
потребою в додатковій пам'яті або її відсутності
потребою в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої
