实验报告银行业务模拟系统的设计与实现

1、 数 据 结 构 实验报告学 号姓 名李晓松年 级2009班级网络工程5班机号：学院机房时 间周三下午2点半-4点周四上午8点-10点指导教师张磊1、 实验题目： 1）通过实验掌握对离散事件模拟的认识； 2）进一步理解队列的实现与应用；3）对链表的操作有更深层次的理解；二、实验要求：1 问题描述：假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制程序以模

2、拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。2一个完整的系统应具有以下功能：1）初始化（OpenForDay），模拟银行开门时各数据结构的状态。2） 事件驱动（EventDrived）, 对客户到达和离开事件做相应处理。3） 下班处理（CloseForDay）, 模拟银行关门时的动作，统计客户平均逗留时间 。备注：假设银行开门的时刻（间）设为0 , 银行每天营业的时间在程序运行时输入（例如480分钟）。每个客户办理业务的时间不超过30分钟，两个相邻客户到达银行的时间间隔不超过5分钟要求程序执行时，只要给出银行每天的营业时间即可输出客户平均逗留的时间。三、总的设计思想、环境语言、工

3、具等总的设计思想：为了计算这个平均的逗留时间，自然需要知道每个客户到达银行和离开银行这两个时刻，后者减去前者即为每个客户在银行的逗留时间。所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。称客户到达银行和离开银行这两个时间发生的事情为“事件”，则整个模拟程序将按事件的先后顺序进行处理。这样一种程序称做事件驱动模拟。下面是上述银行客户的离散事件驱动的模拟算法。 void Bank_Simulation( int CloseTime ) / OpenForDay ( ); /初始化,模拟银行开门时各数据结构的状态。 while(有要处理的事件时) /有事件可处理 EventDri

4、ved ; /事件驱动，从事件表中取出事件en；/根据en的类型（客户到达事件或客户离开事件）做相应的处理 if(en表示客户到达) CustomerArrived( );/ 处理客户到达事件 else CustomerDeparture( ) ;/ 处理客户离开事件 /while CloseForDay( );/计算客户的平均逗留时间/ Bank_Simulation 环境语言：Windows下的Microsoft VC+四、数据结构与模块说明下面是模拟程序中需要的数据结构及其操作。1模拟算法的主要处理对象是“事件”，事件的主要信息是事件的类型和事件的发生时刻。算法中处理的事件有两类：一类是

5、客户到达事件；另一类是客户离开事件。前一类事件发生的时刻随客户的到来自然形成；后一类事件发生的时刻由客户办理业务所需时间和等待时间而定。由于程序驱动是按事件发生时刻的先后顺序进行的，所以事件表应是有序表，其主要操作是插入和删除事件，用一个单链表表示！2模拟程序中需要的另一数据结构是表示客户排队的队列，由于假设银行有4个窗口，因此程序中需要4个队列，队列中有关客户的信息是客户到达的时刻和客户办理业务所需要的时间。每个队列中的队头客户即为正在窗口办理事务的客户，他办完业务离开队列的时刻就是即将发生的客户离开事件的时刻，这就是说，对每个队头客户都存在一个将要驱动的客户离开事件。因此在任何时刻即将发生

6、的事伯只有5种可能：1）新的客户到达；2）1号窗口的客户离开；3）2号窗口的客户离开；4）3号窗口的客户离开；5）4号窗口的客户离开；注：为了使编写的程序具有通用性，在编程序时将银行的营业时间、开的窗口数、客户办业业务的最长时间及两个客户到达的时间间隔都设置成程序运行时动态输入，这样可以对程序以及银开设的窗口的合理性进行分析，实现真正的模拟。从以上分析可知，在模拟程序中只需要两种数据结构：有序链表和队列。程序中用到的头文件、类型定义及主要的函数原型如下：#includestdio.h#includemalloc.h#includemath.h#includestdlib.hint Cks=4;

7、 / 银行办理业务的窗口数,默认值为:4；最大值不超过20；int Qu ; / 客户队列数Qu=Cksint Khjg=5; / 两相邻到达客户的时间间隔最大值,默认值为:5int Blsj=30; / 每个客户办理业务的时间最大值,默认值为:30typedef struct / 定义事件的元素类型ElemType为结构体类型 int OccurTime; / 事件发生时刻 int NType; / 事件类型，Qu表示到达事件,0至Qu-1表示Qu个窗口的离开事件 Event,ElemType; / 事件类型，有序链表LinkList的数据元素类型typedef struct LNode /

