《关于停车场问题的算法》由会员分享,可在线阅读,更多相关《关于停车场问题的算法(17页珍藏版)》请在金锄头文库上搜索。
1、停车场管理问题1)问题描述设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端)。若停车场内已经停满n辆车,那么后来的车只能在门外的便道上等候。一旦有车开走,则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2)基本要求以栈模拟停车场,以队列模拟车场外的便道,按照从终
2、端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项:汽车的“到达”(A表示)或“离去”(D表示)信息、汽车标识(牌照号)以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或者便道上的停车位置;若是车辆离去,则输出汽车在停车场停留的时间和应缴纳的费用(便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。3)提示需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:汽车的牌照号码和进入停车场的时刻。4)输入输出:输入数据:程序接受5个命令,分别是:
3、到达(A,车牌号,时间);离去(D:车牌号,时间);停车场(P,0,0)显示停车场的车数;候车场(W:0,0)显示候车场的车数;退出(E:0,0)退出程序。输出数据:对于车辆到达,要输出汽车在停车场内或者便道上的停车位置;对于车辆离去,则输出汽车在停车场停留的时间和应缴纳的费用(便道上不收费)。二、算法基本思想描述根据要求由此很容易联想到数据结构中的堆栈模型,因此可首先设计一个堆栈,以堆栈来模拟停车场,我设计用顺序存储结构来存储停车场内的车辆信息,并给车辆按进栈顺序编号,当停车场内某辆车要离开时,在他之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入停车场。这是个
4、一退一进的过程,而且让道的汽车必须保持原有的先后顺序,因此可再设计一个堆栈,以之来暂时存放为出站汽车暂时让道的汽车。当停车场满后,继续进来的汽车需要停放在停车场旁边的便道上等候,若停车场有汽车开走,则按排队的先后顺序依次进站,最先进入便道的汽车将会最先进入停车场,这完全是一个先进先出模型,因此可设计一个队列来模拟便道,队列中的数据元素设计成汽车的车牌号,并以链表的形式存储。另外,停车场根据汽车在停车场内停放的总时长来收费的,在便道上的时间不计费,因此必须记录车辆进入停车场时的时间和车辆离开停车场时的时间,然后计算、显示费用情况。三、模块结构及流程图输入离开车辆的离开时间,进行停车费用的计算此车
5、后面的车辆退出并进入临时栈车子离开四、详细设计#include#include#includetypedefstructintnumber;inttime;car;typedefstructcar*base;car*top;intstacksize;sqstack;voidInitstack(sqstack*s)s-base=(car*)malloc(sizeof(car);if(!s-base)exit(-1);s-top=s-base;s-stacksize=0;voidpush(sqstack*s,care)*s-top+=e;s-stacksize+;carpop(sqstack*s)
6、care;if(s-top=s-base)printf(停车场内没有该车辆!n);exit(0);e=*-s-top;s-stacksize-;returne;typedefstructQnodeintnumber;inttime;structQnode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;intlength;LinkQueue;intInitQueue(LinkQueue*Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(-1)
7、;Q-front-next=NULL;Q-length=0;return1;voidEnQueue(LinkQueue*Q,car*a)QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(-1);p-number=a-number;p-time=a-time;p-next=NULL;Q-rear-next=p;Q-rear=p;Q-length+;QueuePtrDeQueue(LinkQueue*Q)QueuePtrp,e,s=0;if(Q-front=Q-rear)printf(便道上没有车辆!n);returns;p=Q-front
8、-next;e=p;Q-front-next=p-next;Q-length-;if(Q-rear=p)Q-front=Q-rear;returne;voidarrive(sqstack*s,LinkQueue*p,cara,intn)if(s-stacksizestacksize);elseEnQueue(p,&a);printf(”由于停车场内车位已满,车牌号为%d的车辆停在便道的%d号位置n,a.number,p-length);voidleave(sqstack*tcc,sqstack*dcc,LinkQueue*p,cara,floatpay,intn)carx,y;QueuePtr
9、b;intfind=1,arrivetime=0;floatcost=0.0;while(find)y=pop(tcc);push(dcc,y);if(y.number=a.number)find=0;cost=(a.time-y.time)*pay;arrivetime=y.time;pop(dcc);while(dcc-stacksize)x=pop(dcc);push(tcc,x);if(tcc-stacksizelength!=0)b=DeQueue(p);x.number=b-number;x.time=a.time;push(tcc,x);printf(车牌号为%d的车辆从便道上进
10、入停车场%d号车道n,x.number,tcc-stacksize);printf(n=n);printf(车牌号码:dn,a.number);printf(进站时亥1:%dn”,arrivetime);printf(”出站时刻:%dn,a.time);printf(停留时间:%dn,a.time-arrivetime);printf(停车费用:.2fn”,cost);printf(=n);intmain()sqstackIn,Out;LinkQueueQ;cara;intsum=1000,n;floatprice;charch;printf(n=停车场管理=n);printf(A或者a表示车
11、辆到达D或者d表示车辆离开E或者e表示退出系统nn);Initstack(&In);Initstack(&Out);InitQueue(&Q);printf(请输入停车场的车位总数以及它的收费标准(元/小时):);scanf(%d%f,&n,&price);getchar();printf(n请输入A/D/E,车牌号,时刻:”);scanf(%c%d%d,&ch,&a.number,&a.time);getchar();while(1)switch(ch)casea:caseA:arrive(&In,&Q,a,n);break;caseD:cased:leave(&In,&Out,&Q,a,p
12、rice,n);break;casee:caseE:exit(-1);break;printf(n请输入A/D/E,车牌号,时刻:”);scanf(%c%d%d,&ch,&a.number,&a.time);getchar();getchar();getchar();return0;五、运行结果=停车场管理=*或者“表示车辆到达JW或者,W耒示车辆离开,E,或者V表示退出系统请输入停车场的车位总数以及它的收费标准(元/小时W3请输入“理,车牌号,时刻油L2牌号为1的车辆进入停车场1号车道请输人白加8车牌号,时刻沖2车牌号为2的车辆进入停车场2号车道请输入“足车牌号,时刻油3由于停车场内车位已満车牌号対3的车抵停在便道的1号位置请输人口必,车牌号,时和DL牌号为3的车辆从便道上进入停车场2号车道1439TI生刻勿间用弄时时时蕃攀站站留车務进出停停青输WWE,车牌号,时刻辺451333=刻勿间用弄时时时费器站站留车內进出停停青输)TE,车牌号,时刻:本实验也可以用如下程序#includeconstintN=2;constintM=3;typedefstructintnum;intarrtime;elemtype;structseqstackelemtypestackN+1;inttop;s1,s2;structlinkelemtypedata;link*next;