《数据结构-停车场管理课程设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构-停车场管理课程设计报告.docx(18页珍藏版)》请在第壹文秘上搜索。
1、课程设计报告一、需求分析1、以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。2、用户输入汽车信息后,程序对每一组输入数据进行操作后的输出信息为:假设是车辆到达,那么输出汽车在停车场内或便到上的停车位置;假设是车辆离去,那么输出汽车在停车场内停留的时间和应缴纳的费用(在便道上停留的时间不收费)。3、本程序要求栈以顺序结构实现,队列以链表结构实现。4、测试数据:设n=2,输入数据为:(“A”,1,5),(“A”,2,10),(“D”,L15),(“A”3,20),(“A”,
2、4,25),(“A”,5,30),(“D”,2,35),AD”,4,40),(“E”,0,0)。其中:“A”表示到达(AiiivaI);wDw表示离去(Departure);itEff表示输入结束(End)e5、程序执行的命令为:1)创立停车场;2)创立便到;3)执行对车辆的运算;4)输出所需的数据。二、概要设计1、设定栈的抽象数据类型定义:ADTStack数据对象:D=aiIaiCharSet,i=l,2,.,n,n0)数据关系:Rl=Ia(i-l),aiD,i=2,.,n)根本操作:InitStack(feS)操作结果:构造一个空栈S。StackEmpty(三)初始条件:栈S已存在。操作结
3、果:假设栈S为空栈,那么返回TURE,否那么FALSE。StackLength(三)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。GetToP(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。Push(feS,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。StackTraverse(S,visit()初始条件:栈S已存在且非空。操作结果:从栈底到栈顶依次对S的每个数据元素调用函数ViSit()。一旦ViSit()失败,那么操作失败。ADTStack2
4、、设定队列的抽象数据类型定义:ADTQueue数据对象:D=aiIaiElemSetJ=I,2,.tn,nO)数据关系:Rl=Ia(i-l),aiD,i=2,.,n)约定其中al端为队列头,an端为队列尾根本操作:InitQUelIe(&Q)操作结果:构造一个空队列Q。QueueEmpty(Q)初始条件:队列Q已存在。操作结果:假设Q为空队列,那么返回TURE,否那么FALSE。QueueLength(Q)初始条件:队列Q已存在。操作结果:返回Q的元素个数,即队列的长度。GetHead(Q,&e)初始条件:Q为非空队列。操作结果:用e返回Q的对头元素。EnQUeUe(&Q,e)初始条件:队列Q
5、已存在。操作结果:插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件:Q为非空队列。操作结果:删除Q的队头元素,并用e返回其值。QueueTraverse(Q,visit()初始条件:Q已存在且非空。操作结果:从队头到队尾,依次对Q的每个数据元素调用函数ViSit()。一旦ViSit()失败,那么操作失败。ADTQueue3、设定停车场的抽象数据类型为:ADTPark(数据对象:D=aiIaiElemSet,i=1,2,.,n,n0数据关系:Rl=Ia(M),aiD,i=2,.,n)根本操作:Arrival(Park&P,Shortcut&S,intn)初始条件:栈S存在。操作
6、结果:在输入车牌号和进场时间后,输出停车的车道。1.eave(Park&P,Park&P1,Shortcut&S,intcost)初始条件:栈S存在且非空。操作结果:在输入车牌号和离场时间后,输出车停留时间以及费用。ADTPark4、设定便到的抽象数据类型为:ADTCarPtr数据对象:D=aiIaiElemSet,i=1,2,.,n,n0数据关系:Rl=Ia(M),aiD,i=2,.,n)根本操作:EnQueue(S,number,ar_time)初始条件:停车场已满,队列存在。操作结果:在输入车牌号和进场时间后,输出车停留在便道上的位置。DeQueue(S,w)初始条件:停车场有车辆离开。
7、操作结果:输出由便到进入停车场的汽车车牌号DeQueue(S,q)初始条件:便道上有车离开。操作结果:输出离开车辆车牌以及停留时间。ADTCarPtr5、本程序包含五个模块1)主程序模块:Voidmain()初始化;Do接受命令;处理命令;while(命令=退出);12)栈模块一一实现栈抽象数据类型3)队列模块一一实现队列抽象数据类型4)停车场模块一一实现停车场抽象数据类型5)便道模块一一实现便到抽象数据类型各模块之间的调用关系如下:主程序模块I栈模块I队列模块I停车场模块I便道模块三、详细设计1、车辆类型typedefstructCarl车intnumber;/汽车车号intar_time;
8、汽车到达时间(CarNode;2、栈类型typedefStnICt停车场CarNode*base;停车场的堆栈底CarNode*lop;/停车场的堆栈顶intstacksize;)Park;栈的根本操作设置如下:VoidInitStack(Stack&S)初始化,设S为空栈IntStackLength(StackS)返回栈S的长度S.sizeStatusGetTop(StackS)假设S为空栈,那么返回TURE;否那么返回FALSEStatusGetTop(StackS,ElemTypee)假设栈S不空,那么以e带回栈顶元素并返回TURE,否那么返回FALSEStatusPush(Stack&
9、S,ElemTypee)假设分配空间成功,那么在S的栈顶插入新的栈顶元素e,并返回TURE否那么栈不变,并返回FALSEStatusPop(Stack&S,ElemType&e)假设栈不空,那么删除S的栈顶元素并以e带回其值,且返回TURE否那么返回FALSEVoidStackTraverseCStackS,Status(*visit)(ElemTypee)从栈底到栈顶依次对S中的每个结点调用函数visit其中局部操作的算法:voidInitStack(Park&P,intn)/初始化停车场P.top=P.base=(CarNode*)malloc(n*sizeof(Carl);Rstacks
10、ize=O;)voidPush(Park&P,CarNodee)车进入停车场*P.top=e;Rtop+;+Rstacksize;)voidPop(Park&P,CarNode&e)(车离开停车场Rtop;e=*P.top;-Rstacksize;3、队列类型typedefstructCar2车intnumber;汽车车号intar_time;汽车到达时间structCar2*next;*CarPtr;typedefstruct便道CarPtrfront;/便道的队列的对头CarPtrrear;便道的队列的队尾intlength;(Shortcut;队列的根本操作设置如下:StatusTnit
11、Queue(LinkQueue&Q)构造一个空列QStatusQueueEmpty(LinkQueueQ)假设队列Q为空队列,那么返回TURE,否那么返回FALSEStatusQueueLengthCLinkQueueQ)返回Q的元素个数,即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e)假设队列不空,那么用e返回Q的队头元素,并返回0K;否那么返回ERRoRStatusEnQueueCLinkQueue&Q,QEIemTypee)插入元素e为Q的新的队尾元素StatusDeQueue(LinkQueueQ,QEIemType&e)假设队列不空,那么删除Q
12、的队头元素,用e返回其值,并返回0K;否那么返回ERRORStatusQueueTraverse(LinkQueueQ,visit()从队头到队尾依次对队列Q中每个元素调用函数ViSit(),一旦ViSit失败,那么操作失败。其中局部操作的算法:voidInitQueue(Shortcut&S)初始化使道S.front=S.rear=(CarPtr)malloc(sizeof(Car2);S.front-next=NULL;SJength=O;)voidEnQueueCShortcut&S,intnumber,intar_time)(车进入便道CarPtrp;p=(CarPtr)malloc(
13、sizeof(Car2);p-number=number;p-ar_time=ar_time;p-next=NULL;S.rear-next=p;相连S.rear=p;+SJength;)voidDeQueue(Shortcut&S,CarPtr&w)(车离开便道if(S.length!=0)(w=S.front-next;S.front-next=S.front-next-next;-SJength;4、停车场、便道的类型其中局部操作的算法:voidArrival(Park&P,Shortcut&S,intn)对进站车辆的处理intnumber,ar_time;Prindr请输入车牌号:”)
14、;scanf(,%d,(fenumber);Printf(进场的时刻scanf(H%d,&ar_time);if(P.stacksizen)1CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);Prinlfr该车应停在第d号车道。n,Rstacksize);1else1EnQueue(S,number,ar_time);PrintIr停车场已满,请暂时停在便道的第d个位置。n,S.length);)voidLeave(Park&P,Park&P1,Shortcut&S,intcost)对离站车辆的处理intnumber,le_time,flag,money;CarPtrc,q;inttimes;Printf(请输入车牌号:”);scanf(%d,&number);Printf(出场的时刻巧;scanf(,%d,(fele-time);CarNodee,m;CarPtrw;While(Rstack