Структуры данных и алгоритмы

begin Read(Source,C); P^.class[i]:=C='X' end;

ReadLn(Source, P^.TotalStation);

New(P^.path);

Q:=P^.path;

{информация о городах следования времени пути, стоянках}

For J:=1 to P^.TotalSTation do begin

K:=((J-1) mod 4)+1;

Read(Source,Q^.Way[K].City,Q^.Way[K].Delay,Q^.Way[K].Reboard);

For I:=1 to MClass do If P^.class[I] then Read(Source,Q^.Way[K].cost[I])

else Q^.Way[K].cost[I]:=0;

If (J mod 4)=0 then begin

If (J<>P^.TotalStation) then begin New(Q^.Next); Q:=Q^.next end

else Q^.next:=nil;

end;

ReadLn(Source);

end;

New(P^.Table);

G:=P^.Table;

L:=G;

{Информация о отправлении из начального пункта}

While Not EOLn(Source) do begin

Read(Source,D);

G^.Time:=(ord(D[1])-ord('0')-1)*1440+((ord(D[3])-ord('0'))*10+ord(D[4])-ord('0'))*60

+(ord(D[6])-ord('0'))*10+ord(D[7])-ord('0');

if L^.time>G^.time then write('Wrong data');

If not EOLn(Source) then begin New(G^.next); G:=G^.next end else G^.next:=nil;

end;

ReadLn(Source);

end;

Load:=A;

end;


const line='--------------------------------------------------------------------------------';


procedure graphout(const city:cities);

var

grDriver: Integer;

grMode: Integer;

p:citycode;

begin

grDriver := Detect;

InitGraph(grDriver, grMode,'');

setcolor(12);

outtextxy(200,0,'Карта транспортной схемы');

p:=1;

while (p<maxcity) and (city[p].name<>'') do begin

setcolor(5);

fillellipse(4*city[p].x,380-3*city[p].y,2,2);

setcolor(11);

outtextxy(4*city[p].x+5,376-3*city[p].y,city[p].name);

inc(p)

end;

end;


var List:PFLight; pattern:blank; st:string; p:answerlist;

city:cities; a:dat;


Procedure Input(var Pattern:blank; var a:dat);

var i:citycode; st:string; b:dat; w:real;

begin

with pattern do begin

GotoXY(30,1);

WriteLn('Ввод исходных данных');

write(line);

repeat

write('Начальный город ... ');

readln(st);

Bcity:=1; while (BCity<Maxcity) and (City[BCity].name<>st) do inc(BCity);

until BCity<>MaxCity;

repeat

write('Конечный город ... ');

readln(st);

Ecity:=1; while (ECity<Maxcity) and (City[ECity].name<>st) do inc(ECity);

until Ecity<>MaxCity;

repeat

gotoxy(1,5);

WriteLn('Дата отправление:');

DTInput(a);

delay:=a.Dweek*1440+a.time;

Write('Максимальное время пути (сутки):');

readln(w);

waytime:=round(1440*w);

until waytime>0;

write('Максимальная стоимость ... ');

ReadLn(cost);

write('Максимальное число пересадок ... ');

readln(reboading);

write('Тип перевозки (авиа,ж.д.,авто,водн.) ... ');

readln(st);

if st='' then for i:=1 to 4 do kind[i]:=true else

for i:=1 to 4 do kind[i]:=(st[i]='Y') or (st[i]='y') or (st[i]='X') or (st[i]='x');

write('Допустимые классы 123456 ... ');

readln(st);

if st='' then for i:=1 to 4 do class[i]:=true else

for i:=1 to 4 do class[i]:=(st[i]='Y') or (st[i]='y') or (st[i]='X') or (st[i]='x');

end;

end;


procedure outres(p:Answerlist; a:dat);

var k:word; q:link; b:dat; i:citycode; y:pway; c:byte;

begin

k:=0;

while P<>nil do begin

inc(k);

{ write(p^.path^.bcity);}

Q:=P^.path;

b:=a;

while Q<>nil do begin

write(city[q^.bcity].name);

