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

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

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

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

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

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

6、本操作：SqStack *Init_SeqStack()/置空栈int ISEmpty_SeqStack(SqStack *s)/判断栈是否为空，栈为空返回1int ISFULL_SeqStack(SqStack *s,int n)/判断栈是否已满，若栈满返回1 void Push_SeqStack(SqStack *p,struct Node s) /入栈int POP_SeqStack(SqStack *s,struct Node car)/出栈2.链表队列数据类型定义QNODE /队列节点struct Node data;QNODE *next;typedef struct linkqu

7、eue /队列结构体定义QNODE *front,*rear;int num;LinkQueue;基本操作：LinkQueue *Init_LQueue() /创建空队列int ISEmpty_LQueue(LinkQueue *q)/判断队列是否为空，队列为空返回1void IN_Lqueue(LinkQueue *q,struct Node s) /入队struct Node Out_LQueue(LinkQueue *q) /出队2. 主程序流程及其模块调用关系 1)主程序模块2) 出栈3） 判断栈是否为空4） 判断栈是否已满5） 判断队列是否为空6） 出队函数调用： main()函数中

8、调用：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)出栈函数中调用：Init_SeqStack();Push_SeqStack(p,s->datas->top);ISEm

9、pty_SeqStack(p)=0三、 详细设计 1. 实现每个操作的伪码1）主程序模块int main()SqStack *parkstack;/parkstack为表示停车场的栈LinkQueue *parkqueue; /parkqueue为表示便道的队列struct Node car;int n,a=0,t; /n为停车场栈的最大容量time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);parkstack=Init_SeqStack();parkqueue=

10、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(parkqueue,car);/

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

12、ack(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"

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

14、p;car.time);printf("输入结束n");return 1;2）置空栈模块SqStack *Init_SeqStack()/置空栈SqStack *s;s=(SqStack*)malloc(sizeof(SqStack); s->top=-1;s->num=0;return s;3）创建空队列模块LinkQueue *Init_LQueue() /创建空队列LinkQueue *q; QNODE *p; q=(LinkQueue*)malloc(sizeof(LinkQueue); p=(QNODE*)malloc(sizeof(QNODE);p-

15、>next=NULL;q->front=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->top=n-1)return 1;elsereturn 0;6）判断队列是否为空模块int ISEmpty_LQueue(LinkQueue

16、*q)/判断队列是否为空，队列为空返回1if(q->front=q->rear)return 1;else return 0;7）入队模块void IN_Lqueue(LinkQueue *q,struct Node s) /入队QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q->num+;p->next=NULL;q->rear->next =p;q->rear =p;8）入栈模块void Push_SeqStack(SqStack *p,struct Node s) /入栈p->to

17、p +;p->datap->top=s;p->num+;9）出栈模块int POP_SeqStack(SqStack *s,struct Node car)/出栈SqStack *p;int t; 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-;whil

18、e(ISEmpty_SeqStack(p)=0)Push_SeqStack(s,p->datap->top);p->top-;p->num-;return t;10）出队模块struct Node Out_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;return p->data;free(p);四、 测试与分

19、析1. 设计与调试过程中遇到的问题分析、体会 1）编写代码时，由于对栈和队列不熟悉，经常会一些问题，该程序定义了车辆信息，停车场的顺序栈，便道上的链表队列，所以在函数代值时会出现代值的问题，例如在出栈的程序POP_SeqStack(SqStack *s,struct Node car)中一开始在s->datas->top.NO !=car.NO这句话中我编的代码是s->data.NO !=car.NO'程序报错.NO' : left operand points to 'struct', use '->'，这就是因为定义的

20、太多了，忘记了当初定义的停车场栈是：struct NodedataMaxSize;就是像程序中s->datas->top.time这样的定义因为太长了经常会搞混，再次像IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car);这种涉及函数调用的尤其要注意代的应该是什么。2. 主要算法的时间复杂度分析 主函数中 对每次输入的车辆信息只选择其中一个执行，时间复杂度O（1）；空间复杂度O（1）；入栈入队列函数根据判断条件将数据入栈或入队列，时间复杂度O（1）；空间复杂度O（1）；出栈数据不在最顶端需将n个数据先出该栈，再入新栈，再回旧

21、栈，时间复杂度O（n）；空间复杂度O（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，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。其中：（A，1，5）表示1号牌照车在5这个时刻到达，而（D，1，15）表示1号牌照车在15这个时刻离去。4. 测试结果 五总结在这个程序中还有一个问题，就是定义的结构体数组有些多，容易混乱，所以我选择每定义一个结构体都将其

22、画出一个图，这样编写的时候就不至于太混乱。这个停车管理系统的设计过程，还是慢慢在适应模块化程序的编写，但有的程序还是喜欢写在一起，使得一个子程序会很长，这个问题希望在之后的问题再继续慢慢改进六附录：源程序清单#include<stdio.h>#include<stdlib.h>#include<malloc.h>/函数返回状态代码#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 5/停车场位置

23、数typedef int Status;/栈,模拟停车场typedef struct Car1/车int number;/汽车车号int ar_time;/汽车到达时间CarNode;typedef struct/停车场CarNode *base;/停车场的堆栈底CarNode *top;/停车场的堆栈顶int stacksize;Park;/队列,模拟便道typedef struct Car2/车int number;/汽车车号int ar_time;/汽车到达时间struct Car2 *next;*CarPtr;typedef struct/便道CarPtr front;/便道的队列的对

24、头CarPtr rear;/便道的队列的队尾int length;Shortcut;Status InitStack(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)/车离开

25、停车场if(P.top=P.base)printf("停车场为空.");elsee=*-P.top;-P.stacksize;return OK;Status InitQueue(Shortcut &S)/初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2);if(!S.front|!S.rear) exit(OVERFLOW);S.front->next=NULL;S.length=0;return OK;Status EnQueue(Shortcut &S,int number,int ar_time)/车

26、进入便道CarPtr p;p=(CarPtr)malloc(sizeof(Car2);if(!p) exit(OVERFLOW);p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;S.rear=p;+S.length;return OK;Status DeQueue(Shortcut &S,CarPtr &w)/车离开便道if(S.length = 0)printf("通道为空.");elsew = S.front->next;S.front->

27、next=S.front->next->next;-S.length;return OK;Status Arrival(Park &P,Shortcut &S)/对进站车辆的处理int number,ar_time;printf("请输入车牌号：");scanf("%d",&number);printf("进场的时刻:");scanf("%d",&ar_time);if(P.stacksize<SIZE)CarNode c;c.number=number;c.ar_

28、time=ar_time;Push(P,c);printf("该车应停在第%d号车道.n",P.stacksize);elseEnQueue(S,number,ar_time);printf("停车场已满,请暂时停在便道的第%d个位置.n",S.length);return OK;Status Leave(Park &P,Park &P1,Shortcut &S)/对离站车辆的处理int number,le_time,flag=1,money,ar_time;printf("请输入车牌号：");scanf("%d",&number);printf("出场的时刻:");scanf("%d",&le_time);CarN