资源描述：
《数据结构基础实验9》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验九栈与队列的应用学生姓名专业班级学号实验成绩指导老师（签名）日期实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用栈和队列的各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。二.实验内容1、请编制程序模拟停车场管理。停车场管理问题描述如下：设有一个可以停放n辆汽车的狭长停车场，它只有一个人门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向人门口处停放（即最先到达的第一辆车停放在停车场的最里血）。如果停车场已放满n辆车，则以后到达的车辆只能在
2、停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车俩再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。要求：（1）以顺序栈模拟停车场，以链队列模拟停车场外的便道，另设一个顺序栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车。⑵按从终端读入的数据序列进行管理。每一组输入数据包括三个数据项：汽车到达或离开的信息、汽车牌照号码、汽车到达或离开的时刻。如：（'A；1,5）,（7V,2,1
3、0）,（D,1,15）,……,（E,0,0）o其中'A'表示到达,D表示离去,E表示结朿。输出数据为：若有车俩到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。⑶建立头文件test9_stack.h和test9_queue.h,分别包含顺序栈和链队列的基本操作实现函数，是立主程序文件test9.cpp,在主函数屮通过调用栈和队列的基本操作函数來实现上述功能。提示：栈与队列中的每个元素表示一辆汽车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test9.cpp中可定义：typedefstruct{intnum;〃汽车牌照号码intt
4、ime;〃进入停车场的时刻}ElemType;〃栈与队列中元素的数据类型主函数的框架可参考如下：voidmain(){ElemTypex,y;charflag;coutvv”请输入车辆情况(A:到达D:离开E:结剌，车牌号码，时间“；cout«endl;cin»flag»x.num»x.time;while(flag!='E‘){if(flag==5A5)•……〃进栈或进队列，并输出汽车的停车位置elseif(flag==,D,)……〃出栈，并输出在车场内停留的时间和应交纳的费用〃若队列非空，则队头元素出队列(便道)并入栈(停车场)else……〃打印出错信息，提示重新输入cout
5、«H请输入车俩情况(A:到达D:离开E:结剌，车牌号码，时间cin>>flag»x.num»x.time;}}2、填'弓实验报告，实验报告文件取名为report9.doc。3、上传实验报告文件report9.doc、源程序文件test9.cpp及test9_stack・h和test9_queue.h到Ftp服务器上(ftp://10.61.14.240:5000)□己的文件夹下。二.抽象数据类型定义(分别说明你设计的栈和队列所包含的基本操作及功能)队列：voidInitQueue(LinkQueue&Q)〃初始化循环队列QvoidEnQueue(LinkQueue&Q,ElemT
6、ypeitem)〃进队列ElemTypeOutQueue(LinkQueue&Q)〃岀队列ElemTypePeekQueue(LinkQueueQ)〃检验队列是否为空ElemTypePeekQueue(LinkQueueQ)〃得到队头元素栈：voidInitStack(Stack&S)〃初始化栈intEmptyStack(StackS)〃若栈S为空栈返回1,否则返回0voidPush(Stack&S,ElemTypeitem)〃元素item进栈ElemTypePop(Stack&S)〃栈S的栈顶元素出栈并返回ElemTypePeek(StackS)〃取栈S的当前栈顶元素并返回vo
7、idClearStack(Stack&S)〃清除栈s,使成为空栈二.存储结构定义及算法思路（包括栈和队列的存储结构定义、数据元素的类型定义及主函数的算法实现思路）队列：structLNode{ElemTypedata;LNode*next;}；structLinkQueue{LNode*front;//头指针LNode*rear;//尾指针栈:structStack{ElemType*stack;//存栈元素inttop;//栈顶指示器intMaxSize;//栈的最大长度}；进
