数据结构停车场问题实验报告.doc

班级：计算机11-2 学号：40 姓名：朱报龙 成绩：_ 实验六 栈和队列的应用一、 实验目的1 掌握栈的数据类型描述及栈的特点；2 掌握栈的顺序存储结构的特点及算法描述；3 掌握队列的数据类型描述及链式存储结构的特点和算法描述。二、 实验内容停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大门口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。二、 设计与编码#includeusing namespace std;const int Max=2;/车库最大容量const double price=30;/每小时的费用class car/车的信息类public:double time;/计费时间int number;/车牌号car *next;/存放car类型元素的数组初始地址;class carstack/栈（停车场）的类friend class parkingmanagement;/parkingmanagement能访问carstack类中所有成员public:carstack();/构造函数，栈的初始化int empty();/判断栈是否为空int full();/判断栈是否为满car *s;/存放car类型栈元素的数组初始地址int top;/栈顶指针;class carqueue/队列（便道）的类friend class parkingmanagement;/parkingmanagement能访问carstack类中所有成员public:carqueue();/构造函数，队列的初始化int full();/判断队列是否为满car *front,*rear;/存放car类型队列元素的数组初始地址;class parkingmanagementpublic:int pushstack(carstack &cs,int cnum,double ctime);/入栈,cs栈内进行调整，返回栈内位置void popstack(carstack &cs,int cnum);/出栈，cs栈内进行调整，int pushqueue(carqueue &cq,int cnum,double ctime);/入队,队内进行调整，返回队内位置int popqueue(carqueue &cq);/出队,队内进行调整，返回汽车车牌号void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);/车辆到达，/根据输入的车牌号、到达时间，变更函数参数；并cout车位信息void leave(carstack &cs,carqueue &cq,int cnum,double ctime);/车辆离开，void deletequeue(carqueue &cq,int i);/删除cq过道中第i辆车int popstacknumber;/专门存放出栈的时候返回的车牌号double popstacktime;/专门存放出栈的时候返回的时刻;carstack:carstack()/构造函数，栈的初始化top=-1;s=new carMax;/创建car类型栈元素的数组if(s=NULL)cout栈空间分配不成功！endl;exit(1);int carstack:full()/判断栈是否为满return top=Max-1;carqueue:carqueue()/构造函数，队列的初始化rear=front=NULL;int parkingmanagement:pushstack(carstack &cs,int cnum,double ctime)/入栈,cs栈内进行调整，返回栈内位置if(cs.top=Max-1)/Max从开始，top从开始cout停车场已满！endl;return Max;else cs.top+;(cs.scs.top).number=cnum;/将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组(cs.scs.top).time=ctime;/将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组return (cs.top+1);/返回栈内位置加，即停车场内车位从号开始void parkingmanagement:popstack(carstack &cs,int cnum)/出栈，cs栈内进行调整，/根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber/将出栈car的time赋值给double popstacktime，无返回值！int i;car p;carstack stemp;/定义一个carstack类型的临时存放出栈元素的栈for(i=0; ii)stemp.s+(stemp.top)=cs.s(cs.top)-;/出栈的元素数组逐个赋给临时栈popstacknumber=p.number;/将这个车牌号信息传给int popstacknumber()popstacktime=p.time;/将该车的时间信息传给double popstacktime()cs.top-;/栈顶指针回到原来位置while(stemp.top=0)cs.s+(cs.top)=stemp.s(stemp.top)-;/临时栈出栈的元素逐个赋给原栈，完成先退再进的工作int parkingmanagement:pushqueue(carqueue &cq,int cnum,double ctime)/入队,队内进行调整，返回队内位置car *p,*countp;int count(1);/count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加p=new car;/创建一个car类型的指针p-number=cnum;p-time=ctime;p-next=NULL;/首先将指向存放car类型元素的数组初始地址置空if (cq.front=NULL)/第一次入队要判断头结点是否为空cq.front=cq.rear=p;else /尾插法插入元素p-next=(cq.rear)-next;(cq.rear)-next=p;cq.rear=(cq.rear)-next;countp=(cq.front)-next;while(countp!=NULL)count+;countp=countp-next;/count即车在过道上的位置，【从开始计！】return count;int parkingmanagement:popqueue(carqueue &cq)/出队,队内进行调整，返回汽车车牌号car p;p.number=(cq.front)-next)-number;/cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息p.time=(cq.front)-next)-time;/cq队里，从cq.front开始指向下一个元素的时刻/赋给car类型的车信息p.next=(cq.front)-next)-next;/cq队里，从cq.front开始指向下一个元素的指针/赋给car类型的车信息的下一个元素的指针return p.number;cq.front=(cq.front)-next;void parkingmanagement:arrival(carstack &cs,carqueue &cq,int cnum,double ctime)/车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息int pos;if(!(cs.full()/如果栈未满，车辆停入停车场int fl(0),i;/定义一个从开始的标记flfor(i=0;i=cs.top;i+)if(cs.si.number=cnum)/如果到达的车的车牌号=栈内已有车辆的车牌号fl=1;/fl记break;if(fl=1)/如果到达的车的车牌号!=栈内已有车辆的车牌号cout输入错误！请重新输入！endl;elsepos=pushstack(cs,cnum,ctime);/入栈，返回车位信息cout该停车场还有空位，请到pos号车位进行泊车endl;coutendl;else/如果栈满，车辆暂停便道pos=pushqueue(cq,cnum,ctime);/入队，返回车位信息cout该停车场已满，请将车停到便道pos号车位上endl;coutendl;void parkingmanagement:leave(carstack &cs,carqueue &cq,int cnum,double ctime)/车辆离开，根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作；并cout停留时间和收费情况int i,flag(0),pstack,count(1),outcarnum;double hour;car *p;for(i=0;i=cs.top;i+)if(cs.si).number=cnum)flag=1;break;if(flag)/如果输入的车牌号与栈内已有车辆的车牌号一致popstack(cs,cnum);/出栈操作hour=ctime-popstacktime;/时间计算outcarnum=popqueue(cq);/将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnumpstack=pushstack(cs,outcarnum,ctime);/将便道上的第一辆车，入栈cout该车在本停车场内停留时间为hour分钟，应付金额hour*(price/60)元！next;if(p-number=cnum)/在过道中找到要出去的车，则在队列中删除该car。/后面的车辆依然顺序排列，补足空位deletequeue(cq,count);if(countMax)cout您的车在便道上的位置为count号车位，请自行驶离，无需付费！endl;break;if(p=NULL)cout您的车不在本停车场内，或输入有误，请重新输入！endl;void parkingmanagement:deletequeue(carqueue &cq,int i) car *p,*q;int j(0);p=cq.front;while(p & jnext;j+;/找到第i个节点(i从开始)if(!p | !p-next)coutnext;p-next=q-next;delete q;/*【以下是主程序】*void print()cout= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =endl;cout= 欢迎光临！=endl;cout= =endl;cout= 本停车场收费标准为：元/小时；车库容量为：=endl;cout= =endl;cout= 请输入您的泊车信息：格式为：（到达/离去/退出）；车牌号；现在时刻=endl;cout= 其中，A：到达；D：离去；E：退出系统=endl;cout= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =acccarnumcartime;if(acc=A)park.arrival(cars,carq,carnum