栈和队列及其应用——停车场管理.doc

华北水利水电学院 数据结构 实验报告20122013学年 第 一 学期 2010级 计算机科学与技术 专业班级：2010136 学号：201013624 姓名： 柴有为 实验二 栈和队列及其应用一、 实验题目：栈和队列及其应用停车场管理二、 实验内容：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。三、 程序源代码：#include#include#includetypedef structlong* base;long* top;int stacksize;SqStack;typedef struct QNodelong data;struct QNode* next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;int lenth;LinkQueue;bool InitStack(SqStack &S,int capacity)S.base=(long*)malloc(10 * sizeof(long);if(!S.base)exit(1);S.top=S.base;S.stacksize=capacity;return 1;/InitStackbool Push(SqStack &S,long e)if(S.top-S.base=S.stacksize)S.base=(long*)realloc(S.base,(S.stacksize+10)*sizeof(long);if(!S.base)exit(1);S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=e;return 1;/Pushbool Pop(SqStack &S,long &e)if(S.top=S.base) return 0;e=*-S.top;return 1;/Popbool InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(1);Q.front-next=NULL;Q.lenth=0;return 1;bool EnQueue(LinkQueue &Q,long e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(1);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;Q.lenth+;return 1;bool DeQueue(LinkQueue &Q,long &e)QueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);Q.lenth-;return 1;void park(SqStack &a,LinkQueue &b,int capacity)if(a.top-a.base)=a.top|tp1;p-)Pop(a,e);Push(s,e);Pop(a,e);rt=difftime(n,e);printf(停车时间为%d秒,应交费%lf元n,rt,(double)(rt)*单价/3600);for(p=s.top;ps.base;p-)Pop(s,e);Push(a,e);void WaitingCarEnter(SqStack &a,LinkQueue &b)long e;DeQueue(b,e);Push(a,e);printf(便道车进站n);void SetPrice(double &a)while(true)printf(请设定单价（元/小时）：);scanf(%lf,&a);getchar();if(a0)printf(单价为%lf元/小时n,a);break;elseprintf(输入值无效！n);void SetCapacity(int &a)while(true)printf(当前停车场容量为%d,请设定容量：,a);scanf(%d,&a);getchar();if(a0)printf(当前容量为:%dn,a);break;elseprintf(输入值无效！n);void main()char a;int n;int capacity=5;double 单价;SqStack s0,s1;LinkQueue q;InitStack(s0,capacity);InitStack(s1,capacity);InitQueue(q);printf(-停车场管理程序-n);printf(命令：p停车，l取车，g停车数量，e停车场扩容，s重设单价，c清空屏幕n);SetPrice(单价);while(true)printf(请输入命令：);a=getchar();getchar();switch(a)case P:case p:park(s0,q,capacity);break;case L:case l:printf(请输入取车车位号:);scanf(%d,&n);getchar();leave(s0,s1,n,单价);break;case G:case g:printf(当前场内停有%d辆车，便道内有%d辆车n,s0.top-s0.base,q.lenth);break;case S:case s:SetPrice(单价);break;case E:case e:SetCapacity(capacity);break;case C:case c:system(cls);printf(-停车场管理程序-n);printf(命令：p停车，l取车，g停车数量，e设置容量，s重设单价，c清空屏幕n);break;while(q.front!=q.rear&s0.top-s0.basecapacity)WaitingCarEnter(s0,q);