栈与队列的应用.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验九 栈与队列的应用 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 05 05 一. 实验目的和要求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: 结束) ，车牌号码，时间；coutflagx.numx.time; while (flag!=E) if (flag=A) . /进栈或进队列，并输出汽车的停车位置else if (flag=D) /出栈，并输出在车场内停留的时间和应交纳的费用 /若队列非空，则队头元素出队列（便道）并入栈（停车场）else /打印出错信息，提示重新输入coutflagx.numx.time; 2、填写实验报告，实验报告文件取名为report9.doc。3、上传实验报告文件report9.doc 、源程序文件test9.cpp及test9_stack.h和test9_queue.h到Ftp服务器上（ 40:5000 ）自己的文件夹下。三. 抽象数据类型定义（分别说明你设计的栈和队列所包含的基本操作及功能） void InitQueue (Queue &Q); /构造一个空队列 Q int EmptyQueue (Queue Q); /判断队列Q是否为空，若空返回1，否则返回0 void EnQueue (Queue &Q, ElemType item); /元素 item 进队列Q ElemType OutQueue (Queue &Q); /队头元素出队列Q，并返回其值 ElemType PeekQueue (Queue Q); /返回队头元素值 void ClearQueue (Queue &Q); /清空队列 栈的动态数组顺序存储结构可定义如下： struct Stack ElemType *stack ;/ 存栈元素 int top; / 栈顶指示器 int MaxSize; / 栈的最大长度 ; 栈的基本操作可包括： void InitStack (Stack &S); /构造一个空栈 S int EmptyStack (Stack S); /若栈S为空栈返回1，否则返回0 void Push(Stack &S, ElemType item); /元素 item进栈 ElemType Pop(Stack &S); /栈S的栈顶元素出栈并返回 ElemType Peek(Stack S); /取栈S的当前栈顶元素并返回 void ClearStack (Stack &S); /清除栈s，使成为空栈四. 存储结构定义及算法思路（包括栈和队列的存储结构定义、数据元素的类型定义及主函数的算法实现思路）（分别说明你设计的栈和队列所包含的基本操作及功能） void InitQueue (Queue &Q); /构造一个空队列 Q int EmptyQueue (Queue Q); /判断队列Q是否为空，若空返回1，否则返回0 void EnQueue (Queue &Q, ElemType item); /元素 item 进队列Q ElemType OutQueue (Queue &Q); /队头元素出队列Q，并返回其值 ElemType PeekQueue (Queue Q); /返回队头元素值 void ClearQueue (Queue &Q); /清空队列 栈的动态数组顺序存储结构可定义如下： struct Stack ElemType *stack ;/ 存栈元素 int top; / 栈顶指示器 int MaxSize; / 栈的最大长度 ; 栈的基本操作可包括： void InitStack (Stack &S); /构造一个空栈 S int EmptyStack (Stack S); /若栈S为空栈返回1，否则返回0 void Push(Stack &S, ElemType item); /元素 item进栈 ElemType Pop(Stack &S); /栈S的栈顶元素出栈并返回 ElemType Peek(Stack S); /取栈S的当前栈顶元素并返回 void ClearStack (Stack &S); /清除栈s，使成为空栈五. 实验结果与分析正常输入的情况截图：错误输入的情况截图:六. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）、上面的截图错误的情况是一开始编的程序，不知道是什么原因，不论怎么也调不出来，最后与同学一起探讨了很久，由于程序代码实在是太多，又没有明显的错误，于是乎，就悲剧了，最后经过同学的改进，以及修改了大段的代码，勉强出了结果，但是还是会偶尔出现死循环，因此这个程序的健壮性不是很强。【附录-源程序】Test9.cpp#include #include typedef structint num; /汽车牌照号码int time; /进入停车场的时刻 ElemType; /栈与队列中元素的数据类型#include test9_stack.h#include test9_queue.hvoid main()ElemType x, y;char flag;int i,n,m,fee,time;bool f;Stack p1,p2;Queue q;InitStack(p1);InitStack(p2);InitQueue(q);EmptyStack(p1);EmptyStack(p2);EmptyQueue(q);coutn;m=n;coutfee;cout请输入进出车辆情况(A为进入 D为离开 E表示结束) ，车牌号码，进出车的时间endl; coutflagx.numx.time; /输入车辆进出情况，车牌号码和时间time=0;i=0;while (flag!=E) f=1; if (flag=A) /进栈或进队列，并输出汽车的停车位置 if(n!=0) i+; Push(p1,x); cout这辆车停在：i车位endl; n-; else EnQueue(q,x); cout此车辆正在等待进车位endl; else if (flag=D) /出栈，并输出在车场内停留的时间和应交纳的费用 /若队列非空，则队头元素出队列（便道）并入栈（停车场） if(n=m) cout停车场为空，没有车辆可以离开，请重新确认！endl; else y=Pop(p1); while(y.num!=x.num) /在停车场中寻找要出站的汽车 Push(p2,y); if(EmptyStack(p1) f=0; break; y=Pop(p1); while(!EmptyStack(p2) Push(p1,Pop(p2); if(f=1) /车辆在停车场中 time=x.time-y.time; /该车在停车场的时间 if(!EmptyQueue(q) /将便道的车停入停车场 y=OutQueue(q); y.time=x.time; Push(p1,y); else /如果便道没有车 n+; if(time0) cout时间输入错误,请重新输入正确时间：x.time; time=x.time-y.time; cout车牌号为x.num的汽车在停车场内停留的时间为timeendl; cout此车辆需要交纳的费用为time*fee元endl; coutendl; i-; else while(!EmptyQueue(q) y=OutQueue(q); if(x.num=y.num) cout车牌号为x.num的汽车开出便道，所交费用为零endl; coutendl; f=0; else Push(p2,y); if(f) cout车号输入有误endl; coutendl; while(!EmptyStack(p2) EnQueue(q,Pop(p2); while(!EmptyQueue(q) Push(p2,OutQueue(q); while(!EmptyStack(p2) EnQueue(q,Pop(p2); else /打印出错信息，提示重新输入 cout输入错误，请重新输入！endl; cout请输入车辆情况(A为进入 D为离开 E表示结束) ，车牌号码，时间flagx.numx.time; ClearQueue(q);ClearStack(p1);ClearStack(p2);test9_queue.hstruct LNodeElemType data;LNode *next;struct QueueLNode *front; / 队头指针LNode *rear; / 队尾指针;void InitQueue(Queue &Q)Q.front=Q.rear=NULL;bool EmptyQueue(Queue &Q) /判断队列是否为空，空返回1，否则返回0return Q.front=NULL;void EnQueue(Queue &Q,ElemType item) /队列插入 LNode *newptr=new LNode;newptr-data=item;newptr-next=NULL;if(Q.rear=NULL) Q.front=Q.rear=newptr;else Q.rear=Q.rear-next=newptr;ElemType OutQueue(Queue &Q) / 出队列if(Q.front=NULL) cerr链队为空,出错!data;LNode *p=Q.front;Q.front=p-next;if(Q.front=NULL) Q.rear=NULL;delete p;return temp;void ClearQueue(Queue &H) /清空队列LNode* p=H.front;while(p!=NULL) H.front=H.front-next; delete p; p=H.front;H.rear=NULL;test9_stackstruct Stack ElemType *stack ; / 存栈元素 char top; / 栈顶指示器 char MaxSize; / 栈的最大长度;void InitStack (Stack &S) /构造一个空栈 SS.MaxSize=10;S.stack=new ElemTypeS.MaxSize;if(!S.stack) cerr动态存储分配失败!endl; exit(1);S.top=-1; int EmptyStack (Stack &S)/若栈S为空栈返回1，否则返回0return S.top=-1;void Push(Stack &S, ElemType item)/元素 item进栈S.top