停车场数据机构设计 23页

'停车场数据机构设计1问题描述1.1题目描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。试用停车场编制按上述要求进行管理的模拟程序。1.2任务要求1.2.1使用顺序栈模拟停车场，链队列模拟车场外的便道，实现车辆入栈、出栈、入队列、出队列、信息输出等功能。1.2.2车辆信息有：车牌号、到达信息、到达时刻、离去信息、离去时刻等；1.2.3输出的信息有：如果是到达的车辆，输出其在停车场中或便道上的位置；1.2.4如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用22 2设计思想及其目的2.1设计思想此停车场管理系统是在一个狭长的通道上的，而且只有一个大门可以供车辆进出，并且要实现停车场内某辆车要离开时，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些辆再依原来的次序进场的功能，就可以设计两个堆栈，其中一个堆栈用来模拟停车场，另一个堆栈用来模拟临时停车场，该临时停车场用来存放当有车辆离开时，原来停车场内为其让路的车辆。至于当停车场已满时，需要停放车辆的通道可以用一个链队列来实现。当停车场内开走一辆车时，通道上便有一辆车进入停车场，此时只需要改变通道上车辆结点的连接方式就可以了，使通道上第一辆车进入停车场这个堆栈，并且使通道上原来的第二辆车成为通道上的第一辆车，此时只需将模拟通道的链队列的头结点连到原来的第二辆车上就可以了。2.2设计目的1通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固。2通过课程设计，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。3通过课程设计，提高程序开发功能，能运用合理的控制流程编写清晰高效的程序。4通过课程设计，训练C程序调试能力，能将一个中小型各级组织系统联调通过。5通过课程设计，开发一个中小型系统，掌握系统研发全过程。6通话课程设计，培养分析问题、解决实际问题的能力。22 3系统具备的功能3.1简体中文控制台界面程序用来实现对停车场内车辆的管理，整个操作界面为中文，更加符合人性化的标准，3.2到达信息当车辆到达时，能够记录到达车辆的号码，记录到达时间。安排停车位置。如果车道满了，就停留在便道上。3.3离开信息当车辆离开时，统计其停留时间，记录其停车费用。3.4查询信息进入查询界面，可以查询目前车长信息，和变到信息。22 4系统流程图22 5主函数、子程序调用关系22 6主要算法实现及其基本操作6.1此停车场管理系统，主要分为以下若干模块：首先定义用来模拟停车场的堆栈以及用来模拟通道的链队列为全局变量，然后编写主函数，在此主函数中实现对其它各个模块的调用。在主函数中首先调用option()函数，出现欢迎用户使用的主界面，然后提示用户进入此停车场管理系统后，再出现一个供用户选择的界面，在用户的选择过程中，程序又分别调用车辆的到达、车辆的离开、停车场内停放车辆的信息以及退出程序这四个函数模块。其中，在车辆的离开那个模块函数中又调用了打印离开车辆信息的函数，在停车场内停放车辆信息的那个模块函数中，又分别调用了显示停车场上车辆信息的函数以及显示便道上车辆信息的函数。最后，从调鼐的这四个函数中回到主函数结束整个程序的运行。6.2在以上各个模块中，各模块的伪码算法：6.2.1栈的初始化：voidInitStack(SeqStackCar*s)/*初始化栈*/{inti;s->top=0;for(i=0;i<=MAX;i++)s->stack[s->top]=NULL;}6.2.2链队列的初始化：intInitQueue(LinkQueueCar*Q)/*初始化队列*/{Q->head=(QueueNode*)malloc(sizeof(QueueNode));if(Q->head!=NULL){Q->head->next=NULL;22 Q->rear=Q->head;return(1);}elsereturn(-1);}6.2.3车辆到达时的算法：intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*车辆到达*/{CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));printf("ttt请输入到达车辆车牌号:");scanf("%d",&(p->num));if(Enter->toptop++;printf("nttt该车辆在停车场的位置是:%dn",Enter->top);printf("nttt请输入该车辆到达的时间:");scanf("%d",&(p->reachtime));Enter->stack[Enter->top]=p;return(1);}else/*车场已满，车进便道*/{printf("nttt停车场已满该车辆需在便道上等待！");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;return(1);}22 }6.2.4车辆离开时的算法：voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)/*车辆离开*/{inti,room;CarNode*p,*t;QueueNode*q;/*判断车场内是否有车*/printf("n********************************************************************************");if(Enter->top>0)/*有车*/{while(1)/*输入离开车辆的信息*/{printf("ttt停车场里停放的车辆总数:%d",Enter->top);printf("nnttt请输入要离开车辆的位置:");scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)/*车辆离开*/{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1)22 {Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p);/*判断通道上是否有车及车站是否已满*/if((W->head!=W->rear)&&Enter->tophead->next;t=q->data;Enter->top++;printf("nnttt便道的%d号车进入车场第%d位置.",t->num,Enter->top);printf("nnttt请输入现在的时间:");scanf("%d",&(t->reachtime));W->head->next=q->next;if(q==W->rear)W->rear=W->head;Enter->stack[Enter->top]=t;free(q);}elseprintf("nnttt便道里没有车.n");}elseprintf("nnttt车场里没有车.");/*没车*/}6.2.5列表现试车场信息voidList1(SeqStackCar*S)/*列表显示车场信息*/22 {inti;if(S->top>0)/*判断车站内是否有车*/{printf("nttt车场:");printf("nnttt位置到达时间车牌号n");for(i=1;i<=S->top;i++){printf("%26d",i);printf("%6d",S->stack[i]->reachtime);printf("%10d",S->stack[i]->num);printf("n");}}elseprintf("nttt车场里没有车");}6.2.6列表显示便道信息voidList2(LinkQueueCar*W)/*列表显示便道信息*/{QueueNode*p;p=W->head->next;if(W->head!=W->rear)/*判断通道上是否有车*/{printf("nttt等待车辆的号码为:");while(p!=NULL){printf("%-10d",p->data->num);p=p->next;}elseprintf("nttt便道里没有车.");}}22 7系统运行环境和开发工具7.1系统运行环境7.1.1硬件环境处理器：InterPentium166MX或更高内存：32MB或更大硬盘空间：1GB以上显卡：SVGA显示适配器7.1.2软件环境操作系统：Windows98/ME/2000/XP7.2开发工具C-FREE4.022 8用户手册8.1用户界面这个程序用来实现对停车场内车辆的管理，整个操作界面为中文，更加符合人性化的标准，使得用户使用方便，而且每一个操作都有提示，使得初次接触该程序的用户也能很快适应程序的操作。22 8.2新的车辆到达这个程序操作简单，对于车牌号，只需输入车牌号上的数字就行，简化了操作。车辆满的时候停靠在便道上。8.3场内车辆离开离开时同样，输入离开的车牌号及其离开时间，自动判断费用。及其便道上车辆进入，以及进入时间。22 8.4查询车辆信息可以查看场内车辆信息和便道上的车辆信息。22 9详细设计9.1源文件#include#include#include#defineMAX10/*车库容量*/#defineprice1/*每车每时刻费用*/typedefstructnode{intnum;intreachtime;intleavetime;}CarNode;/*车辆信息结点*/typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;/*模拟车站*/typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;/*模拟通道*//*---------------------------------------------------------------------------*//*函数声明部分*/voidInitStack(SeqStackCar*);/*初始化栈*/intInitQueue(LinkQueueCar*);/*初始化便道*/intArrival(SeqStackCar*,LinkQueueCar*);/*车辆到达*/voidLeave(SeqStackCar*,SeqStackCar*,LinkQueueCar*);/*车辆离开*/voidList(SeqStackCar,LinkQueueCar);/*显示存车信息*/voidPRINT(CarNode*p);22 /*---------------------------------------------------------------------------*/voidoption(){inti;charchoice;for(i=1;i<=80;i++)printf("04");printf("nnnn");printf("----------------------------n");printf("|停车场管理系统|n");printf("----------------------------n");printf("nnnn");for(i=1;i<=80;i++)printf("04");printf("设计者:王勇n");printf("班级:计算机08-3");printf("n********************************************************************************");printf("nnn是否进入该系统n（y/n）");choice=getchar();if(choice=="N"||choice=="n")exit(0);}voidmain(){SeqStackCarEnter,Temp;LinkQueueCarWait;intch;22 option();InitStack(&Enter);/*初始化车站*/InitStack(&Temp);/*初始化让路的临时栈*/InitQueue(&Wait);/*初始化通道*/while(1){printf("n********************************************************************************");printf("nnttt1.新的车辆到达请选择1");printf("nnttt2.场内车辆离开请选择2");printf("nnttt3.查询车辆信息请选择3");printf("nnttt4.选择退出程序请选择4");printf("nnttt现在请选择以上信息:");while(1){scanf("%d",&ch);printf("n");if(ch>=1&&ch<=4)break;elseprintf("nttt错误！请再次做出选择！nnttt");}switch(ch){case1:Arrival(&Enter,&Wait);break;/*车辆到达*/case2:Leave(&Enter,&Temp,&Wait);break;/*车辆离开*/case3:List(Enter,Wait);break;/*列表打印信息*/case4:exit(0);/*退出主程序*/default:break;}}}/*------------------------------------------------------------------------------*/voidInitStack(SeqStackCar*s)/*初始化栈*/{inti;s->top=0;for(i=0;i<=MAX;i++)22 s->stack[s->top]=NULL;}intInitQueue(LinkQueueCar*Q)/*初始化便道*/{Q->head=(QueueNode*)malloc(sizeof(QueueNode));if(Q->head!=NULL){Q->head->next=NULL;Q->rear=Q->head;return(1);}elsereturn(-1);}voidPRINT(CarNode*p)/*打印出站车的信息*/{intA1,A2;printf("n********************************************************************************");printf("nttt请输入离开时间:");scanf("%d",&(p->leavetime));printf("nttt离开车辆的车牌号:%d",p->num);printf("nnttt离开车辆到达时间:%d",p->reachtime);printf("nnttt离开车辆离开时间:%d",p->leavetime);A1=p->reachtime;A2=p->leavetime;printf("nnttt停车场管理费用:%d",(A2-A1)*price);free(p);}intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*车辆到达*/{CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));printf("ttt请输入到达车辆车牌号:");scanf("%d",&(p->num));if(Enter->toptop++;printf("nttt该车辆在停车场的位置是:%dn",Enter->top);22 printf("nttt请输入该车辆到达的时间:");scanf("%d",&(p->reachtime));Enter->stack[Enter->top]=p;return(1);}else/*车场已满，车进便道*/{printf("nttt停车场已满该车辆需在便道上等待！");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;return(1);}}voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)/*车辆离开*/{inti,room;CarNode*p,*t;QueueNode*q;/*判断车场内是否有车*/printf("n********************************************************************************");if(Enter->top>0)/*有车*/{while(1)/*输入离开车辆的信息*/{printf("ttt停车场里停放的车辆总数:%d",Enter->top);printf("nnttt请输入要离开车辆的位置:");scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)/*车辆离开*/{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;22 Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p);/*判断通道上是否有车及车站是否已满*/if((W->head!=W->rear)&&Enter->tophead->next;t=q->data;Enter->top++;printf("nnttt便道的%d号车进入车场第%d位置.",t->num,Enter->top);printf("nnttt请输入现在的时间:");scanf("%d",&(t->reachtime));W->head->next=q->next;if(q==W->rear)W->rear=W->head;Enter->stack[Enter->top]=t;free(q);}elseprintf("nnttt便道里没有车.n");}elseprintf("nnttt车场里没有车.");/*没车*/}voidList1(SeqStackCar*S)/*列表显示车场信息*/{inti;if(S->top>0)/*判断车站内是否有车*/{printf("nttt车场:");22 printf("nnttt位置到达时间车牌号n");for(i=1;i<=S->top;i++){printf("%26d",i);printf("%6d",S->stack[i]->reachtime);printf("%10d",S->stack[i]->num);printf("n");}}elseprintf("nttt车场里没有车");}voidList2(LinkQueueCar*W)/*列表显示便道信息*/{QueueNode*p;p=W->head->next;if(W->head!=W->rear)/*判断通道上是否有车*/{printf("nttt等待车辆的号码为:");while(p!=NULL){printf("%-10d",p->data->num);p=p->next;}elseprintf("nttt便道里没有车.");}}printf("n");voidList(SeqStackCarS,LinkQueueCarW){intflag,tag;flag=1;while(flag){printf("nnttt1.车场nnttt2.便道nnttt3.返回nnttt");printf("现在请选择以上信息");while(1){scanf("%d",&tag);if(tag>=1||tag<=3)break;elseprintf("现在请选择以上信息");22 }switch(tag){case1:List1(&S);break;/*列表显示车场信息*/case2:List2(&W);break;/*列表显示便道信息*/case3:flag=0;break;default:break;}}}10结果分析及算法评价10.1结果分析10.1.1停车场管理系统，基本上可以完成每一项功能。汽车进入停车场的信息、离开停车场的信息以及通道上的信息都可以在程序上一一实现。10.1.2但是，该程序也有不足的地方。主要表现在车辆的车牌号上，现实中的车牌号是一串字符，可是，在这个程序中，为了简便起见，我们就车牌号定义为了整型，这个与现实是有些不符的。还有一个可以改进的地方就是记录车辆进入停车场以及离开停车场的时间，应该精确到小时以及分钟的，可是在程序中，为了简便起见，我们只是设置成了一个时刻，所以，在这方面还是有待改进的。改进的程序中，还应该增加时间的判断功能，即停车场内有可能有车辆停放的时间超过一天。9.1.3还有一个很重要的问题，对于停车场内可以停放的最多车辆数，为了测试数据的方便，我在程序中，定为了2，在实际使用中，可以改变程度开头的宏定义以增加停车场的容量10.2算法评价10.2.1正确性程序对于几组输入数据能够得出满足规格说明要求的结果10.2.2运行时间，车辆到达时间复杂度为O(n)车辆离开时间复杂度为O(n*n)10.2.3占用的存储空间，车辆到达，车辆离开，车辆存储的空间复杂度均为O(n)11设计体会和总结22 在数据结构课程设计中,我的题目是:停车场管理,通过该题目的设计过程,我加深了对数据结构中线性表及栈的逻辑结构,存储结构的理解，掌握了线性表及栈上基本运算的实现，进一步理解和掌握了课本中所学的各种数据结构，同时也加深了对C语言中知识的理解。学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设计时遇到了很多的问题，在老师和同学的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，我收益很大，学到很多。12参考文献12.1严蔚敏，吴伟民编，《数据结构（C语言版）》。北京：清华大学出版社,2003。12.2严蔚敏，吴伟民编，《数据结构题集（C语言版）》。北京：清华大学出版社，2003。12.3黄明，梁旭编著，《C语言课程设计》。北京：电子工业出版社，2006.6。12.4苏仕华编，〈〈数据结构课程设计〉〉。北京：机械工业出版社，2005.5。22'