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

第1页共9页数据结构实验报告实验二栈和队列及其应用一、实验题目：栈和队列及其应用——停车场管理二、实验内容：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。三、程序源代码：#includestdio.h#includestdlib.h#defineOVERFLOW-1#defineN2#definePRICE20#defineSTACK_INIT_SIZE100//构造顺序栈结构typedefstructdata{intnum;//车牌号intAtime;//车到达时间}data;typedefstruct{data*base;data*top;intstacksize;第2页共9页}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)exit(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;//若栈不空,则用e返回s的栈顶元素，并返回OK;否则返回ERRORif(s.top==s.base)returnfalse;第3页共9页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//---------------------------------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表示车牌号{//插入元素e为q的新的队尾元素QueuePtrp;第4页共9页p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(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)returnfalse;QueuePtrp;p=q.front-next;e=p-num;q.front-next=p-next;if(q.rear==p)q.rear=q.front;free(p);returne;//返回车牌号}boolQueueEmpty(LinkQueue&q){//若队列q为空队列，则返回TRUE，否则返回FLASEif(q.front==q.rear)returntrue;elsereturnfalse;}voidCar(SqStack&s0,SqStack&s1,LinkQueue&q,intn){//构造两个空栈s0s1一个空链队列qInitStack(s0);InitStack(s1);第5页共9页InitQueue(q);charsolu;//车的状态：到达(A),离开(D),结束(E)intcount=0,Atime,Dtime,num,e,e1,m=0;//count停车场的车辆数Atime车进站时刻Dtime车离开时间num车牌号e返回的车牌号e1返回的车进站时刻while(m==0){printf(请输入车的状态：到达(A),离开(D),结束(E)\n);scanf(%c,&solu);if(solu=='A'){printf(请输入车牌号以及车到达的时刻(1-24)：\n);scanf(%d%d,&num,&Atime);if(count=n)//停车场满了，车停进门外的便道即链队列{EnQueue(q,num);printf(停车场满了，车牌号为%d的车停进门外的便道!\n,num);}if(countn)//停车场未满，车进站即进入栈s1{printf(车牌号为%d的车进站！\n,num);Push(s0,num,Atime);count++;}}m=0;if(solu=='D'){printf(请输入车牌号以及车离开的时刻：\n);scanf(%d%d,&num,&Dtime);while(!StackEmpty(s0))第6页共9页{e1=GetTop(s0);//得到栈顶元素到达时间e=Pop(s0);//得到栈顶元素车牌号if(e==num){printf(车牌号为%d的车出站!\n,num);printf(输出该车在停车场停留的时间以及要付的费用：\n);printf(%d%d\n,Dtime-e1,(Dtime-e1)*PRICE);count--;while(!StackEmpty(s1)){e1=GetTop(s1);e=Pop(s1);printf(车牌号为%d的车由临时车站进入车站!\n,e);Push(s0,e,e1);count++;}if(!QueueEmpty(q)){e=DeQueue(q);printf(车牌号为%d的车进站！\n,e);printf(输入车牌号为%d的车的由便道进入车站的时间!\n,e);scanf(%d,&Atime);Push(s0,e,Atime);count++;}break;}else第7页共9页{printf(车牌号为%d的车进入临时车站!\n,e);Push(s1,e,e1);count--;}}m=0;}if(solu=='E'){printf(停车场关门，输出停车场以及便道上车的信息！\n);while(!StackEmpty(s0)){e1=GetTop(s0);//得到栈顶的元素中的到达时间e=Pop(s0);//得到栈顶的元素中的车牌号printf(输出车牌号为%d的车在停车场停留的时间以及要付的费用：\n,e);printf(%d%d\n,24-e1,(24-e1)*PRICE);}while(!QueueEmpty(q)){e=DeQueue(q);printf(输出在便道上的车的车牌号：%d\n,e);}m=1;}}}intmain(){voidCar(SqStack&s0,SqStack&s1,LinkQueue&q,intn);SqStacks0,s1;第8页共9页LinkQueueq;Car(s0,s1,q,N);return0;}四、测试结果：第9页共9页五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）车进站这个实验花费了我相当多的时间，虽然老师给了我们做题的思路，但由于我栈的内容没学扎实，因此在计算停车时间的时候遇到了不能解决的问题，后来参考了网上的做法才知道栈里面可以存放节点，这个问题才得以解决。后来也遇到了一些问题，但都通过努力解决了。注：内容一律使用宋体五号字，单倍行间距