数据结构课程设计――停车场管理.doc

《数据结构课程设计――停车场管理.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、课程设计题目：停车场管理二、课程设计内容：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早、晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，那么，后面进入停车场的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离

2、去，不收停车费，并且在便道上等待的车辆依然保持原有次序不变。设计一个程序，模拟此停车场管理。三、数据结构的提取：1.停车场采用栈式结构定义栈（停车场）structstack初始化栈voidinitstack(stack*s)元素进栈intinstack(stack*s,cinfox)元素出栈cinfooutstack(stack*s)2.停车场外的便道采用队列结构定义队列（车场外的便道）structqueue初始化队列voidinitqueue(queue*q)元素进队列voidinqueue(queue*q,intnum1)元素出队列intoutqueue(queue*q)3.处

3、理车辆到达的情况定义函数voidcarrival(stack*s,queue*q,cinfox)4.处理车辆离开定义函数voidcarleave(stack*s1,stack*s2,queue*q,cinfox)四、原理及关系分析停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进

4、栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队头取出一辆车压入栈中。用栈模拟停车场，用队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车到达或离去的信息，汽车牌照号码以及到达或离去的时刻。每次输入完，进行输出操作：若是车辆到达，输出汽车在停车场内或便道上的停车位置；若是车辆离去，输出停留时间和应缴纳的费用（在便道上停留的时间不收费）。其中栈以顺序结构实现，队列以链表结构实现。五、算法的理论时间及空间复杂度1.车进入及出停车场（车进栈出栈）算法（1）定义数据类型intN;constintM=5;struct

5、cinfo{intcnum;//车号inthour;intminute;//到达时间};structstack//定义栈{cinfocstack[3000];//这里随便定义一个数字表示数组的长度,因为inttop;//后面会根据用户输入的N值作为停车场能够停车的intsize;//数量.};structnode//定义队列节点的类型{intnnum;node*next;};{node*front,*rear;};此算法的时间复杂度T(n)=O(n)（2）车进入停车场voidinitstack(stack*s)//初始化栈{s->top=-1;}intinstack(stack*s

6、,cinfox)//元素进栈{//int元素进栈n;if(s->top==N-1){cout<<"Stackisfull!"<cstack[++s->top]=x;return1;}}此算法的时间复杂度T(n)=O(n)（3）停车场内车要离开cinfooutstack(stack*s)//元素出栈{cinfoy;if(s->top<0){y.cnum=NULL;y.minute=NULL;returny;}else{s->top--;returns->cstack[s->top+1];}}voidcarrival(stack*s,que

7、ue*q,cinfox)//处理车辆到达的情况{intf;f=instack(s,x);if(f==0){inqueue(q,x.cnum);cout<<"TheNumber"<front->nnum<<""<<"oftheroad."<top+1<<""<<"o