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

《栈和队列及其应用——停车场管理》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华北水利水电大学数据结构实验报告2013～2014学年第二学期2013级计算机科学与技术（专升本）专业班级：208学号：姓名：高攀实验二栈和队列及其应用一、实验题目：栈和队列及其应用——停车场管理二、实验内容：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后

2、进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停

3、车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。三、程序源代码：#include#include#defineOVERFLOW-1#defineN2#definePRICE20#defineSTACK_INIT_SIZE100//构造顺序栈结构typedefstructdata{intnum;//车牌号intAtime;//车到达时间}data;typedefstruct{data*base;第9页共9页da

4、ta*top;intstacksize;}SqStack;//构造链队列结构typedefstructQNode{intnum;//车牌号structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidInitStack(SqStack&s){//构造一个空栈ss.base=(data*)malloc(STACK_INIT_SIZE*sizeof(data));if(!s.base)e

5、xit(OVERFLOW);//存储分配失败s.top=s.base;//栈空的条件intsistacksize=STACK_INIT_SIZE;}//InitStackboolStackEmpty(SqStack&s){//若栈s为空栈，则返回TRUE，否则返回FLASEif(s.top==s.base)returntrue;elsereturnfalse;}intGetTop(SqStack&s){inte;第9页共9页//若栈不空,则用e返回s的栈顶元素，并返回OK;否则返回ERRORif(s.top==s.base

6、)returnfalse;e=(s.top-1)->Atime;returne;//返回车进站的时间}//GetTopvoidPush(SqStack&s,inte,inte1)//e表示车牌号e1表示车进站时间{//插入元素e为新的栈顶元素s.top->num=e;s.top->Atime=e1;s.top++;}//PushintPop(SqStack&s){inte;//删除s的栈顶元素，用e返回其值s.top--;e=s.top->num;returne;//返回车牌号}//Pop//---------------

7、------------------voidInitQueue(LinkQueue&q){//构造一个空队列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode));if(!q.front)exit(OVERFLOW);q.front->next=NULL;}voidEnQueue(LinkQueue&q,inte)//e表示车牌号{第9页共9页//插入元素e为q的新的队尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(

8、OVERFLOW);//存储分配失败p->num=e;p->next=NULL;q.rear->next=p;q.rear=p;}intDeQueue(LinkQueue&q){inte;//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERRORif(q.front==q.rear