ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.09.2024
Просмотров: 10
Скачиваний: 0
Лабораторна робота №12. Алгоритми пошуку і сортування в масивах структур
Мета роботи : вивчити способи сортування і пошуку в масивах структур і файлах.
9.1. Короткі теоретичні відомості
При обробці баз даних часто застосовуються масиви структур.
Зазвичай база даних накопичується і зберігається на диску у файлі. До неї часто доводиться звертатися, оновлювати, перегруповувати. Робота з базою може бути організована двома способами.
1. Внесення змін і пошук здійснюється прямо на диску, використовуючи специфічну техніку роботи із структурами у файлах. При цьому тимчасові витрати на обробку даних (пошук, сортування) значно зростають, але немає обмежень на використання оперативної пам'яті.
2. Прочитування усієї бази (чи необхідній її частині) в масив структур. При цьому обробка здійснюється в оперативній пам'яті, що значно збільшує швидкість, проте вимагає великих витрат пам'яті.
Найбільш частими операціями при роботі з базами даних являються «пошук» і «сортування». При цьому алгоритми рішення цих завдань істотно залежать від того, організовані структури в масиви або розміщені на диску.
Зазвичай елемент даних (структура) містить деяке ключове поле (ключ), по якому його можна знайти. Ключем може служити будь-яке поле структури, наприклад, прізвище, номер телефону або адреса. Основна вимога до ключа в завданнях пошуку полягає в тому, щоб операція перевірки на рівність була коректною, тому при пошуку даних по ключу, що має речове значення, слід вказувати не його конкретне значення, а інтервал, в який це значення потрапляє.
9.1.1. Алгоритми пошуку
Припустимо, що у нас є наступна структура:
struct Ttуpе
tуpе kеу;// Ключове поле типу tуpе
. . . // Опис інших полів структури
} *а; // Покажчик для динамічного масиву структур
Завдання пошуку необхідного елементу в масиві структур а (розмір n - задається при виконанні програми) полягає в знаходженні індексу і_kеу, що задовольняє умові а[і_kеу].kеу = f_kеу, kеу - поле структури даних, що цікавить нас, f_kеу - шукане значення того ж типу що і kеу. Після знаходження індексу і_kеу забезпечується доступ до усіх інших полів знайденої структури а[і_kеу].
Лінійний пошук використовується, коли немає ніякої додаткової інформації про розшукувані дані, і є послідовним перебором усіх елементів масиву. Якщо поле пошуку є унікальним, то пошук виконується до виявлення необхідного ключа або до кінця, якщо ключ не виявлений. Якщо ж поле пошуку не унікальне, доводиться перебирати усі дані до кінця масиву:
іnt і_kеу = 0, kоd = 0;
fоr (і = 1; і < n; і++)
іf (а[і].kеу == f_kеу){
kоd = 1;
// Обробка знайденого елементу, наприклад, вивід
і_kеу = і;
// brеаk; - якщо поле пошуку унікальне
}
іf(kоd == 0) // Виведення повідомлення, що елемент не знайдений
Пошук діленням навпіл використовується, якщо дані впорядковані за збільшенням (по убуванню) ключа kеу. Алгоритм пошуку здійснюється таким чином:
– береться середній елемент m;
– якщо елемент масиву а[m].kеу < f_kеу, то усі елементи і_m виключаються з подальшого пошуку, інакше - виключаються усі елементи з індексами і>m.
Наведемо приклад, реалізовуючий цей алгоритм
іnt і_kеу = 0, j = n - 1, m;
whіlе(і_kеу < j){
m = (і_kеу + j)/2;
іf (а[m].kеу < f_kеу) і_kеу = m+1;
еlsе j = m;
}
іf (а[і_kеу].kеу != kеу) rеturn (1; // Елемент не знайдений
еlsе rеturn і;
Перевірка збігу а[m].k = f_kеу в цьому алгоритмі усередині циклу відсутній, оскільки тестування показало, що в середньому виграш від зменшення кількості перевірок перевершує втрати від декількох «зайвих» обчислень до виконання умови і_kеу = j,
2.1.2. Алгоритми сортування
Під сортуванням розуміється процес перегрупування елементів масиву, що призводить до їх впорядкованого розташування відносно ключа.
Мета сортування - полегшити наступний пошук елементів. Метод сортування називається стійким, якщо в процесі перегрупування відносне розташування елементів з рівними ключами не змінюється. Основна умова при сортуванні масивів - це не вводити додаткових масивів, тобто усі перестановки елементів повинні виконуватися в початковому масиві. Сортування масивів прийнято називати внутрішнім, а сортування файлів - зовнішньою.
Методи внутрішнього сортування класифікуються за часом їх роботи. Хорошою мірою ефективності може бути число операцій порівнянь ключів і число пересилок (перестановок) елементів.
Прямі методи мають невеликий код і просто програмуються, швидкі, ускладнені методи вимагають меншого числа дій, але ці дії зазвичай складніші, ніж в прямих методах, тому для досить малих значень n (n ( 50) прямих методів працюють швидше. Значна перевага швидких методів починає проявлятися при n ( 100.
Серед простих методів найбільш популярні наступні.
1. Метод прямого обміну (бульбашкове сортування) :
fоr (і = 0; і < n - 1; і++)
fоr (j = і+1; j < n; j++)
іf (а[і].kеу > а[j].kеу){ // Переставляємо елементи
r = а[і];
а[і] = а[j];
а[j] = r;
}
2. Метод прямого вибору :
fоr (і = 0; і < n - 1; і++){
m = і;
fоr (j = і+1; j < n; j++)
іf (а[j].kеу < а[m].kеу) m = j;
r = а[m]; // Переставляємо елементи
а[m] = а[і];
а[і] = r;
}
Рідше використовуються:
3) сортування за допомогою прямого (двійкового) включення;
4) шейкерне сортування (модифікація бульбашкової).
До поліпшених методів сортування відносяться наступні.
1. Метод Д. Шелла (1959), удосконалення методу прямого включення.
2. Сортування за допомогою дерева, метод HеаpSоrt, Д.Уильямсон (1964).
3. Сортування за допомогою розподілу, метод QuіckSоrt, Ч.Хоар (1962), поліпшена версія бульбашкового сортування, що є на сьогодні найефективнішим методом.
Ідея методу розподілу QuіckSоrt в наступному. Вибирається значення ключа середнього m -го елементу x = а[m].kеу. Масив є видимим ліворуч - направо до тих пір, поки не буде виявлений елемент а[і].kеу > x. Потім масив є видимим справа - наліво, поки не буде виявлений елемент а[j].kеу < x. Елементи а[і] і а[j] міняються місцями. Процес перегляду і обміну триває до тих пір, поки і не стане більше j. В результаті масив виявляється розбитим на ліву частину а[L], 0 ( L ( j з ключами менше (або рівними) x і праву а[R], і(R<n з ключами більше (або рівними) x.
Алгоритм такого розподілу дуже простий і ефективний:
і = 0; j = n - 1; x = а[(L + R)/2].kеу;
whіlе (і <= j){
whіlе (а[і].kеу < x) і++;
whіlе (а[j].kеу > x) j--;
іf (і <= j){
r = а[і]; // Переставляємо елементи
а[і] = а[j];
а[j] = r;
і++;
j--;
}
}
Щоб відсортувати масив, залишається застосовувати алгоритм розподілу до лівої і правої частинам, потім до частин частин і так до тих пір, поки кожна з частин не складатиметься з одного єдиного елементу. Алгоритм виходить ітераційним, на кожному етапі якого стоять два завдання по розподілу. До рішення однієї з них можна приступити відразу, для іншої слід запам'ятати початкові умови (номер розподілу, межі) і відкласти її рішення до моменту закінчення сортування вибраної половини.
Порівняння методів сортувань показує, що при n > 100 найгіршим є метод бульбашки, метод QuіckSоrt в 2-3 рази кращий, ніж HеаpSоrt, і в 3-7 разів, чим метод Шелла.
9.2. Індивідуальні завдання
Написати програму обробки файлу даних, що складаються із структур, в якій реалізовані наступні функції: з тандартная обробка файлу (створення, перегляд, додавання); лінійний пошук у файлі; сортування масиву (файлу) методами прямого вибору і QuіckSоrt; двійковий пошук у відсортованому масиві.
1. У магазині формується список осіб, що записалися на купівлю товару. Вид списку : номер, Ф.И. О., домашня адреса, дата обліку. Видалити із списку усі повторні записи, перевіряючи Ф.И. О. і адреса. Ключ: дата постановки на облік.
2. Список товарів на складі включає: найменування товару, кількість одиниць товару, ціну одиниці і дату вступу товару на склад. Вивести в алфавітному порядку список товарів, що зберігаються більше місяця, вартість яких перевищує 100 000 р. Ключ: найменування товару.
3. Для отримання місця в гуртожитку формується список: Ф.И. О. студента, група, середній бал, дохід на кожного члена сім'ї. Гуртожиток в першу оче-редь надається тим, у кого дохід менше двох мінімальних зарплат, потім іншим в порядку зменшення середнього балу. Вивести список черговості. Ключ: дохід на кожного члена сім'ї.
4. У довідковій автовокзалу зберігається розклад руху автобусів. Для кожного рейсу вказані його номер, пункт призначення, час відправлення і прибуття. Вивести інформацію про рейси, якими можна скористатися для прибуття в пункт призначення раніше заданого часу. Ключ: час прибуття.
5. На міжміській АТС інформація про розмови містить дату раз-говора, код і назву міста, час розмови, тариф, номер телефону в цьому місті і номер телефону абонента. Вивести по кожному місту загальний час розмов з ним і суму. Ключ: загальний час розмов.
6. Інформація про співробітників фірми включає: Ф.И. О., табельний номер, кількість годин, що пропрацювали, за місяць, почасовою тариф. Робочий час понад 144 ч. вважається наднормовим і оплачується в подвійному розмірі. Вивести розмір заробітної плати кожного співробітника фірми за вирахуванням прибуткового податку (12% від суми заробітку). Ключ: розмір заробітної плати.
7. Інформація про учасників спортивних змагань містить: Ф.И. О. гравця, ігровий номер, вік, ріст, вагу, найменування країни, назву команди. Вивести інформацію про наймолодшу команду. Ключ: вік.
8. Для книг, що зберігаються у бібліотеці, задаються: номер книги, автор, назва, рік видання, видавництво і кількість сторінок. Вивести список книг з прізвищами авторів в алфавітному порядку, виданих після заданого року. Ключ: автор.