停车场管理系统的设计与实现

1、程序设计与算法综合训练设计报告2学号：E11514064姓名：汪泓章年级：大一专业：计科项目名称：停车场管理系统的设计与实现：完成日期：2016年6月27日一.需求分析1.问题描述：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场

2、的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达"（'A'表示）或“离去"（'D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。（1） .程序所能达到的

3、基本可能：程序以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。同时另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达"（'A'表示）信息，汽车标识（牌照号）以及到达时刻时，应输出汽车在停车场内或者便道上的停车位置；当输入数据包括数据项为汽车的“离去"（'D'表示）信息，汽车标识（牌照号）以及离去时刻时，应输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）；当输入数据项为（'

4、P',0,0）时，应输出停车场的车数；当输入数据项为（'W,0,0）时，应输出候车场车数；当输入数据项为（'E',0,0）,退出程序；（2） .输入输出形式及输入值范围：程序运行后进入循环，显示提示信息：“请输入停车场最大容量n=："，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息（“到达”或者“离开”，车牌编号，到达或者离开的时间)。若车辆信息为“到达A”，车辆信息开始进栈(模拟停车场)，当栈满，车辆会进队列(模拟停车场旁便道)，若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车

5、早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入('P',0,0),会显示停车场的车数；若输入(W,0,0),会显示便道上的车数；若输入('E',0,0),程序会跳出循环，同时程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开二.概要设计1 .所用到得数据结构及其ADT为了实现上述功能，该程序以顺序栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以链表队列模拟车场外的便道，因

6、此需要栈和队列这两个抽象数据类型。顺序栈数据类型定义typedefstructStackstructNodedataMaxSize;inttop;intnum;SqStack;基本操作：SqStack*Init_SeqStack()/置空栈intISEmpty_SeqStack(SqStack*s)判断栈是否为空，栈为空返回1intISFULL_SeqStack(SqStack*s,intn)判断栈是否已满，若栈满返回1voidPush_SeqStack(SqStack*p,structNodes)/入栈intPOP_SeqStack(SqStack*s,structNodecar)/出栈2

7、.链表队列数据类型定义QNODE/队列节点structNodedata;QNODE*next;typedefstructlinkqueue/队列结构体定义QNODE*front,*rear;intnum;LinkQueue;基本操作：LinkQueue*Init_LQueue()/创建空队列intISEmpty_LQueue(LinkQueue*q)判断队列是否为空，队列为空返回voidIN_Lqueue(LinkQueue*q,structNodes)/入队structNodeOut_LQueue(LinkQueue*q)/出队2.主程序流程及其模块调用关系1)主程序模块2)出栈3)判断栈是

8、否为空4)判断栈是否已满5)判断队列是否为空6)出队函数调用：main()函数中调用：ISFULL_SeqStack(parkstack,n),IN_Lqueue(parkqueue,car);Push_SeqStack(parkstack,car);t=POP_SeqStack(parkstack,car);ISEmpty_LQueue(parkqueue)=0;Push_SeqStack(parkstack,Out_LQueue(parkqueue);POP_SeqStack(SqStack*s,structNodecar)出栈函数中调用：Init_SeqStack();Push_SeqS

9、tack(p,s->datas->top);ISEmpty_SeqStack(p)=0三、详细设计1.实现每个操作的伪码1)主程序模块intmain()SqStack*parkstack;/parkstack为表示停车场的栈LinkQueue*parkqueue;/parkqueue为表示便道的队歹UstructNodecar;intn,a=0,t;/n为停车场栈的最大容量time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);parkstack=Init_SeqStac

10、k();parkqueue=Init_LQueue();printf("请输入停车场最大容量n=n");scanf("%d",&n);printf("请输入车辆信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);while(car.AL!='E')if(car.AL='A')/汽车到达的情况if(ISFULL_SeqStack(parkstack,n)=1)/栈满的情况IN_Lqueue(parkqueu

11、e,car);/进入队列等待printf("这辆车在门外便道上第外位置n",parkqueue->num);printf("n");printf("请输入车辆信息n");elsePush_SeqStack(parkstack,car);/入栈printf（"这辆车在停车场内第d个位置n",parkstack->num）;printf("n");printf("请输入车辆信息n");if(car.AL='D')/汽车离开的情况t=POP_SeqSta

