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

Twinkle 贡献于2015-03-28

作者 liujun  创建于2007-08-30 05:41:00   修改者dell  修改于2014-01-15 15:20:56字数4625

文档摘要: 实验目的和要求1、学会通过对问题的分析,设计一种合理的数据结构,并进行定义及操作的实现。2、掌握利用栈和队列的各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。实验内容1、请编制程序模拟停车场管理。停车场管理问题描述如下:设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出
关键词:

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验九 栈与队列的应用 学生姓名 专业班级 学号 实验成绩 指导老师(签名 ) 日期 一. 实验目的和要求 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服务器上自己的文件夹下。 三. 抽象数据类型定义 栈的基本操作: /*初始化栈S为空*/ void InitStack(Stack &S) /*元素item进栈,即插入到栈顶*/ void Push(Stack &S,ElemType item) /*删除栈顶元素并返回*/ ElemType Pop(Stack &S) /*读取栈顶元素的值*/ ElemType Peek(Stack &S) /*判断S是否为空,若是则返回true,否则返回false*/ bool EmptyStack(Stack &S) /*清除栈S中的所有元素,释放动态存储空间*/ void ClearStack(Stack &S) 队列的基本操作: /*初始化链队*/ void InitQueue(LinkQueue &HQ) /*向链队插入一个元素*/ void EnQueue(LinkQueue &HQ,ElemType item) /*从队列中删除一个元素*/ ElemType OutQueue(LinkQueue &HQ) /*读取队首元素*/ ElemType PeekQueue(LinkQueue &HQ) /*检查链队是否为空*/ bool EmptyQueue((LinkQueue &HQ) /*清除链队列中的所有元素,使之成为空队*/ void ClearQueue(LinkQueue &HQ) 四. 存储结构定义及算法思路 栈的顺序存储结构定义: struct Stack{ ElemType *stack; int top; int MaxSize; }; 队列的链式存储结构定义: struct LNode{ ElemType data; LNode *next; }; struct LinkQueue{ LNode *front; LNode *rear; }; 五. 实验结果与分析 六. 心得体会 【附录----源程序】 test3_3.cpp #include #include typedef struct{ int num; int time; }ElemType; #include"SeqStack.h" #include"LinkQueue.h" void main() { ElemType x,y; char flag; int i=0,j,k,max,count=0,fee,a[100]; Stack park,temp; LinkQueue sidewalk; InitStack (park); InitStack (temp); InitQueue (sidewalk); cout<<"请输入停车场的容量:"; cin>>max; cout<<"请输入停车的费用(h):"; cin>>fee; cout<>flag>>x.num>>x.time; while(flag!='E'){ if(flag=='A'){ for(j=0;j=y.time&&y.num==x.num){ cout<>flag>>x.num>>x.time; } } SeqStack.h struct Stack{ ElemType *stack; int top; int MaxSize; }; void InitStack(Stack &S) { S.MaxSize=10; S.stack=new ElemType[S.MaxSize]; if(!S.stack){ cerr<<"动态存储分配失败!"<data=item; newptr->next=NULL; if(HQ.rear==NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear->next=newptr; } ElemType OutQueue(LinkQueue &HQ) { if(HQ.front==NULL){ cerr<<"链队为空,无法删除!"<data; LNode *p=HQ.front; HQ.front=p->next; if(HQ.front==NULL) HQ.rear=NULL; delete p; return temp; } ElemType PeekQueue(LinkQueue &HQ) { if(HQ.front==NULL){ cerr<<"链队为空无队首元素!"<data; } bool EmptyQueue(LinkQueue &HQ) { return HQ.front==NULL; } void ClearQueue(LinkQueue &HQ) { LNode *p=HQ.front; while(p!=NULL){ HQ.front=HQ.front->next; delete p; p=HQ.front; } HQ.rear=NULL; }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档