资源描述：
《栈和队列及其应用_停车场管理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验2栈和队列及其应用--------停车场管理一．需求分析设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按到达时间的先后顺序，一次由北朝向南排列（大门在最南边最先到达的第一辆汽车停放在车场最北端），若停车场已满，则以后来的汽车只能停在便道上，一旦有车辆开走，则便道上的第一辆车便可开进车场；当车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为其让路，待该车辆开出大门后，其他车辆在按原来顺序开进车场，每辆停放在车场内的车辆按其待得时间长短缴纳费用（便道上不收费）。以栈模拟停车场，以队列模拟便道，按照从终端读入的数据进行模拟管理。每一
2、组数据包括三个数据项：汽车“到达”或“离开”的信息，汽车牌照号以及到达或离开的时间。对每一组输入数据进行操作后的输出信息为：若是车辆到达则输出汽车在停车场或在便道上的位置，若是车辆离开则输出汽车在停车场内停留的时间和需要缴纳的费用（便道不收费）。栈以顺序结构实现，队列以链表结构实现。二．概要设计1.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai
3、ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：R={
4、ai-1,ai∈D}，约定an为栈顶元素基本操作：InitStack(&S)操作结果:构造一个空栈DestroyStack(
5、&S)初始条件:栈S已存在操作结果：销毁栈SClearStack(&S)初始条件:栈S已存在操作结果:将S清为空栈Push(&S,e)初始条件:栈S已存在操作结果：插入e到栈顶Pop(&S,&e)初始条件:栈S已存在且非空操作结果：删除栈顶元素用e返回其值StatusStackFull(SqStackS)初始条件：栈已存在操作结果：栈满则返回TRUE，否则返回FALSEStatusStackEmpty(SqStackS)初始条件：栈已存在操作结果：栈空则返回TRUE，否则返回FALSE}ADTStackr2.设定队列的抽象数据类型定义：ADTQueue{数据对象：D={a
6、i
7、ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：R={
8、ai-1,ai∈D，约定a1为队头，an为对尾部}基本操作：InitQueue(&Q)操作结果:构造一个空队列EnQueue(&Q,e)初始条件:队列Q已存在操作结果：插入e到队尾DeQueue(&Q,&e)初始条件:队列Q已存在且非空操作结果：删除队头元素用e返回其值StatusQueueEmpty(LinkQueue&Q)初始条件：队列存在操作结果：队列空为真，否则为假}ADTQueue3.本程序包含四个模块：1Voidmain(){初始化；while(1){接受用户数据；作出
9、相应操作；}}2栈模块——实现栈抽象数据类型定义；3队模块——实现队列抽象数据类型定义4停车场有关操作三．详细设计#include#include#include#defineTrue1#defineFalse0#defineok1#defineError0#defineInfeasible-1#defineOverflow-2//--*-*-*-*-*-*-*-*-车辆信息定义*-*-*-*-*-*-*//typedefstruct{charAD;intcar_ID;inttime;}car_info;//---
10、---------------------------------------------栈----------------------------------////Status表示函数的返回状态typedefintStatus;typedefcar_infoSElemType;#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStac
11、k(SqStack&S){//构造一个空栈sS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(Overflow);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnok;}//InitStackStatusStackFull(SqStackS){//栈满则返回TRUE，否则返回FALSEif(S.top-S.base>=S.stacksize)returnTrue;
