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

《实验9栈与队列的应用(大作业)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、,10），（‘D’，1,15），……，（‘E’，0,0）。其中‘A’表示到达，‘D’表示离去，‘E’表示结束。输出数据为：若冇车辆到达，则输出该汽午的停午位置；若冇车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。⑶建立头文件SeqStack.h和LinkQueue.h,分别包含顺序栈和链队列的基本操作实现函数，建立主程序文件test3_3.cpp，在主函数中通过调用栈和队列的基木操作函数来实现上述功能。提75:栈与队列中的每个元素表示一辆汽车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test3_3.cpp中可定义：typedefstructintnum;//汽车牌照号码

4、inttime;//进入停车场的时刻}ElemType;//栈与队列屮元素的数据类型2、填写实验报告，实验报告文件取名为report9.doc。3、上传实验报告文件report9.doc、源程序文件test3_3.cpp及SeqStack.h和LinkQueue.h到Ftp服务器上自己的文件夹下。一.抽象数据类型定义(分别说明你设计的栈和队列所包含的基本操作及功能)ADTSTACKisData：n(n>=0)个相同类型数据元素alza2,...，an构成的有限序列。用类型名Stack表示。Operation：voidlnitStack(Stack&S)//初始化栈为空voidPush(Sta

5、ck&S,ElemTypeitem}//元素item进栈，即插入到栈顶ElemTypePop(Stack&S)//删除栈顶元素并返回ElemTypePeek(Stack&S)//读取栈顶元素的值boolEmptyStack(Stack&S)//判断S是否为空，空返回true,否则返回falsevoidClearStack(Stack&S)//清除栈S中的所有素，释放动态存储空间endSTACKADTQUEUEisData：n(n>=0)个相同类型数据元素alza2,…，an构成的有限序列。用类型名QueueType表示。Operation：voidlnitQueue(QueueType&Q)

6、;//初始化链队voidEnQueue(LinkQueue&Q,ElemTypeitem)//向链队屮插入一个元素intEmptyQueue(LinkQueueQ)//判断队列是否空，空返回1，否则返0ElemTypeOutQueue(LinkQueue&Q)//出队列，并返回删除的元素ElemTypePeekQueue(LinkQueueQ)//读取队头元素voidClearQueue(LinkQueue&Q)//清空队列endQUEUE二.存储结构定义及算法思路(包括栈和队列的存储结构定义、数据元素的类型定义及主函数的算法实现思路)栈：structStack{ElemType氺stack

7、;mttop;intMaxSize;};队列：typedefstructnode{ElemTypedata;structnode*next;}LNode;typedefstruct{LNode氺front;LNode*rear;}LinkQueue;主函数：便道用队列，停车场和临时停放地用栈。需要知道停车场共有多少车位，用max表示，并用count表示停车场已经停放的车辆（随着车辆进入停车场将counts）。