数据结构域算法设计-实验3-4栈和队列

《数据结构域算法设计-实验3-4栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三、四：停车场问题班级B11522学号02姓名刘靖宇成绩一、实验目的1.掌握栈的数据类型描述及栈的特点。2.掌握栈的顺序和链接两种存储的特点及算法描述。3.掌握栈的5种基本运算及算法在两种不同存储结构上的实现。4.掌握队列的数据类型描述及链式存储结构的特点和算法描述。5.掌握队列的5种基本运算及链式存储结构上的实现。二、实验内容1.问题描述设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门

2、外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。2．基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去

3、的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3．测试数据自己指定。4．实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。三、实验步骤1．编写栈的初始化、进栈和出栈算法。2．编写队列的初始化、进队和出队算法。3．编写处理车辆到达和

4、车辆离开情况的函数。第13页共13页4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。主函数中输入车辆的编号、到达和离开时间。5将实验源程序调试并运行，写出输入、输出结果。四、设计与编码#includetypedefstructCar{intnumber;intinTime;intoutTime;}Car;typedefCarUser;#defineFEIYONG0.05#defineMAXSIZE5#include"stdlib.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#

5、defineOVERFLOW-2typedefintStatus;typedefUserSElemType;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S)第13页共13页{S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVER

6、FLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack&S){free(S.base);returnOK;}StatusClearStack(SqStack&S){returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){returnS.top-S.base;}StatusGetTop(SqSta

7、ckS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;第13页共13页}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksiz

8、e+=STACKINCREMENT;}