Федеральне агентство зв'язку
Сибірський державний університет телекомунікацій та інформатики
Кафедра прикладної математики і кібернетики
Курсова робота
Інформаційні технології
ВАРІАНТ 2
Виконав: Голубєв Антон
Перевірив: Ракитский Антон Андрійович
Новосибірськ 2014
Зміст
1.Заданіе до курсової
.Теорія до курсової роботи) Сортування методом прямого злиття) одинзв'язного списки
.Код програми
4. Робота функцій
. Висновок
1. Завдання до курсової
Необхідно створити файл зі списком студентів в наступному форматі:
У першому рядку файлу знаходиться число N - кількість рядків з описами студентів (кожний рядок відповідає опису одного студента). У створюваному файлі повинно бути не менше 10 студентів, тобто.
У наступних Nстроках представлена ??інформація про студентів. Кожен рядок містить: прізвище студента, ім'я, номер групи, дата народження у форматі день/місяць/рік (dd/mm/yyyy), оцінка за перший контрольний термін і оцінка за другий контрольний термін. Всі дані відокремлені один від одного рівно одним пропуском, не містять прогалин всередині і слідують строго в описаному порядку.
Необхідно написати програму для роботи з представленої вище «базою даних». Програма повинна мати меню, в якому будуть наступні пункти:
· Додати студента
· Видалити студента
· Редагувати інформацію про студента
· Зберегти інформацію про студентів у файл
· Завантажити інформацію про студентів з файлу
· Впорядкувати студентів і вивести список на екран
· Знайти студента
· Вийти з програми
Вся інформація про студентів повинна зберігатися у вигляді динамічного списку. Для упорядкування студентів іспользоватьбиструю сортування (QuickSort).
Сортувати необхідно наступним чином: студенти повинні бути впорядковані за номером групи, студенти однієї групи повинні бути відсортовані за прізвищем, а в разі однакових прізвищ - по імені.
Для пошуку студента необхідно вводити прізвище, ім'я та номер групи. Щоб спростити виконання роботи, будемо вважати, що не існує двох таких студентів, у яких всі три параметра збігаються.
база дані інформація
2. Теорія до курсової роботи
A) Метод бистройсортіровкі
Метод Хоара або метод швидкого сортування полягає в наступному. Візьмемо довільний елемент масиву x. Переглядаючи масив ліворуч, знайдемо елемент ai? x. Переглядаючи масив праворуч, знайдемо aj? x. Поміняємо місцями aiі aj. Будемо продовжувати процес перегляду та обміну, до тих пір поки i не стане більше j. Тоді масив можна розбити на дві частини: в лівій частині всі елементи не більше x, в правій частині масиву не менше x. Потім до кожної частини масиву застосовуємо той же алгоритм.
Трудомісткість методу істотно залежить від вибору елемента x, який впливає на поділ масиву. Максимальні значення M і Cдля методу швидкого сортування досягаються при сортуванні впорядкованих масивів (в прямому і зворотному порядку). Тоді в цьому випадку в одній частині залишається тільки один елемент (мінімальний або максимальний), а в другій - всі інші елементи. Вирази для M і С мають такий вигляд
M=3 (n - 1), C=(n2 + 5n + 4)/2
Таким чином, у разі впорядкованих масивів трудомісткість сортування має квадратичний порядок.
Елемент am називається медіаною для елементів aL ... aR, якщо кількість елементів менших am дорівнює кількості елементів великих amс точністю до одного елемента (якщо кількість елементів нечетно).
Мінімальна трудомісткість методу Хоара досягається у випадку, коли на кожному кроці алгоритму ведучим елемента вибирається медіана масиву. Кількість порівнянь в цьому випадку C=(n + 1) log (n + 1) - (n + 1). Кількість пересилань залежить від положення елементів, але не може бути більше одного обміну на два порівняння. Тому кількість пересилань - величина того ж порядку, що і число порівнянь. Асимптотичні оцінки для середніх значень M і Cімеют наступний вигляд.
С=О (nlogn), М=О (nlogn) при n?...
