栈与队列的应用

《栈与队列的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验九栈与队列的应用学生姓名专业班级学号实验成绩指导老师（签名）日期0505一.实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用栈和队列的各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。二.实验内容1、请编制程序模拟停车场管理。停车场管理问题描述如下：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向大门口处停放(即最先到达的第一辆车停放在停车场的最里

2、面)。如果停车场已放满n辆车，则以后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。要求：⑴以顺序栈模拟停车场，以链队列模拟停车场外的便道，另设一个顺序栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车。⑵按从终端读入的数据序列进行管理。每一组输入数据包括三个数据项：汽车到

3、达或离开的信息、汽车牌照号码、汽车到达或离开的时刻。如:（‘A’,1,5）,(‘A’,2,10),(‘D’,1,15),……,(‘E’,0,0)。其中‘A’表示到达，‘D’表示离去，‘E’表示结束。输出数据为：若有车辆到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。⑶建立头文件test9_stack.h和test9_queue.h，分别包含顺序栈和链队列的基本操作实现函数，建立主程序文件test9.cpp，在主函数中通过调用栈和队列的基本操作函数来实现上述功能。提示：栈与队列中的每个元素表示一辆汽

4、车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test9.cpp中可定义：typedefstruct{intnum;//汽车牌照号码inttime;//进入停车场的时刻}ElemType;//栈与队列中元素的数据类型主函数的框架可参考如下：voidmain(){ElemTypex,y;charflag;……cout<<"请输入车辆情况(A:到达D:离开E:结束)，车牌号码，时间"；cout<>flag>>x.num>>x.time;while(flag!=’E’){if(flag==’A’)…….//进栈或进队

5、列，并输出汽车的停车位置elseif(flag==’D’)……//出栈，并输出在车场内停留的时间和应交纳的费用//若队列非空，则队头元素出队列（便道）并入栈（停车场）else……//打印出错信息，提示重新输入cout<<"请输入车辆情况(A:到达D:离开E:结束)，车牌号码，时间"；cin>>flag>>x.num>>x.time;}}2、填写实验报告，实验报告文件取名为report9.doc。3、上传实验报告文件report9.doc、源程序文件test9.cpp及test9_stack.h和test9_queue.h到Ftp服务器上（f

6、tp://10.61.14.240:5000）自己的文件夹下。三.抽象数据类型定义（分别说明你设计的栈和队列所包含的基本操作及功能）①voidInitQueue(Queue&Q);//构造一个空队列Q②intEmptyQueue(QueueQ);//判断队列Q是否为空，若空返回1，否则返回0③voidEnQueue(Queue&Q,ElemTypeitem);//元素item进队列Q④ElemTypeOutQueue(Queue&Q);//队头元素出队列Q，并返回其值⑤ElemTypePeekQueue(QueueQ);//返回队头元素值⑥

7、voidClearQueue(Queue&Q);//清空队列⑴栈的动态数组顺序存储结构可定义如下：structStack{ElemType*stack;//存栈元素inttop;//栈顶指示器intMaxSize;//栈的最大长度};⑵栈的基本操作可包括：①voidInitStack(Stack&S);//构造一个空栈S②intEmptyStack(StackS);//若栈S为空栈返回1，否则返回0③voidPush(Stack&S,ElemTypeitem);//元素item进栈④ElemTypePop(Stack&S);//栈S的栈顶元

8、素出栈并返回⑤ElemTypePeek(StackS);//取栈S的当前栈顶元素并返回⑥voidClearStack(Stack&S);//清除栈s，使成为空栈四.存储结构定义及