Структури даних і алгоритми
Курсова робота студента Гридасова А. Ю.
Новосибірський державний технічний університет
Кафедра прикладної математики
Новосибірськ
1998
Умова задачі p> Мається деякий кінцеве число міст, які пов'язані транспортної мережею, що складається з авіа, залізничних, автомобільних і водних рейсів довільного напрями і включають довільне число міст. Вартість проїзду різна по класах. Рейс відправляються по тижневому розкладом. При пересадки між рейсами має бути не менше 2-х годин. По заданих початкового і кінцевого містам, датою бажаного відправлення, максимальному часу шляху і максимальної вартості і максимальному числу пересадок видати всі можливі маршрути, так, щоб маршрути з меншою датою і часом прибуття відображалися раніше, ніж з великим.
Аналіз завдання В p> Транспортна схема являє собою спрямований зважений мультіграф. Кожна дуга характеризується приналежністю до рейсу, часом шляху, ціною кожного з класів, часом відправлення. h2> Вхідними даними є:
Транспортна система. (Міста і всі рейси)
Початковий, кінцевий місто, орієнтовна дата та час відправлення, максимальний час шляху максимальна ціна, максимальну кількість пересадок.
Причому дані першої групи змінюються вкрай рідко і задаються розробником транспортної системи, а дані другої групи змінюються від завдання до завдання і задаються кожним користувачем.
Результатом роботи програми є кінцеве безліч маршрутів. Два маршруту ми будемо вважати різними, якщо вони відрізняються хоча б одним містом прямування або хоча б одним рейсом. Після того, як знайдені всі маршрути вони упорядковано часу прибуття.
Метод рішення - метод послідовних випробувань. Пошук рішень здійснюватиметься рекурсивно, причому максимальна глибина рекурсії буде рівна максимальній кількістю пересадок. Так як ми маємо обмеження по деяких параметрах то ми можемо відсікти явно помилкову гілку пошуку рішень, зробивши перевірку на перевищення параметрів. Це дозволить виграти додатковий час. (Про реалізації більш детально п.4)
Вибір і обгрунтування форм представлення даних. p> Так як транспортна система включає в себе досить великий обсяг інформації, в цілях доступу до більшого обсягу пам'яті, також з метою більш раціонального використання пам'яті і з причини неприпустимість використання статичних об'єктів в деяких випадках, в програмі для внутрішнього уявлення широко використовуються динамічні об'єкти.
Для об'єднання великої кількості даних в одному об'єкті, а також для реалізації динамічних об'єктів використовується комбінований тип (запис).
Для внутрішнього зберігання інформації про рейси використовується ланцюг (односпрямований список) PFlight з 7-ма інформаційними полями різних типів:
Для зберігання назви компанії-перевізника використовується тип string [20] так зі зрозумілих причин....
