数据结构 实验2 停车场问题

HUNANUNIVERSITY实验二最终报告题目：停车场管理学生姓名学生学号专业班级指导老师完成日期2014年4月24日一、需求分析1．输入形式：用户通过键盘输入一组数据：字符、整数、整数后，输出汽车到达或者汽车离去的相应信息到DOS界面。当用户输入数据不符合规范时，提示重新输入。输入规则：第一个字符中‘A’表示车辆到达；‘D’表示车辆离去；‘E’表示输入结束；第二个整数代表车牌号码；第三个整数代表到达或离去的时刻。2．输出形式：1)停入停车场：车牌号为x的汽车到达，位于停车场位置y2)停入便道：停车场已满，车牌号为x的汽车位于便道位置y3)移动停车位置：车牌号为x的汽车停在停车场位置y4)离开车辆信息：车牌号为x的汽车离开，停车时间y小时，缴费z元3．功能：根据用户输入数据，若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。4．测试数据停车场系统容量为2收费标准：每小时5元输入：A15输出：车牌号为1的汽车到达，位于停车场位置1输入：A210输出格式：车牌号为2的汽车到达，位于停车场位置2输入：A320输出格式：停车场已满，车牌号为3的汽车位于便道位置1输入：D115输出格式：车牌号为1的汽车离开，停车时间10小时，缴费50元。输出格式：车牌号为3的汽车到达停车场，位于位置2输入：E00二、概要设计抽象数据类型根据题目设计要求，车辆只能从一个大门出入，汽车只能从停车场唯一一条狭长通道驶入驶出，而暂时停放车辆的便道同理。每一辆停入停车场或便道的汽车有唯一的前驱和后继，所以问题适合建立一个线性数据关系求解。因为停车场具有只有一个出入口、容量限定的特点，所以实现停车场的线性结构需要具备可限定空间大小，“先进后出”，只有一端出入口的特性，所以用堆栈实现它。而临时车道停放车辆后要按原序停放回停车场，具有“先进后出”的特点，且需要的临时车道的容量小于等于停车场容量，所以用实现停车场的同一堆栈实现它。停车便道具有“先进先出”的特点，且需要停车便道的长度不可预测，所以使用链式队列实现。由于每辆汽车都包含车牌号、停放时间的信息，所以定义一个汽车类为每辆汽车打包这些信息。classcar//car类{public:intnum;//车牌号码inttime;//汽车停放时间};堆栈ADT定义：数据对象：car类数据关系：R={ai-1,ai|ai-1,ai∈car,i=1,2,3….n}约定an为栈顶，a1为栈底。Stack();//结构初始化操作boolpush(constcar&it);//压入一个数据boolpop(car&it);//依次弹出m个数据booltopValue(car&it);//获取栈顶元素~Stack();//结构销毁操作intlength()const;//获取栈的长度队列ADT定义：数据对象：car类数据关系：R={ai-1,ai|ai-1,ai∈car,i=1,2,3….n}约定a1为队列头，an为队列尾。Queue();//队列结构初始化~Queue();//结构销毁操作boolpush(constcar&it);//数据入列boolpop(car&it);//数据出列virtualintlength()const；//获取队列长度算法的基本思想1）如果有一辆车要停入，先判断停车场是否已满。若未满，把汽车停入停车场(入栈)，记录下汽车的车牌号和停放时间。若已满，把汽车停入便道(入队列)中，记录汽车车牌号，并提示输出停放位置。2）如果一辆车要离开，用该车车牌号查找停车场中的车，如果不是所查找的车，把此车驶出停车场(出栈)，停入临时车道中(入临时栈)，直到查找到该车为止。若查找到，把此车驶出停车场，记录汽车驶离时间，计算停车费用。汽车离开后把临时车道中的汽车依次驶出(出临时找)，并停入停车场中(入栈)。最后判断便道内是否停有汽车，如果有，把便道中的第一辆车驶出(出队列)停放到停车场(入栈)内，记录停放时间为汽车驶离时间。程序的流程（1）输入模块：输入一组包含汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻的数据。（2）判断模块：判断汽车是“到达”或“离开”，若为“到达”执行第(3)1)步，若为“离开”执行第(3)2)步。（若为‘结束’则停止程序。）（3）处理模块：1)汽车“到达”：把汽车包含的信息存入栈中，如果入栈失败，则存入队列中。返回第（1）步。2)汽车“离开”：根据要离开汽车的车牌号对栈中数据判断，不是寻找的数据则出栈存入临时栈中。找到数据则返回其时间信息并弹出该数据，再判断队列中是否有数据，有则把队列头的数据弹出，压入栈中。（4）输出模块：根据时间信息计算停车费用输出到屏幕，并返回第（1）步。三、详细设计根据题目需求，用堆栈实现停车场和临时车道，为了有更高的空间效率和节省结构性开销，用顺序表实现堆栈，链式队列实现便道物理数据类型用字符变量存储用户输入“来去”信息，用car类存储汽车车牌号、来去时间。classcar{public:intnum;inttime;};停车场和临时车道的堆栈基本操作如下：classStack{private:intsize;inttop;car*data;public:Stack(){//结构初始化操作size=n;top=0;data=newcar[n];}~Stack(){//结构销毁操作delete[]data;}//压入数据，成功返回true，失败返回falseboolpush(constcar&it){if(top==size)returnfalse;else{data[top++]=it;returntrue;}}//弹出数据，成功返回true，失败返回falseboolpop(car&it){if(top==0)returnfalse;else{it=data[--top];returntrue;}}//获取栈顶元素，获取成功返回true，失败返回falsebooltopValue(car&it)const{if(top==0)returnfalse;else{it=data[top-1];returntrue;}}intlength()const{returntop;}//获取栈的长度};用于便道的链式队列实现如下：classqnode//定义单链表的结点{public:carelem;qnode*next;qnode(constcar&elemval,qnode*nextval=NULL){elem=elemval;next=nextval;}qnode(qnode*nextval=NULL)next=nextval;};classQueue{private:intsize;qnode*front;qnode*next;qnode*rear;car*data;public:Queue(){//队列结构初始化size=0;front=NULL;rear=NULL;}~Queue(){//结构销毁操作while(front!=NULL){rear=front;front=front-next;deleterear;}rear=NULL;size=0;}//数据入列，成功返回true，失败返回boolpush(constcar&it){if(rear==NULL)front=rear=newqnode(it,NULL);else//append{rear-next=newqnode(it,NULL);rear=rear-next;}size++;returntrue;}//数据出列，成功返回true，失败返回boolpop(car&it){if(length()==0)returnfalse;it=front-elem;qnode*ltemp=front;front=front-next;deleteltemp;if(front==NULL)rear=NULL;size--;returntrue;}//获取队列长度intlength()const{returnsize;}};算法的具体步骤停车场问题中各部分调用的流程图如下：输入数据车辆来(A)or去(D)or结束程序(E)'E'结束栈满？Npark.push();数据入栈path.push();数据入队列Y'A''D'park.topValue()车牌相同？park.pop();park.pop();temp.push();park.topValue();车辆出栈入队列YN输出停车时长停车费用队列是否为空？NYpath.pop();park.push();车辆“到达”处理模块车辆“离开”处理模块程序结束//定义使用到的变量charcomego;carCar;Stackpark;Stacktemp;Queuepath;cout停车场系统容量为2endl;//停车场容量、收费标准提示信息cout收费标准：每小时5元endl;//提示输入carc;while(comego!='E'||comego!='e')//如果输入不为’E’或’e’时，进入循环{switch(comego){case'a'://如果输入字符为’a’或’A’，进行车辆到达相关操作case'A'://在基本操作中定义push()为bool型函数，当栈不满时压栈成功返回true，否则返回false，所以用压栈操作park.push()作为入栈成功与否的判断条件if(park.push(Car))//如果入栈成功//输出停车车牌号和位于停车场的位置else//入栈失败{path.push(Car);//输出停车车牌号和位于便道的位置break;case'D'://如果输入字符为’d’或’D’case'd':park.topValue(c);//如果车辆离开，在停车场中查找离开车辆的车牌号，当车牌号相等时，表明在停车场中找到该车//若所查找的车辆不为离开车辆，则把该车先压入临时栈中，并取得停车场下一车辆车牌号待查while(c.num!=Car.num){park.pop(c);temp.push(c);park.topValue(c);}park.topValue(c);//找到该车，获得车辆数据park.pop(c);EndTime=Car.time;//车辆离开时间为结束时间StartTime=c.time;//存储的时间为开始时间，计算停放time=EndTime-StartTime;//时长。//考虑到输入时间时，离开时间会小于起始时间，当time=0时不作处理，当time0时，用算数关系，作计停车过20小时处理if(time=0)cost=(EndTime-StartTime)*5;else//离开时间小于停车时间，按停车“过夜”计算{time=24-StartTime+EndTime;cost=time*5;}//输出停车时长和停车费用信息//车辆离开后，把临时车道中的车全部停放回停车场。判断临时栈中是否为空，判断临时栈中数据是否全部压回原栈(停车场)。while(temp.length()!=0){temp.pop(c);park.push(c);park.topValue(c);//输出停车位置更改提示}//当车辆全部从临时栈中压回原栈后，原栈中空出一个存储空间，这时判断队列(便道)是否为空来表示是否有元素(汽车)在队列中,如果有则压入原栈中。if(path.length()!=0)//队列不为空{path.pop(c);c.time=Car.time;park.push(c);//输出停车车牌和停车位置提示}break;case'E'://输入’E’或’e’，结束程序case'e':exit(0);default://有其他输入时，报错并提示重新输入//报错，提示输入汽车信息break;}//提示输入汽车信息}算法的时空分析及改进设想分析可知，当汽车要离开时时间复杂度较汽车进入时的每次压栈和弹栈的基本操作的时间