12、ck(parkstack,car);/出栈printf("这辆车停留时间为dn",t);printf("n");printf("请输入车辆信息n");if(ISEmpty_LQueue(parkqueue)=0)/队列不为空需要进栈Push_SeqStack(parkstack,Out_LQueue(parkqueue);if(car.AL='P'&&car.NO=0&&car.time=0)/显示停车场的车数printf("停车场的车数为dn",parkstack-

13、>num);printf("n");printf("请输入车辆信息n");if(car.AL='WI&&car.NO=0&&car.time=0)/显示候车场的车数printf("候车场的车数为dn",parkqueue->num);printf("n");printf("请输入车辆信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);printf(&qu

14、ot;输入结束n");return1;2)置空栈模块SqStack*Init_SeqStack()/置空栈SqStack*s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;s->num=0;returns;3)创建空队列模块LinkQueue*Init_LQueue()/创建空队列LinkQueue*q;QNODE*p;q=(LinkQueue*)malloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p->next=NULL;q->front=q->re

15、ar=p;q->num=0;returnq;4)判断栈是否为空模块/判断栈是否为空，栈为空返回 1/判断栈是否已满，若栈满返回1intISEmpty_SeqStack(SqStack*s)if(s->top=-1)return1;elsereturn0;5)判断栈是否已满模块intISFULL_SeqStack(SqStack*s,intn)if(s->top=n-1)return1;elsereturn0;6)判断队列是否为空模块/判断队列是否为空，队列为空返回intISEmpty_LQueue(LinkQueue*q)if(q->front=q->rear)r

16、eturn1;elsereturn0;7)入队模块voidIN_Lqueue(LinkQueue*q,structNodes)/入队QNODE*p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q->num+;p->next=NULL;q->rear->next=p;q->rear=p;8)入栈模块voidPush_SeqStack(SqStack*p,structNodes)/入栈p->top+;p->datap->top=s;p->num+;9)出栈模块intPOP_SeqStack(SqSta

17、ck*s,structNodecar)/出栈SqStack*p;intt;p=Init_SeqStack();while(s->datas->top.NO!=car.NO)找到车牌号为P.NO的车,Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=car.time-s->datas->top.time;s->top-;s->num-;while(ISEmpty_SeqStack(p)=0)Push_SeqStack(s,p->datap->top);p->top-;p-

18、>num-;returnt;10)出队模块structNodeOut_LQueue(LinkQueue*q)/出队QNODE*p;p=q->front->next;q->front->next=p->next;q->num-;if(q->front->next=NULL)q->rear=q->front;returnp->data;free(p);四、测试与分析1 .设计与调试过程中遇到的问题分析、体会1)编写代码时，由于对栈和队列不熟悉，经常会一些问题，该程序定义了车辆信息，停车场的顺序栈，便道上的链表队列，所以在函数代

19、值时会出现代值的问题，例如在出栈的程序POP_SeqStack(SqStack*s,structNodecar)中一开始在s->datas->top.NO!=car.NO这句话中我编的代码是s->data.NO!=car.NO'程序报错.NO':leftoperandpointsto'struct',use'->'，这就是因为定义的太多了，忘记了当初定义的停车场栈是：structNodedataMaxSize;就是像程序中s->datas->top.time这样的定义因为太长了经常会搞混，再次像IN_Lqueu

