实验三 栈和队列的应用.doc

一、 实验目的1 掌握栈的数据类型描述及栈的特点；2 掌握栈的顺序存储结构的特点及算法描述；3 掌握队列的数据类型描述及链式存储结构的特点和算法描述。二、实验内容停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大95E8口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。三、 算法描述提示：可以将停车场定义成一个顺序栈s1，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。当有车辆进停车场时，直接进入s1栈，若s1栈满，则进入便道（链队列q）。若有s1中车辆x离开时，先让在x后面进栈的车从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有车辆退栈并重新进入s1栈，最后，将链队列q的队头车辆进栈到s1中并删除队头车辆。若有链队列q（便道）中的车辆y离开时，从链队列中删除该车辆即可，不收停车费。车辆的数据可以表示为（车辆编号，到达/离开时间）。四.程序清单:#include using namespace std;const int StackSize=5;class SeqStackpublic:SeqStack()top=-1;SeqStack();void Push(int x);void Push2(int x);int *Return();int Pop(int y);int Count();void PrintStack();private:int dataStackSize;int top;/入栈void SeqStack:Push (int x)if(top=StackSize-1) throw上溢;for(int i=0;i=top+1;i+)if(datai=x) coutx;top+;datatop=x;/返回数组地址int *SeqStack:Return()return data;/临时栈void SeqStack:Push2(int x)top+;datatop=x;/输出函数void SeqStack:PrintStack ()for(int i=0;i=top;i+)cout位置为i+1的车辆车牌号为: datainext=NULL;front=rear=s;/入队void LinkQueue:EnQueue (int x,int *q)Node *s=new Node;Node *p=new Node;p=front;while(p)if(p-data =x)coutx;for(int i=0;i5;i+)if(x=qi)coutx;i=-1;p=front;p=p-next ;s-data =x;s-next =NULL;rear-next =s;rear=s;/出队int LinkQueue:DeQueue ()if(front=rear) throw便道无车辆;Node *p=new Node;int x;p=front-next ;x=p-data ;front-next =p-next ;if(p-next =NULL) rear=front;delete p;return x;/计算结点数int LinkQueue:Count ()Node *p=new Node;p=front;int i=0;while(p&p-next!=NULL )p=p-next;i+;return i;/选择性出队void LinkQueue:xzDeQueue (int x)if(rear=front) throw便道无车辆;Node *p=new Node;p=front;int y;int i=0;for(;p-next!=NULL;p=p-next)if(p-next-data =x)if(p-next-next!=NULL)Node *q=new Node;q=p-next ;y=q-data ;p-next =q-next ;i=1;delete q;cout车牌号为:y的车辆已经离开!next ;y=q-data ;p-next =NULL;i=1;delete q;if(front-next=NULL) rear=front;cout车牌号为:y的车辆已经离开!endl;break;if(i=0) cout无车牌号为:x的车辆存在!endl;void main()SeqStack a;/a是作为停车场的栈SeqStack b;/b是作为临时存放车辆的栈LinkQueue c;/c是作为便道的队列couttttt1.车辆进入endl;couttttt2.车辆离开endl;couttttt3.查看车牌号endl;couttttt4.便道车辆离开endl;couttttt5.修改费用单价(默认1元/小时)endl;couttttt6.退出系统endl;int zl;/zl为操作指令int xh1=1;/xh1为菜单最外层的循环控制变量int time100;/记录各车辆进入停车场的时间int t1=0;/作为车辆对应的时间编号int money=1;while(xh1=1)coutzl;switch(zl)case 1:tryint n1=a.Count ();int n;coutn;if(n1=4)int *Num=a.Return ();for(int i=0;i=4;i+)if(Numi=n)coutn;i=-1;int *CarNum=a.Return ();c.EnQueue (n,CarNum);cout停车场已满,请在便道等候!endl;break;a.Push (n);couttimet1;while(timet1=24)couttimet1;t1+;catch(char*s)coutsendl;break;case 2:tryint n2;/离开车辆的编号coutn2;if(a.Count ()+1=0)cout该停车场没有车辆,请选择其他操作!;break;elsewhile(n2a.Count ()+1)cout请输入1a.Count ()+1n2;int j=a.Count ();for(int i=0;i(j+1-n2);i+)b.Push2(a.Pop(n2);a.Pop (n2);int j2=b.Count ();for(int i1=0;i1=j2;i1+)a.Push (b.Pop (n2);int j3=c.Count ();int time1;couttime1;while(time123)couttime1;int day=0;if(time1timen2-1)coutday;while(day=0)coutday;cout您的费用是(元): (time1-timen2-1+24*day)*moneyendl;for(int i2=0;i2(j+1-n2);i2+)timen2-1+i2=timen2+i2;t1-;if(j3!=0)a.Push (c.DeQueue ();coutttt通知: 便道车辆请进入停车场!endl;couttimet1;while(timet1=24)couttimet1;t1+;catch(char *s)coutsendl;break;case 3:a.PrintStack ();break;case 4:int n3;c