数据结构试验二停车场管理问题

1、HUNANUNIVERSIT Y课程实习报告题目停车场管理问题学生姓名学生学号专业班级指导老师李晓鸿完成日期2 0 1 5年11月 25日、需求分析1. 输入的形式的输入的范围： 选择功能： 1 停车 2 离开停车场 3 离开过道 若输入 1（停车），输入当前车牌号和当前的时间； 若输入 2（离开停车场），输入车票号和当前时间； 若输入 3（离开过道），输入车牌号。2. 输出的形式： 提示选择功能“ 1. 停车 2 离开停车场 3 离开过道”。 若输入 1（停车），并且输入当前车牌号和当前的时间后，若停车场未满， 输出“成功停入停车场，停车场内有 n辆车，过道上有 m辆车等候”；若停车场满，输

2、出 “停 车场已满，请在过道等候”。若输入 2（离开停车场），输入车票号和当前时间，输出“存车总计时间，收费q 元，停车场内有n辆车，过道上有 m辆车等候”；如果进停车场和出停车场时间错误，输出“时间输入有误，请重新输入”； 如果停车场没有此车 ，输出“车牌号有误，请重新 输入”。若输入 3（离开过道），输入车牌号，输出“此车已成功离开过道”；若无此车 ，输出停车过道为空”若输入其他，则提示选择功能“ 1. 停车 2 离开停车场 3 离开过道”。3. 程序所能达到的功能：有一个可以停放 n 辆汽车的狭长停车场， 它只有一个大门可以供车辆进出。 车辆按到达 停车场时间的早晚依次从停车场最里面向大

3、门口处停放 （最先到达的第一辆车放在停车场的 最里面 ） 。如果停车场已放满 n 辆车，则后来的车辆只能在停车场大门外的便道上等待，一 旦停车场内有车开走， 则排在便道上的第一辆车就进入停车场。 停车场内如有某辆车要开走， 在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后， 这些车辆再依原来的次序进场。 每辆车在离开停车场时， 都应根据它在停车场内停留的时间长短交费。 如 果停留在便道上的车未进停车场就要离去， 允许其离去， 不收停车费， 并且仍然保持在便道 上等待的车辆的次序。4. 测试数据： 正常的进入停车场，出停车场，离开过道的模拟输入 11（车牌）1（当前时间）输入

4、12（车牌）2（当前时间）输入 22（车牌）3（当前时间）输入 13（车牌）4（当前时间）输入 14（车牌）5（当前时间）输入 34（车牌） 停车场里没有车出停车场的模拟输入 21（车牌） 过道没车出过道的模拟输入 31（车牌） 进入停车场时间与出停车场时间的模拟 输入 11（车牌）1（进停车场的时间）输入 21（车牌）0（出停车场的时间） 停车场模拟系统功能输入错误输入4二.概要设计抽象数据类型：.由于该停车场只有一个门供出入，并且最先进的停在停车场的最末，最先进的车辆要出停车场需要之后进入的车先出，满足先进后出的结构， 其限制是仅允许在表的一端进行插入和删除运算，所以用栈来模拟停车场。.由

5、于这是一个模拟的车库，车辆出停车场，后面车辆不得不被动跟着出停车场，我们需要对这些车辆进行管理，将第一辆被动出停车场的放置到一个队伍的前端，接下来被动出停车场的车辆依次放到第一辆车之后，当需要离开的车出栈后，对被动出停车场的车辆进行管理，又队伍的前端依次进入停车场，由于满足只允许在表的前端进行删除操作，而在表的后端进行插入操作，所以用队列来模拟被动出停车场车辆的管理。基本思想1. 给定一个size为停车场的容量。2. 每一辆车进栈前，储存车辆编号和进栈的时间。3. 对于栈满的情况，再来的车辆不进栈，只记录编号。4. 对于出栈的车辆，先将出栈车辆之前的停车场内车辆由后往前依次进入队列中，将进栈和

6、出栈时间相比较算出需要付的金额，之后再将队列中的元素由前往后依次进栈。程序的流程程序由三个模块组成：输入模块：按照提示输入计算模块：计算（出栈时间-进栈时间）*每小时金额。输出模块：首先提示 请选择：1、停车；2、离开停车场；3、离开过道；“选择提示“请输入车牌号和现在的时间：“选择3提示“请输入车牌号”基本ADT 栈空判别算法int Empty_SeqStack(queue *s)if (s-top = -1)return 0;elsereturn 1; 入栈算法void Push_SeqStack(queue *s, Datatype x)s_top+;s-data1s-top = x;

7、|return; 岀栈算法void Pop_SeqStack(queue *s, Datatype *x)*x = s-data1s-top;s-top-;return; 列队初始化C_SeQueue *ln it_SeQueue()C_SeQueue *q;q = new C_SeQueue;q-fro nt = q-rear = MAXSIZE - 1;q_num = 0;return q; 入队算法void In _SeQueue(C_SeQueue *q, Datatype x)q-rear = (q-rear + 1) % MAXSIZE;q-data2q-rear = x;q_n