Writeln(' <',q^.flight^pany,q^.Flight^.Number,'> ',city[Q^.Target].name);

newdat(b,Q^.ddelay,b);

write('Отправление: '); writedat(b);

newdat(b,Q^.waytime,b);

write(' Прибытие: '); writedat(b); writeln;

Q:=Q^.last;

end;

newdat(a,p^.waytime,b);

writeln (' цена: ',P^.mincost,' - ',p^.maxcost);

readln(st);

if st='p' then begin

graphout(city);

q:=p^.path;

c:=2;

while q<>nil do begin

i:=1;

y:=q^.flight^.path;

while y^.way[i].city<>q^.bcity do begin

i:=(i mod 4)+1; if i=1 then y:=y^.next;

end;

setcolor(c);

moveto(4*city[q^.bcity].x,380-3*city[q^.bcity].y);

repeat

i:=(i mod 4)+1; if i=1 then y:=y^.next;

lineto(4*city[y^.way[i].city].x,380-3*city[y^.way[i].city].y);

until (y^.way[i].city=q^.target);

Q:=Q^.last; inc(c);

end; repeat until keypressed; CloseGraph;

end;

P:=P^.next;

end;

if k=0 then write('При данных условиях добраться нельзя') else writeln('Всего ',k,' маршшрутов');

end;


Begin

List:=Load(nil,'trafic',city);

graphout(city);

repeat until keypressed;

closegraph;

Input(pattern,a);

new(lanswer);

lanswer^.next:=nil;

Search(List,pattern,nil);

outres(Lanswer^.next,a);

end.


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


В качестве транспортной системы бала взята система, состоящая из 23 городов, соединенных 19 прямыми и таким же числом обратных рейсами. Название городов и перевозчиков вымышленные. Рейсы были разработаны так, что имеется несколько крупных транспортных развязок: Palace of Dream, Diamond World, Golden River, Seaside City; и несколько «удаленных» городов: Far Star City, Oil City, North Star City.

Разные рейсы отправляются от 3 до 18 раз в неделю.

1. Общий тест

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.2008 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 3

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port <GoldenAirBridge004> Palace Of The Dream

Отправление: 14:29 8.5.2008 Пт Прибытие: 19:14 8.5.2008 Пт

Palace Of The Dream <GoldenAirBridge009> Diamond World

Отправление: 2:15 9.5.2008 Пт Прибытие: 5:15 9.5.2008 Пт

Diamond World <DiamondAirlines003> Beatiful

Отправление: 17:20 9.5.2008 Пт Прибытие: 19:20 9.5.2008 Пт

цена: 195 – 250

Tropic Port <GoldenAirBridge004> Lakes Land

Отправление: 14:29 8.5.2008 Пт Прибытие: 16:29 8.5.2008 Пт

Lakes Land <DiamondAirlines006> Diamond World

Отправление: 0:25 9.5.2008 Пт Прибытие: 3:25 9.5.2008 Пт

Diamond World <DiamondAirlines003> Beatiful

Отправление: 17:20 9.5.2008 Пт Прибытие: 19:20 9.5.2008 Пт

цена: 165 - 195

Tropic Port <DeepWater02> Oil City

Отправление: 12:0 8.5.2008 Пт Прибытие: 4:40 9.5.2008 Пт

Oil City <TransExpress002> Beatiful

Отправление: 12:0 9.5.2008 Пт Прибытие: 16:10 10.5.2008 Пт

цена: 75 – 105

2. Тест с «урезанием бюджета»

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.2008 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 180

Максимальное число пересадок ... 3

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port <GoldenAirBridge004> Lakes Land

Отправление: 14:29 8.5.2008 Пт Прибытие: 16:29 8.5.2008 Пт

Lakes Land <DiamondAirlines006> Diamond World

Отправление: 0:25 9.5.2008 Пт Прибытие: 3:25 9.5.2008 Пт

Diamond World <DiamondAirlines003> Beatiful

Отправление: 17:20 9.5.2008 Пт Прибытие: 19:20 9.5.2008 Пт

