数据结构综合实验示例

《数据结构综合实验示例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1银行排队事件模拟2迷宫问题数据结构综合实验1排队问题仿真例1排队问题用队列结构可以模拟现实生活中的很多排队现象，如车站候车、医院候诊、银行排队等都可以通过程序进行仿真模拟，并由此预测客流等多种经营指标。下面以理发店为背景，讨论排队类问题的系统仿真。问题描述假设理发店内设有N把理发椅，可同时为N位顾客进行理发。顾客进门，可能有两种情况。①若当时理发店内尚有空闲理发椅，则该顾客可立即入座理发，他在店内的逗留时间即为他理发所需时间；1排队问题仿真②否则需要排队候理，则他在店内的逗留时间应为他理发所需时间

2、和排队等候的时间之和。一旦有顾客理完发离去时，排在对头的顾客便开始理发。顾客的到达时间和理发所需时间均可随机生成，并约定，过了营业时间顾客不再进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。1排队问题仿真题目要求编制一个事件驱动仿真程序以模拟理发店内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在店内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。通过队列模拟理发店的排队现象，通过仿真办法评估理发店的营业状况。排队问题1排队问题仿真1排队问题仿真

3、需求分析“事件驱动模拟”为计算出每个顾客自进门到出门之间在理发馆内逗留的时间，只需要在顾客“进门”和“出门”这两个时刻进行模拟处理。定义在这两个时刻内发生的事情为“事件”，整个仿真程序可以按事件发生的先后次序逐个处理事件，这种模拟的工作方式称为“事件驱动模拟”。建立数据模型-数据结构设计本题目需要两种数据结构：链队列：登录排队等候理发的顾客情况，队列中的每个元素应包括顾客进门的时刻和理发所需的时间。链表：登录顾客进门和出门的事件。表中的元素应包括事件类型，还应按事件发生的先后次序有序。1排队问题仿真

4、1排队问题仿真事件表数据类型定义typedefstruct{//数据域intoccurTime;//事件发生时刻charNType;//事件类型}ElemType,Event;typedefstructLnode{//链表结点ElemTypedata;structLnode*next;}*Link,*Position;1排队问题仿真事件链表结构定义typedefstruct{Linkhead,tail;//头、尾指针intlength;//链表长度Linkcurrent;//当前指针}LinkLis

5、t;typedefLinkListEventList;//事件链表类型，定义为有序链表等待队列定义typedefstruct{//数据域intarrivalTime;//顾客到达时间intduration;//顾客理发所需时间}QElemType;typedefstructQnode{//链表结点QElemTypedata;structQnode*next;}Qnode,*QueuePtr;1排队问题仿真链队列结构定义typedefstruct{QueuePtrfront;//头指针QueuePtr

6、rear;//尾指针}LinkQueue;1排队问题仿真主算法设计假设进门事件类型为’A’，出门事件类型为’D’。为便于按事件发生的先后次序顺序进行处理，事件表应按发生的“时刻”有序。实际问题中，顾客进门的时刻和理发所需要的时间都是随机的。假设第一个顾客进门的时刻为0。之后每个顾客进门的时刻在前一个顾客进门时设定，即以两个顾客之间的时间间隔来确定下一个顾客的到达时间。1排队问题仿真生成“顾客理发所需时间durtime”和“下一顾客到达的时间间隔intertime”两个随机数可从C语言的随机数函数得到

7、。假设当前事件发生的时刻为occurtime，则下一顾客进门事件发生的时刻则为occurtime+intertime。该顾客在当前时刻开始理发，经过durtime时间之后便可离开理发馆，则应发生时刻为occurtime+durtime。1排队问题仿真排队问题主算法描述主算法是以处理顾客进门事件和顾客离开事件为线索进行的。voidBarberShop_Simulation(intchairNum,intcloseTime){//理发店馆业务模拟//chatrNum为假设的理发馆的//规模closeTi

8、me为营业时间OpenForDay;//初始化1排队问题仿真whileMoreEventdo{EventDrived(OccurTime,EventType);//事件驱动switch(EventType){case‘A’:CustomerArrived;break;//处理顾客到达事件case'D':CustomerDeparture;break;//处理顾客离开事件1排队问题仿真default:Invalid;}//switch}//whileCloseForDa