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

实验2栈和队列及其应用--------停车场管理一．需求分析设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按到达时间的先后顺序，一次由北朝向南排列（大门在最南边最先到达的第一辆汽车停放在车场最北端），若停车场已满，则以后来的汽车只能停在便道上，一旦有车辆开走，则便道上的第一辆车便可开进车场；当车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为其让路，待该车辆开出大门后，其他车辆在按原来顺序开进车场，每辆停放在车场内的车辆按其待得时间长短缴纳费用（便道上不收费）。以栈模拟停车场，以队列模拟便道，按照从终端读入的数据进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离开”的信息，汽车牌照号以及到达或离开的时间。对每一组输入数据进行操作后的输出信息为：若是车辆到达则输出汽车在停车场或在便道上的位置，若是车辆离开则输出汽车在停车场内停留的时间和需要缴纳的费用（便道不收费）。栈以顺序结构实现，队列以链表结构实现。二．概要设计1.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}数据关系：R={ai-1,ai|ai-1,ai∈D}，约定an为栈顶元素基本操作：InitStack(&S)操作结果:构造一个空栈DestroyStack(&S)初始条件:栈S已存在操作结果：销毁栈SClearStack(&S)初始条件:栈S已存在操作结果:将S清为空栈Push(&S,e)初始条件:栈S已存在操作结果：插入e到栈顶Pop(&S,&e)初始条件:栈S已存在且非空操作结果：删除栈顶元素用e返回其值StatusStackFull(SqStackS)初始条件：栈已存在操作结果：栈满则返回TRUE，否则返回FALSEStatusStackEmpty(SqStackS)初始条件：栈已存在操作结果：栈空则返回TRUE，否则返回FALSE}ADTStackr2.设定队列的抽象数据类型定义：ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}数据关系：R={ai-1,ai|ai-1,ai∈D，约定a1为队头，an为对尾部}基本操作：InitQueue(&Q)操作结果:构造一个空队列EnQueue(&Q,e)初始条件:队列Q已存在操作结果：插入e到队尾DeQueue(&Q,&e)初始条件:队列Q已存在且非空操作结果：删除队头元素用e返回其值StatusQueueEmpty(LinkQueue&Q)初始条件：队列存在操作结果：队列空为真，否则为假}ADTQueue3.本程序包含四个模块：1Voidmain(){初始化；while(1){接受用户数据；作出相应操作；}}2栈模块——实现栈抽象数据类型定义；3队模块——实现队列抽象数据类型定义4停车场有关操作三．详细设计#includestdio.h#includestdlib.h#includemalloc.h#defineTrue1#defineFalse0#defineok1#defineError0#defineInfeasible-1#defineOverflow-2//--*-*-*-*-*-*-*-*-车辆信息定义*-*-*-*-*-*-*//typedefstruct{charAD;intcar_ID;inttime;}car_info;//------------------------------------------------栈----------------------------------////Status表示函数的返回状态typedefintStatus;typedefcar_infoSElemType;#defineSTACK_INIT_SIZE4//存储空间初始分配量typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){//构造一个空栈sS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(Overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnok;}//InitStackStatusStackFull(SqStackS){//栈满则返回TRUE，否则返回FALSEif(S.top-S.base=S.stacksize)returnTrue;elsereturnFalse;}//栈满吗StatusStackEmpty(SqStackS){//栈空则返回TRUE，否则返回FALSEif(S.top==S.base)returnTrue;elsereturnFalse;}//栈空吗StatusPush(SqStack&S,SElemTypee){//插入元素e为新的栈顶元素*S.top=e;S.top++;returnok;}//PushStatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值if(S.top==S.base)returnError;S.top--;e=*S.top;returnok;}//Pop//*-**-*-*-*-*队列*-*-*-*-*-*-*-//typedefcar_infoQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(Overflow);//存储分配失败Q.front-next=NULL;returnok;}//InitQueueStatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(Overflow);//存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnok;}//EnQueueStatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回ok;//否则返回Errorif(Q.front==Q.rear)returnError;QueuePtrp;p=Q.front-next;e=p-data;Q.front-next=p-next;if(p==Q.rear)Q.rear=Q.front;free(p);returnok;}//DeQueueStatusQueueEmpty(LinkQueue&Q){if(Q.front==Q.rear)returnok;elsereturnError;}//*-*-*-*-*-*-*-*-*费用定义函数*-*-*-**-*-*-*-*//intGetFee(car_infonow,car_infobefore){intNowTime;intBeforeTime;intFee;NowTime=now.time;BeforeTime=before.time;Fee=(NowTime-BeforeTime)*10;//每分钟10元returnFee;}//-----*-*-*-*-*-*-*-*-*-*-*--*-车辆到达函数-*-*-*-*-*-*-*-*-*-*-//voidArriveF(SqStack&parking,LinkQueue&road,car_infot,int&p,int&a){if(StackFull(parking)){EnQueue(road,t);a++;printf(汽车在便道上第%d个位置\n,a);}//如果停车场栈满，则入队else{Push(parking,t);p++;printf(在停车场第%d个位置。\n,p);//不满进停车场栈，并输出位置}}//---*-*-*-*-*-*-*-*-*-*-*-*-*-*-----车辆离开函数--*-*-*-*-*-*-*-*-*-*-*-//voidDepartF(SqStack&parking,LinkQueue&road,SqStack&S,car_infot,int&p,int&a){car_infoe;inttemp;intFee;if(t.time==0)//证明在便道上{e=t;DeQueue(road,e);a--;printf(车辆%d开出便道。\n,e.car_ID);}else//在停车场{temp=(*--parking.top).car_ID;//停车场的最后一位置车牌号赋予temp++parking.top;while(temp!=t.car_ID&&!StackEmpty(parking)){Pop(parking,e);Push(S,e);//从停车场栈出来进入暂存栈temp=(*--parking.top).car_ID;//现有车辆的最后一辆++parking.top;p--;//出去一辆车就p--，表示现有最后一辆车的位置}if(StackEmpty(parking))printf(输入有误！请检查输入数据！！\n);else{Pop(parking,e);//从停车场出来，但并不进暂存栈，而应计费Fee=GetFee(t,e);printf(该车应缴费用为%d\n,Fee);//计费完毕p--;//从暂存栈进入停车场栈，并且在便道上的第一辆车开始进入停车场栈while(!StackEmpty(S))//只要暂存栈不空{Pop(S,e);Push(parking,e);//从暂存栈进入停车场栈p++;}//在便道上的第一辆车开始进入停车场站栈，并且应输入进停车场栈时间和在停车场站的位置if(!QueueEmpty(road)){DeQueue(road,e);temp=e.car_ID;printf(车辆%d出便道进停车场，请输入进停车场时间\n,temp);scanf(%d,&e.time);Push(parking,e);p++;}elseprintf(便道现已没车辆！\n);}}}//--*-*-*-*-*-*-*-主函数*-*-*-*-*-*-//voidmain(){SqStackparking;SqStackS;LinkQueueroad;InitStack(parking);InitStack(S);InitQueue(road);inti=0;inta=0;//显示在便道上的位置intp=0;//显示在停车场上的位置car_infocar[100];//用以存放每辆车的数据printf(举例说明本程序用法：\n如果输入A112,表示牌照号为1的车辆到达时间为12！\n);printf(如果输入为D112,表示牌照号为1的车辆离开停车场，离开时间为12！\n);printf(如果下班请输入E00\n);while(1){i++;printf(请输入车辆进出情况：\n);scanf(%c%d%d,&car[i].AD,&car[i].car_ID,&car[i].time);charc;c=car[i].AD;if(c=='A'){//*-*-*-***--*-*-*-*-*-*-*-*-*-*-*-**-*-*-*-*-*-*-*-*-*-*若