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

HUNAN UNIVERSITY
课程实习报告
题 目： 停车场管理问题
学生姓名
学生学号
专业班级
指导老师李晓鸿
完 成 日 期2 0 1 5年 11 月 25日
一、 需求分析
1. 输入的形式的输入的范围：
①．选择功能：1停车 2离开停车场 3离开过道
②．若输入1（停车)，输入当前车牌号和当前的时间；
若输入2（离开停车场），输入车票号和当前时间；
若输入3（离开过道）,输入车牌号.
2. 输出的形式：
①．提示选择功能“1。停车 2离开停车场 3离开过道”。
②．若输入1（停车），并且输入当前车牌号和当前的时间后，若停车场未满，输出“成功 停入停车场，停车场内有n辆车，过道上有m辆车等候"；若停车场满，输出 “停 车场已满,请在过道等候"。
若输入2（离开停车场)，输入车票号和当前时间，输出“存车总计时间，收费q元, 停车场内有n辆车，过道上有m辆车等候”；如果进停车场和出停车场时间错误，输 出“时间输入有误，请重新输入”；如果停车场没有此车，输出“车牌号有误，请重新 输入"。
若输入3（离开过道），输入车牌号,输出“此车已成功离开过道"；若无此车,输出 “停车过道为空"。
若输入其他，则提示选择功能“1。停车 2离开停车场 3离开过道”。
3. 程序所能达到的功能：
有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出.车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后,这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。
4. 测试数据:
①正常的进入停车场，出停车场,离开过道的模拟
输入1
1（车牌）
1(当前时间）
输入 1
2（车牌）
2(当前时间)
输入2
2（车牌）
3（当前时间）
输入1
3（车牌）
4（当前时间）
输入1
4(车牌)
5（当前时间）
输入3
4（车牌）
②．停车场里没有车出停车场的模拟
输入2
1（车牌)
③．过道没车出过道的模拟
输入3
1（车牌）
④．进入停车场时间与出停车场时间的模拟
输入1
1(车牌）
1（进停车场的时间）
输入2
1(车牌）
0(出停车场的时间）
⑤．停车场模拟系统功能输入错误
输入4
二。概要设计
抽象数据类型：
①．由于该停车场只有一个门供出入，并且最先进的停在停车场的最末，最先进的车辆要出停车场需要之后进入的车先出，满足先进后出的结构，其限制是仅允许在表的一端进行插入和删除运算，所以用栈来模拟停车场.
②．由于这是一个模拟的车库，车辆出停车场，后面车辆不得不被动跟着出停车场，我们需要对这些车辆进行管理,将第一辆被动出停车场的放置到一个队伍的前端,接下来被动出停车场的车辆依次放到第一辆车之后，当需要离开的车出栈后,对被动出停车场的车辆进行管理,又队伍的前端依次进入停车场，由于满足只允许在表的前端进行删除操作,而在表的后端进行插入操作，所以用队列来模拟被动出停车场车辆的管理。
基本思想
1。给定一个size为停车场的容量.
2.每一辆车进栈前，储存车辆编号和进栈的时间。
3。对于栈满的情况,再来的车辆不进栈，只记录编号。
4.对于出栈的车辆，先将出栈车辆之前的停车场内车辆由后往前依次进入队列中，将进栈和出栈时间相比较算出需要付的金额，之后再将队列中的元素由前往后依次进栈.
程序的流程
程序由三个模块组成:
输入模块：按照提示输入
计算模块：计算(出栈时间—进栈时间）＊每小时金额。
输出模块:首先提示 "请选择：1、停车；2、离开停车场;3、离开过道；”
选择1.2提示 ”请输入车牌号和现在的时间：”
选择3提示“请输入车牌号”
基本ADT
①．栈空判别算法
int Empty_SeqStack（queue *s)
｛
if （s—>top == -1）
return 0;
else
return 1;
｝
②．入栈算法
void Push_SeqStack（queue ＊s, Datatype x）
｛
s->top++;
s—>data1[s—>top］ = x;
return；
｝
③．出栈算法
void Pop_SeqStack（queue *s, Datatype *x）
｛
*x = s—〉data1[s—〉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；
q—〉data2［q—>rear］ = x；
q—〉num++；
return;
｝
⑥．出队算法
void Out_SeQueue(C_SeQueue ＊q, Datatype ＊x)
{
q—〉front = （q—〉front + 1） ％ MAXSIZE；
＊x = q—〉data2[q->front］；
q—〉num--；
return；
｝
算法流程图（进入车库和出车库）

三． 详细设计
1. 数据类型
用Int型整数储存车辆的信息。车辆进出时间。收取的费用
2.算法的具体步骤
①车进入停车场的基本操作
void Arrive（queue ＊s, C_SeQueue ＊q， int x， double t)
{
int y；
int a = s—〉top;
while (a != —1） //判断将要存的车是否已存在于停车场，防止出现有相同车牌号的车出现在停车场内；
{
if （s—>data1［a］ == x)
｛
cout 〈〈 "此车已存在停车场内！” 〈〈 endl;
return;
}
else
a—-；
｝
if （Push_SeqStack1（s， x， t)）
cout << "此车已成功存入停车场。" << endl；
else
{
cout <〈 "停车场已满，后来车辆请在便道等候。" 〈〈 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—〉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 <= 24 ＆＆ t>s-〉time[s—〉top]）
｛
d = t — s—〉time［s—〉top]；
Pop_SeqStack(s， ＆y）；
cout 〈< "存车时间总计：” 〈< d <〈 ”小时" <〈 endl
<< "收费为：" 〈〈 d << "元" 〈〈 endl;
i = 0；
｝
else
{
cout << "时间输入有误，请重新输入。” 〈< endl; //时间容错处理；
i = 1；
cin 〉> t；
}
｝
｝
else
｛
cout << "车牌号有误，停车场中无此车。" 〈〈 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-〉data2［a］ != x &＆ (a + MAXSIZE） ％ MAXSIZE ！= q—>front）
a—-;
if (q—>data2［（a + MAXSIZE） ％ MAXSIZE］ == x)
｛
while （(a + MAXSIZE） % MAXSIZE != q->rear — 1)
｛
q—>data2［a] = q—>data2[a + 1];
a++；
｝
q—>num——；
cout <〈 "此车已成功离开过道。” << endl;
}
else
cout << ”此车不在过道中。” << endl；
show（s, q）;
}
3。算法的时空分析和改进设想
每次进栈的时间复杂度为O（1)，当要出车辆后有n辆车时，出栈时间复杂度为O（n）,也许对于一个车库来说n并不会很大,但是考虑实际这个停车场的设计非常不合理。
4。输入和输出格式
输入:功能选择输入为整数1—3，输入车牌号为大于零的整数，时间为大于零的整数。
输出：输出整数型的应收的价格
四． 调试分析
1. 为了简化程序，采用手动输入进栈车辆的排序。进栈时间。出栈时间.
2. 同时因为需要输入多组数据，在程序完工后又加上许多引导性的话,例如提示停车场内有几辆车。停车场外有多少车.车辆是否进入车库成功.车辆是否在车库外等候.
3. 对于时间的处理过于简陋，只用了一位数表示时间，与实际情况不太符合.
4. 对于车牌处理也过于简单，可以在车的储存信息加入车牌号。
五． 测试结果
情况1测试结果
情况2测试
情况3测试
情况4测试
情况5测试
六． 试验心得
1.书上对栈的实现太少不详细，查阅了许多栈的各类实现怎么写.
2。存车取车问题比较简单，在程序完成后发现程序的容错率为0，当不小心输入了相同车牌时程序直接报错，不得不添加了许多容错代码,容错程序代码很是让人费神,现在容错已完善再完善了，但还是未能完全解决问题，例如,在过道停的车辆不能保证其中没有相同车牌号的车，还有时间处理的比较简单原始化，这些都有待以后提高,继续完善。
3。这道题过于死板,完全是为了栈强行设计了一道门的停车场,每次有车出来后面的车都要移动位置，这种车库，不停也罢。
七．代码
＃include〈iostream>
usingnamespace std;
#defineMAXSIZE 10
#defineMINSIZE 2
typedefintDatatype;
typedefstruct{
Datatype data1[MINSIZE］；
int top;
double time[MINSIZE]；
}queue;
queue ＊Init_SeqStack（） //栈的初始化；
{
queue ＊s；
s = newqueue；
if （！s){
cout << "空间不足” 〈< endl；
returnNULL；
｝
else｛
s—〉top = —1;
return s；
｝
}
int Empty_SeqStack（queue *s) //栈空判别算法;
{
if （s-〉top == —1）
return 0；
else
return 1；
｝
void Push_SeqStack(queue ＊s, Datatypex) //入栈算法;
｛
s->top++;
s—〉data1［s->top］ = x；
return；
｝
int Push_SeqStack1（queue ＊s, Datatypex, doublet) //入栈算法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(queue ＊s, Datatype ＊x） //出栈算法；
｛
＊x = s—〉data1［s—>top]；
s—>top——;
return;
}
typedefstruct
｛
Datatype data2[MAXSIZE］；
int rear， front;
int num；
｝C_SeQueue;
C_SeQueue *Init_SeQueue(） //列队初始化;
{
C_SeQueue *q;
q = newC_SeQueue;
q->front = q—>rear = MAXSIZE — 1；
q—〉num = 0;
return q；
｝
void In_SeQueue(C_SeQueue *q， Datatypex） //入队算法；
｛
q—>rear = （q-〉rear + 1) ％ MAXSIZE；
q—〉data2［q->rear] = x;
q->num++;
return；
｝
void Out_SeQueue(C_SeQueue ＊q, Datatype ＊x)//出队算法；
｛
q—〉front = (q—〉front + 1） ％ MAXSIZE；
＊x = q—〉data2［q->front]；
q—>num-—;
return；
｝
void show（queue ＊s， C_SeQueue ＊q） //显示停车情况；
｛
cout <〈 ”停车场内有” << s-〉top + 1 〈〈 ”辆车。” 〈〈 endl；
cout 〈〈 ”通道上有” 〈< q-〉num << ”辆车在等候。” 〈< endl;
}
void Arrive（queue ＊s， C_SeQueue *q， intx, doublet） //停车；
｛
int y；
int a = s->top;
while (a != —1） //判断将要存的车是否已存在于停车场，防止出现有相同车牌号的车出现在停车场内;
｛
if (s—>data1［a] == x)
｛
cout 〈< "成功停入车场" 〈< endl；
return;
｝
else
a-—；
｝
if （Push_SeqStack1(s， x， t））
cout << ”成功停入车场。" << endl；
else
｛
cout 〈〈 ”停车场已满,后来车辆请在便道等候.” 〈〈 endl;
In_SeQueue（q， x）；
｝
show（s， q）；
｝
void Leave（queue ＊s, C_SeQueue ＊q， intx， doublet) //离开停车场；
｛
int y；
int i = 1；
double d；
queue *s1；
s1 = Init_SeqStack（）；
while （s—〉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 <= 24 ＆＆ t〉s—〉time［s->top］)
{
d = t - s—〉time[s—〉top］;
Pop_SeqStack（s， ＆y)；
cout 〈〈 "存车时间总计:" 〈< d <〈 ”小时” 〈< endl
<〈 ”收费为：” 〈< d 〈〈 ”元” 〈< endl;
i = 0；
}
else
｛
cout 〈〈 ”时间输入有误,请重新输入。” <〈 endl； //时间容错处理；
i = 1；
cin >〉 t;
}
｝
｝
else
｛
cout <〈 "车牌号有误,停车场中无此车。” 〈〈 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, intx) //离开过道;
{
if （q—〉num == 0）
{
cout <〈 "停车过道为空." 〈< endl；
return;
}
int a = q—>rear；
while （q—〉data2［a］ ！= x ＆& (a + MAXSIZE) % MAXSIZE ！= q—>front)
a——;
if (q—>data2[（a + MAXSIZE） ％ MAXSIZE］ == x)
｛
while （（a + MAXSIZE) ％ MAXSIZE ！= q—>rear — 1）
｛
q—〉data2［a] = q—〉data2［a + 1];
a++；
｝
q-〉num-—;
cout << ”此车已成功离开过道.” 〈< endl；
}
else
cout <〈 ”此车不在过道中。” 〈< endl；
show(s， q);
｝
void main（）
｛
double time;
int x， a;
queue *s;
C_SeQueue *q；
s = Init_SeqStack（);
q = Init_SeQueue（);
while (1）
｛
cout 〈< ”请选择:1、停车；2、离开停车场；3、离开过道；" 〈〈 endl；
cin 〉> a;
switch （a)
｛
case 1：｛
cout <〈 ”请输入车牌号和现在的时间：” << endl；
cin 〉> x >〉 time；
Arrive（s， q， x， time）；
｝break;
case 2：｛
cout <〈 "请输入车牌号和现在的时间：” <〈 endl；
cin >〉 x >〉 time；
Leave(s， q， x， time）；
｝break;
case 3：｛
cout 〈< "请输入车牌号:” <〈 endl;
cin 〉> x；
Leave1(s, q, x)；
cout 〈< endl;
｝break；
case 0:return；
｝
｝
｝