цена: 165 - 195

Tropic Port <DeepWater02> Oil City

Отправление: 12:0 8.5.2008 Пт Прибытие: 4:40 9.5.2008 Пт

Oil City <TransExpress002> Beatiful

Отправление: 12:0 9.5.2008 Пт Прибытие: 16:10 10.5.2008 Пт

цена: 75 – 105

3. Уменьшение числа пересадок

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.2008 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 2

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port <DeepWater02> Oil City

Отправление: 12:0 8.5.2008 Пт Прибытие: 4:40 9.5.2008 Пт

Oil City <TransExpress002> Beatiful

Отправление: 12:0 9.5.2008 Пт Прибытие: 16:10 10.5.2008 Пт

цена: 75 – 105

4. Нереальные условия

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.2008 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 1

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

При данных условиях добраться нельзя

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


Время пути зависит от дня оправления.

По причине ожидания рейса можно с меньшим числом пересадок добраться позже, чем с большим

Дороже – не значит быстрее

Для нормальной транспортной системы нужно как можно больше больших транспортных узлов

Приложение


Unit Date;

interface

Var DTErr:boolean;

Type Dat=record

day:1..31;

month:1..12;

year:integer;

dweek:0..6;

time:word;

end;

Const EWeek:array[0..6] of string[2]=('Mo','Tu','We','Th','Fr','Sa','Sa');

Const RWeek:array[0..6] of string[2]=('Џ­','‚в','‘а','—в','Џв','‘Ў','‚б');

procedure newdat(a:dat; delay:word; var b:dat);

procedure writedat(b:dat);

Function DayDiffer(A,B:dat):Integer;

Function STime(st:string):word;

Function dweek (a:dat):byte;

Procedure DTInput(var d:dat);

Procedure SDate(St:string; var a:dat);


Implementation

uses dos,crt;

Function DayInMonth(m:byte; y:integer):byte;forward;


procedure SDate(St:string; var a:dat);

const mthe:array[1..12] of string[3] =('JAN','FEB','MAR','APR','MAY','JUN','JUL','AUG','SEP','OCT','NOV','DEC');

const mthru:array[1..12] of string[3] =('џЌ‚','”…‚','ЊЂђ','ЂЏђ','ЊЂ‰','ˆћЌ','ˆћ‹','Ђ‚ѓ','‘…Ќ','ЋЉ’','ЌЋџ','„…Љ');

const mthrl:array[1..12] of string[3] =('п­ў','䥢','¬ а',' Їа','¬ ©','Ёо­','Ёо«',' ўЈ','ᥭ','®Єв','­®п','¤ҐЄ');

var i,j,e:byte; mode:byte; S:word; err:boolean; D,M,Y,wd:word; c:shortint;

Procedure add(mode:byte;s:word;var a:dat);

begin

case mode of

1:if (s>0) and (s<=31) then A.day:=S else DTErr:=true;

3:if (s>0) and (s<=12) then A.month:=S else DTErr:=true;

5:if s>=100 then A.year:=S else A.year:=S+100*(Y div 100);

end;

end;

begin

DTErr:=false;

GetDate(Y,M,D,wd);

e:=length(st);

i:=1; mode:=0;

while (i<=e) do begin

c:=ord(st[i])-ord('0');

if ((mode mod 2)=0) and (c>=0) and (c<=9) then begin S:=c; inc(mode) end

else if (c<=9) and (c>=0) then S:=S*10+c

else if (mode mod 2)=1 then begin Add(mode,S,a); Inc(mode) end;

if (mode=2) then

for j:=1 to 12 do

if (mthe[j,1]=upcase(st[i])) and (mthe[j,2]=upcase(st[i+1])) and (mthe[j,3]=upcase(st[i+2])) or

((mthru[j,1]=st[i]) or (mthrl[j,1]=st[i])) and ((mthru[j,2]=st[i+1]) or (mthrl[j,2]=st[i+1])) and

((mthru[j,3]=st[i+2]) or (mthrl[j,3]=st[i+2])) then

begin add(3,j,a); mode:=4 end;

