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

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

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

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

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

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

6、uct Stackstruct Node dataMaxSize;int top;int num;SqStack;基本操作：SqStack *lnit_SeqStack()/ 置空栈int ISEmpty_SeqStack(SqStack *s)/判断栈是否为空，栈为空返回1int ISFULL_SeqStack(SqStack *s,int n)/ 判断栈是否已满，若栈满返回1void Push_SeqStack(SqStack *p,struct Node s) /入栈int POP_SeqStack(SqStack *s,struct Node car)/出栈2. 链表队列数据类型定义Q

7、NODEII队列节点struct Node data;QNODE *n ext;typedef struct lin kqueue II队列结构体定义QNODE *fron t,*rear;int num;Lin kQueue;基本操作：Lin kQueue *In it_LQueue()/创建空队列int ISEmpty_LQueue(LinkQueue *q)/判断队列是否为空，队列为空返回1void IN_Lqueue( Lin kQueue *q,struct Node s) /入队struct Node Out_LQueue(L in kQueue *q) /出队2.主程序流程及其模

8、块调用关系1) 主程序模块2) 出栈3) 判断栈是否为空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,struct Node car

9、)出栈函数中调用：In it_SeqStack();Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0三、详细设计1.实现每个操作的伪码1) 主程序模块int mai n()SqStack *parkstack;Lin kQueue *parkqueue; struct Node car;int n, a=0,t;time_t rawtime; struct tm * timei nfo;/parkstack/parkqueuen为表示停车场的栈为表示便道的队列为停车场栈的最大容量time (&rawtime);time

10、i nfo = localtime (&rawtime);parkstack= Ini t_SeqStack();parkqueue=Ini t_LQueue();printf("请输入停车场最大容量n=n");scan f("%d",&n);printf("请输入车辆信息n");scan f("%c,%d,%d", &car.AL,&car.NO,&car.time);while(car.AL!='E')if(car.AL='A')/汽车到达

11、的情况if(ISFULL_SeqStack(parkstack,n)=1)/ 栈满的情况IN_Lqueue(parkqueue,car);/ 进入队列等待printf("这辆车在门外便道上第d个位置n",parkqueue->num);prin tf("n");printf("请输入车辆信息n");elsePush_SeqStack(parkstack,car);/ 入栈printf("这辆车在停车场内第 d个位置n",parkstack->num);prin tf("n");pri

12、ntf("请输入车辆信息n");if(car.AL='D' )/汽车离开的情况t=POP_SeqStack(parkstack,car);出栈prin tf(" 这辆车停留时间为%dn",t);prin tf("n");printf("请输入车辆信息n");if(ISEmpty_LQueue(parkqueue)=O) /队列不为空需要进栈Push_SeqStack(parkstack,Out_LQueue(parkqueue);if(car.AL='P'&&car.

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

14、;);scan f("%c,%d,%d",&car.AL,&car.NO,&car.time);printf("输入结束 n");return 1;2) 置空栈模块SqStack *lnit_SeqStack()/ 置空栈SqStack *s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;s->num=O;return s;3) 创建空队列模块Lin kQueue *In it_LQueue()/创建空队列Lin kQueue *q;QNODE *p;q=(L in kQue

15、ue*)malloc(sizeof(L in kQueue);p=(QNODE*)malloc(sizeof(QNODE);p-> next=NULL;q->fro nt=q->rear=p;q_>num=0;return q;4) 判断栈是否为空模块int ISEmpty_SeqStack(SqStack *s)/判断栈是否为空，栈为空返回1if(s->top =-1)return 1;elsereturn 0;5) 判断栈是否已满模块int ISFULL_SeqStack(SqStack *s,int n)/ 判断栈是否已满，若栈满返回1if(s->to

16、p=n-1)return 1;elsereturn 0;6) 判断队列是否为空模块int ISEmpty_LQueue(LinkQueue *q)/判断队列是否为空，队列为空返回1if(q->fron t=q_>rear)return 1;elsereturn 0;7) 入队模块void IN_Lqueue( Lin kQueue *q,struct Node s) /入队QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q_>nu m+;p-> next=NULL;q->rear- >n ext =p

17、;q->rear =p;8) 入栈模块void Push_SeqStack(SqStack *p,struct Node s) /入栈p->top +;p->datap->top=s;p_>nu m+;9) 出栈模块int POP_SeqStack(SqStack *s,struct Node car)/出栈SqStack *p;int t;p=I nit_SeqStack();while(s->datas->top.NO !=car.NO)找到车牌号为 P.NO 的车，Push_SeqStack(p,s->datas->top);s-&g

18、t;top-; s->nu m-;t=car.time-s->datas->top.time;s->top-;s_>nu m_;while(ISEmpty_SeqStack(p)=O)Push_SeqStack(s,p->datap->top);p->top-;p_>nu m_;return t;10) 出队模块struct Node Out_LQueue(L in kQueue *q) /出队QNODE *p;p=q->front_>n ext;q->front->n ext=p->n ext;q_>n

19、um -;if( q->fro nt- >n ext=NULL)q->rear=q->front;return p->data;free(p);四、测试与分析1. 设计与调试过程中遇到的问题分析、体会1)编写代码时，由于对栈和队列不熟悉，经常会一些问题，该程序定义了车辆信息，停车 场的顺序栈，便道上的链表队列，所以在函数代值时会出现代值的问题，例如在出栈的程序POP_SeqStack(SqStack *s,struct Node car) 中一开始在 s->datas->top.NO !=car.NO 这句话中我编的代码是s->data.NO !

