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

1、1 / 8 实验2栈和队列及其应用 - 停车场管理 一. 需求分析 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。 汽车在停车场内按到达时间的先后顺序，一次由北朝向南排列(大门在最南边最 先到达的第一辆汽车停放在车场最北端)，若停车场已满，则以后來的汽车只能 停在便道上，一旦有车辆开走，则便道上的第一辆车便可开进车场；当车场内某 辆车要离开时，在他之后进入的车辆必须先退出车场为其让路，待该车辆开出大 门后，其他车辆在按原来顺序开进车场，每辆停放在车场内的车辆按其待得时 间长短缴纳费用(便道上丌收费)。 以栈模拟停车场，以队列模拟便道，按照从终端读入的数据进行模拟管理。 每

2、一组数据包括三个数据项：汽车“到达”或“离开”的信息，汽车牌照号以及 到达或离开的时间。对每一组输入数据进行操作后的输出信息为：若是车辆到达 则输出汽车在停车场或在便道上的位置，若是车辆离开则输出汽车在停车场内停 留的时间和需要缴纳的费用(便道丌收费)。栈以顺序结构实现，队列以链表结 构实现。 二. 概要设计 1. 设定栈的抽象数据类型定义： ADT Stack 数据对象：D=ai|ai e ElemSet,i= 1,2,-,n,n=0 数据关系：R=|ai-1 ,aieD,约定an为栈顶元素 基本操作： IiutStack (&S) 操作结果:构造一个空栈 DestroyStack( &S)

3、 初始条件：栈s己存在 操作结果：销毁栈S CleaiStack(&S) 初始条件：栈s己存在 操作结果将S清为空栈 Piish(&S,e) 初始条件：栈s己存在 操作结果：插入e到栈顶 Pop(&S、&e) 初始条件：栈S己存在且非空 操作结果：删除栈顶元素用e返回其值 Status StackFull(SqStack S) 初始条件：栈已存在 操作结果：栈满则返回TRUE ,否则返回FALSE Status StackEniptv(SqStack S) 2 / 8 初始条件：栈已存在 操作结果：栈空则返回TRUE ,否则返回FALSE ADT Stackr 2. 设定队列的抽象数据类型定义

4、： ADT Queue 数聶对象：D=ai|ai e ElemSet,i= 1,2,-,n,n=0 数据关系：R=|ai-l,aiGD,约定al为队头，an为对尾部 基本操作： IiiitQueue (&Q) 操作结果:构造一个空队列 EnQueue(&Q,e) 初始条件：队列Q己存在 操作结果：插入e到队尾 DeQueue(&Q,&e) 初始条件：队列Q己存在且非空 操作结果：删除队头元素用e返回其值 Status QueueEmpty(LnikQueue &Q) 初始条件：队列存在 操作结果：队列空为真，否则为假 ADT Queue 3. 本程序包含四个模块： 1 Void main()

5、初始化； while(l) 接受用户数据； 作出相应操作； 2栈模块一一实现栈抽象数据类型定义； 3队模块一一实现队列抽象数据类型定义 4停车场有关操作 三.详细设计 # iiiclude # iiiclude # mclude define True 1 define False 0 define ok 1 define Error 0 3 / 8 define Infeasible define Oveiilow -2 _*_*_*_*_*_*_*_*一车辆彳言息、定义 *_*_*_*_*_*_*/ tvpedef stmct chai AD: int car_ID: int time;

6、cai_infb; / - 栈 - / /Status表示函数的返回状态 tvpedef int Status; tvpedef cai_infb SElemTvpe; define STACK_INIT_SIZE 100 /存储空间初始分配量 #define STACKINCREMENT 10 存储空间分配增量 tvpedef stmct SElemType *base; SElemType *top; int stacksize; JSqStack; Status IiutStack(SqStack &S) /构造一个空栈s S.base=(SElemType*)nialloc(STACK

7、_INIT_SIZE * sizeofSElemTvpe); if(!S.base) exit(Overflow); 存储分配失败 S.top=S.base; S.stacksize=STACK INIT SIZE; return ok; /IiiitStack Status StackFull(SqStack S) 栈满则返回TRUE ,否则返回FALSE if(S.top-S.base=S.stacksize) return Tine; else return False; /栈满吗 Status StackEmpty(SqStack S) 栈空则返回TRUE ,否则返回FALSE if(

8、Stop=Sbase)etuin True; else return False; /栈空吗 Status Push(SqStack &S,SElemType e) 插入元素e为新的栈顶元素 *S.top=e; S.top+； 4 / 8 return ok; /Push Status Pop(SqStack &S.SElemTvpe &e) 若栈丌空，则删除s的栈顶元素，用e返回其值 if(S.top=S.base) return Enor; S.top; e=*S.top; return ok; /Pop * 队歹J*. *.*-* tvpedef cai_infb QElemTvpe;

