数据结构-停车场管理课程设计报告.docx
课程设计报告一、需求分析1、以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。2、用户输入汽车信息后，程序对每一组输入数据进行操作后的输出信息为：假设是车辆到达，那么输出汽车在停车场内或便到上的停车位置；假设是车辆离去，那么输出汽车在停车场内停留的时间和应缴纳的费用(在便道上停留的时间不收费)。3、本程序要求栈以顺序结构实现，队列以链表结构实现。4、测试数据：设n=2,输入数据为：(“A”，1,5),(“A”，2,10),(“D”，L15),(“A”3,20),(“A”,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=<a(i-l),ai>Ia(i-l),aiD,i=2,.,n)根本操作：InitStack(<feS)操作结果：构造一个空栈S。StackEmpty(三)初始条件：栈S已存在。操作结果：假设栈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、设定队列的抽象数据类型定义：ADTQueue数据对象：D=aiIaiElemSetJ=I,2,.tn,nO)数据关系：Rl=<a(i-l),ai>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已存在。操作结果：插入元素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=<a(i-1),ai>Ia(M),aiD,i=2,.,n)根本操作：Arrival(Park&P,Shortcut&S,intn)初始条件：栈S存在。操作结果：在输入车牌号和进场时间后，输出停车的车道。1.eave(Park&P,Park&P1,Shortcut&S,intcost)初始条件：栈S存在且非空。操作结果：在输入车牌号和离场时间后，输出车停留时间以及费用。ADTPark4、设定便到的抽象数据类型为：ADTCarPtr数据对象：D=aiIaiElemSet,i=1,2,.,n,n0数据关系：Rl=<a(i-1),ai>Ia(M),aiD,i=2,.,n)根本操作：EnQueue(S,number,ar_time)初始条件：停车场已满，队列存在。操作结果：在输入车牌号和进场时间后，输出车停留在便道上的位置。DeQueue（S,w）初始条件：停车场有车辆离开。操作结果：输出由便到进入停车场的汽车车牌号DeQueue（S,q）初始条件：便道上有车离开。操作结果：输出离开车辆车牌以及停留时间。ADTCarPtr5、本程序包含五个模块1）主程序模块：Voidmain（）初始化；Do接受命令；处理命令；while（"命令"=''退出"）；12）栈模块一一实现栈抽象数据类型3）队列模块一一实现队列抽象数据类型4）停车场模块一一实现停车场抽象数据类型5）便道模块一一实现便到抽象数据类型各模块之间的调用关系如下：主程序模块I栈模块I队列模块I停车场模块I便道模块三、详细设计1、车辆类型typedefstructCarl车intnumber;/汽车车号intar_time;汽车到达时间(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&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);Rstacksize=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;队列的根本操作设置如下：StatusTnitQueue(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的队头元素，用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(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请输入车牌号：”)；scanf(',%d",(fenumber);Printf("进场的时刻scanf(H%d",&ar_time);if(P.stacksize<n)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
