中法计122班实验二剖析.docx
《中法计122班实验二剖析.docx》由会员分享，可在线阅读，更多相关《中法计122班实验二剖析.docx（15页珍藏版）》请在冰点文库上搜索。
中法计122班实验二剖析
数据结构实验二
停车场管理
【实验内容】
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。
每一组输入数据包括三个数据项：
汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
对一组输入数据进行操作后的输出信息为：
若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。
栈以顺序结构实现。
队列以链表结构实现。
【实验目的】
（1）深入了解栈和队列的特性，掌握栈和队列的存储方法。
（2）掌握栈和队列的基本操作，如初始化、入栈（队列）、出栈（队列）等，并能在实际问题背景下灵活运用。
【程序清单】
#include
#include
#include
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineTRUE1
#defineFALSE0
typedefintStatus;
intsi;
//栈，模拟停车场
typedefstructCar1{//车
intnumber;//汽车车号
intar_time;//汽车到达时间
}CarNode;
typedefstruct{//停车场
CarNode*base;//停车场的堆栈底
CarNode*top;//停车场的堆栈顶
intstacksize;
}Park;
//队列，模拟便道
typedefstructCar2{//车
intnumber;//汽车车号
intar_time;//汽车到达时间
structCar2*next;
}*CarPtr;
typedefstruct{//便道
CarPtrfront;//便道的队列的对头
CarPtrrear;//便道的队列的队尾
intlength;
}Shortcut;
StatusInitStack（Park&P）{//初始化停车场
P.base=（CarNode*）malloc（si*sizeof（Car1））;
if（!
P.base）exit（OVERFLOW）;
P.top=P.base;
P.stacksize=0;
returnOK;
}
StatusPush（Park&P,CarNodee）{//车进入停车场
*P.top++=e;
++P.stacksize;
returnOK;
}
StatusPop（Park&P,CarNode&e）{//车离开停车场
if（P.top==P.base）
printf（"停车场为空。
"）;
else
{
e=*--P.top;
--P.stacksize;
}
returnOK;
}
StatusInitQueue（Shortcut&S）{//初始化便道
S.front=S.rear=（CarPtr）malloc（sizeof（Car2））;
if（!
S.front||!
S.rear）exit（OVERFLOW）;
S.front->next=NULL;
S.length=0;
returnOK;
}
StatusEnQueue（Shortcut&S,intnumber,intar_time）{//车进入便道
CarPtrp;
p=（CarPtr）malloc（sizeof（Car2））;
if（!
p）exit（OVERFLOW）;
p->number=number;
p->ar_time=ar_time;
p->next=NULL;
S.rear->next=p;
S.rear=p;
++S.length;
returnOK;
}
StatusDeQueue（Shortcut&S,CarPtr&w）{//车离开便道
if（S.length==0）
printf（"通道为空。
"）;
else
{
w=S.front->next;
S.front->next=S.front->next->next;
--S.length;
}
returnOK;
}
StatusArrival（Park&P,Shortcut&S）{//对进站车辆的处理
intnumber,ar_time;
printf（"请输入车牌号：
"）;
scanf（"%d",&number）;
printf（"进场的时刻:
"）;
scanf（"%d",&ar_time）;
if（P.stacksize{
CarNodec;
c.number=number;
c.ar_time=ar_time;
Push（P,c）;
printf（"该车应停在第%d号车道。
\n",P.stacksize）;
}
else
{
EnQueue（S,number,ar_time）;
printf（"停车场已满，请暂时停在便道的第%d个位置。
\n",S.length）;
}
returnOK;
}
StatusLeave（Park&P,Park&P1,Shortcut&S）{//对出站的车辆进行管理
intnumber,le_time,flag=1,money,ar_time;
printf（"请输入车牌号：
"）;
scanf（"%d",&number）;
printf（"出场的时刻:
"）;
scanf（"%d",&le_time）;
CarNodee,m;
CarPtrw;
while（P.stacksize）
{
Pop（P,e）;
if（e.number==number）
{
flag=0;
money=（le_time-e.ar_time）*2;
ar_time=e.ar_time;
break;
}
Push（P1,e）;
}
while（P1.stacksize）
{
Pop（P1,e）;
Push（P,e）;
}
//车从停车场中出
if（flag==0）
{
if（S.length!
=0）
{
DeQueue（S,w）;
m.ar_time=le_time;
m.number=w->number;
Push（P,m）;
free（w）;
printf（"车牌号为%d的车已由便道进入停车场\n",m.number）;
}
printf（"停车费为%d,占用车位数为%d\n",money,P.stacksize）;
}
else
{
printf（"停车场不存在牌号为%d的车\n",number）;
}
returnOK;
}
intmain（）
{
printf（"请输入停车场容量：
"）;
scanf（"%d",&si）;
intm=1;
charflag;//选项
ParkP,Q;
ShortcutS;
InitStack（P）;
InitStack（Q）;
InitQueue（S）;
while（m）
{
printf（"\n欢迎进入停车场管理程序\n"）;
printf（"===============================================\n"）;
printf（"**A汽车进车场**\n"）;
printf（"****\n"）;
printf（"**D汽车出车场**\n"）;
printf（"****\n"）;
printf（"**E退出程序**\n"）;
printf（"===============================================\n"）;
printf（"请选择您的动作（A,D,E）:
"）;
scanf（"%c",&flag）;
switch（flag）
{
case'A':
case'a':
Arrival（P,S）;break;//车进入停车场
case'D':
case'd':
Leave（P,Q,S）;break;//车离开停车场
case'E':
case'e':
m=0;
break;
default:
printf（"Inputerror!
\n"）;
break;
}
//while（flag!
='\n'）
scanf（"%c",&flag）;
}
}
【调试步骤】
1.输入停车场容量si
2.输入您希望的操作A进入停车场D离开停车场E结束操作
3.若输入为A则请输入您希望的车牌号和您的停车时间——则显示您的所在车位。
若无空位则显示须在几号便道等位。
4.若输入为D则会显示你所交停车费，和之后几号等候车可以进入停车场的几号车位
5.如此循环，知道用户输入E终止操作。
【算法的基本思想】
1、对于指定大小的停车场，其只有一端出口，先进后出，用栈存储；
超过停车场容量的车停在便道上，先进先出，用队列存储；
当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入车场，需要一个临时栈存储。
2、每进入一辆车，进行入栈操作，即停车场；如果入栈不成功则入队列StatusEnQueue，即便道。
每离开一辆车：
1）要对在该车之后进入的车辆进行弾栈操作，出栈的元素依次存入另一个临时堆栈，即为离开车辆开道。
2）在对该车进行出栈操作后，再将临时堆栈的元素弹回原栈。
3）通过离开时间与该车储进入车库中的到达时间差获得停车时间以及费用（费用的计算根据2元/小时）。
计算公式为money=（le_time-e.ar_time）*2;
4）此时如果队列不为空，表明便道上有车待入，修改此待入车辆的到达时间为离开车的离开时间，并进行入栈操作。
当输入不为‘E’时，循环进行上述操作。
【具体步骤】
车辆进入A：
StatusPush（Park&P,CarNodee）{//车进入停车场
*P.top++=e;
++P.stacksize;
returnOK;
}
停车场仍有空余，入栈成功：
if（P.stacksize{
CarNodec;
c.number=number;
c.ar_time=ar_time;
Push（P,c）;
printf（"该车应停在第%d号车道。
\n",P.stacksize）;
}
停车场已满，入栈失败，则入队列：
EnQueue（S,number,ar_time）;
printf（"停车场已满，请暂时停在便道的第%d个位置。
\n",S.length）;
车辆离开D：
离开停车场
StatusPop（Park&P,CarNode&e）{//车离开停车场
if（P.top==P.base）
printf（"停车场为空。
"）;
else
{
e=*--P.top;
--P.stacksize;
}
returnOK;
}
后来车进入便道
StatusEnQueue（Shortcut&S,intnumber,intar_time）{
CarPtrp;
p=（CarPtr）malloc（sizeof（Car2））;
if（!
p）exit（OVERFLOW）;
p->number=number;
p->ar_time=ar_time;
p->next=NULL;
S.rear->next=p;
S.rear=p;
++S.length;
returnOK;
}
原在便道上的车入栈
StatusDeQueue（Shortcut&S,CarPtr&w）{
if（S.length==0）
printf（"通道为空。
"）;
else
{
w=S.front->next;
S.front->next=S.front->next->next;
--S.length;
}
returnOK;
}
【运行结果】
【分析与思考】
通过这次实验，让我对栈和队列的这两种常用的数据结构有了更好的认识，达到了实验目的，栈是后进先出，队列是先进先出。
由于时间仓促和个人能力有限，程序中仍有一些不足，容错性能还有待提高。
升级会员 