9、tvpedef stmct QNode QElemTvpe data; stmct QNode *next; QNode,*QueuePti; tvpedef stmct QueuePtr front; QueuePti rear; JLuikQueue; Status IiiitQueue(LuikQueue &Q) /构造一个空队列Q Q.fiont=Q.iear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(Overflow)/存储分配失败 Q. fi ont-next=NULL; return ok; /IiiitQueue Sta

10、tus EnQueue(LinkQueue &Q.QElemTvpe e) /插入元素e为Q的新的队尾元素 QueuePti p; p=(QueuePtr)malloc(sizeof(QNode); if(! p) exit(Overflow);存储分配失败 p-data=e; p-next=NULL; Q.rear-next=p; Q.reai-p; return ok; / EnQueue Status DeQueue(LuikQueue &Q.QElemTvpe &亡) 若队列丌空，则删除Q的队头元素，用e返回其值，并返回ok; 否则返回Enor iRQ fiont=Q.reai) re

11、turn Error; QueuePti p; 5 / 8 p=Q.fiont-next; e=p-data; Q. fi ont-next=p-next; if(p=Q.rear) Q.reai-Q. front; fiee(p); return ok;/DeQueue Status QueueEmpty(LuikQueue &Q) if(Q. fiont=Q.rear) return ok; else return Error; /*.*.*.*.*_*_*_*_* 费用定义函 *-*-*-*-*-*-*-*/ mt GetFee(car_mfo now,car_mfo before) i

12、nt NowTiine; int BefbreTime; int Fee; NowTiiiie=now.tiiiie; BefbreTmie=before. time; Fee=(NowTime-BefbieTune)* 10/每分钟 10 元 return Fee; / - 函数 void AiTiveF(SqStack &parking,LuikQueue &road,car_uifb t,int &pjnt &a) if(StackFull(parkuig) EnQueue(road.t); a+; pnntf(”汽车在便道上第1个位置ira); 如果停车场栈满，则入队 else Pus

13、h(paiking,t); p+; prmtfC*在停车场第01个位置。iip); 丌满进停车场栈，并输出位置 6 / 8 _ 车辆离开函 void DepartF(SqStack &parkuigXmkQueue &road.SqStack &S,cai_info t,mt &p,int &a) car_iiifb e; int temp; int Fee; if(t.tiine=O)/证明在便道上 e=t； DeQueue(road,e); a; pnntfp车辆d 开出便道。ire.cai_ID); else/在停车场 temp=(*-paikuig.top).car_ID;/停车场的最

14、后一位置车牌号赋予temp 卄packing, top; while(temp!=t. c ar.ID&! StackEmpty(paikuig) Pop(paikuig,e); Push(S,e);/从停车场栈出来进入暂存栈 temp=( *-parkuig. top ).cai_ID;现有车辆的最后一辆 +paikingtop; p-;/出去一辆车就p-,表示现有最后一辆车的位置 if(StackEmpty(paikuig) piintf(输入有误！请检查输入数据！ n”)； else Pop(paikiiig,e);/从停车场出来，但并丌进暂存栈，而应计费 Fee=GetFee(t,e)

15、; pnntf(”该车应缴费用为dS”,Fee);计费完毕 p； 从暂存栈进入停车场栈，并且在便道上的第一辆车开始进入停车 场栈 wliile(! StackEmpty(S)/ 只要暂存栈丌空 Pop(S,e); Pu sh(parking,e);从暂存栈进入停车场栈 P+； 在便道上的第一辆车开始进入停车场站栈，并且应输入进停车场栈 时间和在停车场站的位置 if(! QueueEmpty(road) DeQueue(road,e); temp=e.cai_ID; pnntf(“车辆4出便道进停车场，请输入进停车场时间n”,temp); scanf(,%d,5&e.time); Push(pa

16、rkuig,e); 7 / 8 P卄; else 道现己没车辆！ iiH）； void main() SqStack parknig; SqStack S; LinkQueue road; IiutStack(paiking); IiutStack(S); IiutQueue(road); mt 1=0; nit a=0;/显示在便道上的位置 intp=0;/显示在停车场上的位置 car_info car100/ffl以存放每辆车的数据 pmitf(”举例说明本程序用法：n如果输入A 1 12,表示牌照号为1的车辆到达时间为12 ! 5”)； pnntf(如果输入为D1 12,表示牌照号为1的车辆离开停车场，离开时间为12! n”)； pnntf(如果下班请输入E 0 011); while(l) i+； pnmf(”请输入车辆进出情况：n”)； scanf(”c %d %cf；&caUAD,&caiicaT_ID,&caiidnw); chai c; c=cari.AD; AiTiveF(parkuig,road,cari pa); c=getcharQ； DepaitF(paikHig,ioad,S,cari,p,a); c=getcharQ; else if(c=E) prmtf(H F班时间，回家吃饭！ iin)； break; pnntfC输