实验二、停车场管理系统.doc

实验二:停车场管理问题一、 问题描述1、实验题目： 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车停在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可进入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原来的次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。2、基本要求： 为停车场编制按上述要求进行管理的模拟程序。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、本程序是模拟现实生活中的停车场管理系统，有较强的实用性，及较高的可靠性。2、该程序具有友好的用户界面，操作多样，管理方面。3、用户根据提示选择相应的操作，并根据提示输入每辆车的信息。三、 概要设计1、停车场的管理流程分析：当车辆进入停车场时，首先检查停车场是否已满，若未满，车辆进入停车场，若已满，车辆进入便道等候。当车辆要求离开时，先让在它之后进入的车辆退出停车场为它让路，再让该车退出停车场，之后，让路的所有车辆再按其原来进入停车场的次序进入停车场。再检查便道上是否还有车等候，有车则让最先等候的那辆车进入停车场。2、数据结构分析 由于停车场只有一个大门，当停车场内某辆车要离开时，在它之后的车辆必须先退出停车场为它让路，先进停车场的后退出，符合“先进后出”的特点，所以用一个栈来模拟停车场。 当停车场满了后，后来的车辆都要到便道上等候，先排队的车辆先离开便道进入停车场，符合队列的“先进先出”的特点，所以用一个队列来模拟便道。 由于停车场中的车辆可以随时离开，当车辆要离开时，在它后面的车辆都要先退出停车场，所以要再设置一个辅助栈来模拟车辆退出停车场。 综上所述，求解本题用到了两个栈和一个队列。栈以顺序结构模拟，队列一链式结构模拟。抽象数据类型的定义 #define Parking struct parkingADT Parking 数据对象：D= |Parking, i=1,2,3. 数据关系：R= ADT Parking;#define Assistant struct assistantADT Assistant 数据对象：D= |Assistant, i=1,2,3. 数据关系：R= ADT Assistant;#define Qnode struct qnodeADT Qnode 数据对象：D= |Qnode, i=1,2,3. 数据关系：R= ADT Qnode;#define LinkQueue struct linkqueueADT LinkQnode 数据对象：D= |LinkQnode, i=1,2,3. 数据关系：R= ADT LinkNode; 自定义函数 void Print_Parking(Parking *p)/打印停车场中所停的车辆信息for() coutendl; void In_Parking(Parking *p,int c,int t)/进入停车场车辆进入停车场，对应于Parking栈的操作；void In_LinkQueue(LinkQueue *L,int c,int t)/进入便道车辆进入便道，对应于链队的操作，链队的尾指针向后移动；void Take_Out(Parking *p,Assistant *a,int c,int t)/车要离开停车场有车辆要离开，先对Parking栈操作，将该车之后的所有车辆存放到辅助栈中然后再将所有的车辆依次移入Parking栈中判断便道上是否有车，若有车，则进入停车场 若无车，提示便道为空void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t)/*便道上的车进入停车场*/ 将便道上的车移入停车场，对应于链队及Parking栈的操作void Operate(Parking *p,Assistant *a,LinkQueue *L)/对停车场程序的操作输入操作；switch()case 本程序的保护模块 结构体模块 主程序模块 自定义函数模块调用关系：结构体模块主函数模块 自定义函数模块3、程序设计 主要算法的程序流程图： Print_Parking( )的算法流程图：Take_Out( )的算法流程图：四、详细设计1、抽象数据类型的定义与实现模拟停车场的顺序栈 #define Parking struct parkingParking/*停车场用顺序栈来模拟，存放停车的车牌号，进入停车场的时间*/ 车牌号 int car_numMaxSize; 进入或离开的时间 int timeMaxSize; 栈内元素个数 int top; 模拟车辆退出停车场时的顺序辅助栈 #define Assistant struct assistantAssistant/*辅助栈，用于存放退出停车场的车辆信息*/ 车牌号 int car_numMaxSize; 进入的时间 int timeMaxSize; 栈内元素个数 int top; 模拟便道的链式队列 #define Qnode struct qnode#define LinkQueue struct linkqueueQnode/*链队的结点类型*/车牌号 int car_num;进入时间 int time;便道站台号 int station;Qnode *next; LinkQueue/*将头尾指针封装在一起*/Qnode *front,*rear; ; 2、自定义函数 void Print_Parking(Parking *p)/打印停车场中所停的车辆信息int i;cout车位号t车牌号t停车时间endl;for(i=0;itop;i+)couti+1tcar_numittimeitop+;p-car_nump-top=c;p-timep-top=t;cout车牌号为：c 车已经进入停车场，车位号位：top+1car_num=c;q-time=t;q-station=L-rear-station+1;cout请进入便道的第 station 号位置！next=NULL;L-rear-next=q;L-rear=q;void Take_Out(Parking *p,Assistant *a,int c,int t)/车要离开停车场int i, m=0;while(p-car_numm!=c)m+; while(m=MaxSize)cout停车场中没有改车牌号，请重新输入！c;m=0;while(p-car_numm!=c)m+; while(ttimem)cout输入的时间有误，请重新输入！t;cout车牌号为：c 的车辆即将离开停车场!endl;cout停留时间为：timemt应缴纳的费用为：PRICE*timemtop)for(i=p-top;itop+;a-car_numa-top=p-car_numi;a-timea-top=p-timei; /*将离开车辆之后的车辆移入Assistant栈*/for(i=a-top;icar_numm=a-car_numi;/*车辆离开后，将Assistant栈中的车辆依次移入停车场中*/p-timem=a-timei;m+;a-top=-1;p-top-;void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t)/*便道上的车进入停车场*/p-top+;p-car_nump-top=L-front-next-car_num;p-timep-top=t;L-front=L-front-next;/q;L-rear-station-;void Operate(Parking *p,Assistant *a,LinkQueue *L)/对停车场程序的操作char ch;int c,t;coutendl请输入操作：（A，D，P，W，E）ch;switch(ch)case E:/退出程序break;case A: cout请输入车牌号：c;cout请输入进入停车场的时间：t;if(p-top+1!=MaxSize) /停车场未满，存储车辆 In_Parking(p,c,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);else /停车场已满，车辆进入便道cout对不起，停车场已满，请进入便道停车！rear-station=0)if(p-top=-1)cout停车场已经空了！endl;elsecout请输入要离开的车牌号：c;cout请输入离开的时间：t;Take_Out(p,a,c,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);elsecout请输入要离开的车牌号：c;cout请输入离开的时间：t;Take_Out(p,a,c,t);cout便道上第 1 辆车即将进入停车场！endl;/便道上第一辆车进入停车场LinkQueue_to_Parking(L,p,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);Operate(p,a,L);break;case P:cout停车场中共有 top+1 辆车，还可以存放 top+1) 辆车！endl;Operate(p,a,L);break;case W:cout便道上共有 rear-station 辆车！endl;Operate(p,a,L);break;default:cout输入错误,请重新输入操作！top=-1; /初始化停车场a=(Assistant *)malloc(sizeof(Assistant);a-top=-1; /初始化辅助栈qq=(Qnode *)malloc(sizeof(Qnode);qq-station=0;qq-next=NULL; /初始化链队结点L=(LinkQueue *)malloc(sizeof(LinkQueue);L-front=qq;L-rear=qq;/初始化链队cout * 停车场管理程序 *endl;cout=endlcout A-到达停车场tD-离开停车场endl;cout P-停车场车数tW-候车场车数endl;cout E-退出程序endl;cout=endlcout请按上述提示输入您的操作！endl;Operate(p,a,L); /操作函数return 0; 4、函数的调用关系 主函数main()调用自定义函数void Operate(Parking *p,Assistant *a,LinkQueue *L);/对停车场程序的操作 Operate（）函数调用void Print_Parking(Parking *p);/打印停车场中所停的车辆信息、void In_Parking(Parking *p,int c,int t);/进入停车场、void In_LinkQueue(LinkQueue *L,int c,int t);/进入便道、void Take_Out(Parking *p,Assistant *a,int c,int t);/车要离开停车场、void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t);/便道上的车进入停车场。五、 调试分析1、程序中将停车场用顺序栈来模拟，便道用链队来模拟，车辆离开停车场时，导致其他车辆的移动，用一个辅助顺序栈来模拟。通过分析，这种模拟合乎我们的逻辑思维，便于理解及代码的编写。2、在调试过程中，遇到很多问题，尤其是在有车辆要离开停车场的时候，这时候要考虑的问题比较多，便道上是否有车辆，车辆如何计费，车辆如何退出，如何进入，如果便道上有车辆进入，便道上其余的车辆有何变动，因此 ，会引发一系列问题，但通过认真的研究与思考，这些问题也被一一解决了。3、算法的时空分析：该程序中用到了较多的自定义函数，每个自定义函数用到辅助空间不多，时间复杂度也不是很大。例如， void Take_Out()/*车要离开停车场*/,涉及到大量元素的移动；void LinkQueue_to_Parking()/*便道上的车进入停车场*/，涉及到插入与删除的问题等等。4、该系统存在的缺陷是：如果停车场时这种布局，只有一个进口，当车辆要离开时，我觉得有必要考虑一下，如果便道上的车辆有急事，需要离开的问题，那么我觉得程序中也应给出相应的操作算法；还有一个是关于容错率的问题，如果操作人员不慎将车离开时间输错，或者车牌号输错，程序应该能给出相应的解决办法，否则会导致系统的崩溃；该程序对于停车场而言，不具有普适性，模拟现实中的大型停车场的话，不应该存在停车场只有一个出口和进口，停车场也不应该用顺序栈的结构来模拟。所以，如果考虑到现实情况，这个程序就不具有价值性。六、 使用说明 程序运行后，将自动跳出一个“停车场管理系统的界面”，及相应操作的快捷键，用户根据事情发生的先后顺序依次录入操作，并给出该操作后，停车中的所停放的车辆。若果车辆离开，将给出车辆应付的金额。如果停车场中已没有车辆，而用户不小心输入“取车”操作时，会提示“停车场已满”。七、结果 八、 附录源程序清单：#include#include#include#define Parking struct parking#define Assistant struct assistant#define Qnode struct qnode#define LinkQueue struct linkqueue#define MaxSize 2 /停车场最大容量void Print_Parking(Parking *p);/打印停车场中所停的车辆信息void In_Parking(Parking *p,int c,int t);/进入停车场void In_LinkQueue(LinkQueue *L,int c,int t);/进入便道void Take_Out(Parking *p,Assistant *a,int c,int t);/车要离开停车场void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t);/便道上的车进入停车场void Operate(Parking *p,Assistant *a,LinkQueue *L);/对停车场程序的操作Parking/*停车场用顺序栈来模拟，存放停车的车牌号，进入停车场的时间*/int car_numMaxSize;int timeMaxSize;int top; Assistant/*辅助栈，用于存放退出停车场的车辆信息*/int car_numMaxSize;int timeMaxSize;int top; Qnode/链队的结点类型int car_num;int time;int station;Qnode *next; LinkQueue/将头尾指针封装在一起 Qnode *front,*rear; ;int main()Parking *p;Assistant *a;Qnode *qq;LinkQueue *L;p=(Parking *)malloc(sizeof(Parking);p-top=-1; /初始化停车场a=(Assistant *)malloc(sizeof(Assistant);a-top=-1; /初始化辅助栈qq=(Qnode *)malloc(sizeof(Qnode);qq-station=0;qq-next=NULL; /初始化链队结点L=(LinkQueue *)malloc(sizeof(LinkQueue);L-front=qq;L-rear=qq;/初始化链队cout * 停车场管理程序 *endl;cout=endlcout A-到达停车场tD-离开停车场endl;cout P-停车场车数tW-候车场车数endl;cout E-退出程序endl;cout=endlcout请按上述提示输入您的操作！endl;Operate(p,a,L); /操作函数return 0;void Print_Parking(Parking *p)/打印停车场中所停的车辆信息int i;cout车位号t车牌号t停车时间endl;for(i=0;itop;i+)couti+1tcar_numittimeitop+;p-car_nump-top=c;p-timep-top=t;cout车牌号为：c 车已经进入停车场，车位号位：top+1car_num=c;q-time=t;q-station=L-rear-station+1;cout请进入便道的第 station 号位置！next=NULL;L-rear-next=q;L-rear=q;void Take_Out(Parking *p,Assistant *a,int c,int t)/车要离开停车场int i, m=0;while(p-car_numm!=c)m+; while(m=MaxSize)cout停车场中没有改车牌号，请重新输入！c;m=0;while(p-car_numm!=c)m+; while(ttimem)cout输入的时间有误，请重新输入！t;cout车牌号为：c 的车辆即将离开停车场!endl;cout停留时间为：timemt应缴纳的费用为：PRICE*timemtop)for(i=p-top;itop+;a-car_numa-top=p-car_numi;a-timea-top=p-timei; /*将离开车辆之后的车辆移入Assistant栈*/for(i=a-top;icar_numm=a-car_numi;/*车辆离开后，将Assistant栈中的车辆依次移入停车场中*/p-timem=a-timei;m+;a-top=-1;p-top-;void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t)/*便道上的车进入停车场*/p-top+;p-car_nump-top=L-front-next-car_num;p-timep-top=t;L-front=L-front-next;/q;L-rear-station-;void Operate(Parking *p,Assistant *a,LinkQueue *L)/对停车场程序的操作char ch;int c,t;coutendl请输入操作：（A，D，P，W，E）ch;switch(ch)case E:/退出程序break;case A: cout请输入车牌号：c;cout请输入进入停车场的时间：t;if(p-top+1!=MaxSize) /停车场未满，存储车辆 In_Parking(p,c,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);else /停车场已满，车辆进入便道cout对不起，停车场已满，请进入便道停车！rear-station=0)if(p-top=-1)cout停车场已经空了！endl;elsecout请输入要离开的车牌号：c;cout请输入离开的时间：t;Take_Out(p,a,c,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);elsecout请输入要离开的车牌号：c;cout请输入离开的时间：t;Take_Out(p,a,c,t);cout便道上第 1 辆车即将进入停车场！endl;/便道上第一辆车进入停车场LinkQueue_to_Parking(L,p,t);coutendl现在停车场内有车辆为：endl;Print_Parking(p);Operate(p,a,L);break;case P:cout停车场中共有 top+1 辆车，还可以存放 top+1) 辆车！endl;Operate(p,a,L);break;case W:cout便道上共有 rear-station 辆车！endl;Operate(p,a,L);break;default:cout输入错误,请重新输入操作！endl;Operate(p,a,L);break;九、 扩展 考虑到现实中的停车场，便道上的车也有离开的时候，操作人员也有输入错误的时候，这时候就必须采取相应的操作，才能保证系统的正常运行，所以，就必须保证系统有一定的容错功能。下面将给出多种错误情况下的程序代码及调试结果： #include#include#include#define Parking struct parking#define Assistant struct assistant#define Qnode struct qnode#define LinkQueue struct linkqueue#define MaxSize 2 /停车场最大容量void Print_Parking(Parking *p);/打印停车场中所停的车辆信息void In_Parking(Parking *p,int c,int t);/进入停车场void In_LinkQueue(LinkQueue *L,int c,int t);/进入便道int FindCar_LinkQueue(LinkQueue *L,int c);/查找所要取出的车牌号是否在便道int FindCar_Parking(Parking *p,int c);/查找所要取出的车牌号是否在停车场中void Take_Out(Parking *p,Assistant *a,int c,int t);/车要离开停车场void LinkQueue_to_Parking(LinkQueue *L,Parking *p,int t);/便道上的车进入停车场void Operate(Parking *p,Assistant *a,LinkQueue *L);/对停车场程序的操作Parking int car_numMaxSize;int timeMaxSize;int top; /停车场用顺序栈来模拟，存放停车的车牌号，进入停车场的时间Assistant int car_numMaxSize;int timeMaxSize;int top; /辅助栈，用于存放退出停车场的车辆信息Qnode int car_num;int time;int station;Qnode *next; /链队的结点类型LinkQueue Qnode *front,*rear;/将头尾指针封装在一起; int main()Parking *p;Assistant *a;Qnode *qq;LinkQueue *L;p=(Parking *)malloc(sizeof(Parking);p-top=-1; /初始化停车场a=(Assistant *)malloc(sizeof(Assistant);a-top=-1; /初始化辅助栈qq=(Qnode *)malloc(sizeof(Qnode);qq-station=0;qq-next=NULL; /初始化链队结点L=(LinkQueue *)malloc(sizeof(LinkQueue);L-front=qq;L-rear=qq;/初始化链队cout * 停车场管理程序 *endl;cout=endl；cout A-到达停车场tD-离开停车场endl;cout P-停车场车数tW-候车场车数endl;cout E-退出程序endl;cout=endl;cout请按上述提示输入您的操作！endl;Operate(p,a,L); /操作函数return 0;void Print_Parking(Parking *p)/打印停车场中所停的车辆信息int i;cout车位号t车牌号t停车时间endl;for(i=0;itop;i+)couti+1tcar_numittimeitop+;p-car_nump-top=c;p-timep-top=t;cout车牌号为：c 车已经进入停车场，车位号位：top+1car_num=c;q-time=t;q-station=L-rear-station+1;cout请进入便道的第 station 号位置！next=NULL;L-rear-next=q;L-rear=q;int FindCar_LinkQueue(LinkQueue *L,int c)/查找所要取出的车牌号是否在便道int n=0;Qnode *s;s=L-front-next;if(L-rear-station!=0)while(s-car_num!=c) n+;if(s=L-rear)break;s=s-next;elsen=-1;/n=-1表示，便道是空的return n; int FindCar_Parking(Parking *p,int c)/查找所要取出的车牌号是否在停车场中int m=0;while(p-car_numm!=c)m+; if(m=MaxSize)m=-1;/m=-1表示停车场中没有该车牌号return m;void Take_Out(Parking *p,Assistant *a,LinkQueue *L,int c,int t)int i,m,n;Qnode *s;s=L-front;m=FindCar_Parking(p,c);n=FindCar_LinkQueue(L,c);while(m=-1&n=-1)/输入了错误的车牌号cout停车场及便道上均没有改车牌号，请重新输入车牌号！”c;m=FindCar_Parking(p,c);n=FindCar_LinkQueue(L,c);if(m=-1&(n0&nrear-station)/所取出的车牌号在便道上cout便道上第n+1号车位的车辆即将离开便道！rear-station-1)/当所取出的车牌号是队列的尾指针时，这时要单独考虑，因为此时要移动尾指针for(i=0;irear-station-1;i+)s=s-next;L-rear=s;L-rear-next=NULL;else/若所取出的车牌号不是队列尾指针时，尾指针不动，只需将其车位号减1for(i=0;inext;s-next=s-next-next;L-rear-station-;else/表示所要取出的车牌号在停车场中while(ttimem)/表示时间输入有误cout输入的时间有误，请重新输入！t;if(m!=-1&m!=p-top)/表示所要取出的车牌号不在停车场的最后一个时，要使用辅助栈cout车牌号