8、um+;return; 岀队算法void Out_SeQueue(C_SeQueue *q, Datatype *x)q-fro nt = (q-fro nt + 1) % MAXSIZE;*x = q-data2q-fr on t;q_n um-;return;算法流程图(进入车库和出车库)三详细设计1. 数据类型用Int型整数储存车辆的信息.车辆进岀时间.收取的费用2. 算法的具体步骤车进入停车场的基本操作void Arrive(queue *s, C_SeQueue *q, int x, double t)int y;int a = s-top;while (a != -1)法的时空分析

9、和改进设想每次进栈的时间复杂度为0( 1)，当要出车辆后有n辆车时，出栈时间复杂度为0(n),也许对于一个车库来说n并不会很大，但是考虑实际这个停车场的设计非常不合理。4. 输入和输出格式输入：功能选择输入为整数1-3，输入车牌号为大于零的整数，时间为大于零的整数。输出：输出整数型的应收的价格四. 调试分析1.为了简化程序，采用手动输入进栈车辆的排序.进栈时间.出栈时间2. 同时因为需要输入多组数据，在程序完工后又加上许多引导性的话，例如提示停车场内有几辆车停车场外有多少车.车辆是否进入车库成功.车辆是否在车库外等候。3. 对于时间的处理过于简陋，只用了一位数表示时间，与实际情况不太符合。4.

10、 对于车牌处理也过于简单，可以在车的储存信息加入车牌号。五. 测试结果情况1测试结果情况2测试情况3测试情况4测试情况5测试六. 试验心得1. 书上对栈的实现太少不详细，查阅了许多栈的各类实现怎么写。2. 存车取车问题比较简单，在程序完成后发现程序的容错率为0,当不小心输入了相同车牌时程序直接报错，不得不添加了许多容错代码，容错程序代码很是让人费神，现在容错已完善再完善了，但还是未能完全解决问题，例如，在过道停的车辆不能保证其中没有相同车牌号的车，还有时间处理的比较简单原始化，这些都有待以后提高，继续完善。每次有车岀来后面的车都要移动3. 这道题过于死板，完全是为了栈强行设计了一道门的停车场,

11、 位置，这种车库，不停也罢。七. 代码#include using namespacestd;#defi neMAXSIZE10#defi neMINSIZE2typedefint Datatype ;typedefstruct Datatype data1 MINSIZE;int top;double time MINSIZE; queue;queue *Init_SeqStack() / 栈的初始化;queue *s;s = new queue;if (!s)cout 空间不足top = -1;return s;int Empty_SeqStack( queue * s) / 栈空判别算法

12、；if ( s-top = -1)return 0;elsereturn 1;void Push_SeqStack( queue * s, Datatype x) / 入栈算法；s_top+;s-data1 s-top = x;return ;int Push_SeqStack1( queue * s, Datatype x, double t)/ 入栈算法 1 ；if ( s-top = MINSIZE-1)return 0;else s-top+;s-data1 s-top = x;s-time s-top = t;return 1;/出栈算法;void Pop_SeqStack( que

13、ue * s, Datatype * x)*x = s-data1 s_top;s-top-;return ;typedef structDatatype data2 MAXSIZEint rear, front;int num; C_SeQueueC_SeQueueinit_SeQueue()/ 列队初始化;C_SeQueu0q;q = new C_SeQueueq-fro nt = q-rear = MAXSIZE- 1;q_num = 0;return q; void In_SeQueue( C_SeQueue q, Datatype x) / 入队算法;q-rear = ( q-rea

14、r + 1) % MAXSIZEq-data2 q-rear = x;q_n um+;return ;void Out_SeQueue( C_SeQueue q. Datatype *x) 岀队算法；q-fro nt = (q-fro nt + 1) % MAXSIZE*x = q-data2 q_front;q_n um-;return ;void show( queue * s, C_SeQueue q) / 显示停车情况；cout 停车场内有top + 1 辆车。 endl;cout 通道上有num 辆车在等候。top;while (a != -1)/判断将要存的车是否已存在于停车场，防

15、止岀现有相同车牌号的车岀现在停车场内；if ( s-data1a = x)cout 成功停入车场 endl;return ;elsea-; |if (Push_SeqStack1( s, x, t)cout 成功停入车场。 endl;elsecout 停车场已满，后来车辆请在便道等候。data1 s-top !=x&!Empty_SeqStack(s)Pop_SeqStack(s, &y);Push_SeqStack(s1, y);if ( s-data1 s-top = x)while (i)if ( t = 1 & t s-time s-top)d = t - s-time s-top;P

16、op_SeqStack(s, &y);cout 存车时间总计：“ d 小时 endl 收费为： d 元 endl;i = 0;elsecout 时间输入有误，请重新输入。 t;elsecout num != 0 & s-top != MINSIZE-1)Out_SeQueueq, &y);Push_SeqStack1(s, y, t);show(s, q);return ;void Leave1( queue * s, C_SeQueu q, int x) / 离开过道;if ( q_num = 0)cout 停车过道为空。rear;q-fro nt)while ( q-data2a != x & (a + MAXSIZE% MAXSIZE= a_;if ( q-data2(a + MAXSIZE% MAXSIZE= x)while (a + MAXSIZE% MAXSIZE= q-rear - 1)q-data2a = q-data2a + 1;a+;q_n um-;cout 此车已成功离开过道。 endl;elsecout 此车不在过道中。 endl;show(s, q);void main()double time;int x, a;queue *s;C_SeQueueq;s = In it_SeqStack(