8、定义事件表的结点类型 ElemType data ;struct LNode *next; LNode, *LinkList; typedef LinkList EventList; / 事件链表类型，定义为有序链表typedef struct /定义客户队列的元素类型 int ArrivalTime; / 到达时刻 int Duration; / 办理事务所需时间 QElemType; / 定义QElemType(队列的数据元素类型)为结构体类型;typedef struct QNode /定义客户队列的结点类型 QElemType data ;struct QNode *next; QNo

9、de, *Queue; typedef struct Queue head; Queue tail; LinkQueue;LinkQueue qQu+1; / Qu个客户队列void OpenForDay()； /模拟银行开门的动作，即初始化操作 void CustomerArrived() / 处理客户到达事件void CustomerDeparture() / 处理客户离开事件五、主要算法的设计与实现void OpenForDay() /模拟银行开门的动作，即初始化操作 int i; InitList(ev); / 初始化事件链表为空 en.OccurTime=0; / 设定第一个客户到达

10、事件 en.NType=0; / 客户到达事件 Insert_EventList(ev, en);/插入事件 q=(LinkQueue*)malloc(Qu+1)*sizeof(LinkQueue);/为队列申请Qu+1个队头指针，第0个不用 for(i=1;iQu+1;+i) / 置空队列 InitQueue(qi); void CustomerArrived() / 处理客户到达事件 QElemType f; int durtime,intertime,i; +CustomerNum; Random(durtime,intertime); / 生成随机数 /printf(%d %dn,du

11、rtime,intertime); et.OccurTime=en.OccurTime+intertime; / 下一客户到达时刻 et.NType=0; / 队列中只有一个客户到达事件 /printf(%d %dn,et.NType,et.OccurTime); if(et.OccurTimeCloseTime) / 银行尚未关门，插入事件表 Insert_EventList(ev,et); i=Minimum(q); / 求长度最短队列的序号,等长为最小的序号 f.ArrivalTime=en.OccurTime; f.Duration=durtime; EnQueue(qi,f); if

12、(QueueLength(qi)=1) et.OccurTime=en.OccurTime+durtime; et.NType=i; Insert_EventList(ev,et); / 设定第i队列的一个离开事件并插入事件表 void CustomerDeparture() / 处理客户离开事件，en.NTyPe!=0 int i; i=en.NType; DelQueue(qi,customer); / 删除第i队列的排头客户 TotalTime+=en.OccurTime-customer.ArrivalTime; / 累计客户逗留时间 if(!QueueEmpty(qi) / 设定第i

13、队列的一个离开事件并插入事件表 GetHead_q(qi,customer); et.OccurTime=en.OccurTime+customer.Duration; et.NType=i; Insert_EventList(ev,et); void Bank_Simulation() int i; OpenForDay( ); / 初始化 while(!ListEmpty(ev) /output_ev(ev); /for(i=1;iQU+1;i+) output_q(qi); /getchar();/为观察执行结果用 Gethead(ev,en); /printf(事件%d %dn ,en

14、.NType,en.OccurTime); if(en.NType=0) CustomerArrived(); / 处理客户到达事件 else CustomerDeparture(); / 处理客户离开事件 / 计算并输出平均逗留时间 printf(顾客总数:%d, 所有顾客共耗时:%d分钟, 平均每人耗时: %d分钟n,CustomerNum,TotalTime,TotalTime/CustomerNum); 六、源程序 见电子稿(文件名为: Bank_Simulation .cpp ); 七、运行结果请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数C

15、ks=4请输入客户办理业务的最长时间Blsj=30请输入两个相邻客户到达银行的时间间隔的最大值Khjg=5顾客总数:154, 所有顾客共耗时:11303分钟, 平均每人耗时: 73分钟Press any key to continue请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数Cks=5请输入客户办理业务的最长时间Blsj=30请输入两个相邻客户到达银行的时间间隔的最大值Khjg=5顾客总数:154, 所有顾客共耗时:3854分钟, 平均每人耗时: 25分钟Press any key to continue请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数Cks=6请输入客户办理业务的最长时间Blsj=30请输入两个相邻客户到达银行的时间间隔的最大值Khjg=5顾客总数:154, 所有顾客共耗时:2705分钟, 平均每人耗时: 17分钟请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数Cks=4请输入客户办理业务的最长时间Blsj=15请输入两个相邻客户到达银行的时间间隔的最大值Khjg=5顾客总数:154, 所有顾客共耗时:1181分钟, 平均每人耗时: 7分钟 从运行结果看，银行设置6个窗口比较合适！8、 自我评析与总结 该实验涉及到线性表的建