Структуры данных и алгоритмы - Курсовая работа

Новосибирский государственный технический университет Кафедра прикладной математикиИмеется некоторое конечное число городов, которые связаны транспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов произвольного направления и включающих произвольное число городов.Транспортная схема представляет собой направленный взвешенный мультиграф. Каждая дуга характеризуется принадлежностью к рейсу, временем пути, ценой каждого из классов, временем отправления. Причем данные первой группы изменяются крайне редко и задаются разработчиком транспортной системы, а данные второй группы изменяются от задачи к задачи и задаются каждым пользователем. Два маршрута мы будем считать различными, если они отличаются хотя бы одним городом следования или хотя бы одним рейсом.Так как транспортная система включает в себя достаточно большой объем информации, в целях доступа к большему объему памяти, также в целях более рационального использования памяти и по причине недопустимости использования статических объектов в некоторых случаях, в программе для внутреннего представления широко используются динамические объекты. Для внутреннего хранения информации о рейсах используется цепь (однонаправленный список) PFLIGHT с 7-ю информационными полями различных типов: Для хранения названия компании-перевозчика используется тип string[20] так по понятным причинам. Для хранения номера рейса используется тип string[10] т.к. в номерах рейса часто используются различные не цифровые шифры, индексы, коды. Динамический тип использован по причине большого разброса в частоте отправления рейсов (могут быть рейсы, отправляющиеся каждый день через час, а могут быть рейсы отправляющиеся раз в неделю). А для хранения названий городов и их координат для отображения на экране используется свой тип - массив, элементами которого являются записи с полями для названия города и координат.Begin {Процедура поиска маршрута с данным шаблоном и уже построенной частью маршрута} While {просмотрены не все рейсы} do begin If {город отправления присутствует в рейсе, причем раньше конечной станции} then begin If {текущий город еще не проезжали} and {время пути не превышает максимального} and {количество пересадок не превышает максимального} and {не приехали} then {Добавить к маршруту проеханный участок.Cities=array[CITYCODE] of {Названия и координаты городов} record name:string[20]; repeat b:=Q^.way[i].CITYL; {Проверка города на дублирование} i:=(i mod 4) 1; if i=1 then Q:=Q^.next until (Q^.way[i].city=P^.target) or not b; {переход к следующему пока не город назначения} p:=p^.last end; While Pnil do begin {Просмотр всех рейсов} if ((Path=nil) or (PPATH^.Flight)) and Pattern.Kind[P^.Kind] then {не повторяется рейс и сответствует тип перевозки} begin If B2 and B1 then Answer(Npath,pattern.cost); {Если приехали, добавить маршрут в список} end {найден начальный город} end; {маршрут подходит по типу} For J:=1 to MC do begin READLN(source,City[j].name); readln(source,city[j].x,city[j].y) end;В качестве транспортной системы бала взята система, состоящая из 23 городов, соединенных 19 прямыми и таким же числом обратных рейсами. Рейсы были разработаны так, что имеется несколько крупных транспортных развязок: Palace of Dream, Diamond World, Golden River, Seaside City; и несколько "удаленных" городов: Far Star City, Oil City, North Star City. Дата отправление: Дата ... Отправление: 14:29 8.5.1998 Пт Прибытие: 19:14 8.5.1998 Пт Отправление: 17:20 9.5.1998 Пт Прибытие: 19:20 9.5.1998 Пт цена: 195 - 250Время пути зависит от дня оправления.

Оглавление

1. Условие задачи

2. Анализ задачи

3. Выбор и обоснование форм представления данных

4. Алгоритм

5. Текст программы на языке Pascal

6. Выбор и обоснование набора тестов

7. Анализ результатов

Приложение