20、e(parkqueue,car);,Push_SeqStack(parkstack,car);这种涉及函数调用的尤其要注意代的应该是什么。2 .主要算法的时间复杂度分析主函数中对每次输入的车辆信息只选择其中一个执行，时间复杂度O(1);空间复杂度O(1);入栈入队列函数根据判断条件将数据入栈或入队列，时间复杂度O(1);空间复杂度O(1);出栈数据不在最顶端需将n个数据先出该栈，再入新栈，再回旧栈，时间复杂度O(n);空间复杂度O(1);3 .测试数据.设n=2,输入数据为：('A',1,5),('A',2,10),('D',1,15),(

21、9;A',3,20),('A',4,25),('A',5,30),('D',2,35),('D',4,40),('E',0,0)。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，'A'表示到达；D表示离去，'E'表示输入结束。其中：('A',1,5)表示1号牌照车在5这个时刻到达，而('D',1,15)表示1号牌照车在15这个时刻离去。4 .测试结果停车场管理程序青选择(A,D,E):A15青输入

22、车牌号：进场的时刻:该车应停在第1号车道.停车场管理程序青选择(比D,E);A210青输入车牌号，进场的时刻:该车应停在第猾车道.停车场管理程序青选择D115青输入车牌号工出场的时刻:停车费为20,占用车位数为1停车场管理程序青选择A320青输入车牌号：进场的时刻:该车应停在第2号车道.1停车场管理程序请选择(A,D,E):A425请输入车牌号；进场的时刻:该车应停在第*号车道.停车场管理程序请选择(A,D,E):D235请输入车牌号：出场的时刻:停车费为50,占用车位数为2停车场管理程序请选择(A,D,E);E005 .总结在这个程序中还有一个问题，就是定义的结构体数组有些多，容易混乱，所以

23、我选择每定义一个结构体都将其画出一个图，这样编写的时候就不至于太混乱。这个停车管理系统的设计过程，还是慢慢在适应模块化程序的编写，但有的程序还是喜欢写在一起，使得一个子程序会很长，这个问题希望在之后的问题再继续慢慢改进6 .附录：源程序清单#include<stdio.h>#include<stdlib.h>#include<malloc.h>/函数返回状态代码# defineOK1# defineERROR0# defineTRUE1# defineFALSE0# defineINFEASIBLE-1# defineOVERFLOW-2# defineSI

24、ZE5停车场位置数typedefintStatus;/栈,模拟停车场typedefstructCar1/车intnumber;/汽车车号intar_time;/汽车到达时间CarNode;typedefstruct停车场CarNode*base;停车场的堆栈底CarNode*top;/停车场的堆栈顶intstacksize;Park;/队列，模拟便道typedefstructCar2/车intnumber;/汽车车号intar_time;/汽车到达时间structCar2*next;*CarPtr;typedefstruct便道CarPtrfront;/便道的队列的对头CarPtrrear;/

25、便道的队列的队尾intlength;Shortcut;StatusInitStack(Park&P)初始化停车场P.base=(CarNode*)malloc(SIZE*sizeof(Car1);if(!P.base)exit(OVERFLOW);P.top=P.base;P.stacksize=0;returnOK;StatusPush(Park&P,CarNodee)/车进入停车场*P.top+=e;+P.stacksize;returnOK;StatusPop(Park&P,CarNode&e)/车离开停车场if(P.top=P.base)printf(&

26、quot;停车场为空.")；elsee=*-P.top;-P.stacksize;returnOK;StatusInitQueue(Shortcut&S)初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2);if(!S.front|!S.rear)exit(OVERFLOW);S.front->next=NULL;S.length=0;returnOK;StatusEnQueue(Shortcut&S,intnumber,intar_time)/车进入便道CarPtrp;p=(CarPtr)malloc(sizeof(C

27、ar2);if(!p)exit(OVERFLOW);p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;S.rear=p;+S.length;returnOK;StatusDeQueue(Shortcut&S,CarPtr&w)车离开便道if(S.length=0)printf("通道为空.")；elsew=S.front->next;S.front->next=S.front->next->next;-S.length;returnO

28、K;StatusArrival(Park&P,Shortcut&S)对进站车辆的处理intnumber,ar_time;printf("请输入车牌号：”)；scanf("%d",&number);printf("进场的时刻：")；scanf("%d",&ar_time);if(P.stacksize<SIZE)CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);printf("该车应彳亭在第%d号车道.n",P.stacksize);elseEnQueue(S,number,ar_time);printf("停车场已满，请暂时停在便道的第d个位置.n",S.length);returnOK;StatusLeave(Park&P,Park&P1,Shortcut&S)对离站车辆的处理intnumber,le_time,flag=1,money,ar_time;printf("请输入车牌号：”)；scanf("%d",&number);printf("出场的