停车场管理实验数据结构与算法.doc

广州中医药大学信息技术学院实 验 报 告课程名称：数据结构与算法专业班级：计算机科学与技术( 2011 )级实验组号：第七组学生学号和姓名：实验名称：停车场管理实验成绩：课程类别： 必修 限选 公选 其它 实验五 停车场管理实验目的：学习使用栈与队列解决实际问题。实验内容：停车场问题模拟班级：计算机科学与技术专业（2011）级（B）班实验组号：第七组完成日期：2012年11月20日一.问题的需求分析1.问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制程序模拟该停车场的管理。2.需求分析（1）设计存储结构（2）分析与定义基本操作。二.抽象数据类型的设计PSeqStack A=createSeqStack_seq();/*初始化停车场*/PSeqStack B=createSeqStack_seq();/*初始化停车场的临时栈道*/PLinkQueue C=createEmptyQueue_link( );/*初始化便道*/根据题目要求，停车场只有一个大门，因此可用一个栈来模拟，我们称之为主栈； 当停车场满后，到来的车辆只能停在便道上，根据便道停车的特点，可用一个队列来模拟（先排队的车辆先离开便道，进入停车场） 而每当停车场中间的车辆离开时，要求大门到欲离开车辆之间的车辆必须先离开停车场，让此车辆离去，然后再依序进入停车场，为保存这些车辆的位置也需栈，称为辅助栈。因此本问题需要用到两个栈和一个队列。 三.算法与数据结构的设计void gettime(int*i,char*hour,char*minute,char*String)int arrival(PSeqStack Enter,PLinkQueue W)/*车辆到达*/void print(CarNode m,int p)/*打印车的信息*/void Leave1(PSeqStack A,PSeqStack B, PLinkQueue C)/*停车场的车离开*/void Leave2(PLinkQueue A) /*便道上的车离开*/void list1(PSeqStack p)/*查看停车场车辆情况*/void list2(PLinkQueue s) /*显示便道的情况*/void printMenu(PSeqStack A,PSeqStack B, PLinkQueue C)/*程序的主要界面*/主函数main创建两个栈：A（停车场）一个队列C（便道）操作界面调用函数printMenuBALCDEarrivallist1leave2leave1退出程序list2创建辅助栈B四. 算法的精化与程序的实现/进入停车场管理系统的操作界面函数：void printMenu(PSeqStack A,PSeqStack B, PLinkQueue C)/*程序的主要界面*/char a;intb;printf(=欢迎进入停车场管理系统=n);printf( A. 车辆到达 n); printf( B. 查看便道停车情况 n);printf( C. 查看停车场停车情况 n);printf( D. 便道车辆离开 n);printf( L. 停车场车辆离开 n);printf( E. 退出 n);printf(=n);while(1)b=MAXSIZE-A-top-1;printf(你好! 本停车场共有%d个车位,现还有%d个空位,停车收费为%d元/分钟n,MAXSIZE,b,price);printf(请输入你的选择:); while(1)scanf(%s,&a);if(a=A|a=B|a=C|a=D|a=L|a=E|a=a|a=b|a=c|a=d|a=l|a=e)break;else printf(n输入有误,请重新输入!n);printf(请输入你的选择:);switch(a)case A:case a:arrival(A,C);break; /*车辆到达*/case L:case l:Leave1(A,B,C);break; /*停车场车辆离开*/case D:case d:Leave2(C);break;/*便道车辆离开*/case C:case c:listone(A);break;/*查看停车场停车情况*/case B:case b:listtwo(C);break;/*查看便道停车情况*/case E:case e:exit(0); /*退出主程序*/default: break;/获取时间函数：void gettime(int*i,char*hour,char*minute,char*String)memcpy(hour,String+0,2);hour2=0;i0=atoi(hour);memcpy(minute,String+3,2);minute2=0;i1=atoi(minute);/车辆进入函数：int arrival(PSeqStack Enter,PLinkQueue W) /*车辆到达*/CarNode p; PNode t; p=(CarNode)malloc(sizeof(struct node); if(Enter-topnum);printf(请输入这辆车到达的时间(如08:00):);gets(p-arrive); Enter-top=Enter-top+1;Enter-sEnter-top=p;printf(=n);return(1);elseprintf(n停车场已满，请在便道排队等候!n);t=(PNode)malloc(sizeof(struct Node);flushall();printf(n请输入车牌号:);gets(p-num);printf(n请输入这辆车到达便道的时间(如08:00):);gets(p-arrive);t-info=p;t-link=NULL;if (W-f=NULL) W-f=t; else W-r-link=t;W-r=t;printf(=n);return(1); /*停车场已经满啦，请在便道排队*/记录车牌号码、车辆到达、离开时间，收取费用等信息函数void print(CarNode m,int p) /*打印停车场的车的信息*/char hour3,minute3;int i3,j3; float a,b,sum1=0,sum2=0; printf(请输入车离开的时间(如08:00):);scanf(%s,&(m-leave);printf(=n);printf(离开车的车牌号码:); puts(m-num);printf(车到达停车场时间(如08:00): %sn,m-arrive);printf(车离开停车场时间(如08:00): %sn,m-leave);gettime(i,hour,minute,m-arrive);gettime(j,hour,minute,m-leave); for(int c=0;c3;c+)if(c=0) a=(float)i0*60;if(c=1) a=(float)i1;sum1+=a;for(int d=0;d=0&atop) break;for(int i=A-top;ia;i-) B-top+;B-sB-top=A-sA-top;SeqStackPop(A); p=A-sa; print(p,a); SeqStackPop(A); while(!isEmptyStack_seq(B) A-top+;A-sA-top=B-sB-top;SeqStackPop(B);/*判断便道是否有车和停车场是否有空位*/if(!isEmptyQueue_link(C)&A-topf;t=q- info;A-top+;int a=A-top+1;printf(n便道中车牌号为%s的车进入停车场第%d个位置,t-num,a);printf(n请输入这辆车到达停车场的时间(如08:00):);scanf(%s,&(t-arrive); A-sA-top=t;deQueue_link(C);else printf(n便道里没有车.n); else printf(n停车场没有车n); printf(=n);return ;void Leave2(PLinkQueue A)/*便道的车离开*/ int a;if(!isEmptyQueue_link(A)printf(n请输入要离开车的数量:); scanf(%d,&a);for(int i=0;if-info-leave);printf(=n);printf(离开便道的车的车牌号码:); puts(A-f-info-num);printf(车到达便道时间: %sn,A-f-info-arrive);printf(车离开便道时间: %sn,A-f-info-leave);deQueue_link(A); else printf(n便道里没有车.n);printf(=n);void listone(PSeqStack p) /*显示停车场里面的情况*/int i;if(p-top-1) /*判断停车场是否为空*/printf(停车场:);printf(n 位置 到达时间 车牌号n);for(i=0;itop;i+)int a=0; a=i+1;printf( %d ,a);printf( %s ,p-si-arrive);puts(p-si-num);else printf(n停车场没有车n);printf(=n);/查询函数：void list1(PSeqStack p) /*显示停车场里面的情况*/int i;if(p-top-1) /*判断停车场是否为空*/printf(停车场:);printf(n 位置 到达时间 车牌号n);for(i=0;itop;i+)int a=0; a=i+1;printf( %d ,a);printf( %s ,p-si-arrive);puts(p-si-num);else printf(n停车场没有车n);printf(=n);void list2(PLinkQueue s) /*显示便道的情况*/ PNode p; int i=0;p= s-f; if(!isEmptyQueue_link(s)printf(n便道:);printf(n 位置 到达时间 车牌号n);while(p!=NULL)i+; printf( %d ,i);printf( %s ,p-info-arrive);puts(p-info-num);p=p-link;else printf(n便道里没有车.n);printf(=n);四程序的调试与计算的结果分析用户进入停车场管理系统主界面如下图：1、 调试分析：（1）车辆到达时输入车的信息： （2）停车场已满时，提示停车场已满，请刚来的车进入便道等候（3）查看停车场停车情况（4）查看便道上车的情况 (5)停车场的车离开，打印离开的车的信息和停车需要缴纳的费用（6）停车场有空位时，便道上的车进入停车场六时间代价的分析本程序，运用了if语句、while语句、switch语句，这些语句的运行、车进栈和停车场里的车出栈、再进栈、便道上的车入队和出队、以及查看停车场里的情况和计算停车时间的费用比较耗时，对于这个程序，每插入一个数据，平均每次运行次数为1。所以要插入n个数据，时间复杂度就是O（n）。在进栈时，设有t个数据输入，则时间复杂度就是O（t）。在查看队列时，插入和输出的次数是相同的。所以，设有s个数据输入，则该时间复杂度就是O（s）。七、有待改进的问题，收获和体会1、有待改进的问题：1）虽然用栈和队列来模拟停车场让整个问题显得简单，易于实现，但栈和队列这两个数学模型用在停车场管理上有失妥当，现实中停车场的出入口一般不会是同一处。另外，当一辆车要离开时，后面进来的车不可能都必须为它让路。2）在实际中，不同的车应该有不同的车牌号，但本程序在输入车的信息时，允许前后输入相同的车牌号。因此，本程序应该编写一个函数，用来判断输入的刚到达的车辆信息是否与之前输入的车辆有相同的车牌号，如果有，应提示“输入车牌号有误，请重新输入！”。3）当停车场有车要离开时，便道上先到达的车应几乎同时进入停车场。经调试，我们发现，每次停车场