停车场管理问题

实验二：停车场管理问题一．问题描述1.实验题目：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3.测试数据：设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。二．需求分析1.程序所能达到的基本可能：程序以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。同时另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达”（‘A’表示）信息，汽车标识（牌照号）以及到达时刻时，应输出汽车在停车场内或者便道上的停车位置；当输入数据包括数据项为汽车的“离去”（‘D’表示）信息，汽车标识（牌照号）以及离去时刻时，应输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）；当输入数据项为（‘P’，0，0）时，应输出停车场的车数；当输入数据项为（‘W’,0,0）时，应输出候车场车数；当输入数据项为（‘E’,0,0），退出程序；2.输入输出形式及输入值范围：程序运行后进入循环，显示提示信息：“请输入停车场最大容量n=:”，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息（“到达”或者“离开”，车牌编号，到达或者离开的时间）。若车辆信息为“到达A”，车辆信息开始进栈(模拟停车场），当栈满，车辆会进队列（模拟停车场旁便道），若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入（‘P’，0，0），会显示停车场的车数；若输入（‘W’，0，0），会显示便道上的车数；若输入（‘E’，0，0），程序会跳出循环，同时程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开3.测试数据要求：设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。三．概要设计1.所用到得数据结构及其ADT为了实现上述功能，该程序以顺序栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以链表队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。顺序栈数据类型定义typedefstructStack{structNodedata[MaxSize];inttop;intnum;}SqStack;基本操作：SqStack*Init_SeqStack()//置空栈intISEmpty_SeqStack(SqStack*s)//判断栈是否为空，栈为空返回1intISFULL_SeqStack(SqStack*s,intn)//判断栈是否已满，若栈满返回1voidPush_SeqStack(SqStack*p,structNodes)//入栈intPOP_SeqStack(SqStack*s,structNodecar)//出栈2.链表队列数据类型定义QNODE//队列节点{structNodedata;QNODE*next;};typedefstructlinkqueue//队列结构体定义{QNODE*front,*rear;intnum;}LinkQueue;基本操作：LinkQueue*Init_LQueue()//创建空队列intISEmpty_LQueue(LinkQueue*q)//判断队列是否为空，队列为空返回1voidIN_Lqueue(LinkQueue*q,structNodes)//入队structNodeOut_LQueue(LinkQueue*q)//出队2.主程序流程及其模块调用关系1)主程序模块开始初始界面显示输入停车场最大容量n输入车辆信息car.AL=='A'car.AL=='D'car.AL='P'，car.NO=0，car.time=0car.AL='W'，car.NO=0，car.time=0car.AL!='E'栈满进入队列输出车辆在便道的位置入栈，输出车辆在停车场的位置出栈，输出车辆停留时间队列为空进栈，车辆从便道进入停车场显示停车场的车数显示候车场的车数输入结束结束输入车辆信息NYYYYYNNNN2)出栈开始找到车牌号为P.NO的车，驶出停车场计算停留时间输出候车场为空候车场驶入停车场结束NY3）判断栈是否为空开始s-top==-1栈空返回1栈不为空返回0结束YN4）判断栈是否已满开始s-top=n-1栈满返回1栈不满返回0结束NY5）判断队列是否为空开始q-front==q-rear队列空返回1队列不为空返回0结束NY6）出队开始q-front-next==NULLq-rear=q-front;结束NYp=q-front-next;q-front-next=p-next;q-num--;函数调用：main()函数中调用：ISFULL_SeqStack(parkstack,n)，IN_Lqueue(parkqueue,car);Push_SeqStack(parkstack,car);t=POP_SeqStack(parkstack,car);ISEmpty_LQueue(parkqueue)==0；Push_SeqStack(parkstack,Out_LQueue(parkqueue));POP_SeqStack(SqStack*s,structNodecar)出栈函数中调用：Init_SeqStack();Push_SeqStack(p,s-data[s-top]);ISEmpty_SeqStack(p)==0函数调用关系图main()函数ISFULL_SeqStack()Push_SeqStack()ISEmpty_LQueue()POP_SeqStack()IN_Lqueue()Push_SeqStack()Init_SeqStack();四、详细设计1.实现每个操作的伪码，重点语句加注释1）主程序模块intmain(){SqStack*parkstack;//parkstack为表示停车场的栈LinkQueue*parkqueue;//parkqueue为表示便道的队列structNodecar;intn,a=0,t;//n为停车场栈的最大容量time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue();printf(/*************************************/\n);//初始界面printf(学号：031350102\n);printf(姓名：王亚文\n);printf(停车场管理问题\n);printf(/*************************************/\n);printf(请输入停车场最大容量n=\n);scanf(%d,&n);printf(请输入车辆信息\n);scanf(%c,%d,%d,&car.AL,&car.NO,&car.time);while(car.AL!='E'){if(car.AL=='A'){//汽车到达的情况if(ISFULL_SeqStack(parkstack,n)==1)//栈满的情况{IN_Lqueue(parkqueue,car);//进入队列等待printf(这辆车在门外便道上第%d个位置\n,parkqueue-num);printf(\n);printf(请输入车辆信息\n);}else{Push_SeqStack(parkstack,car);//入栈printf(这辆车在停车场内第%d个位置\n,parkstack-num);printf(\n);printf(请输入车辆信息\n);}}if(car.AL=='D')//汽车离开的情况{t=POP_SeqStack(parkstack,car);//出栈printf(这辆车停留时间为%d\n,t);printf(\n);printf(请输入车辆信息\n);if(ISEmpty_LQueue(parkqueue)==0)//队列不为空需要进栈Push_SeqStack(parkstack,Out_LQueue(parkqueue));}if(car.AL=='P'&&car.NO==0&&car.time==0)//显示停车场的车数{printf(停车场的车数为%d\n,parkstack-num);printf(\n);printf(请输入车辆信息\n);}if(car.AL=='W'&&car.NO==0&&car.time==0)//显示候车场的车数{printf(候车场的车数为%d\n,parkqueue-num);printf(\n);printf(请输入车辆信息\n);}scanf(%c,%d,%d,&car.AL,&car.NO,&car.time);}printf(输入结束\n);return1;}2）置空栈模块SqStack*Init_SeqStack()//置空栈{SqStack*s;s=(SqStack*)malloc(sizeof(SqStack));s-top=-1;s-num=0;returns;}3）创建空队列模块LinkQueue*Init_LQueue()//创建空队列{LinkQueue*q;QNODE*p;q=(LinkQueue*)malloc(sizeof(LinkQueue));p=(QNODE*)malloc(sizeof(QNODE));p-next=NULL;q-front=q-rear=p;q-num=0;returnq;}4）判断栈是否为空模块intISEmpty_SeqStack(SqStack*s)//判断栈是否为空，栈为空返回1{if(s-top==-1)return1;elsereturn0;}5）判断栈是否已满模块intISFULL_SeqStack(SqS