08级实验3-05.doc

实验报告姓名： 丁 烨 班级： 信科08-1班 学号： 05号（B25） 实验日期： 12月2日一、实验目的1、掌握栈的数据类型描述及栈的特点；2、掌握栈的顺序和链式两种存储结构的特点及算法描述；3、掌握栈的5种基本运算及算法在两种不同存储结构上的实现；4、掌握队列的数据类型描述及链式存储结构的特点和算法描述；5、掌队列的5种基本运算及在链式存储结构上的实现。二、实验内容停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以提供车辆进出。车辆按到达停车场时间先后依次从停车场最里面向大门口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场能有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某车辆要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不受停车费，并且仍然保持在便道上的车辆次序。是编程模拟停车场管理三、实验算法与分析可以将停车场定义成一个顺序栈s1，便道定义为一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。当有车辆进停车场时，直接进入s1栈，若s1栈满，怎进入便道（链队列q）。若有s1中车辆x离开时，先让在x后面进栈的车队从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有元素退栈并重新进入s1栈，最后，将链队q的队头元素进栈s1中并删除队头元素。若链队q（便道）中的元素y离开时，从链队中删除该元素即可，不收停车费。车辆的数据可以表示为（车辆编号，到达/离开时间）。（1）输入车辆编号，时间及动作（进入或者离开或者结束），若进入，转（2），若离开，转（3），若结束，则终止程序；（2）判断s1是否满栈，若满栈，则进入队列q中，否则进栈；（3）将车辆a之后的元素进入栈s2 中，a退栈并根据时间计费。将s2中的元素依次入栈s1，将对头元素进入栈中。四、可执行程序及注释/算法实现#include const int N=5; /停车场栈的长度const int M=6; /单位时间内停车场收费值typedef structint num; /车辆编号int arrtime; /到达或离开时间elemtype;struct seqstackelemtype stackN+1;int top;s1,s2;struct linkelemtype data;link *next;struct linkqueuelink *front,*rear;q;seqstack inistack(seqstack s) /栈的初始化s.top=0;return s;seqstack push(seqstack s,elemtype x) /进栈s.top+;s.stacks.top=x;return s;seqstack pop(seqstack s) /退栈s.top-;return s;elemtype gettop(seqstack s) /取栈顶元素return s.stacks.top;int empty(seqstack s) /判断栈空if(s.top=0)return 1;elsereturn 0;linkqueue iniqueue(linkqueue s) /链队列初始化link *p;p=new link;p-next=NULL;s.front=s.rear=p;return s;linkqueue enqueue(linkqueue s,elemtype x) /进队link *p;p=new link;p-data=x;p-next=s.rear-next;s.rear-next=p;s.rear=p;return s;linkqueue dlqueue(linkqueue s) /出队link *p=s.front;s.front=p-next;delete p;return s;elemtype gethead(linkqueue s) /取对头元素return s.front-next-data;int emptyqueue(linkqueue s)if(s.front=s.rear) return 1;elsereturn 0;/处理车辆到达的情形void arrive(elemtype x)/x为到达的车辆if(s1.top=N)q=enqueue(q,x); /进入便道elses1=push(s1,x); /进入停车场/处理车辆离开的情形void delive(elemtype x)/x为离开的车辆int f=1;elemtype y;link *r;while(!empty(s1)&(f=1) /在停车场中找要离开的车辆if(s1.stacks1.top.num!=x.num)y=gettop(s1);s1=pop(s1);s2=push(s2,y);elsef=0;y=gettop(s1);s1=pop(s1);cout停车场中有编号为x.num的车endl;cout该车将离开，应收停车费：(x.arrtime-y.arrtime)*M元data.num!=x.num)r=p;p=p-next;if(p!=NULL)cout便道上有编号为：x.num的车辆endl;cout该车辆将离开，应收停车费0.00元：next=p-next;delete p;elsecout便道上没有编号为x.num的车辆，输入的车辆不存在！endl;void pr1() /输出停车场中车辆编号和到达时间int t=s1.top;cout停车场中的车辆编号和到达时间endl;while(t!=0)couts1.stackt.num s1.stackt.arrtimeendl;t-;coutnext;cout便道中的车辆编号和到达时间endl;while(p!=NULL)coutdata.num data.arrtimenext;coutendl;void main()int n;elemtype x;s1=inistack(s1);s2=inistack(s2);q=iniqueue(q);while(1)coutendl;cout请输入车辆编号，到达或离开时间x.numx.arrtime;coutn;if(n=1)arrive(x);pr1();pr2();else if(n=2)delive(x);pr1();pr2();else break;coutendl;运行结果：五、实验小结栈的进栈，出栈，初始化，判断为空的算法时间复杂度都为O(1)；队列的进队、出队，取队头元素的算法都为O(1)。停车场问题用到了栈和队列。运用栈和队列可以解决一些特