数据结构-停车场管理课程设计报告

课程设计报告一、需求分析1、以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。2、用户输入汽车信息后，程序对每一组输入数据进行操作后的输出信息为：假设是车辆到达，那么输出汽车在停车场内或便到上的停车位置；假设是车辆离去，那么输出汽车在停车场内停留的时间和应缴纳的费用〔在便道上停留的时间不收费〕。3、本程序要求栈以顺序结构实现，队列以链表结构实现。4、测试数据：设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”表示到达〔Aiiival〕；“D”表示离去〔Departure〕；“E”表示输入结束〔End〕。5、程序执行的命令为：1〕创立停车场；2〕创立便到；3〕执行对车辆的运算；4〕输出所需的数据。二、概要设计1、设定栈的抽象数据类型定义：ADTStack{ 数据对象：D={ai｜ai∈CharSet,i=1,2,…,n,n≥0}数据关系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty(S)初始条件：栈S已存在。操作结果：假设栈S为空栈，那么返回TURE,否那么FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，那么操作失败。}ADTStack2、设定队列的抽象数据类型定义：ADTQueue{数据对象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}约定其中a1端为队列头，an端为队列尾根本操作：InitQueue(&Q)操作结果：构造一个空队列Q。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：假设Q为空队列，那么返回TURE，否那么FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的对头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit())初始条件：Q已存在且非空。操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，那么操作失败。}ADTQueue3、设定停车场的抽象数据类型为：ADT数据对象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：Arrival(Park&P,Shortcut&S,intn)初始条件：栈S存在。操作结果：在输入车牌号和进场时间后，输出停车的车道。Leave(Park&P,Park&P1,Shortcut&S,intcost)初始条件：栈S存在且非空。操作结果：在输入车牌号和离场时间后，输出车停留时间以及费用。}ADT4、设定便到的抽象数据类型为：ADTCarPtr{数据对象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：EnQueue(S,number,ar_time)初始条件：停车场已满，队列存在。操作结果：在输入车牌号和进场时间后，输出车停留在便道上的位置。DeQueue(S,w)初始条件：停车场有车辆离开。操作结果：输出由便到进入停车场的汽车车牌号DeQueue(S,q)初始条件：便道上有车离开。操作结果：输出离开车辆车牌以及停留时间。}ADTCarPtr5、本程序包含五个模块1〕主程序模块：Voidmain(){初始化；Do{接受命令；处理命令；}while(“命令”=”退出”)；}2〕栈模块——实现栈抽象数据类型3〕队列模块——实现队列抽象数据类型4〕停车场模块——实现停车场抽象数据类型5〕便道模块——实现便到抽象数据类型各模块之间的调用关系如下：主程序模块↓栈模块↓队列模块↓停车场模块↓便道模块三、详细设计1、车辆类型typedefstructCar1{//车intnumber;//汽车车号intar_time;//汽车到达时间}CarNode;2、栈类型typedefstruct{//停车场CarNode*base;//停车场的堆栈底CarNode*top;//停车场的堆栈顶intstacksize;}Park;栈的根本操作设置如下：VoidInitStack(Stack&S)//初始化，设S为空栈IntStackLength(StackS)//返回栈S的长度S.sizeStatusGetTop(StackS)//假设S为空栈，那么返回TURE；否那么返回FALSEStatusGetTop(StackS,ElemTypee)//假设栈S不空，那么以e带回栈顶元素并返回TURE，否那么返回FALSEStatusPush(Stack&S,ElemTypee)//假设分配空间成功，那么在S的栈顶插入新的栈顶元素e，并返回TURE//否那么栈不变，并返回FALSEStatusPop(Stack&S,ElemType&e)//假设栈不空，那么删除S的栈顶元素并以e带回其值，且返回TURE//否那么返回FALSEVoidStackTraverse(StackS,Status(*visit)(ElemTypee))//从栈底到栈顶依次对S中的每个结点调用函数visit其中局部操作的算法：voidInitStack(Park&P,intn){//初始化停车场P.top=P.base=(CarNode*)malloc(n*sizeof(Car1));P.stacksize=0;}voidPush(Park&P,CarNodee){//车进入停车场*P.top=e;P.top++;++P.stacksize;}voidPop(Park&P,CarNode&e){//车离开停车场--P.top;e=*P.top;--P.stacksize;}3、队列类型typedefstructCar2{//车intnumber;//汽车车号intar_time;//汽车到达时间structCar2*next;}*CarPtr;typedefstruct{//便道CarPtrfront;//便道的队列的对头CarPtrrear;//便道的队列的队尾intlength;}Shortcut;队列的根本操作设置如下：StatusTnitQueue(LinkQueue&Q)//构造一个空列QStatusQueueEmpty(LinkQueueQ)//假设队列Q为空队列，那么返回TURE，否那么返回FALSEStatusQueueLength(LinkQueueQ)//返回Q的元素个数，即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e)//假设队列不空，那么用e返回Q的队头元素，并返回OK；否那么返回ERRORStatusEnQueue(LinkQueue&Q,QElemTypee)//插入元素e为Q的新的队尾元素StatusDeQueue(LinkQueueQ,QElemType&e)//假设队列不空，那么删除Q的队头元素，用e返回其值，并返回OK;//否那么返回ERRORStatusQueueTraverse(LinkQueueQ,visit())//从队头到队尾依次对队列Q中每个元素调用函数visit()，一旦visit失败，那么操作失败。其中局部操作的算法：voidInitQueue(Shortcut&S){//初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2));S.front->next=NULL;S.length=0;}voidEnQueue(Shortcut&S,intnumber,intar_time){//车进入便道CarPtrp;p=(CarPtr)malloc(sizeof(Car2));p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;//相连S.rear=p;++S.length;}voidDeQueue(Shortcut&S,CarPtr&w){//车离开便道if(S.length!=0){w=S.front->next;S.front->next=S.front->next->next;--S.length;}}4、停车场、便道的类型其中局部操作的算法：voidArrival(Park&P,Shortcut&S,intn){//对进站车辆的处理intnumber,ar_time;printf("请输入车牌号：");scanf("%d",&number);printf("进场的时刻:");scanf("%d",&ar_time);if(P.stacksize<n){CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);printf("该车应停在第%d号车道。\n",P.stacksize);}else{EnQueue(S,number,ar_time);printf("停车场已满，请暂时停在便道的第%d个位置。\n",S.length);}}voidLeave(Park&P,Park&P1,Shortcut&S,intcost){//对离站车辆的处理intnumber,le_time,flag,money;CarPtrc,q;inttimes;printf("请输入车牌号：");scanf("%d",&number);printf("出场的时刻:");scanf("%d",&le_time);CarNodee,m;CarPtrw;while(P.stacksize){Pop(P,e);if(e.number==number){flag=0;money=(le_time-e.ar_time)*cost;times=le_time-e.ar_time;break;}Push(P1,e);}while(P1.stacksize){Pop(P1,e);Push(P,e);}//车从停车场中出if(flag==0){if(S.length!=0){DeQueue(S,w);m.ar_time=le_time;m.number=w->number;Push(P,m);free(w);printf("车牌号为%d的车已由便道进入停车场\n",m.number);}printf("停车费为%d,停车时间为%d\n",money,times);}else{printf("停车场不存在牌号为%d的车,在便道上找\n",number);c=S.front;if(S.length!=0){ while(c->next!=NULL) { if(c->next->number==number) { printf("%d车从便道上离开，停留时间%d\n",c->next->number,le_time-c->next->ar_time); c->next=c->next->next; --S.length; break;}c=c->next;DeQueue(S,q);S.rear->next=q;S.rear=q;}} }}五、主函数的算法：voidmain(){intn,cost;charflag;//选项ParkP,Q;printf("输入停车场的规模:"); scanf("%d",&n); printf("每小时收费:"); scanf("%d",&cost);ShortcutS;InitStack(P,n);//初始化InitStack(Q,n);InitQueue(S);while(1){cout<<"请选择〔A,D,E〕：\n"; cin>>flag;switch(flag){case'A':case'a':Arrival(P,S,n);break;//车进入停车场case'D':case'd':Leave(P,Q,S,cost);break;//车离开停车场case'E':case'e':return0;break;default:printf("Inputerror!\n");break;}}}六、函数的调用关系图反映了演示程序的层次结构：四、调试分析1、由于刚开始对队列元素删除的不了解，使得程序的操作直接对队列中的元素删除，而不是删除对头元素，这违背了题目要求。经过修改后，这一问题得到解决。2、栈的元素中step域没有太多用处，可以省略。3、StackTravers在调试过程中很有用，它可以插入在算法中多处，以观察停车场管理中车辆走动的次序是否正确，但对最后的执行版本么有用。五、用户手册1、本程序的运行环境为Windows，执行文件为：停车场管理.exe2、进入演示程序后，即显示文本方式的用户界面：3、进入车辆输入信息的命令后，程序开始运行。4、按回车后程序输出相应的结果。六、测试结果 七、附录#include<stdio.h>#include<malloc.h>#include<iostream.h>//栈，模拟停车场typedefstructCar1{//车intnumber;//汽车车号intar_time;//汽车到达时间}CarNode;typedefstruct{//停车场CarNode*base;//停车场的堆栈底CarNode*top;//停车场的堆栈顶intstacksize;}Park;//队列，模拟便道typedefstructCar2{//车intnumber;//汽车车号intar_time;//汽车到达时间structCar2*next;}*CarPtr;typedefstruct{//便道CarPtrfront;//便道的队列的对头CarPtrrear;//便道的队列的队尾intlength;}Shortcut;voidInitStack(Park&P,intn){//初始化停车场P.top=P.base=(CarNode*)malloc(n*sizeof(Car1));P.stacksize=0;}voidPush(Park&P,CarNodee){//车进入停车场*P.top=e;P.top++;++P.stacksize;}voidPop(Park&P,CarNode&e){//车离开停车场--P.top;e=*P.top;--P.stacksize;}voidInitQueue(Shortcut&S){//初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2));S.front->next=NULL;S.length=0;}voidEnQueue(Shortcut&S,intnumber,intar_time){//车进入便道CarPtrp;p=(CarPtr)malloc(sizeof(Car2));p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;//相连S.rear=p;++S.length;}voidDeQueue(Shortcut&S,CarPtr&w){//车离开便道if(S.length!=0){w=S.front->next;S.front->next=S.front->next->next;--S.length;}}voidArrival(Park&P,Shortcut&S,intn){//对进站车辆的处理intnumber,ar_time;printf("请输入车牌号：");scanf("%d",&number);printf("进场的时刻:");scanf("%d",&ar_time);if(P.stacksize<n){CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);printf("该车应停在第%d号车道。\n",P.stacksize);}else{EnQueue(S,number,ar_time);printf("停车场已满，请暂时停在便道的第%d个位置。\n",S.length);}}voidLeave(Park&P,Park&P1,Shortcut&S,intcost){//对离站车辆的处理intnumber,le_time,flag,money;CarPtrc,q;inttimes;printf("请输入车牌号：");scanf("%d",&number);printf("出场的时刻:");scanf("%d",&le_time);CarNodee,m;CarPtrw;while(P.stacksize){Pop(P,e);if(e.number==number){flag=0;money=(le_time-e.ar_time)*cost;times=le_time-e.ar_time;break;}Push(P1,e);}while(P1.stacksize){Pop(P1,e);Push(P,e);}printf("停车费为%d,停车时间为%d\n",money,times);//车从停车场中出While(S.stacksize){DeQueue(S,w);m.ar_time=le_time;m.number=w->number;Push(P,m);