ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.09.2024
Просмотров: 5
Скачиваний: 0
Лабораторна робота №12. Алгоритми пошуку і сортування в масивах структур
Мета роботи : вивчити способи сортування і пошуку в масивах структур і файлах.
Контрольні питання
-
Дайте визначення масиву.
Масив – однорідна, фіксована за розміром і конфігурацією, послідовність елементів простої або складної структури, впорядкованих по індексах і розташованих в пам'яті підряд. Елементи цієї послідовності даних називаються елементами масиву. Нумерація елементів виконується індексними послідовностями: кожний елемент масиву має свій індекс.
-
Що, в вашому розумінні, пошук? Навіщо потрібна дана операція?
Завдання пошуку необхідного елементу в масиві структур а (розмір n - задається при виконанні програми) полягає в знаходженні індексу і_kеу, що задовольняє умові а[і_kеу].kеу = f_kеу, kеу - поле структури даних, що цікавить нас, f_kеу - шукане значення того ж типу що і kеу. Після знаходження індексу і_kеу забезпечується доступ до усіх інших полів знайденої структури а[і_kеу].
-
Які алгоритми пошуку вам відомі? Що в них спільного та відмінного?
Лінійний пошук, Пошук діленням навпіл, Алгоритми сортування: Метод прямого обміну, Метод прямого вибору, Метод Д. Шелла.
-
Опишіть алгоритм Лінійного пошуку.
Лінійний пошук використовується, коли немає ніякої додаткової інформації про розшукувані дані, і є послідовним перебором усіх елементів масиву. Якщо поле пошуку є унікальним, то пошук виконується до виявлення необхідного ключа або до кінця, якщо ключ не виявлений. Якщо ж поле пошуку не унікальне, доводиться перебирати усі дані до кінця масиву:
-
Опишіть алгоритм Пошуку діленням навпіл.
Пошук діленням навпіл використовується, якщо дані впорядковані за збільшенням (по убуванню) ключа kеу. Алгоритм пошуку здійснюється таким чином:
– береться середній елемент m;
– якщо елемент масиву а[m].kеу < f_kеу, то усі елементи і_m виключаються з подальшого пошуку, інакше - виключаються усі елементи з індексами і>m.
-
Що, в вашому розумінні, сортування? Навіщо потрібна дана операція?
Під сортуванням розуміється процес перегрупування елементів масиву, що призводить до їх впорядкованого розташування відносно ключа.
-
Які алгоритми сортування вам відомі? Що в них спільного та відмінного?
Метод прямого обміну, Метод прямого вибору, Метод Д. Шелла
-
Дайте короткий опис Методу прямого обміну в сортуванні.
Бульбашкове сортування
-
Дайте короткий опис Методу прямого вибору в сортуванні.
Порівняння
-
Дайте короткий опис шейкерного сортування.
шейкерне сортування (модифікація бульбашкової).
-
Дайте короткий опис Метод Д. Шелла в сортуванні.
Метод Д. Шелла (1959), удосконалення методу прямого включення.
-
Дайте короткий опис Сортування за допомогою дерева.
Сортування за допомогою дерева, метод HеаpSоrt, Д.Уильямсон (1964).
-
Дайте короткий опис Сортування за допомогою розподілу.
Сортування за допомогою розподілу, метод QuіckSоrt, Ч.Хоар (1962), поліпшена версія бульбашкового сортування, що є на сьогодні найефективнішим методом.
Висновок: на лабораторній роботі я вивчив способи сортування і пошуку в масивах структур і файлах.
Додаток до лабораторної роботи №10
Додаток 10.1
Додаток 10.2
Додаток 10.3
Додаток 10.4