《创新课程设计实践
》
学院:软件学院
学号 :220600134
班级 :06 (1)班
姓名:郑志敏
2008-6-11
停车场管理问题
问题描述:设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进场。每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。
实现要求:要求程序输出每辆车到达后的停车位置(停车场或便道上),以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。
一. 需求分析
(1)要实现停车场管理的功能,建立两个栈s,dcc和一个队列Q,其中栈s模拟停车场,另一个栈s临时存放给要离开的汽车让路而从停车场退出的汽车,队列Q用来模拟停车便道。
(2)定义栈和队列的结构体,实现队列和栈的初始化以及栈,压车元素进栈,取车元素出栈,车元素入列,队头元素出列和取出队列中车元素操作。
(3)当车辆到达时,首先检查停车场是否是满的,若不满则放入停车场内,若停车场是满的,则放在便道上。即若栈是不满的就入栈,否则就入队列。
(4)当车辆离开时,首先要寻找到要离开车辆的车牌号,若车是从停车场离开,则在它之后进入的车辆必须先退出为它让路,待该辆车开出大门外,其它车辆再按原次序进入停车场,并将停放在便道上第一位置的车开进停车场,离开的车辆按其在停车场内停留的时间交费。即当元素在栈s1中时,就将在它之后的元素出栈并依序放入栈s0中,此元素出栈,随后将栈s0中的元素放入s0中,最后将队列Q的首元素放入栈s1中。
(5)若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,从停车场离去,则输出汽车应交的费用,否则停车便道直接离去,此时排在它之前的汽车要先开走让路,然后依次排到队尾。
.
(7)测试数据,当输入数据为2,5 ('A',1,5), ('A',2,10), ('D',1,15),
输出结果为:
二.概要设计
该程序主要分六个模块:定义栈和队列的结构体,实现队列和栈的初始化以及栈,压车元素进栈,取车元素出栈,车元素入列,队头元素出列和取出队列中车元素操作。
typedef struct
{int car_num;
int time;
}car_info
操作结果:定义车节点
void Initstack(sqstack *s)
操作结果: 构造一个长度为n的空栈
void push(sqstack *s,car_info e)
初始条件:栈S已经存在
操作结果:若栈不满则压一个车元素进栈,是把数据拷贝进
car_info pop(sqstack *s)
初始条件:栈S已经存在
操作结果:从栈S中取出元素e,若e不在栈顶,将栈顶元素一个一个取出放入栈S中
void EnQueue(LinkQueue *Q,car_info *a )
初始条件:存在队列Q
操作结果:将元素查入队列
QueuePtr DeQueue(LinkQueue *Q)
初始条件:存在队列Q
操作结果:从队列中取出某个要离开的元素
void arrive(sqstack *s,LinkQueue *p,car_info a,int n)
操作结果:此函数用来表示进入车辆
{ push(s,a)
操作结果:车进栈
EnQueue(p,&a)停车场已满,停通道
Void leave(sqstack *tcc,sqstack*dcc,LinkQueue *p,car_info a,float pay)
操作结果:用来出车
主程序模块:
void main(){
初始化 while(sum)
{ Initstack(&tcc);
Initstack(&dcc);
InitQueue(&p);
switch(sign)
{
case 'a':
case 'A':arrive(&tcc,&p,a,n);break;
case 'D':
case 'd':leave(&tcc,&dcc,&p,a,pay);break;
case 'e':
case 'E':exit(OVERFLOW);break;
} }
三.详细设计
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 1
栈类型
typedef int status ;
#include
#include
#include
#include
typedef struct
{int car_num;
int time;
}car_info;
typedef struct
{
car_info *base;
car_info *top;
status stacksize;
}sqstack;
void Initstack(sqstack *s)
{
s->base=(car_info *)malloc(STACK_INIT_SIZE*sizeof(car_info));
if(!s->base) exit(OVERFLOW);
s->top=s->base;
s->stacksize=0;
}
其中部分操作的算法
void push(sqstack *s,car_info e)
{
*s->top++=e;
s->stacksize++;
}
car_info pop(sqstack *s)
{car_info e;
if(s->top==s->base)
{printf("停车场内没有该车辆!\n");
exit(0) ;}
e=*--s->top;
s->stacksize--;
return e;
}
typedef struct Qnode
{
int car_num;
int time;
struct Qnode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
int lenth;
}LinkQueue;
status InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front)exit(OVERFLOW);
Q->front->next=NULL;
Q->lenth=0;
return OK;
}
void EnQueue(LinkQueue *Q,car_info *a )
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p->car_num=a->car_num;
p->time=a->time;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
Q->lenth++;
}
QueuePtr DeQueue(LinkQueue *Q)
{ QueuePtr p,e,s={0};
if(Q->front==Q->rear)
{printf("便道上没有车辆!\n"); return s;}
p=Q->front->next;
e=p;
Q->front->next=p->next;
Q->lenth--;
if(Q->rear==p)Q->front=Q->rear;
//free(p);
return e;
}
void arrive(sqstack *s,LinkQueue *p,car_info a,int n)
{
if(s->stacksizestacksize);
}
else
{
EnQueue(p,&a);
printf("\n停车场已满,车牌号为%d的车辆停在便道的%d号位置\n",a.car_num,p->lenth);
}
}
void leave(sqstack *tcc,sqstack *dcc,LinkQueue *p,car_info a,float pay)
{
car_info x,ss;
QueuePtr b;
int find=1,arrivetime=0;
float cost=0.0;
while(find)
{
ss=pop(tcc);
push(dcc,ss);
if(ss.car_num==a.car_num)
{
find=0;
cost=(a.time-ss.time)*pay;
arrivetime=ss.time;
}
}
pop(dcc); //把临时堆栈的第一辆车(要离开的)去掉;
while(dcc->stacksize)
{
x=pop(dcc);
push(tcc,x);
}
if(tcc->stacksize<2&&p->lenth!=0)
{
b=DeQueue(p);
x.car_num=b->car_num;
x.time=b->time;
push(tcc,x);
printf("车牌号为%d的车辆由便道进入停车场%d号车道\n",x.car_num,tcc->stacksize);
}
printf("\n**********************************************\n");
继续阅读