Дослідження алгоритмів з використанням різних структур даних: черг та графів - Курсовая работа

Структура даних - програмна одиниця, що дозволяє зберігати і обробляти безліч однотипних і / або логічно повязаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс. Структура даних часто є реалізацією будь-якого абстрактного типу даних. При розробці програмного забезпечення велику роль грає проектування сховища даних і представлення всіх даних у вигляді безлічі повязаних структур даних. Добре спроектоване сховище даних оптимізує використання ресурсів (таких як час виконання операцій, на обсяг оперативної памяті, число звернень до дискових накопичувачів), необхідних для виконання найбільш критичних операцій.Черга в програмуванні - динамічна структура даних , що працює за принципом "перший прийшов - перший пішов" (англ. У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)Блок-схема алгоритму роботи програми 1У випадку коли T <t1 або T <t2 або будь-яка змінна з вхідних даних = 0 вхідні дані задані невірно.В клас стандартного діалогового вікна було додано такі елементи: Edit1-поле для вводу кількості покупців m Edit2-поле для вводу t1 Edit3-поле для вводу t2 В клас стандартного діалогового вікна було додано такі функції: afx_msg void ONBNCLICKEDBUTTON1() - функція для керування кнопкою 1 afx_msg void ONBNCLICKEDBUTTON2() - функція для керування кнопкою 2 void dodavsja() - функція, що додає до черги покупця void obslygily() - функція, що вилучає з черги покупця void pilgoviy() - функція, що додає до черги пільгового покупця void zvaluv() - функція, що вилучає з черги покупця, який не витримав очікування в черзі В клас стандартного діалогового вікна було додано такі змінні: int now_get1 - Змінна для запамятовування покупця, який зараз додається до черги int now_get2 - Змінна для запамятовування покупця, який зараз вилучається з черги int now_time - Змінна, в якій задається текучий час int real1 - Змінна, в яку записується випадкове значення, з діапазону 1..t1 int real2 - Змінна, в яку записується випадкове значення, з діапазону 1..t2 int real3 - Змінна, в яку записується випадкове значення, з діапазону 1..t3 int real4 - Змінна, в яку записується випадкове значення, з діапазону 1..t4Результат виконання програми з вхідними даними 1Обєкти розглядаються як вершини, або вузли графу, а звязки - як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість звязків і додатковими даними про вершини або ребра. Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини - це статті, а дуги (орієнтовані ребра) - посилання на інші статті. Граф або неорієнтований граф G - це впорядкована пара G: = (V,E), для якої виконуються наступні умови: V - множина вершин або вузлів, E - множина пар (у випадку неорієнтованого графу - невпорядкованих) вершин, які називають ребрами.Блок-схема алгоритму роботи програми 2Залежно від вхідного файлу з даними створюється певна структура даних (граф) з вершинами, що задані у вхідному файлі та з ребрами (звязками) між вершинами, які задаються парою вершин у вхідному файлі. Всі дані з файлу зберігаються у графі під час роботи програми.В клас стандартного діалогового вікна було додано такі елементи: Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі Button2 - кнопка за допомогою якої формується граф з вхідного файлу та виводиться результат обрахунку на екран STATICTEXT1-текстове поле яке виводить допоміжне повідомлення (Необхідно )Текстовий файл з вхідними даними та граф, який під цим розумієтьсяВиконуючи дану курсову роботу, я закріпив основи роботи з такими структурами даних як черга та граф.

Зміст черга граф програмування

Вступ

1. Завдання 1

1.1 Теоретична частина

1.2 Алгоритм розвязку

1.3 Система тестів

1.4 Специфікація програми

1.5 Результати виконання програми

2. Завдання 2

2.1 Теоретична частина

2.2 Алгоритм розвязку

2.3 Система тестів

2.4 Специфікація програми

2.5 Результати виконання програми

Висновки

Список літератури

Додаток

Виконуючи дану курсову роботу, я закріпив основи роботи з такими структурами даних як черга та граф. Вивчив методи і принципи роботи з ними і алгоритми роботи черги та графа. Закріпив знання про створення проектів MFC.

ГОСТ 19.701-90 (ИСО 5807-85) ЕСПД. Схемы алгоритмов и программ, данных и систем. Условные обозначения и правила выполнения.

Берзтисс А.Т. Структуры данных . - М.:Статистика, 1974 - 408 с.

А.Ахо, Дж.Хопкрофт, Дж.Ульман, Д.Джеффри. Структуры данных и алгоритмы.; Пер. с англ.- М.:Изд.дом ”Вильямс”, 2001. - 384 с.

Уильям Топп, Уильям Форд. Структуры данных в С . - М.:Бином, 2000 - 700 с.

Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, pp. 425-461; Mareљ, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes", Archivum mathematicum Т. 40 (3): 315-320.