20、=car.NO'程序报错.NO' : left opera nd poi nts to'struct', use '->'，这就是因为定义的太多了，忘记了当初定义的停车场栈是：struct NodedataMaxSize;就是像程序中s->datas->top.time 这样的定义因为太长了经常会搞 混，再次像 IN_Lqueue(parkqueue,car); ， Push_SeqStack(parkstack,car); 这种涉及函 数调用的尤其要注意代的应该是什么。2. 主要算法的时间复杂度分析主函数中 对每次输入的车辆信

21、息只选择其中一个执行，时间复杂度0( 1)；空间复杂度 O(1)；入栈入队列函数根据判断条件将数据入栈或入队列，时间复杂度0( 1)；空间复杂度0( 1)；出栈数据不在最顶端需将n个数据先出该栈，再入新栈，再回旧栈，时间复杂度O(n)；空间复杂度0( 1)；3. 测试数据设 n=2,输入数据为：('A' 1，5)，(' A' 2，10)，(' D' 1，15)，(' A' 3，20)，(' A'4，25), (' A' 5，30)，(' D'，2，35), (' D'

22、 4，40), (' E' 0，0)。每一组输入数据包 括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，'A'表示到达；D表示离去，E'表示输入结束。其中：(A'，1， 5)表示1号牌照车 在5这个时刻到达，而(D'，1, 15)表示1号牌照车在15这个时刻离去。4. 测试结果停车场管理程序青选择(A, D, E): A 1 5青输入车牌号*进场的时刻:该车应停在第1号车道.停车场管理程序青选择(打D,E); A 2 10 青输入车牌号，进场的时刻;该车应停在第冯车道.停车场管理程序青选择(打口 E): D

23、 1 15青输入车牌号乂岀场的时刻:停车费为20,占用车位数为1停车场管理程序青选择(A, D, E): A 3 20 青输入车牌号：迸场的时刻:该车应停在第2号车道.停车场管理程序请选择A 4 25请输入车牌号；进场的时刻:该车应停在第3号车道.停车场管理程序请选择（扎D,E）: D 2 35请输入车牌号：岀场的时刻:停车费为50,占用车位数为2停车场管理程序请选择D, E） ： E 0 0五.总结在这个程序中还有一个问题，就是定义的结构体数组有些多，容易混乱，所以我选择每定义一个结构体都将其画出一个图，这样编写的时候就不至于太混乱。这个停车管理系统的设计过程，还是慢慢在适应模块化程序的编写

24、，但有的程序还是喜欢写在一起，使得一个子程序会很长，这个问题希望在之后的问题再继续慢慢改进六附录：源程序清单#i nclude<stdio.h>#in clude<stdlib.h>#in clude<malloc.h>/函数返回状态代码#defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#defi ne FALSE 0#defi ne INFEASIBLE -1#defi ne OVERFLOW -2#defi ne SIZE 5停车场位置数typedef int Status;/栈,模拟停车场typedef struc

25、t Car1车int nu mber;/汽车车号int ar_time;/ 汽车到达时间CarNode;typedef struct/ 停车场CarNode *base;/ 停车场的堆栈底CarNode *top;停车场的堆栈顶int stacksize;Park;/队列，模拟便道typedef struct Car2车int nu mber;/汽车车号int ar_time;/汽车到达时间struct Car2 *n ext;*CarPtr;typedef struct便道CarPtr fron t;/便道的队列的对头CarPtr rear;/便道的队列的队尾in t le ngth;Sho

26、rtcut;Status In itStack(Park & P)初始化停车场P.base=(CarNode*)malloc(SIZE*sizeof(Car1);if(!P.base) exit(OVERFLOW);P.top=P.base;P.stacksize=0;return OK;Status Push(Park & P,CarNode e)/车进入停车场*P.top+=e;+P.stacksize;return OK;Status Pop(Park & P,CarNode &e)/车离开停车场if(P.top=P.base)printf("停

27、车场为空.");elsee=*-P.top;-P.stacksize;return OK;Status Ini tQueue(Shortcut & S)初始化便道S.fro nt=S.rear=(CarPtr)malloc(sizeof(Ca )；if(!S.fro nt|!S.rear) exit(OVERFLOW);S.fro nt-> next=NULL;S.le ngth=0;return OK;车进入便道Status En Queue(Shortcut &S,i nt nu mber,i nt ar_time)CarPtr p;p=(CarPtr)ma

28、lloc(sizeof(Ca )；if(!p) exit(OVERFLOW);p->nu mber =nu mber;p->ar_time=ar_time;p-> next=NULL;S.rear- >n ext=p;S.rear=p;+S.le ngth;return OK;Status DeQueue(Shortcut & S,CarPtr &w)车离开便道if(S.le ngth = 0)printf("通道为空.");elsew = S.front->n ext;S.fro nt-> next=S.fr on t-

29、> next-next;-S.le ngth;return OK;Status Arrival(Park & P,Shortcut & S)/对进站车辆的处理int nu mber,ar_time;prin tf("请输入车牌号：");sca nf("%d",&nu mber);printf("进场的时刻：”)；sea nf("%d",&ar_time);if(P.stacksize<SIZE)CarNode c;c.nu mber= nu mber;c.ar_time=ar_ti

30、me;Push(P,c);printf("该车应停在第 d号车道.n",P.stacksize);elseEn Queue(S, nu mber,ar_time);printf("停车场已满，请暂时停在便道的第d个位置.n",S.length);return OK;Status Leave(Park & P,Park & P1,Shortcut & S)对离站车辆的处理int nu mber,le_time,flag=1,m on ey,ar_time;prin tf("请输入车牌号：");sca nf("%d",&nu mber);printf("出场的