实验9 栈与队列的应用(大作业).docVIP

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验九 栈与队列的应用 学生姓名 郑健超 专业班级 计算机1008班 学号 实验成绩 指导老师（签名 ） 日期 实验目的和要求 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用栈和队列的各种操作来进行具体的实际应用。 3、加强综合程序的分析、设计能力。 实验内容 1、请编制程序模拟停车场管理。停车场管理问题描述如下： 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向大门口处停放 (即最先到达的第一辆车停放在停车场的最里面) 。如果停车场已放满n辆车，则以后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。 要求： ⑴ 以顺序栈模拟停车场，以链队列模拟停车场外的便道，另设一个顺序栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车。 ⑵ 按从终端读入的数据序列进行管理。每一组输入数据包括三个数据项：汽车到达或离开的信息、汽车牌照号码、汽车到达或离开的时刻。如: （‘A’, 1, 5）, (‘A’, 2, 10), (‘D’, 1, 15), …… , (‘E’, 0, 0)。 其中 ‘A’ 表示到达，‘D’ 表示离去，‘E’表示结束。输出数据为：若有车辆到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。 ⑶ 建立头文件test9_stack.h和test9_queue.h，分别包含顺序栈和链队列的基本操作实现函数，建立主程序文件test9.cpp，在主函数中通过调用栈和队列的基本操作函数来实现上述功能。 提示： 栈与队列中的每个元素表示一辆汽车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test9.cpp中可定义： typedef struct { int num; //汽车牌照号码 int time; //进入停车场的时刻 } ElemType; //栈与队列中元素的数据类型 主函数的框架可参考如下： void main() { ElemType x, y; char flag; …… cout请输入车辆情况(A: 到达 D: 离开 E: 结束) ，车牌号码，时间； coutendl; cinflagx.numx.time; while (flag!=’E’) { if (flag==’A’) ……. //进栈或进队列，并输出汽车的停车位置 else if (flag==’D’) …… //出栈，并输出在车场内停留的时间和应交纳的费用 //若队列非空，则队头元素出队列（便道）并入栈（停车场） else …… //打印出错信息，提示重新输入 cout请输入车辆情况(A: 到达 D: 离开 E: 结束) ，车牌号码，时间； cinflagx.numx.time; } } 2、填写实验报告，实验报告文件取名为report9.doc。 3、上传实验报告文件report9.doc 、源程序文件test9.cpp及test9_stack.h和test9_queue.h到Ftp服务器上（ 40:5000 ）自己的文件夹下。 三. 抽象数据类型定义 void qinitiate(lqueue *q) //初始化队列 int empty(lqueue q) //清空队列 int append(lqueue *q,int x,int y) //插入队列 int qdelete(lqueue *q,int *d1,int *d2) //删除队列 void initiate(seqstack *s) //初始化堆栈 int push(seqstack *s,int x,int y) //入栈 int pop(seqstack *s,int *d1,int