栈和队列及其应用停车场管理.pdf
.实验 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，否则返回 FALSE Status StackEmpty(SqStack S)初始条件：栈已存在 操作结果：栈空则返回 TRUE，否则返回 FALSE ADT Stackr 2.设定队列的抽象数据类型定义：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 Queue 3.本程序包含四个模块：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 struct char 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 struct SElemType*base;SElemType*top;int stacksize;SqStack;Status InitStack(SqStack&S)/构造一个空栈 s S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(Overflow);/存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;.return ok;/InitStack Status StackFull(SqStack S)/栈满则返回 TRUE，否则返回 FALSE if(S.top-S.base=S.stacksize)return True;else return False;/栈满吗 Status StackEmpty(SqStack S)/栈空则返回 TRUE，否则返回 FALSE if(S.top=S.base)return True;else return False;/栈空吗 Status Push(SqStack&S,SElemType e)/插入元素 e 为新的栈顶元素 *S.top=e;S.top+;return ok;/Push Status 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 QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;.Status InitQueue(LinkQueue&Q)/构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(Overflow);/存储分配失败 Q.front-next=NULL;return ok;/InitQueue Status 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;/EnQueue Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 ok;/否则返回 Error if(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;/DeQueue Status 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);/如果停车场栈满，则入队 else Push(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;int temp;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);else Pop(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)printf(下班时间，回家吃饭！n);break;else printf(输入有误！请重新输入！n);c=getchar();四 调试分析 处于调试需要，本程序设置的停车场容量为 4。当输入的进场车辆数量小于等于 4 时，计算机会依次显示车辆在的位置，当大于 4 时，会依次显示在便道上的位置。当输入出场车辆信息时，会显示停留时间以及费用并会显示从便道进车场的车辆信息。当用户输入的车牌号不在车场时系统会提示你输入错误，请重新输入。注意：本程序的计费单位为 10 元/分钟。车辆从便道进入车场会要求重新输入时间，因为在便道上不收费！具体操作请看下图！
