搜索
数据结构综合实验1银行排队事件模拟2迷宫问题数据结构综合实验数据结构综合实验1排队问题仿真例1排队问题用队列结构可以模拟现实生活中的很多排队现象，如车站候车、医院候诊、银行排队等都可以通过程序进行仿真模拟，并由此预测客流等多种经营指标。下面以理发店为背景，讨论排队类问题的系统仿真。数据结构综合实验问题描述假设理发店内设有N把理发椅，可同时为N位顾客进行理发。顾客进门，可能有两种情况。①若当时理发店内尚有空闲理发椅，则该顾客可立即入座理发，他在店内的逗留时间即为他理发所需时间；1排队问题仿真数据结构综合实验②否则需要排队候理，则他在店内的逗留时间应为他理发所需时间和排队等候的时间之和。一旦有顾客理完发离去时，排在对头的顾客便开始理发。顾客的到达时间和理发所需时间均可随机生成，并约定，过了营业时间顾客不再进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。1排队问题仿真数据结构综合实验题目要求编制一个事件驱动仿真程序以模拟理发店内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在店内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。通过队列模拟理发店的排队现象，通过仿真办法评估理发店的营业状况。排队问题1排队问题仿真数据结构综合实验1排队问题仿真需求分析“事件驱动模拟”为计算出每个顾客自进门到出门之间在理发馆内逗留的时间，只需要在顾客“进门”和“出门”这两个时刻进行模拟处理。定义在这两个时刻内发生的事情为“事件”，整个仿真程序可以按事件发生的先后次序逐个处理事件，这种模拟的工作方式称为“事件驱动模拟”。数据结构综合实验建立数据模型-数据结构设计本题目需要两种数据结构：链队列：登录排队等候理发的顾客情况，队列中的每个元素应包括顾客进门的时刻和理发所需的时间。链表：登录顾客进门和出门的事件。表中的元素应包括事件类型，还应按事件发生的先后次序有序。1排队问题仿真数据结构综合实验1排队问题仿真事件表数据类型定义typedefstruct{//数据域intoccurTime;//事件发生时刻charNType;//事件类型}ElemType,Event;typedefstructLnode{//链表结点ElemTypedata;structLnode*next;}*Link,*Position;数据结构综合实验1排队问题仿真事件链表结构定义typedefstruct{Linkhead,tail;//头、尾指针intlength;//链表长度Linkcurrent;//当前指针}LinkList;typedefLinkListEventList;//事件链表类型，定义为有序链表数据结构综合实验等待队列定义typedefstruct{//数据域intarrivalTime;//顾客到达时间intduration;//顾客理发所需时间}QElemType;typedefstructQnode{//链表结点QElemTypedata;structQnode*next;}Qnode,*QueuePtr;1排队问题仿真数据结构综合实验链队列结构定义typedefstruct{QueuePtrfront;//头指针QueuePtrrear;//尾指针}LinkQueue;1排队问题仿真数据结构综合实验主算法设计假设进门事件类型为’A’，出门事件类型为’D’。为便于按事件发生的先后次序顺序进行处理，事件表应按发生的“时刻”有序。实际问题中，顾客进门的时刻和理发所需要的时间都是随机的。假设第一个顾客进门的时刻为0。之后每个顾客进门的时刻在前一个顾客进门时设定，即以两个顾客之间的时间间隔来确定下一个顾客的到达时间。1排队问题仿真数据结构综合实验生成“顾客理发所需时间durtime”和“下一顾客到达的时间间隔intertime”两个随机数可从C语言的随机数函数得到。假设当前事件发生的时刻为occurtime，则下一顾客进门事件发生的时刻则为occurtime+intertime。该顾客在当前时刻开始理发，经过durtime时间之后便可离开理发馆，则应发生时刻为occurtime+durtime。1排队问题仿真数据结构综合实验排队问题主算法描述主算法是以处理顾客进门事件和顾客离开事件为线索进行的。voidBarberShop_Simulation(intchairNum,intcloseTime){//理发店馆业务模拟//chatrNum为假设的理发馆的//规模closeTime为营业时间OpenForDay;//初始化1排队问题仿真数据结构综合实验whileMoreEventdo{EventDrived(OccurTime,EventType);//事件驱动switch(EventType){case‘A’:CustomerArrived;break;//处理顾客到达事件case'D':CustomerDeparture;break;//处理顾客离开事件1排队问题仿真数据结构综合实验default:Invalid;}//switch}//whileCloseForDay;//计算平均逗留时间和排队的平均长度}//BarberShop_Simulation1排队问题仿真数据结构综合实验主算法详细描述BarberShop_Simulation{设定事件表中的第一个元素；置空队列；while（当事件表不空）{删除事件表中发生时刻最早的元素；if（事件类型=0）{//处理顾客进门事件累计顾客进门人数；if（下一个到达时刻关门时刻）进门事件插入事件表；1排队问题仿真数据结构综合实验if（有空闲理发椅）{新出门事件插入事件表；累计顾客逗留时间；}else{当前顾客插入队尾；累计队列长度；}}//if1排队问题仿真数据结构综合实验else{//事件类型=1，处理顾客离开事件if（队列不空）{删除队头元素；记录顾客离开的最晚时间；新出门事件插入事件表；累计顾客逗留时间；}//if}//else}//while1排队问题仿真数据结构综合实验计算平均队列长度；计算平均逗留时间；}//BarberShop_Simulation1排队问题仿真数据结构综合实验voidCustomerArrived(eventListevL,QueueQ,Eventen){//处理顾客进门事件Random(durtime,intertime);nextAT=en.occurTime+intertime;//下一顾客到达时刻，evL为事件表，表//中的第1个事件为(0,‘A’)。durtime为当//前进门的顾客理发所需时间，intertime//为下一个顾客即将进门的间隔时间。1排队问题仿真数据结构综合实验if(nextATcloseTime){newAEvent=(nextAT,‘A’);//新的进门事件MakeNode(newp,newAEvent);LocateElem(evL,newAEvent,compare);Insafter(evL,newp);//插入事件表}1排队问题仿真数据结构综合实验if(freeChair){//顾客即刻开始理发，freeChair的初//值即为chairNum。dT=en.occurTime+durtime;newDEvent=(dT,‘D’);//新的出门事件MakeNode(newp,newDEvent);LocateElem(evL,newDEvent,compare);1排队问题仿真数据结构综合实验Insafter(evL,newp);//插入事件表totalTime+=durtime;//累计逗留时间，TotalTime、//customerNum和totalQLength的//初值均为0。--freeChair;}1排队问题仿真数据结构综合实验else{//顾客排队等候newCustomer=(en.occuTime,durtime);EnQueue(Q,newCustomer);}++customerNum;//统计顾客总人数totalQLength+=QueueLength(Q);//累计排队的长度}//CustomerArrived1排队问题仿真数据结构综合实验voidCustomerDeparture(eventListevL,QueueQ,Eventen){//处理顾客出门事件if(!DeQueue(Q,cm))++FreeChair;//无人等候理发else{//排头顾客出列开始理发dT=en.occurTime+cm.duration;newDEvent=(dT,'D');//新的出门事件1排队问题仿真数据结构综合实验MakeNode(newp,newDEvent);LocateElem(evL,newDEvent,compare);Insafter(evL,newp);//插入事件表totalTime+=(dT-cm.arrivalTime);}//累计逗留时间1排队问题仿真数据结构综合实验totalFreeChair+=freeChair;//累计空椅数}//CustomerDeparture1排队问题仿真数据结构综合实验主程序模块间调用关系主程序模块事件模块队列模块链表模块1排队问题仿真数据结构综合实验主程序算法voidmain(){//全局变量定义EventListev;//事件表Eventen;//事件LinkQueueQ;//等候理发的顾客队列QElemTypecustomer;//顾客记录intt2,t1,Totaltime,CustomerNum;intCloseTime,k,CurrentChair;//累计顾客逗留时间，顾客数1排队问题仿真数据结构综合实验floatTotallength;intt=0;OpenForDay();//初始化while(!ListEmpty(ev)){DelFirst(ev,en);if(en.NType==0)CustomerArrived();//处理进门事件elseCustomerDeparture();//处理离开事件}//while1排队问题仿真数据结构综合实验cout“NumberofcustomerCustomerNumendl;coutAveragetimeTotaltime/CustomerNumendl;//求平均逗留时间coutAveragequeuelength“Totallength/CustomerNumendl;//求平均的队列长度}//main1排队问题仿真数据结构综合实验模拟运行理发店有四个工作室，Ntype=0表示客户到达，Ntype=1,2,3,4表示在1号、2号、3号和4号理发室等待或理发。一对随机数（a,b），a表示理发需要的时间，b表示下一个客户到达的时间。假设每个客户理发时间不超过30分钟；两个相邻到达理发店的客户的时间间隔不超过5分钟。模拟程序从第一个客户到达时间为“o”开始起运行。1排队问题仿真数据结构综合实验初始状态ev.first为链表头指针。删除事件表上第一个结点，得到en.OccurTime=0，en.Ntype=0；1排队问题仿真数据结构综合实验状态1因为en.Ntype=0，则随即得到两个随机效(23，4)，生成一个下一客户到达的事件(OccurTime=4，NTyPe=o)插入事件表；1排队问题仿真数据结构综合实验状态2刚到的第一位客户排在第一个理发室等待的队列中(ArrivalTime=0，Duration=23)，由于他是排头，故生成一个客户将离开的事件(OccurTime=23，NType＝1)插入事件表。1排队问题仿真数据结构综合实验状态3删除事件表上第一个结点，因为en.Ntype=0仍是新客户到达事件，en.OccurTime=4，得到随机数为(3，1)，则下一客户到达的时间为OccurTime=4+1=5；1排队问题仿真数据结构综合实验状态4由于此时第二间理发室是空的，则刚到的第二位客户为第二个队列的队头(Ar