实验九栈与队列的应用.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验九 栈与队列的应用 学生姓名 潘志良 专业班级 计算1201 学号 31201104 实验成绩 指导老师（签名 ） 日期 2013-11-27 一. 实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用栈和队列的各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。二. 实验内容1、请编制程序模拟停车场管理。停车场管理问题描述如下：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向大门口处停放 (即最先到达的第一辆车停放在停车场的最里面) 。如果停车场已放满n辆车，则以后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。要求： 以顺序栈模拟停车场，以链队列模拟停车场外的便道，另设一个顺序栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车。 按从终端读入的数据序列进行管理。每一组输入数据包括三个数据项：汽车到达或离开的信息、汽车牌照号码、汽车到达或离开的时刻。如: （A, 1, 5）, (A, 2, 10), (D, 1, 15), , (E, 0, 0)。 其中 A 表示到达，D 表示离去，E表示结束。输出数据为：若有车辆到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间和应交纳的费用。 建立头文件SeqStack.h和LinkQueue.h，分别包含顺序栈和链队列的基本操作实现函数，建立主程序文件test3_3.cpp，在主函数中通过调用栈和队列的基本操作函数来实现上述功能。提示：栈与队列中的每个元素表示一辆汽车，包含两个数据项：汽车牌照号码和进入停车场的时间。即在test3_3.cpp中可定义：typedef struct int num; /汽车牌照号码 int time; /进入停车场的时刻 ElemType; /栈与队列中元素的数据类型2、填写实验报告，实验报告文件取名为report9.doc。3、上传实验报告文件report9.doc 、源程序文件test3_3.cpp及SeqStack.h和LinkQueue.h到Ftp服务器上自己的文件夹下。三. 抽象数据类型定义（分别说明你设计的栈和队列所包含的基本操作及功能）typedef structint num;int time;ElemType;四. 存储结构定义及算法思路（包括栈和队列的存储结构定义、数据元素的类型定义及主函数的算法实现思路）struct StackElemType *stack;int top;int MaxSize;struct LNodeElemType data; LNode *next;void InitQueue(LinkQueue &Q)初始化列表bool EmptyQueue(LinkQueue &Q)判断列表是否为空void EnQueue(LinkQueue &Q,ElemType item)插入列表元素ElemType OutQueue(LinkQueue &Q)取列表元素ElemType PeekQueue(LinkQueue Q)取列表表头元素void ClearQueue(LinkQueue &Q)清除列表void InitStack(Stack &S)初始堆栈bool EmptyStack(Stack S)判断堆栈是否为空void Push(Stack &S,ElemType item)插入堆栈元素ElemType Pop(Stack &S)取堆栈元素ElemType Peek(Stack S)取堆栈表头元素void ClearStack(Stack &S)清除堆栈五. 实验结果与分析（包括运行结果截图、结果分析等）六. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】SeqStack.h: struct StackElemType *stack;int top;int MaxSize;void InitStack(Stack &S) S.MaxSize=10;S.stack=(ElemType*)malloc(S.MaxSize*sizeof(ElemType); if(!S.stack)cout分配内存失败!endl;exit(1);S.top=-1;bool EmptyStack(Stack S) return S.top=-1;void Push(Stack &S,ElemType item) if(S.top=S.MaxSize-1)S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*sizeof(ElemType);S.MaxSize*=2;S.top+;S.stackS.top=item;ElemType Pop(Stack &S)if(S.top=-1)cout顺序链为空endl;exit(1); S.top-;return S.stackS.top+1; ElemType Peek(Stack S)if(S.top=-1)cout顺序链为空data=item;newptr-next=NULL;if(Q.front=NULL) Q.front=newptr;else Q.rear-next=newptr;Q.rear=newptr;ElemType OutQueue(LinkQueue &Q)if(Q.front=NULL)cout队列为空的!ndata; LNode *p=Q.front;Q.front=p-next;if(Q.front=Q.rear) free(p);return temp;ElemType PeekQueue(LinkQueue Q) if(Q.front=NULL)cout队列为空的!ndata;void ClearQueue(LinkQueue &Q)if(Q.front!=NULL) delete Q.front;Q.front=Q.rear=NULL;test3_3.cpp:#include#include#include#includeusing namespace std;typedef struct int num;int time;ElemType;#includeSeqStack.h#includeLinkQueue.hint main()ElemType x,y;char Character;int max,n=0,Fare;Stack CarPark,temp;LinkQueue pavement;InitStack(CarPark);InitStack(temp);InitQueue(pavement);coutmax;cout请输入每小时停车的费用Fare; cout请输入车辆情况(A:到达 D:离开 E:结束),车牌号,时间Character;if(Character!=A&Character!=D&Character!=E)cout请按格式输入x.numx.time;if(Character=A) if(n=max) EnQueue(pavement,x);cout该车停在便道上endl;else Push(CarPark,x);cout该车停在停车场的第+n号endl;else if(Character=D)y=Pop(CarPark);while(y.num!=x.num) if(EmptyStack(CarPark)&y.num!=x.num) cout第x.num号车不在停车场=y.time&y.num=x.num)coutx.num号车停放了x.time-y.time小时，需要付款Fare*(x.time-y.time)元endl;n-;whi