实验一停车场管理.doc

实 验 报 告| 实验名称 停车场管理 课程名称 算法与数据结构实验 | 一、实验目的：理解和掌握栈和队列的相应操作二、实验要求：使用线性表实现相应的过程可以采用顺序存储结构，也可以采用链式存储结构。三、实验内容：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按接车辆先后到达的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆停放在车场的最北端），若车场内已停满n辆汽车则后来的汽车只能在门外便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入车厂的车辆必须先退出车场为它让路，待该辆车开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走，设计一个停车场管理程序。四、实验原理：停车场采用栈结构，车辆按次序入栈，执行停车操作。车辆停放，若栈满，车辆入便道，便道采用队列，而停车场内有车驶出时，停车场内需要开出的车直到停车场内最后一辆车放入临时栈内，临时栈顶元素出栈，然后临时栈车辆又压栈到停车场内，然后队头车辆入栈，完成车辆离开操作。设置一个显示函数显示停车场和便道上的车辆。五、程序代码#include const int n=2;/n为停车场长度typedef struct int num; /汽车牌照号 element;struct seqstackint top;element stackn+1;s1,s2; /顺序栈s1模拟停车场,s2临时停放为给要离去的汽车让路而从停车场退出的汽车struct linkelement data;link *next;struct queuelink *front,*rear;q; /队列q模拟车场外的便道seqstack initstack(seqstack s) /初始化s.top = 0;return s;seqstack push(seqstack s,element x) /进栈s.top+;s.stacks.top = x;return s;seqstack pop(seqstack s) /出栈s.top-;return s;element gettop(seqstack s) /取栈顶元素return s.stacks.top;int empty(seqstack s) /判栈空if(s.top = 0) return 1;else return 0;queue initqueue(queue q) /队列初始化link *p;p = new link;p-next = NULL;q.front = q.rear = p;return q;queue inqueue(queue q,element x) /入队link *p;p = new link;p-data = x;p-next = q.rear-next;q.rear-next = p;q.rear = p;return q;queue outqueue(queue q) /出队link *p = q.front;q.front = p-next;delete p;return q;element gethead(queue q) /取队头元素return q.front-next-data;int emptyqueue(queue q)if(q.front = q.rear) return 1;else return 0;/处理汽车到达的情形void arrive(element x)/X为到达的车辆if(s1.top = n) q = inqueue(q,x); /停车场无空位，进入便道else s1 = push(s1,x); /停车场有空位，进入停车场/处理汽车离开的情形void live(element x)/X为离开的车辆int f = 1;element 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);/进栈else /最后进入停车场s1中的车离开 f = 0;y = gettop(s1);s1 = pop(s1); cout停车场中汽车牌照号为x.num的车将离开data.num != x.num)r = p;p = p-next;if(!emptyqueue(q)link *p= q.front;while(p != NULL)&(p-data.num != x.num)r=p;p=p-next;if(p != NULL)coutendl;coutn便道上汽车牌照号为x.num的车辆将离开next=p-next;delete p;elsecout停车场内及便道上均没有编号为x.num的车辆，输入的车辆不存在!nendl;void process1() /输出停车场中的车辆编号int t=s1.top;couttt 停车场使用情况endl;coutttendlendl;coutt 1.停车场中的汽车牌照号endl;while(t!=0)couttts1.stackt.numendl;t-;coutnext;coutt 2.便道中的汽车牌照号endl;while(p!=NULL)coutttdata.numnext;coutendl;void main()char c; /c代表车辆到达、离开或者结束element x;s1=initstack(s1);s2=initstack(s2);q=initqueue(q);while(1)cout请选择处理车辆的事件nA) 到达 nB) 离开 nC) 结束 n;coutc;if(c=A|c=a) coutx.num;arrive(x);process1();process2(); else if(c=B|c=b) coutx.num;coutendl;live(x);process1();process2(); else if(c=C|c=c) cout结束，按任意键退出!n;break; elsecout输入错误，请重新输入!n;coutendl; 六、实验结果 七、实验体会 本次试验第一次使用栈和队列来解决一些实际问题，停车场采用了顺序栈，而甬道使用了顺序队列，通过这次实验熟悉并掌握了关于栈和队列的基本操作，诸如进栈、出栈、入队出队等操作，