数据结构停车场管理实验报告.doc

河北工业大学数据结构课程实验实 验 报 告题目： 停车场管理 专业： 软件 班级： 102 姓名： 完成日期： 2012-5-19 一、 试验内容 设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出场为它让路，待该辆车开出大门外，其他车辆再按次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。二、 试验目的（1）深入了解栈和队列的特性，掌握栈和队列的存储方法。（2）掌握栈和队列的基本操作，如初始化、入栈（队列）、出栈（队列）等，并能在实际问题背景下灵活运用。三、流程图各主要函数的流程图：A_cars:printf(The parking place is full!n);s-top!=n-1(s-top)+;QNODE*t; Judge_Output :(*r).bb=E|(*r).bb=eprintf(STOP!n); Y N(*r).bb=P|(*r).bb=p Y Nprintf(The number of parking cars is %dn,(s-top)+1);(*r).bb=W|(*r).bb=ww Y Nprintf(The number of waiting cars is %dn,q-geshu) (*r).bb=W|(*r).bb=wwA_cars(s,q,*r); Y N(*r).bb=W|(*r).bb=wwN D_cars(s,q,*r); Y ERROR; main:i=0SqStack*s;iMAXSIZEnyprintf(请输入车的信息:车的进出、车牌号、时间:n);aai.bb=Enybreak;i+四、源程序代码#include /*调用的头文件库声明*/#include#define MAXSIZE 14#define n 2#define fee 10 struct car /*用该结构体来存放车的状态，编号和时间信息 */ char bb; int num; int time; ;typedef struct stack /*用该栈来模拟停车场*/struct car Gn; int top;SqStack;struct rangweicar /*用该结构体来存放临时让出的车辆的编号以及时间信息*/int num; int time;typedef struct stackk /*用该栈来模拟临时让出的车辆的停靠场地*/struct rangweicar HMAXSIZE; int topp;SqStackk;#define QNODE struct QnodeQNODE int data; /*链队结点的类型*/QNODE *next; ;typedef struct linkqueue /*用该链队来模拟便道*/QNODE *front,*rear; int geshu; LinkQueue;void A_cars(SqStack *s,LinkQueue *q,struct car a) /*该算法实现对车辆状态为到达的车辆的操作*/QNODE *t; if(s-top!=n-1) /*若停车场还没有满，则车进停车场，并存入车辆的状态，车牌编号和到达时间信息*/ (s-top)+; (s-Gs-top).bb=a.bb; (s-Gs-top).num=a.num; (s-Gs-top).time=a.time; else printf(The parking place is full!n); /*若停车场已满，车进便道，并显示该车的车牌编号，同时记录便道车辆数目*/ t=(QNODE *)malloc(sizeof(QNODE); t-data=a.num; t-next=NULL; q-rear-next=t; q-rear=t; printf(停车场已满，车进便道，并显示该车的车牌编号:%dn,q-rear-data); q-geshu+; int D_cars(SqStack *s,LinkQueue *q,struct car d) /*该算法实现车辆状态为离开的车辆的操作*/int i,j,l; float x,y; QNODE *p; SqStackk *k; if(d.num=(s-Gs-top).num) /*若待离开车为最后进停车场的车的情况*/ x=float(d.time-(s-Gs-top).time); y=fee*x; /*直接计算停车时间，费用并离去*/ printf(停车时间为 %.2f 个小时,费用是 %.2f 元n,x,y); if(q-geshu=0) /*若便道上无车，函数返回*/ printf(便道上无车!n); return 0; else /*若便道上有车，第一辆车进停车场*/ p=q-front-next; q-front-next=p-next; (s-Gs-top).num=p-data; /*并存入其车牌编号及进停车场的时间*/ (s-Gs-top).time=d.time; free(p); q-geshu-; if(q-front-next=NULL) q-rear=q-front; /*若此时便道上无车，返回1*/ return 1; else /*待离开的车不是最后进停车场的那辆车的情况*/ for(i=0;itop);i+) /*先找到待离开车在停车场中的位置*/ if(s-Gi).num!=d.num) continue;else break; if(i=(s-top) printf(ERROR!n); return -1; x=float(d.time-(s-Gi).time); /*计算待离开车的停车时间并计算费用*/ y=fee*x; printf(停车时间为 %.2f 个小时,费用是 %.2f 元n,x,y); k=(SqStackk *)malloc(sizeof(SqStackk); /*设立一个新栈临时停放为该车离开而让路的车辆*/ k-topp=-1; for(j=(s-top);ji;j-) k-topp+; (k-Hk-topp).num=(s-Gj).num; (k-Hk-topp).time=(s-Gj).time; s-top-; for(l=0;ltopp);l+) printf(新栈中的车辆信息车号和时间:n); printf(%d,%dn,(k-Hl).num,(k-Hl).time); /*显示在新栈中的车辆信息*/ s-top-; while(k-topp=0) /*将新栈中的车重新开入停车场中*/ s-top+; (s-Gs-top).bb=A; (s-Gs-top).num=(k-Hk-topp).num; (s-Gs-top).time=(k-Hk-topp).time; k-topp-; if(q-geshu=0) /*若便道上无车，则返回2，无车开入停车场中*/ printf(便道上无车!n); return 2; else /*若便道上有车，则第一辆车开入停车场中*/ s-top+; p=q-front-next; q-front-next=p-next; (s-Gs-top).num=p-data; (s-Gs-top).time=d.time; free(p); q-geshu-; if(q-front-next=NULL) q-rear=q-front; return 3; void Judge_Output(SqStack *s,LinkQueue *q,struct car *r) /*该算法通过传递来的车辆信息调*/ /* 用相关函数实现操作*/ if(*r).bb=E|(*r).bb=e) /*若车辆状态为E，终止程序*/ printf(STOP!n); else if(*r).bb=P|(*r).bb=p) /*若车辆状态为P，输出停车场车辆数*/ printf(The number of parking cars is %dn,(s-top)+1); else if(*r).bb=W|(*r).bb=w) /*若车辆状态为W，输出便道车辆数*/ printf(The number of waiting cars is %dn,q-geshu); else if(*r).bb=A|(*r).bb=a) /*若车辆状态为A，调用A_cars函数*/ A_cars(s,q,*r); else if(*r).bb=D|(*r).bb=d) /*若车辆状态为D，调用D_cars函数*/ D_cars(s,q,*r); else printf(ERROR!n); /*若车辆状态为其他字母，报错*/ void main() SqStack *s; LinkQueue *q; QNODE *p; struct car aaMAXSIZE; int i; s=(SqStack *)malloc(sizeof(SqStack); /*对停车场初始化*/ s-top=-1; q=(LinkQueue *)malloc(sizeof(LinkQueue); p=(QNODE *)malloc(sizeof(QNODE); /*对便道初始化*/ p-next=NULL; q-front=q-rear=p; q-geshu=0; printf(*n); printf(*n); printf(* 我们的停车场管理系统 *n); printf(*n); printf(*n); for(i=0;iMAXSIZE;i+) /*输入车辆信息*/ printf(请输入车的信息:车的进出、车牌号、时间:n); scanf(%c,%d,%d,&(aai.bb),&(aai.num),&(aai.time); getchar();Judge_Output(s,q,&aai); if(aai.bb=E) break; 五、调试过程该程序是几个程序调试中最顺利的一个，只在一个地方上出了问题，就是输入字符时由于回车键也是字符，回车键总会被读入，导致经常输出“ERROR！”。后来找到原因后在scanf函数后紧接着加了一个getchar（）；语句后就恢复了正常。六、结果分析 输入数据：（A，1，5），（A，2，10），（D，1，15），（A，3， 20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（P，0，0），（W，0，0），（F，0，0），（E，0，0）。运行结果截屏：方法优缺点分析：优点：用栈和队列来模拟停车场让整个问题显得简单，易于实现；缺点：栈和队列这两个数学模型用在停车场管理上还是有失妥当的，现实中停车场出口入口不可能为同一处，不可能当一辆车要离开，在它后面进来的车必须为它让路，因此无法用栈的“后进先出”原则来模拟；而且没有考虑便道上的车在等待过程中可以中途开走等情况，而这些都无法用队列的“先进先出”原则来模拟。主要算法的时间和空间复杂度分析：（1）由于算法Judge_Output函数根据判断条件，每次只选择一个程序段执行，所以其时间复杂度是O(1)；（2）由于算法A_cars函数根据判断条件，将数据入栈或入队列，所以其时间复杂度也是O(1)；（3）由于算法D_cars函数在出栈数据不在最顶端时需将n个数据先出该栈，再入新栈，再回旧栈的操作，故其时间复杂度是O(n)；（4）所有算法的空间复杂度都是O(1)。