Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
metodichka_po_labaratornym_robotam_ASD-S.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
567 Кб
Скачать
☆

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), але вони відрізняються гнучкістю застосування. Для спеціальних випадків (типів даних) існують більш ефективні алгоритми.

Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:

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

Існує три групи методів внутрішнього сортування (сортування включенням, сортування вибором, обмінна сортування).

У сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.

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

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

Обсяг даних не дозволяє їм розміститися в ОЗУ.

Також алгоритми класифікуються за:

  • потребою в додатковій пам'яті або її відсутності

  • потребою в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої