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

1、HUNAN UNIVERSITY课程实习报告题 目： 停车场管理问题 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日 期 2 0 1 5年 11 月 25日 1、 需求分析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（当前时间）输入 12（车牌）2（当前时间）输入22（车牌）3（当前时间）输入1

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

5、，将第一辆被动出停车场的放置到一个队伍的前端，接下来被动出停车场的车辆依次放到第一辆车之后，当需要离开的车出栈后，对被动出停车场的车辆进行管理，又队伍的前端依次进入停车场，由于满足只允许在表的前端进行删除操作，而在表的后端进行插入操作，所以用队列来模拟被动出停车场车辆的管理。基本思想1.给定一个size为停车场的容量。2.每一辆车进栈前，储存车辆编号和进栈的时间。3.对于栈满的情况，再来的车辆不进栈，只记录编号。4.对于出栈的车辆，先将出栈车辆之前的停车场内车辆由后往前依次进入队列中，将进栈和出栈时间相比较算出需要付的金额，之后再将队列中的元素由前往后依次进栈。程序的流程 程序由三个模块组成：

6、 输入模块：按照提示输入 计算模块：计算（出栈时间-进栈时间）*每小时金额。 输出模块：首先提示 "请选择：1、停车；2、离开停车场；3、离开过道；" 选择1.2提示 "请输入车牌号和现在的时间：" 选择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;retur

7、n;出栈算法void Pop_SeqStack(queue *s, Datatype *x) *x = s->data1s->top;s->top-;return;列队初始化C_SeQueue *Init_SeQueue() C_SeQueue *q;q = new C_SeQueue;q->front = q->rear = MAXSIZE - 1;q->num = 0;return q;入队算法void In_SeQueue(C_SeQueue *q, Datatype x) q->rear = (q->rear + 1) % MAXSIZE

8、;q->data2q->rear = x;q->num+;return;出队算法void Out_SeQueue(C_SeQueue *q, Datatype *x)q->front = (q->front + 1) % MAXSIZE;*x = q->data2q->front;q->num-;return;算法流程图（进入车库和出车库）3 详细设计1. 数据类型用Int型整数储存车辆的信息.车辆进出时间.收取的费用2.算法的具体步骤车进入停车场的基本操作void Arrive(queue *s, C_SeQueue *q, int x, do

9、uble t) int y;int a = s->top;while (a != -1) /判断将要存的车是否已存在于停车场，防止出现有相同车牌号的车出现在停车场内；if (s->data1a = x)cout << "此车已存在停车场内！" << endl;return;elsea-;if (Push_SeqStack1(s, x, t)cout << "此车已成功存入停车场。" << endl;elsecout << "停车场已满，后来车辆请在便道等候。" &

10、lt;< endl;In_SeQueue(q, x);show(s, q);离开停车场的基本操作void Leave(queue *s, C_SeQueue *q, int x, double t) int y;int i = 1;double d;queue *s1;s1 = Init_SeqStack();while (s->data1s->top != x&&!Empty_SeqStack(s)Pop_SeqStack(s, &y);Push_SeqStack(s1, y);if (s->data1s->top = x) while

11、(i)if (t >= 1 && t <= 24 && t>s->times->top)d = t - s->times->top;Pop_SeqStack(s, &y);cout << "存车时间总计：" << d << "小时" << endl<< "收费为：" << d << "元" << endl;i = 0;elsecout &l

12、t;< "时间输入有误，请重新输入。" << endl; /时间容错处理；i = 1;cin >> t;elsecout << "车牌号有误，停车场中无此车。" << endl; /容错，离开时也要输入正确车牌号，否则无此车，也不耽误程序执行；while (Empty_SeqStack(s1) != 0)Pop_SeqStack(s1, &y);Push_SeqStack(s, y);if (q->num != 0 && s->top != MINSIZE - 1)

13、Out_SeQueue(q, &y);Push_SeqStack1(s, y, t);show(s, q);return;离开过道的基本操作void Leave1(queue *s, C_SeQueue *q, int x) if (q->num = 0)cout << "停车过道为空。" << endl;return;int a = q->rear;while (q->data2a != x && (a + MAXSIZE) % MAXSIZE != q->front)a-;if (q->dat

14、a2(a + MAXSIZE) % MAXSIZE = x)while (a + MAXSIZE) % MAXSIZE != q->rear - 1)q->data2a = q->data2a + 1;a+;q->num-;cout << "此车已成功离开过道。" << endl;elsecout << "此车不在过道中。" << endl;show(s, q);3.算法的时空分析和改进设想 每次进栈的时间复杂度为O（1），当要出车辆后有n辆车时，出栈时间复杂度为O（n），也许对于一

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

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

17、e std;#define MAXSIZE 10#define MINSIZE 2typedef int Datatype;typedef structDatatype data1MINSIZE;int top;double timeMINSIZE;queue;queue *Init_SeqStack() /栈的初始化；queue *s;s = new queue;if (!s)cout << "空间不足" << endl;return NULL;elses->top = -1;return s;int Empty_SeqStack(queue

18、 *s) /栈空判别算法；if (s->top = -1)return 0;elsereturn 1;void Push_SeqStack(queue *s, Datatype x) /入栈算法；s->top+;s->data1s->top = x;return;int Push_SeqStack1(queue *s, Datatype x, double t) /入栈算法1；if (s->top = MINSIZE - 1)return 0;elses->top+;s->data1s->top = x;s->times->top =

19、 t;return 1;void Pop_SeqStack(queue *s, Datatype *x) /出栈算法；*x = s->data1s->top;s->top-;return;typedef structDatatype data2MAXSIZE;int rear, front;int num;C_SeQueue;C_SeQueue *Init_SeQueue() /列队初始化；C_SeQueue *q;q = new C_SeQueue;q->front = q->rear = MAXSIZE - 1;q->num = 0;return q;v

20、oid In_SeQueue(C_SeQueue *q, Datatype x) /入队算法；q->rear = (q->rear + 1) % MAXSIZE;q->data2q->rear = x;q->num+;return;void Out_SeQueue(C_SeQueue *q, Datatype *x)/出队算法；q->front = (q->front + 1) % MAXSIZE;*x = q->data2q->front;q->num-;return;void show(queue *s, C_SeQueue *q

21、) /显示停车情况；cout << "停车场内有" << s->top + 1 << "辆车。" << endl;cout << "通道上有" << q->num << "辆车在等候。" << endl;void Arrive(queue *s, C_SeQueue *q, int x, double t) /停车；int y;int a = s->top;while (a != -1) /判断将要存的

22、车是否已存在于停车场，防止出现有相同车牌号的车出现在停车场内；if (s->data1a = x)cout << "成功停入车场" << endl;return;elsea-;if (Push_SeqStack1(s, x, t)cout << "成功停入车场。" << endl;elsecout << "停车场已满，后来车辆请在便道等候。" << endl;In_SeQueue(q, x);show(s, q);void Leave(queue *s, C

23、_SeQueue *q, int x, double t) /离开停车场；int y;int i = 1;double d;queue *s1;s1 = Init_SeqStack();while (s->data1s->top != x&&!Empty_SeqStack(s) Pop_SeqStack(s, &y);Push_SeqStack(s1, y);if (s->data1s->top = x) while (i)if (t >= 1 && t <= 24 && t>s->time

24、s->top)d = t - s->times->top;Pop_SeqStack(s, &y);cout << "存车时间总计：" << d << "小时" << endl<< "收费为：" << d << "元" << endl;i = 0;elsecout << "时间输入有误，请重新输入。" << endl; /时间容错处理；i = 1;cin

25、 >> t;elsecout << "车牌号有误，停车场中无此车。" << endl; /容错，离开时也要输入正确车牌号，否则无此车，也不耽误程序执行；while (Empty_SeqStack(s1) != 0)Pop_SeqStack(s1, &y);Push_SeqStack(s, y);if (q->num != 0 && s->top != MINSIZE - 1)Out_SeQueue(q, &y);Push_SeqStack1(s, y, t);show(s, q);return;void Leave1(queue *s, C_SeQueue *q, int x) /离开过道；if (q->num = 0)cout << "停车过道为空。" << endl;return;int a = q->rear;while (q->data2a != x && (a +