栈和队列及其应用_停车场管理.doc

实验2 栈和队列及其应用-停车场管理一 需求分析设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按到达时间的先后顺序，一次由北朝向南排列（大门在最南边最先到达的第一辆汽车停放在车场最北端），若停车场已满，则以后来的汽车只能停在便道上，一旦有车辆开走，则便道上的第一辆车便可开进车场；当车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为其让路，待该车辆开出大门后，其他车辆在按原来顺序 开进车场，每辆停放在车场内的车辆按其待得时间长短缴纳费用（便道上不收费）。以栈模拟停车场，以队列模拟便道，按照从终端读入的数据进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离开”的信息，汽车牌照号以及到达或离开的时间。对每一组输入数据进行操作后的输出信息为：若是车辆到达则输出汽车在停车场或在便道上的位置，若是车辆离开则输出汽车在停车场内停留的时间和需要缴纳的费用（便道不收费）。栈以顺序结构实现，队列以链表结构实现。二 概要设计1. 设定栈的抽象数据类型定义：ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,n,n=0 数据关系：R=|ai-1,aiD，约定an为栈顶元素 基本操作： InitStack (&S) 操作结果:构造一个空栈 DestroyStack(&S) 初始条件: 栈S已存在 操作结果：销毁栈S ClearStack(&S) 初始条件: 栈S已存在 操作结果:将S清为空栈 Push(&S,e) 初始条件: 栈S已存在 操作结果：插入e到栈顶 Pop(&S,&e) 初始条件: 栈S已存在且非空 操作结果：删除栈顶元素用e返回其值Status StackFull(SqStack S)初始条件：栈已存在 操作结果：栈满则返回TRUE ，否则返回FALSEStatus StackEmpty(SqStack S)初始条件：栈已存在 操作结果：栈空则返回TRUE ，否则返回FALSE ADT Stackr2. 设定队列的抽象数据类型定义： ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,n,n=0 数据关系：R=|ai-1,aiD，约定a1为队头，an为对尾部 基本操作： InitQueue (&Q) 操作结果:构造一个空队列 EnQueue(&Q,e) 初始条件: 队列Q已存在 操作结果：插入e到队尾 DeQueue(&Q,&e) 初始条件: 队列Q已存在且非空 操作结果：删除队头元素用e返回其值Status QueueEmpty(LinkQueue &Q)初始条件：队列存在操作结果：队列空为真，否则为假 ADT Queue3. 本程序包含四个模块： 1 Void main()初始化；while(1)接受用户数据；作出相应操作；2 栈模块实现栈抽象数据类型定义；3 队模块实现队列抽象数据类型定义4 停车场有关操作三详细设计#include#include#include#define True 1#define False 0#define ok 1#define Error 0#define Infeasible -1#define Overflow -2/-*-*-*-*-*-*-*-*-车辆信息定义*-*-*-*-*-*-*/typedef structchar AD;int car_ID;int time;car_info;/-栈-/Status表示函数的返回状态typedef int Status;typedef car_info SElemType;#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef structSElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(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;return ok;/InitStackStatus StackFull(SqStack S)/栈满则返回TRUE ，否则返回FALSEif(S.top-S.base=S.stacksize) return True;else return False;/栈满吗Status StackEmpty(SqStack S)/栈空则返回TRUE ，否则返回FALSEif(S.top=S.base)return True;else return False;/栈空吗 Status Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素*S.top=e;S.top+;return ok;/PushStatus Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值if(S.top=S.base)return Error;S.top-;e=*S.top;return ok;/Pop/*-*-*-*-*-*队列*-*-*-*-*-*-*-/typedef car_info QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(Overflow);/存储分配失败Q.front-next=NULL;return ok;/InitQueueStatus EnQueue(LinkQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(Overflow);/存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return ok;/ EnQueueStatus DeQueue(LinkQueue &Q,QElemType &e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回ok;/否则返回Errorif(Q.front=Q.rear)return Error;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(p=Q.rear)Q.rear=Q.front;free(p);return ok;/DeQueueStatus QueueEmpty(LinkQueue &Q)if(Q.front=Q.rear)return ok;else return Error;/*-*-*-*-*-*-*-*-*费用定义函数*-*-*-*-*-*-*-*/int GetFee(car_info now,car_info before)int NowTime;int BeforeTime;int Fee;NowTime=now.time;BeforeTime=before.time;Fee=(NowTime-BeforeTime)*10;/每分钟10元return Fee;/-*-*-*-*-*-*-*-*-*-*-*-*-车辆到达函数-*-*-*-*-*-*-*-*-*-*-/void ArriveF(SqStack &parking,LinkQueue &road,car_info t,int &p,int &a)if(StackFull(parking)EnQueue(road,t);a+;printf(汽车在便道上第%d个位置n,a);/如果停车场栈满 ，则入队elsePush(parking,t);p+;printf(在停车场第%d个位置。n,p);/不满进停车场栈，并输出位置/-*-*-*-*-*-*-*-*-*-*-*-*-*-*-车辆离开函数-*-*-*-*-*-*-*-*-*-*-*-/void DepartF(SqStack &parking,LinkQueue &road,SqStack &S,car_info t,int &p,int &a)car_info e;inttemp;int Fee;if(t.time=0)/证明在便道上e=t;DeQueue(road,e);a-;printf(车辆%d开出便道。n,e.car_ID);else/在停车场temp=(*-parking.top).car_ID;/停车场的最后一位置车牌号赋予temp+parking.top;while(temp!=t.car_ID&!StackEmpty(parking)Pop(parking,e);Push(S,e);/从停车场栈出来进入暂存栈temp=(*-parking.top).car_ID;/现有车辆的最后一辆+parking.top;p-;/出去一辆车就p-，表示现有最后一辆车的位置if(StackEmpty(parking)printf(输入有误！请检查输入数据！n);elsePop(parking,e);/从停车场出来，但并不进暂存栈，而应计费Fee=GetFee(t,e);printf(该车应缴费用为%dn,Fee);/计费完毕p-;/从暂存栈进入停车场栈，并且在便道上的第一辆车开始进入 停车场栈while(!StackEmpty(S)/只要暂存栈不空Pop(S,e);Push(parking,e);/从暂存栈进入停车场栈p+;/在便道上的第一辆车开始进入停车场站栈，并且应输入进停车场栈时间和在停车场站的位置if(!QueueEmpty(road)DeQueue(road,e);temp=e.car_ID;printf(车辆%d出便道进停车场，请输入进停车场时间n,temp);scanf(%d,&e.time);Push(parking,e);p+;else printf(便道现已没车辆！n);/-*-*-*-*-*-*-*-主函数*-*-*-*-*-*-/void main()SqStack parking;SqStack S;LinkQueue road;InitStack(parking);InitStack(S);InitQueue(road);int i=0;int a=0;/显示在便道上的位置int p=0;/显示在停车场上的位置car_info car100;/用以存放每辆车的数据printf(举例说明本程序用法：n如果输入A 1 12,表示牌照号为1的车辆到达时间为12！n);printf(如果输入为D 1 12,表示牌照号为1的车辆离开停车场，离开时间为12！n);printf(如果下班请输入E 0 0n);while(1)i+;printf(请输入车辆进出情况：n);scanf(%c %d %d,&cari.AD,&cari.car_ID,&cari.time);char c;c=cari.AD;if(c=A)/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*若车辆到达-*-*-*ArriveF(parking,road,cari,p,a);c=getchar();else if(c=D)/-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-若车辆离开-*-*-*-*-*-*-*DepartF(parking,road,S,cari,p,a);c=getchar();else if(c=E)p