ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
Кафедра Інформатики
Пояснювальна записка
Курсова робота
З КУРСУ
"Об'єктно-орієнтоване програмування на Visual C + + "на тему: "Методи сортування. Їх порівняльний аналіз"
Виконав: Перевірив:
Ст. гр. СУА-03-1 старший викладач
Котляров М.М. Брітік В.І.
Харків 2004
ЗМІСТ
ВСТУП
1 Рішення інтелектуальної завдання на комп'ютері
2 ПОБУДОВА АЛГОРИТМУ КОДУВАННЯ НА VISUALC + +
2.1 Алгоритм рішення задачі
2.2 Опис програми "Sort"
3 Інструкції користувача
ВИСНОВОК
Додаток
ЛІТЕРАТУРА І ДЖЕРЕЛА
РЕФЕРАТ
Записка пояснювальна до курсової роботи містить: 24 стор
Предмет дослідження - сучасні методи розробки програм таких, як об'єктно-орієнтоване програмування та візуальне проектування, а також структурний і модульне програмування.Мета курсової роботи - систематизація, поглиблення і активне застосування знань з системного програмування, закріплення знань, отриманих у лекційному курсі, а також на практичних та лабораторних заняттях.
Метод дослідження - вивчення літератури, складання та налагодження програм на комп'ютері.
Програма типу "Sort" може використовуватися, як програма, призначена для сортування елементів масиву.
Розроблено проект "Sort" повністю відповідний умовою завдання і має досить зручний інтерфейс.
КЛЮЧОВІ СЛОВА: SORT, Visual C + +, функція, проект, повідомлення, програма.
ВСТУП
В даний час обчислювальна техніка проникла практично в усі сфери людської діяльності. За допомогою ЕОМ можна вирішувати найрізноманітніші завдання. Але для того, щоб вирішити поставлену задачу, необхідно вказати послідовність дій, виконання яких приведе до необхідного результату, - скласти програму. Для зручності роботи з ЕОМ ця операція проводиться за допомогою мов програмування (високого або низького рівня).
Один із широко використовуваних мов програмування - це Visual C + +, який можна використовувати для написання програм, що працюють в операційному середовищі Windows. На даний час однієї з найпоширеніших його версій є Microsoft Visual C + +, і середовище програмування Microsoft Developer Studio 6.0.
Середовище програмування Microsoft Developer Studio 6.0 дозволяє створювати тексти програм, компілювати їх, знаходити помилки і оперативно їх виправляти; компонувати програми з окремих частин, включаючи стандартні модулі, налагоджувати і виконувати налагоджену програму.
Використовуючи перераховані можливості, можна створювати різні прикладні програми, наприклад, такі, як програма, написана при виконанні даної курсової роботи.
1 Рішення інтелектуальної завдання на комп'ютері
У даному курсовому проекті необхідно розробити програму типу "Sort", за допомогою якої можна проводити сортування масиву різними методами. Зокрема в даному курсовому проекті використовуються такі методи: "Обмінна сортування з розділенням (quicksort)", "Метод Шелла" та "Метод прямого обміну (Бульбашки)". Програма повинна мати зручний інтерфейс.
2 ПОБУДОВА АЛГОРИТМУ КОДУВАННЯ НА VISUAL C + +
Середовище Visual C + + - це складний механізм, що забезпечує високоефективну роботу програміста. Створення прикладних програм, або програм виконується в інтегрованому середовищі розробки IDE (Integrated Development Environment). IDE служить для організації взаємодії з програмістом і включає ряд вікон, що містять різні керуючі елементи. За допомогою засобів інтегрованої середовища розробник може проектувати інтерфейсну частину програми, а також писати програмний код і пов'язувати його з керуючими елементами. При цьому вся робота по створенню програми, включаючи налагодження, відбувається в IDE.
Інтегроване середовище розробки Visual C + + являє собою багатовіконну систему. Вид інтегрованого середовища розробки (інтерфейс) може відрізнятися в залежності від настройок. Крім стандартних вікон, на екрані можуть бути присутні і інші вікна, що відображаються при виклику відповідних коштів, наприклад, Image Editor (Редактор зображень). Вікна Visual C + + (але не головне) можна переміщати, забирати з екрана, а також змінювати їх розміри.
Незважаючи на наявність багатьох вікон, Visual C + + є одне-документної середовищем, тобто дозволяє одночасно працювати тільки з одним додатком (проектом програми). Назва проекту програми виводиться в рядку заголовка головного вікна у верхній частині екрана.
Якщо згорнути головне вікно, то відбувається мінімізація всього інтерфейсу Visual C + + і, відповідно, всіх відкритих вікон. При закритті головного вікна робота з Visual C + + припиняється.
Самою останньою і найбільш вдосконаленою версією став Microsoft Visual C + + 6.0. Visual C + + 6.0, увібравши в себе все найкраще від попередніх версій, надає ряд нових можливостей. Так, наприклад, став більш зручним та сучасним інтерфейс середовища програмування, створювані Visual C + + програми враховують архітектуру сучасних процесорів, суттєво розширені можливості отладчика.
Visual C + + 6.0 може працювати в середовищі операційних систем від Windows 95 до Windows 2000. Особливих вимог до комп'ютера система не пред'являє, за винятком того, що процесор має бути типу Pentium, оперативної пам'яті - не менше 32 Мбайт і достатня кількість вільної дискової пам'яті (близько 200 Мбайт).
2.1 Алгоритм рішення задачі
Основними операціями, виконуваними над масивами, є впорядкування (сортування) записів і пошук у масиві записи по заданій умові (по ключу). Сортування є операцією розстановки записів масиву в певному порядку у відповідності з деяким критерієм упорядкування. Сортування здійснюється у відповідності зі значенням ключів всіх записів (напр., упорядкування прізвищ за алфавітом або чисел за збільшенням). Існує досить багато методів сортування, принципово відрізняються один від одного. Якщо масив цілком поміщається в оперативній пам'яті ЕОМ, то його впорядкування називають внутрішнім. Якщо для зберігання впорядковуємо даних використовуються зовнішній пристрій, то таке впорядкування називають зовнішнім. Критеріями оцінки методів сортування є:
С - кількість операцій порівняння пар ключів,
Р - число перестановок елементів,
S - резерв пам'яті.
Середня кількість операцій порівняння залежить від методу сортування і при раціональному виборі методу досягає деякого мінімуму, що залежить від n - розміру масиву (розмір масиву - кількість містяться в ньому записів). Методи внутрішнього сортування можна розділити на дві групи:
- Методи, які не потребують резерву пам'яті;
- Методи, що вимагають резерву пам'яті.
До першої групи належать такі методи, як метод вибірки, "бульбашки", вставки, Шелла. До другої групи належать метод квадратичної вибірки, метод злиття та інші. Прості методи сортування (вибором, обміном, вставкою) вимагають приблизно n ** 2 порівнянь. Більш складні алгоритми зазвичай забезпечують отримання результату за n * log2 (n) порівнянь в середньому: сортування методом Шелла, злиттям, "швидке сортування". Однак оптимальною в будь-якому випадку сортування не існує, оскільки їх ефективність істотно залежить від типу ключів у масиві та їх попередньої впорядкованості.
Розглянемо алгоритми найбільш поширених методів внутрішнього сортування (впорядкування виконується за зростанням значень ключа).
· Метод "Бульбашки".
При використанні цього способу потрібно щонайбільше (n-1) проходів. Протягом першого проходу масиву порівнюються ключі К1 і К2 першої та другої записів, і, якщо порядок між ними порушений, то записи R1 і R2 міняються місцями. Потім цей процес повторюється для записів R2 і R3, R3 і R4 і т.д. Даний метод змушує рухатися, або "спливати", записи з малими ключами. Після першого проходу запис з найбільшим ключем буде перебувати на n - й позиції масиву. При кожному наступному проході запису зі наступному найбільшим ключем будуть розташовуватися в позиціях n-1, n-2, ... , 2 відповідно, в результаті чого буде сформована відсортована таблиця. Після кожного проходу через масив може бути зроблена перевірка, чи були здійснені перестановки протягом даного проходу. Якщо перестановок не було, то це означає, що масив вже відсортований та подальших проходів не потрібно. Крім того, можна запам'ятовувати індекс останньої перестановки. Це дозволить зменшити на наступному кроці переглядається масив.
Характеристики сортування методом "бульбашки" у гіршому випадку становлять n (n-1) / 2 порівнянь і n (n-1) / 2 перестановок (гіршим вважається випадок, коли елементи найбільш віддалені від своїх кінцевих позицій). Середнє число порівнянь і перестановок має порядок n ** 2. Сортування бульбашковим методом використовує метод обмінної сортування. Вона заснована на виконанні в циклі операцій порівняння і за необхідності обміну сусідніх елементів. Її назва походить з-за подібності процесу руху бульбашок в резервуарі з водою коли кожен пляшечку знаходить свій власний рівень.
Сортування бульбашковим методом можна в деякій мірі поліпшити і тим самим трохи поліпшити її тимчасові характеристики. Можна, наприклад, помітити, що сортування бульбашковим методом володіє однією особливістю: розташований не на своєму місці в кінці масиву елемент (наприклад, елемент "а" в масиві "dcab") досягає свого місця за один прохід, а елемент, розташований на початку масиву (наприклад, елемент "d"), дуже поволі досягає свого місця. Необов'язково всі перегляди робити в одному напрямку. Замість цього кожен подальший перегляд можна робити в протилежному напрямку. У цьому випадку сильно віддалені від свого місця елементи будуть швидко переміщатися в відповідне місце. Хоча ця сортування є поліпшенням бульбашковим методом, її не можна рекомендувати для використання, оскільки час виконання як і раніше залежить квадратично від числа елементів. Число порівнянь не змінюється, а число обмінів зменшується лише на незначну величину.
· Метод Шелла.
Загальний метод, який використовує сортування вставкою, застосовує принцип зменшення відстані між порівнюваними елементами. Спочатку сортуються всі елементи, які зміщені один від одного на три позиції. Потім сортуються всі елементи, які зміщені на дві позиції. І, нарешті, впорядковуються всі сусідні елементи.
При поверхневому погляді на алгоритм не можна сказати, що він дає хороший результат і навіть те, що в результаті вийде відсортований масив. Проте, він дає і те й інше. Ефективність цього алгоритму пояснюється тим, що при кожному проході використовується відносно невелике число елементів або елементи масиву вже знаходяться у відносному порядку, а впорядкованість збільшується при кожному новому перегляді даних.
Відстані між порівнюваними елементами можуть змінюватися по-різному. Обов'язковим є лише те, що останній крок повинен дорівнювати одиниці. Наприклад, хороші результати дає послідовність кроків 9, 5, 3, 2, 1, яка використана в даній курсовій роботі. Слід уникати послідовностей ступеня двійки, які, як показують складні математичні викладки, знижують ефективність алгоритму сортування. / Однак, при використанні таких послідовностей кроків між порівнюваними елементами ця сортування буде як і раніше працювати правильно. Злегка змінені версії сортування Шелла використовують спеціальні керуючі елементи, які не є насправді частиною тієї інформації, яка повинна сортуватися. Керуючі елементи мають граничні для масиву даних значення, тобто найменше та найбільше значення. У цьому випадку не обов'язково виконувати перевірку на граничні значення. Однак, застосування таких керуючих елементів вимагає спеціальних знань про ту інформацію, яка сортується, і це знижує універсальність процедури сортування. Аналіз сортування Шелл вимагає розв'язання деяких складних математичних завдань. Час виконання сортування Шелла пропорційно n ** 1.2. Ця залежність значно краще квадратичної залежності, якій підпорядковуються розглянуті раніше алгоритми сортування. Однак, перш ніж ви вирішите використовувати сортування Шелла, слід мати на увазі, що швидке сортування дає навіть ще кращі результати.
У розглянутих алгоритмах сортування запис переміщається щоразу лише на одну позицію. При цьому середній час роботи буде в кращому випадку пропорційно n. Методом, істотно перевершує прості вставки, при якому записи переміщуються великими стрибками, є метод Шелла (сортування з убуваючим кроком). Метод полягає в тому, що впорядкований масив поділяється на групи елементів, кожна з яких упорядковується методом вставки. У процесі впорядкування розміри таких груп збільшуються до тих пір, поки всі елементи масиву не увійдуть у впорядковану групу. Вибір черговий впорядковуємо групи і її розташування всередині масиву виробляються так, щоб можна було використовувати попередню впорядкованість. Групою масиву називають послідовність елементів, номери яких утворюють арифметичну прогресію з різницею h (h називають кроком групи). На початку процесу впорядкування вибирається перший крок групи h1, який залежить від розміру таблиці. Шелл запропонував брати
h1 = [n / 2], а hi = h ((i-1) / 2).
У більш пізніх роботах Хиббард показав, що для прискорення процесу доцільно визначити крок h1 за формулою:
h1 = 2 ** k +1, де 2 ** k <n <= 2 ** (k +1).
Після вибору h1 методом вставки упорядковуються групи, що містять елементи з номерами позицій
i, i + h1, i +2 * h1, ..., i + mi * h1.
При цьому i = 1,2 ,..., h1; m [i] - найбільше ціле, яке задовольняє нерівності i + m [i] * hi <= n.
Потім вибирається крок h2 <h1 і впорядковуються групи, що містять елементи з номерами позицій i, i + h2, ..., i + m [i] * h2. Ця процедура з все зменшуються кроками продовжується до тих пір, поки черговий крок h [l] стане рівним одиниці (h1> h2 >...> hl). Цей останній етап являє собою впорядкування всього масиву методом вставки. Але так як вихідний масив упорядковуються окремими групами з послідовним об'єднанням цих груп, то загальна кількість порівнянь значно менше, ніж n / 4, необхідний при методі вставки. Число операцій порівняння пропорційно n * (log2 (n)) ** 2.
· Обмінна сортування з розділенням (Quicksort).
Даний метод є одним з кращих методів внутрішнього сортування і вельми ефективний для великих масивів. Метою кожного кроку у цьому методі є приміщення черговий розглянутої запису на кінцеву позицію всередині масиву. Якщо діяти таким способом, то всі записи, що передують даній, будуть мати менший ключ, в той час як всі наступні - більший. При використанні такого методу масив завжди ділиться на два подмассивов. Рівнів процес може бути застосований до кожного з цих подмассивов і повторюватися до тих пір, поки всі записи не будуть встановлені на їх кінцеві позиції. Використовуються два індекси i і j з початковими значеннями кордонів масиву. Порівнюються ключі K [i] і K [j], і якщо перестановка не потрібно, то j зменшується на 1, і процес повторюється. У тому випадку, коли K [i]> = K [j], записи R [i] і R [j] міняються місцями. Потім цей процес повторюється з i, збільшеним на 1, і фіксованим j до тих пір, поки не виникає інша перестановка. У цей момент j знову буде зменшено на 1, а i залишиться фіксованим, і т.д. Процес виконується до тих пір, поки i <j.
Кожного разу масив розбивається на два подмассивов, один з яких обробляється, у той час як кордони другий запам'ятовуються з тим, щоб він був оброблений пізніше. У цих цілях може бути використаний стек, що представляє собою матрицю з двох стовпців. У першому стовпці зберігаються нижні межі поділюваних подмассивов, у другому - верхні межі. Кожного разу один з отриманих в результаті поділу подмассивов піддається подальшому поділу, а кордони іншого поміщаються у вільний рядок стека (зазвичай в стек поміщаються кордону більшого по довжині масиву, оскільки це зменшує необхідний розмір стека). Як тільки завершується процес поділу поточного подмассивов, тобто її довжина стане менше трьох, для поділу береться подмассів, межі якого були занесені в стек останніми. Рядок стека, в якій зберігалися ці межі, звільняється. Процес упорядкування завершується, коли стек повністю звільняється.
Поділ слід застосовувати для подмассивов, довжина яких більше 9, а короткі подмассивов впорядковувати методом вставки.
Стек займає мало місця. Наприклад, стек з 20 рядків дозволяє впорядкувати масив, що містить до 10 ** 7 результатів. Крім того, в сучасних мовах програмування при роботі рекурсивних програм занесення і витяг з стека виконується автоматично, тому рекомендується використовувати саме цей механізм. Середнє число порівнянь для даного алгоритму становить n * log (n) де n - кількість записів у сортованому масиві, m - розмір подмассивов, сортируемое методом вставки.
Найгіршою ситуацією при використанні розглянутого алгоритму є випадок, коли масив вже відсортований. При цьому число порівнянь порядку n, тобто алгоритм не краще сортування вибіркою.
2.2 Опис програми "Sort"
Даний проект створювався за допомогою AppWizard - генератором коду, що створює робочу заготовку Windows-програми з тими компонентами, іменами класів і вихідними файлами, що були вказані через діалогові вікна. Зокрема: у закладці Project вибираємо - MFC AppWizard (exe). Потім потрібно пройти серію екранів AppWizard:
Step 1: вибираємо "Single document"
Step 2: залишаємо без зміни
Step 3: без зміни
Step 4: залишаємо тільки прапорці "3D controls", "Docking ToolBar"
Step 5: встановлюємо "As a statically linked library"
Step 6: відображає інформацію про створені класах
Після цього AppWizard згенерує код для підтримки функціональних можливостей програми на базі бібліотеки MFC, тобто створить каркас додатка. Розглянемо деякі елементи програми, створені на даному етапі:
Клас CSortApp. Об'єкт класу CSortApp представляє програму. У програмі визначається єдиний глобальний об'єкт класу CSortApp - theApp. Базовий клас CWinApp визначає основні характеристики об'єкта theApp.
Клас CSortView. Об'єкт класу CSortView представляє основне вікно програми. Коли конструктор викликає функцію-член Create базового класу CFrameWnd, Windows створює дійсну віконну структуру, а каркас додатку пов'язує її з C + +-об'єктом. Функції ShowWindow і UpdateWindow, що є також функціями-членами базового класу, викликаються для виведення вікна на екран.
При запуску проекту операційна система викликає у програмі функцію WinMain, а та шукає глобально сконструйований об'єкт класу, похідного від CWinApp. У будь-якому додатку, в тому числі і в "Sort", обов'язково повинна бути присутня ця функція, на яку покладається ряд специфічних завдань. І найважливіша - створення основного вікна програми, з яким має бути пов'язаний код, який здатний обробляти повідомлення, що передаються операційною системою цьому вікну. У нашому випадку при програмуванні на Microsoft Visual C + + 6.0, з бібліотекою класів Microsoft Foundation Class (MFC) Library 6.0, ця функція прихована усередині каркаса програми і немає необхідності в її написанні, але необхідно розуміти, що саме за допомогою неї здійснюється зв'язок між операційною системою і програмою.
Бібліотека MFC прямо підтримує близько 140 функцій, які обробляють Windows-повідомлення. Крім того, можна визначати свої власні повідомлення, пов'язані з обробниками команд меню, елементів управління і т.д. У програмі "Sort" використовується понад 40 функцій, методів і повідомлень Windows. Нижче вони перераховані в порядку їх появи в програмі з коротким описом:
Format - перетворить типи змінних;
InvalidateRect і Invalidate - оновлюють робочу область і генерують повідомлення WM_PAINT;
DestroyWindow - руйнує вікно;
PostQuitMessage - посилає вікну повідомлення WM_DESTROY;
ShowWindow - відображає або приховує вікно;
UpdateWindow - змушує вікно перемалювати свій вміст;
TextOut - виведення тексту на екран;
Після виклику функції UpdateWindow, вікно остаточно виведено на екран. Тепер програма повинна підготувати себе для отримання інформації від користувача через клавіатуру і мишу. Windows підтримує "черга повідомлень" (message queue) для кожної програми, що працює в даний момент у системі Windows. Коли відбувається введення інформації, Windows перетворює її в "повідомлення", яке міститься в чергу повідомлень програми. Кожне одержуване вікном повідомлення ідентифікується номером, який міститься в параметрі message віконної процедури. У заголовних файлах Windows визначені ідентифікатори, що починаються із префікса WM ("window message") для кожного типу повідомлень. Нижче приведені всі повідомлення використовуються в курсовому проекті:
Повідомлення WM_CREATE - це перше повідомлення, яке Windows посилає об'єкту View. Воно передається, коли каркас додатку викликає віконну функцію Create, тобто в той момент, коли створення вікна ще не закінчено і його не видно на екрані. Отже, обробник OnCreate поки не може звертатися до Windows-функцій, доступним тільки після відображення вікна. Такі функції можна викликати з заміщений функції OnInitialUpdate.
Функція-член OnDraw (). Це віртуальна функція-член класу CView; каркас додатків викликає її всякий раз, коли приходить повідомлення про те, що потрібно перемалювати вікно відображення. А така необхідність виникає при масштабуванні вікна або при появі раніше прихованої його частини, або при зміні програмою даних, пов'язаних з цим вікном. У перших двох випадках каркас додатку викликає OnDraw, але якщо якась функція в програмі змінює дані, вона повинна повідомити про це Windows, викликавши наслідувану функцію-член Invalidate (або InvalidateRect) для даної області відображення. Виклик Invalidate призводить згодом до автоматичного викликом OnDraw.
Windows не дозволяє прямий доступ до V обладнання, звернення до нього проходить через так званий контекст пристрою (device context), співставлений з конкретним вікном. У бібліотеці MFC контекст пристрою - це С + +-об'єкт класу CDC, рухаючись функції OnDraw (за вказівником) як параметр. Отримавши покажчик на контекст пристрою, можна викликати безліч функцій-членів CDC, які й виконують всю роботу з малювання.
У даному курсовому проекті при виклику функції OnDraw відбувається виведення вихідного і відсортованого масиву на екран, а також інформації про кількість перестановок вироблених під час сортування.
Коли користувач вибирає пункт меню, Windows посилає програмі повідомлення WM_COMMAND, що містить ідентифікатор цього пункту меню в молодшому слові параметра повідомлення. Нижче розглянуті ідентифікатори, відповідне пунктам меню програми:
ID_QUIK - це ідентифікатор пункту "Обмінна сортування з розділенням (quicksort)" в меню. Вибір цього пункту призводить до сортування масиву даним методом.
ID_SHELL - це ідентифікатор пункту "Метод Шелла" в меню. Вибір цього пункту призводить до сортування масиву методом Шелла.
ID_PUZIROK - цьому ідентифікатору в меню відповідає пункт "Метод прямого обміну (Бульбашки)". Вибір цього пункту призводить до сортування масиву методом "Бульбашки".
Вибір пункту меню "Про програму ...", якому відповідає ідентифікатор ID_APP_ABOUT, виведе модальне вікно діалогу, в якому міститься коротка інформація про розробника та програмі.
ID_APP_EXIT - цьому ідентифікатору в меню відповідає пункт "Вихід". При виборі цього пункту відбувається виклик функції OnDestroy, що призводить до руйнування вікна і завершення роботи з програмою.
3 ІНСТРУКЦІЯ КОРИСТУВАЧА
Запуск програми здійснюється при відкритті файлу Sort.exe, який знаходиться на дискеті. При цьому на екрані з'явиться вікно, в лівій верхній частині якого буде видно напис "Методи сортування" - це ім'я програми. Нижче розташовується меню, за допомогою якого можна виконати різні дії з даним додатком. При натисканні на пункті меню "Файл", випаде, так зване, спливаюче меню, в якому знаходиться пункт "Вихід". При виборі цього пункту програма закривається.
Наступний пункт головного меню - це "Сортування", підменю якого містить пункти "Обмінна сортування з розділенням (quicksort)", "Метод Шелла" та "Метод прямого обміну (Бульбашки)". Вибір першого пункту дозволяє зробити сортування масиву методом "Обмінний сортування з поділом". Натискання на пункті меню "Метод Шелла" призводить до сортування масиву методом Шелла. І вибір останнього підпункту меню сортує масив методом "Бульбашки".
Останнім пунктом меню є "Допомога". Якщо вибрати цей пункт, то в підменю можна побачити пункт: "Про програму", який містить інформацію про розробника та про саму програму.
Під меню розташовується панель інструментів, яка дублює всі пункти основного меню. Ще нижче розташована клієнтська область, в якій відбувається весь вивід інформації.
Системні вимоги: Pentium 133, 16 MB RAM, Windows 95/98/2000 NT / XP.
ВИСНОВОК
У ході виконання даного курсового проекту були розроблена програма на мові високого рівня Visual C + +. А також вивчено можливості цієї мови.
Систематизовано і закріплені практичні навички використання ЕОМ, програмного забезпечення, існуючих засобів обслуговування системних програмістів, а також теоретичні знання з основних розділів курсу "Об'єктно-орієнтованого програмування". Основну увагу приділено вивченню сучасних методів захисту інформації, способів проектування додатків, об'єктно-орієнтованому та системного програмування.
При виконанні курсового проекту вироблено знайомство з реферативними журналами та іншими інформаційними джерелами по об'єктно-орієнтованого і системного програмування з метою аналізу стану розв'язуваної задачі.
Отримано практичні навички роботи в середовищі Visual C + +.
ДОДАТОК
# Include "stdafx.h"
# Include "Sort.h"
# Include "SortDoc.h"
# Include "SortView.h"
# Ifdef _DEBUG
# Define new DEBUG_NEW
# Undef THIS_FILE
static char THIS_FILE [] = __FILE__;
# Endif
/ / Оголошення глобальних змінних
int mas [20] = {30,5,17,8,1,14,12,3,77,2,45,89,33,21,6}, mas2 [20], kol = 15, count = 0 ;
CString str;
bool sort = false;
int metod = 0;
/ / 1 - quicksort
/ / 2 - shell
/ / 3 - бульбашки
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView
IMPLEMENT_DYNCREATE (CSortView, CView)
BEGIN_MESSAGE_MAP (CSortView, CView)
/ / {{AFX_MSG_MAP (CSortView)
ON_COMMAND (ID_QUICK, OnQuick)
ON_COMMAND (ID_PUZIROK, OnPuzirok)
ON_COMMAND (ID_SHELL, OnShell)
/ /}} AFX_MSG_MAP
END_MESSAGE_MAP ()
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView construction / destruction
CSortView:: CSortView ()
{
/ / TODO: add construction code here
}
CSortView:: ~ CSortView ()
{
}
BOOL CSortView:: PreCreateWindow (CREATESTRUCT & cs)
{
/ / TODO: Modify the Window class or styles here by modifying
/ / The CREATESTRUCT cs
return CView:: PreCreateWindow (cs);
}
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView drawing
/ / Функція виводу даних на екран
void CSortView:: OnDraw (CDC * pDC)
{
CSortDoc * pDoc = GetDocument ();
ASSERT_VALID (pDoc);
/ / TODO: add draw code for native data here
int i;
/ / Виводимо вихідний масив на екран
for (i = 0; i <kol; i + +)
{
str.Format ("% d,", mas [i ]);// формування рядка
pDC-> TextOut (10 + i * 20,10, str); / / вивід на екран
}
/ / Якщо був обраний який-небудь метод сортування
if (sort)
{
if (metod == 1) / / якщо обраний Quicksort
pDC-> TextOut (10,40, "Обмінна сортування з розділенням (quicksort )");// висновок рядка на екран
if (metod == 2) / / якщо обраний Shell
pDC-> TextOut (10,40, "Метод Шелла ");// висновок рядка на екран
if (metod == 3) / / якщо обраний Bubble
pDC-> TextOut (10,40, "Метод прямого обміну (Бульбашки )");// висновок рядка на екран
/ / Виводимо відсортований масив
for (i = 0; i <kol; i + +)
{
str.Format ("% d,", mas2 [i ]);// формування рядка
pDC-> TextOut (10 + i * 20,80, str); / / вивід рядка на екран
}
str.Format ("Кількість перестановок в нашому випадку:% d", count); / / формування рядка
pDC-> TextOut (10,110, str); / / вивід рядка на екран
if (metod == 3) / / якщо було обрано метод "Бульбашки"
{
str.Format ("Максимальна кількість перестановок для масиву з% d елементів методом 'Бульбашки':% d", kol, kol * (kol-1) / 2); / / формування рядка
pDC-> TextOut (10,140, str); / / вивід рядка на екран
}
}
}
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView diagnostics
# Ifdef _DEBUG
void CSortView:: AssertValid () const
{
CView:: AssertValid ();
}
void CSortView:: Dump (CDumpContext & dc) const
{
CView:: Dump (dc);
}
CSortDoc * CSortView:: GetDocument () / / non-debug version is inline
{
ASSERT (m_pDocument-> IsKindOf (RUNTIME_CLASS (CSortDoc)));
return (CSortDoc *) m_pDocument;
}
# Endif / / _DEBUG
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView message handlers
/ / При виборі сортування Quicksort
void CSortView:: OnQuick ()
{
/ / Оголошення локальних змінних
sort = true;
metod = 1;
int i;
count = 0;
for (i = 0; i <kol; i + +)
{
mas2 [i] = mas [i];
}
quicksort (0, kol-1); / / виклик функції quicksort
Invalidate (true); / / перемальовування вмісту вікна
}
/ / При виборі сортування Shell
void CSortView:: OnShell ()
{
/ / Оголошення локальних змінних
sort = true;
metod = 2;
int ii, t = 5, i, j, k, s, m, h [6], x;
count = 0;
for (ii = 0; ii <kol; ii + +)
{
mas2 [ii] = mas [ii];
}
h [1] = 9; h [2] = 5; h [3] = 3; h [4] = 2; h [5] = 1;
////////////////////////////////////////////
/ / АЛГОРИТМ
for (m = 1; m <= t; m + +)
{
k = h [m];
s =- k;
for (i = k +1; i <= kol; i + +)
{
x = mas2 [i];
j = ik;
while (x <mas2 [j] & & j <kol)
{
mas2 [j + k] = mas2 [j];
j = jk;
}
mas2 [j + k] = x;
count + +;
}
}
x = mas2 [0];
mas2 [0] = mas2 [1];
mas2 [1] = x;
////////////////////////////////////////////
Invalidate (true); / / перемальовування вмісту вікна
}
/ / При виборі сортування Bubble
void CSortView:: OnPuzirok ()
{
/ / Оголошення локальних змінних
int dop;
bool end;
count = 0;
sort = true;
metod = 3;
int i, j;
for (i = 0; i <kol; i + +)
{
mas2 [i] = mas [i];
}
////////////////////////////////////////////
/ / АЛГОРИТМ
for (i = 0; i <kol; i + +)
{
end = true;
for (j = i +1; j <kol; j + +)
{
if (mas2 [i]> mas2 [j])
{
dop = mas2 [i];
mas2 [i] = mas2 [j];
mas2 [j] = dop;
end = false;
count + +;
}
}
if (end == true) break;
}
/////////////////////////////////////////////
Invalidate (true); / / перемальовування вмісту вікна
}
/ / Функція швидкого пошуку
void CSortView:: quicksort (int l, int r)
{
int i, j;
i = l; j = r;
{
part (l, r, i, j);
if (i <r) quicksort (i, r); / / перехід до сортування лівій частині
if (j> l) quicksort (l, j); / / перехід до сортування правій частині
}
}
/ / Функція пошуку по частинах
void CSortView:: part (int l, int r, int & i, int & j)
{
int x, dop;
i = l;
j = r;
x = (l + r) / 2;
do
{
while (mas2 [i] <mas2 [x])
i + +;
while (mas2 [j]> mas2 [x])
j -;
if (i <= j)
{
dop = mas2 [i];
mas2 [i] = mas2 [j];
mas2 [j] = dop;
i + +; j -; count + +;
}
}
while (i <j);
}
Література
1. Петзольд Ч. Програмування під Windows 95. У двох книгах: BHV - Санкт - Петербург, 1997, silt.
2. Річард С. Лінкер, Том Арчер. Програмування для Windows 98. Біблія розробника. "Діалектика" - Москва, 1999.-864 с.: Іл .- Хрон. тит. англ. Уч.пос.
3. Джесс Ліберті. С + + за 21 день. "Вільямс" - Москва, 2000.-816 с.: Іл. - Парал.тіт. англ.
4. Девід Дж. Круглінскі. Основи С + +. "Російська редакція" - Москва, 1997 .- 696 с.: Іл.
5. Кейт Грегорі. Використання Visual C + +. "Вільямс" - Москва, 1999.-864 с.: Іл .. - Парал.тіт. англ., уч. сел.
7. Конспект лекцій.
Поділ слід застосовувати для подмассивов, довжина яких більше 9, а короткі подмассивов впорядковувати методом вставки.
Стек займає мало місця. Наприклад, стек з 20 рядків дозволяє впорядкувати масив, що містить до 10 ** 7 результатів. Крім того, в сучасних мовах програмування при роботі рекурсивних програм занесення і витяг з стека виконується автоматично, тому рекомендується використовувати саме цей механізм. Середнє число порівнянь для даного алгоритму становить n * log (n) де n - кількість записів у сортованому масиві, m - розмір подмассивов, сортируемое методом вставки.
Найгіршою ситуацією при використанні розглянутого алгоритму є випадок, коли масив вже відсортований. При цьому число порівнянь порядку n, тобто алгоритм не краще сортування вибіркою.
2.2 Опис програми "Sort"
Даний проект створювався за допомогою AppWizard - генератором коду, що створює робочу заготовку Windows-програми з тими компонентами, іменами класів і вихідними файлами, що були вказані через діалогові вікна. Зокрема: у закладці Project вибираємо - MFC AppWizard (exe). Потім потрібно пройти серію екранів AppWizard:
Step 1: вибираємо "Single document"
Step 2: залишаємо без зміни
Step 3: без зміни
Step 4: залишаємо тільки прапорці "3D controls", "Docking ToolBar"
Step 5: встановлюємо "As a statically linked library"
Step 6: відображає інформацію про створені класах
Після цього AppWizard згенерує код для підтримки функціональних можливостей програми на базі бібліотеки MFC, тобто створить каркас додатка. Розглянемо деякі елементи програми, створені на даному етапі:
Клас CSortApp. Об'єкт класу CSortApp представляє програму. У програмі визначається єдиний глобальний об'єкт класу CSortApp - theApp. Базовий клас CWinApp визначає основні характеристики об'єкта theApp.
Клас CSortView. Об'єкт класу CSortView представляє основне вікно програми. Коли конструктор викликає функцію-член Create базового класу CFrameWnd, Windows створює дійсну віконну структуру, а каркас додатку пов'язує її з C + +-об'єктом. Функції ShowWindow і UpdateWindow, що є також функціями-членами базового класу, викликаються для виведення вікна на екран.
При запуску проекту операційна система викликає у програмі функцію WinMain, а та шукає глобально сконструйований об'єкт класу, похідного від CWinApp. У будь-якому додатку, в тому числі і в "Sort", обов'язково повинна бути присутня ця функція, на яку покладається ряд специфічних завдань. І найважливіша - створення основного вікна програми, з яким має бути пов'язаний код, який здатний обробляти повідомлення, що передаються операційною системою цьому вікну. У нашому випадку при програмуванні на Microsoft Visual C + + 6.0, з бібліотекою класів Microsoft Foundation Class (MFC) Library 6.0, ця функція прихована усередині каркаса програми і немає необхідності в її написанні, але необхідно розуміти, що саме за допомогою неї здійснюється зв'язок між операційною системою і програмою.
Бібліотека MFC прямо підтримує близько 140 функцій, які обробляють Windows-повідомлення. Крім того, можна визначати свої власні повідомлення, пов'язані з обробниками команд меню, елементів управління і т.д. У програмі "Sort" використовується понад 40 функцій, методів і повідомлень Windows. Нижче вони перераховані в порядку їх появи в програмі з коротким описом:
Format - перетворить типи змінних;
InvalidateRect і Invalidate - оновлюють робочу область і генерують повідомлення WM_PAINT;
DestroyWindow - руйнує вікно;
PostQuitMessage - посилає вікну повідомлення WM_DESTROY;
ShowWindow - відображає або приховує вікно;
UpdateWindow - змушує вікно перемалювати свій вміст;
TextOut - виведення тексту на екран;
Після виклику функції UpdateWindow, вікно остаточно виведено на екран. Тепер програма повинна підготувати себе для отримання інформації від користувача через клавіатуру і мишу. Windows підтримує "черга повідомлень" (message queue) для кожної програми, що працює в даний момент у системі Windows. Коли відбувається введення інформації, Windows перетворює її в "повідомлення", яке міститься в чергу повідомлень програми. Кожне одержуване вікном повідомлення ідентифікується номером, який міститься в параметрі message віконної процедури. У заголовних файлах Windows визначені ідентифікатори, що починаються із префікса WM ("window message") для кожного типу повідомлень. Нижче приведені всі повідомлення використовуються в курсовому проекті:
Повідомлення WM_CREATE - це перше повідомлення, яке Windows посилає об'єкту View. Воно передається, коли каркас додатку викликає віконну функцію Create, тобто в той момент, коли створення вікна ще не закінчено і його не видно на екрані. Отже, обробник OnCreate поки не може звертатися до Windows-функцій, доступним тільки після відображення вікна. Такі функції можна викликати з заміщений функції OnInitialUpdate.
Функція-член OnDraw (). Це віртуальна функція-член класу CView; каркас додатків викликає її всякий раз, коли приходить повідомлення про те, що потрібно перемалювати вікно відображення. А така необхідність виникає при масштабуванні вікна або при появі раніше прихованої його частини, або при зміні програмою даних, пов'язаних з цим вікном. У перших двох випадках каркас додатку викликає OnDraw, але якщо якась функція в програмі змінює дані, вона повинна повідомити про це Windows, викликавши наслідувану функцію-член Invalidate (або InvalidateRect) для даної області відображення. Виклик Invalidate призводить згодом до автоматичного викликом OnDraw.
Windows не дозволяє прямий доступ до V обладнання, звернення до нього проходить через так званий контекст пристрою (device context), співставлений з конкретним вікном. У бібліотеці MFC контекст пристрою - це С + +-об'єкт класу CDC, рухаючись функції OnDraw (за вказівником) як параметр. Отримавши покажчик на контекст пристрою, можна викликати безліч функцій-членів CDC, які й виконують всю роботу з малювання.
У даному курсовому проекті при виклику функції OnDraw відбувається виведення вихідного і відсортованого масиву на екран, а також інформації про кількість перестановок вироблених під час сортування.
Коли користувач вибирає пункт меню, Windows посилає програмі повідомлення WM_COMMAND, що містить ідентифікатор цього пункту меню в молодшому слові параметра повідомлення. Нижче розглянуті ідентифікатори, відповідне пунктам меню програми:
ID_QUIK - це ідентифікатор пункту "Обмінна сортування з розділенням (quicksort)" в меню. Вибір цього пункту призводить до сортування масиву даним методом.
ID_SHELL - це ідентифікатор пункту "Метод Шелла" в меню. Вибір цього пункту призводить до сортування масиву методом Шелла.
ID_PUZIROK - цьому ідентифікатору в меню відповідає пункт "Метод прямого обміну (Бульбашки)". Вибір цього пункту призводить до сортування масиву методом "Бульбашки".
Вибір пункту меню "Про програму ...", якому відповідає ідентифікатор ID_APP_ABOUT, виведе модальне вікно діалогу, в якому міститься коротка інформація про розробника та програмі.
ID_APP_EXIT - цьому ідентифікатору в меню відповідає пункт "Вихід". При виборі цього пункту відбувається виклик функції OnDestroy, що призводить до руйнування вікна і завершення роботи з програмою.
3 ІНСТРУКЦІЯ КОРИСТУВАЧА
Запуск програми здійснюється при відкритті файлу Sort.exe, який знаходиться на дискеті. При цьому на екрані з'явиться вікно, в лівій верхній частині якого буде видно напис "Методи сортування" - це ім'я програми. Нижче розташовується меню, за допомогою якого можна виконати різні дії з даним додатком. При натисканні на пункті меню "Файл", випаде, так зване, спливаюче меню, в якому знаходиться пункт "Вихід". При виборі цього пункту програма закривається.
Наступний пункт головного меню - це "Сортування", підменю якого містить пункти "Обмінна сортування з розділенням (quicksort)", "Метод Шелла" та "Метод прямого обміну (Бульбашки)". Вибір першого пункту дозволяє зробити сортування масиву методом "Обмінний сортування з поділом". Натискання на пункті меню "Метод Шелла" призводить до сортування масиву методом Шелла. І вибір останнього підпункту меню сортує масив методом "Бульбашки".
Останнім пунктом меню є "Допомога". Якщо вибрати цей пункт, то в підменю можна побачити пункт: "Про програму", який містить інформацію про розробника та про саму програму.
Під меню розташовується панель інструментів, яка дублює всі пункти основного меню. Ще нижче розташована клієнтська область, в якій відбувається весь вивід інформації.
Системні вимоги: Pentium 133, 16 MB RAM, Windows 95/98/2000 NT / XP.
ВИСНОВОК
У ході виконання даного курсового проекту були розроблена програма на мові високого рівня Visual C + +. А також вивчено можливості цієї мови.
Систематизовано і закріплені практичні навички використання ЕОМ, програмного забезпечення, існуючих засобів обслуговування системних програмістів, а також теоретичні знання з основних розділів курсу "Об'єктно-орієнтованого програмування". Основну увагу приділено вивченню сучасних методів захисту інформації, способів проектування додатків, об'єктно-орієнтованому та системного програмування.
При виконанні курсового проекту вироблено знайомство з реферативними журналами та іншими інформаційними джерелами по об'єктно-орієнтованого і системного програмування з метою аналізу стану розв'язуваної задачі.
Отримано практичні навички роботи в середовищі Visual C + +.
ДОДАТОК
# Include "stdafx.h"
# Include "Sort.h"
# Include "SortDoc.h"
# Include "SortView.h"
# Ifdef _DEBUG
# Define new DEBUG_NEW
# Undef THIS_FILE
static char THIS_FILE [] = __FILE__;
# Endif
/ / Оголошення глобальних змінних
int mas [20] = {30,5,17,8,1,14,12,3,77,2,45,89,33,21,6}, mas2 [20], kol = 15, count = 0 ;
CString str;
bool sort = false;
int metod = 0;
/ / 1 - quicksort
/ / 2 - shell
/ / 3 - бульбашки
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView
IMPLEMENT_DYNCREATE (CSortView, CView)
BEGIN_MESSAGE_MAP (CSortView, CView)
/ / {{AFX_MSG_MAP (CSortView)
ON_COMMAND (ID_QUICK, OnQuick)
ON_COMMAND (ID_PUZIROK, OnPuzirok)
ON_COMMAND (ID_SHELL, OnShell)
/ /}} AFX_MSG_MAP
END_MESSAGE_MAP ()
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView construction / destruction
CSortView:: CSortView ()
{
/ / TODO: add construction code here
}
CSortView:: ~ CSortView ()
{
}
BOOL CSortView:: PreCreateWindow (CREATESTRUCT & cs)
{
/ / TODO: Modify the Window class or styles here by modifying
/ / The CREATESTRUCT cs
return CView:: PreCreateWindow (cs);
}
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView drawing
/ / Функція виводу даних на екран
void CSortView:: OnDraw (CDC * pDC)
{
CSortDoc * pDoc = GetDocument ();
ASSERT_VALID (pDoc);
/ / TODO: add draw code for native data here
int i;
/ / Виводимо вихідний масив на екран
for (i = 0; i <kol; i + +)
{
str.Format ("% d,", mas [i ]);// формування рядка
pDC-> TextOut (10 + i * 20,10, str); / / вивід на екран
}
/ / Якщо був обраний який-небудь метод сортування
if (sort)
{
if (metod == 1) / / якщо обраний Quicksort
pDC-> TextOut (10,40, "Обмінна сортування з розділенням (quicksort )");// висновок рядка на екран
if (metod == 2) / / якщо обраний Shell
pDC-> TextOut (10,40, "Метод Шелла ");// висновок рядка на екран
if (metod == 3) / / якщо обраний Bubble
pDC-> TextOut (10,40, "Метод прямого обміну (Бульбашки )");// висновок рядка на екран
/ / Виводимо відсортований масив
for (i = 0; i <kol; i + +)
{
str.Format ("% d,", mas2 [i ]);// формування рядка
pDC-> TextOut (10 + i * 20,80, str); / / вивід рядка на екран
}
str.Format ("Кількість перестановок в нашому випадку:% d", count); / / формування рядка
pDC-> TextOut (10,110, str); / / вивід рядка на екран
if (metod == 3) / / якщо було обрано метод "Бульбашки"
{
str.Format ("Максимальна кількість перестановок для масиву з% d елементів методом 'Бульбашки':% d", kol, kol * (kol-1) / 2); / / формування рядка
pDC-> TextOut (10,140, str); / / вивід рядка на екран
}
}
}
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView diagnostics
# Ifdef _DEBUG
void CSortView:: AssertValid () const
{
CView:: AssertValid ();
}
void CSortView:: Dump (CDumpContext & dc) const
{
CView:: Dump (dc);
}
CSortDoc * CSortView:: GetDocument () / / non-debug version is inline
{
ASSERT (m_pDocument-> IsKindOf (RUNTIME_CLASS (CSortDoc)));
return (CSortDoc *) m_pDocument;
}
# Endif / / _DEBUG
////////////////////////////////////////////////// ///////////////////////////
/ / CSortView message handlers
/ / При виборі сортування Quicksort
void CSortView:: OnQuick ()
{
/ / Оголошення локальних змінних
sort = true;
metod = 1;
int i;
count = 0;
for (i = 0; i <kol; i + +)
{
mas2 [i] = mas [i];
}
quicksort (0, kol-1); / / виклик функції quicksort
Invalidate (true); / / перемальовування вмісту вікна
}
/ / При виборі сортування Shell
void CSortView:: OnShell ()
{
/ / Оголошення локальних змінних
sort = true;
metod = 2;
int ii, t = 5, i, j, k, s, m, h [6], x;
count = 0;
for (ii = 0; ii <kol; ii + +)
{
mas2 [ii] = mas [ii];
}
h [1] = 9; h [2] = 5; h [3] = 3; h [4] = 2; h [5] = 1;
////////////////////////////////////////////
/ / АЛГОРИТМ
for (m = 1; m <= t; m + +)
{
k = h [m];
s =- k;
for (i = k +1; i <= kol; i + +)
{
x = mas2 [i];
j = ik;
while (x <mas2 [j] & & j <kol)
{
mas2 [j + k] = mas2 [j];
j = jk;
}
mas2 [j + k] = x;
count + +;
}
}
x = mas2 [0];
mas2 [0] = mas2 [1];
mas2 [1] = x;
////////////////////////////////////////////
Invalidate (true); / / перемальовування вмісту вікна
}
/ / При виборі сортування Bubble
void CSortView:: OnPuzirok ()
{
/ / Оголошення локальних змінних
int dop;
bool end;
count = 0;
sort = true;
metod = 3;
int i, j;
for (i = 0; i <kol; i + +)
{
mas2 [i] = mas [i];
}
////////////////////////////////////////////
/ / АЛГОРИТМ
for (i = 0; i <kol; i + +)
{
end = true;
for (j = i +1; j <kol; j + +)
{
if (mas2 [i]> mas2 [j])
{
dop = mas2 [i];
mas2 [i] = mas2 [j];
mas2 [j] = dop;
end = false;
count + +;
}
}
if (end == true) break;
}
/////////////////////////////////////////////
Invalidate (true); / / перемальовування вмісту вікна
}
/ / Функція швидкого пошуку
void CSortView:: quicksort (int l, int r)
{
int i, j;
i = l; j = r;
{
part (l, r, i, j);
if (i <r) quicksort (i, r); / / перехід до сортування лівій частині
if (j> l) quicksort (l, j); / / перехід до сортування правій частині
}
}
/ / Функція пошуку по частинах
void CSortView:: part (int l, int r, int & i, int & j)
{
int x, dop;
i = l;
j = r;
x = (l + r) / 2;
do
{
while (mas2 [i] <mas2 [x])
i + +;
while (mas2 [j]> mas2 [x])
j -;
if (i <= j)
{
dop = mas2 [i];
mas2 [i] = mas2 [j];
mas2 [j] = dop;
i + +; j -; count + +;
}
}
while (i <j);
}
Література
1. Петзольд Ч. Програмування під Windows 95. У двох книгах: BHV - Санкт - Петербург, 1997, silt.
2. Річард С. Лінкер, Том Арчер. Програмування для Windows 98. Біблія розробника. "Діалектика" - Москва, 1999.-864 с.: Іл .- Хрон. тит. англ. Уч.пос.
3. Джесс Ліберті. С + + за 21 день. "Вільямс" - Москва, 2000.-816 с.: Іл. - Парал.тіт. англ.
4. Девід Дж. Круглінскі. Основи С + +. "Російська редакція" - Москва, 1997 .- 696 с.: Іл.
5. Кейт Грегорі. Використання Visual C + +. "Вільямс" - Москва, 1999.-864 с.: Іл .. - Парал.тіт. англ., уч. сел.
7. Конспект лекцій.