数据结构停车场管理课程设计报告.docx

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.stacksizenumber;Push(P,m);free(w);Prinlf(车牌号为d的车已由便道进入停车场n,m.number);)PrinIf(停车费为d,停车时间为dn,money,Mmes);1elsePrintf(停车场不存在牌号为d的车,在便道上找n二number);c=S.front;if(S.length!=0)(while(c-next!=NULL)(if(c-next-number=number)(printf(%d车从便道上离开，停留时间%dnc-n

15、ext-number,le-time-c-next-ar_time);c-next=c-next-next;S.length;break;)c=c-next;DeQueue(S,q);S.rear-next=q;S.rear=q;1)五、主函数的算法:voidmain()intn,cost;CharfIag/选项ParkP,Q;Prinlf(输入停车场的规模:)；scanf(,%d,n);Printfr每小时收费门;scanf(H%dH,&cost);ShortcutS;InitStaCk(P,n);初始化InitStack(Q,n);InitQueue(三);while(l)(COUIfla

16、g;switch(flag)(caseA,:casea:Arrival(P,S,n);break;车进入停车场case,D:cased,:1.eave(P,Q,S,cost);break;车离开停车场caseE,:casee,:return0;break;default:printf(Inputerror!n);break;六、函数的调用关系图反映了演示程序的层次结构:四、调试分析1、由于刚开始对队列元素删除的不了解，使得程序的操作直接对队列中的元素删除，而不是删除对头元素，这违背了题目要求。经过修改后，这一问题得到解决。2、栈的元素中SteP域没有太多用处，可以省略。3、StaCkTraVe

17、rS在调试过程中很有用，它可以插入在算法中多处，以观察停车场管理中车辆走动的次序是否正确，但对最后的执行版本么有用。五、用户手册1、本程序的运行环境为WindoWs,执行文件为：停车场管理.exe2、进入演示程序后，即显示文本方式的用户界面：3、进入车辆输入信息的命令后，程序开始运行。4、按回车后程序输出相应的结果。六、测试结果机叫停钿电.exe胞入停车场的规模：2售小时收费：2请选择(a,d,e)1,1就肇置超彘L号车道。请选择(A,D,E)：All三u,山DD,E)拿人车牌号：1圆的时刻n5军费知0,停车时间为10友择(A,D,E),遒箭专牌号：3进场的时刻：2。该奉应停在第2号车道。请选

18、择(A,D,E)I牌号：4ABddS科供据结构机程序停车法婕exe5请E)2*1:番时已I的场择空选r.1E号:3，D,明酒车时已I入的选.5道号:3内，D牌如450A,车时为为I*牌车速anykeytocontinue.10A,车时为为I人的tK鲁牌车选七、附录#include#include#include栈，模拟停车场typedefstructCarl车intnumber;汽车车号intar_time;汽车到达时间)CarNode;typedefStrUCt停车场CarNode*base;/停车场的堆栈底CarNode*top;停车场的堆栈顶intstacksize;)Park;队列，模

19、拟便道typedefstructCar2车intnumber;汽车车号intar_time;汽车到达时间structCar2*next;I*CarPtr;typedefstruct便道CarPtrfront;便道的队列的对头CarPtrrear;便道的队列的队尾intlength;(Shortcut;voidInitStack(Park&P,intn)初始化停车场P.top=P.base=(CarNode*)malloc(n*sizeof(Carl);Rstacksize=O;1voidPush(Park&P,CarNodee)车进入停车场*P.top=e;Rtop+;+Rstacksize;

20、1voidPop(Park&P,CarNOde&e)车离开停车场-Rtop;e=*P.top;-Rstacksize;voidInitQueueCShortcut&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.rea

21、r-next=p;/S.rear=p;+S.length;)voidDeQueueCShortcut&S,CarPtr&w)/车离开便道if(S.length!=0)(w=S.front-next;S.front-next=S.front-next-next;-SJength;voidArrivaI(Park&P,Shortcut&S,intn)对进站车辆的处理intnumber,ar_time;Printfc请输入车牌号：”)；scanf(,%d,number);Primf(进场的时刻scanf(,%d,&ar_time);if(P.stacksizen)(CarNodec;c.number

22、number;c.ar_time=ar_time;Push(P,c);Printf(该车应停在第d号车道。n,Rstacksize);else(EnQueue(S,number,ar_time);Printf(停车场己满，请暂时停在便道的第d个位置。n”,SJength);voidLeave(Park&P,Park&P1,Shortcut&S,intcost)对离站车辆的处理intnumber,le_time,flag,money;CarPtrc,q;inttimes;Printf(请输入车牌号：”)；scanf(,%d,number;Push(P,m);free(w);Prinlf(车牌号

23、为d的车已由便道进入停车场n,m.number);elsePrintf(停车场不存在牌号为d的车,在便道上找n,number);(c=S.front;if(S.length!=O)(while(c-next!=NULL)(if(c-next-number=number)(Printfe%d车从便道上离开，停留时间%dnc-next-number,le-time-c-next-ar-time);c-next=c-next-next;-SJength;c=c-next;break;1elseDeQueue(S,c);主函数voidmain()(intn,cost;charflag;/选项ParkP,Q;PrinIfc输入停车场的规模scanf(%d,(fcn);Primfc每小时收费scanf(%d,fccost);ShortcutS;InitStaCk(P,n);初始化InitStack(Q,n);InitQueue(三);while(l)(CoUtVflag;switch(flag)(caseA,:casea:Arrival(P,S,n);break;车进入停车场case,D,:cased:1.eave(P,Q,S,cost);break;车离开停车场caseE:casee,:return0;break;default:printf(Inputerror!n);break;