inc(i);

end;

if (mode mod 2)=1 then add(mode,S,a);

if mode<1 then add(1,D,a);

if mode<3 then add(3,M,a);

if mode<5 then add(5,Y,a);

if not DTErr then DTErr:=a.day>DayInMonth(a.month,a.year);

if not DTErr then a.dweek:=dweek(a);

end;


function dweek (a:dat):byte;

var n,m,y:word;

begin

DTErr:=false;

y:=a.year;

if a.month<=2 then begin m:=a.month+12; dec(y) end else m:=a.month;

n:=(A.day+2*m+trunc(0.6*(m+1))+y+(y div 4)-(y div 100)+(y div 400)) mod 7;

dweek:=n;

end;


Function STime (st:string):Word;

var i,e,mode:byte; a,s:word; c:shortint;

begin

DTErr:=false;

e:=length(st);

i:=1; mode:=0; a:=0;

while (i<=e) do begin

c:=ord(st[i])-ord('0');

if ((mode mod 2)=0) and (c>=0) and (c<=9) then begin S:=c; inc(mode) end

else if (c<=9) and (c>=0) then S:=S*10+c

else if mode=1 then begin A:=S; inc(mode) end

else if mode=3 then begin A:=A*60+S; inc(mode) end;

inc(i)

end;

if mode=3 then A:=a*60+s;

if a<1440 then Stime:=a else DTErr:=true;

end;


Function DayInMonth(m:byte; y:integer):byte;

const DayInM:array[1..12] of byte=(31,29,31,30,31,30,31,31,30,31,30,31);

begin

If M<>2 then DayInMonth:=DayInM[M]

else if (y mod 4)<>0 then DayInMonth:=28

else if (y mod 100)<>0 then DayInMonth:=29

else if (y mod 400)<>0 then DayInMonth:=28 else DayInMonth:=29

end;


Function DayDiffer(A,B:dat):Integer;

Var m1,m2,y1,y2:Integer;

Begin

DTErr:=false;

y1:=A.year;

y2:=B.year;

if a.month<=2 then begin m1:=a.month+12; dec(y1) end else m1:=a.month;

if b.month<=2 then begin m2:=b.month+12; dec(y2) end else m2:=b.month;

DayDiffer:=-(A.day+30*m1+trunc(0.6*(m1+1))+365*y1+(y1 div 4)-(y1 div 100)+(y1 div 400))+

(B.day+30*m2+trunc(0.6*(m2+1))+365*y2+(y2 div 4)-(y2 div 100)+(y2 div 400));

End;


Procedure DTInput(var d:dat);

var st:string; y:byte;

const empty=' ';

begin

y:=wherey;

repeat

GotoXY(1,y);

Write('„ в  ... ',empty);

GotoXY(10,y);

ReadLn(St);

SDate(st,d);

Until not DTErr;

GotoXY(10,y);

writeln(d.day,'.',d.month,'.',d.year,' ',Rweek[Dweek(d)]);

repeat

gotoxy(1,y+1);

write('‚६п ... ',empty);

gotoxy(11,y+1);

readln(st);

d.time:=stime(st);

until not DTErr;

gotoxy(11,y+1);

writeln(stime(st) div 60,':',stime(st) mod 60);

end;


procedure writedat(b:dat);

begin

write(b.time div 60,':',b.time mod 60,' ',b.day,'.',b.month,'.',b.year,' ',Rweek[b.dweek]);

end;


procedure newdat(a:dat; delay:word; var b:dat);

var c:word;

begin

B:=A;

B.time:=(a.time+(delay mod 1440)) mod 1440;

delay:=(delay div 1440)+((a.time+(delay mod 1440)) div 1440);

while delay+b.day>DayInMonth(b.month,b.year) do begin

delay:=delay-1-DayInMonth(b.month,b.year)+b.day;

b.day:=1;

b.month:=(b.month mod 12)+1;

if b.month=1 then inc(b.year);

end;

b.day:=delay+b.day;

end;


begin

end.

1 Текущий город – есть пункт назначения.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: