数据结构实验报告实验3：银行业务模拟系统姓名：范亚平年级：2010级学号：1008114061专业：计算机科学与技术专业（1）班数据结构实验报告一、实验目的：1）通过实验掌握对离散事件模拟的认识；2）进一步理解队列的实现与应用；3）对链表的操作有更深层次的理解；二、实验条件：学院提供公共机房，1台/学生微型计算机。
三、实验要求：1问题描述：假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。
由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。
现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
2．一个完整的系统应具有以下功能：1）初始化（OpenForDay），模拟银行开门时各数据结构的状态。
2事件驱动（EventDrived）, 对客户到达和离开事件做相应处理。
3下班处理（CloseForDay）, 模拟银行关门时的动作，统计客户平均逗留时间。
[备注]：假设银行开门的时刻（间）设为0 , 银行每天营业的时间在程序运行时输入（例如480分钟）。
每个客户办理业务的时间不超过30分钟，两个相邻客户到达银行的时间间隔不超过5分钟要求程序执行时，只要给出银行每天的营业时间即可输出客户平均逗留的时间。
四、总的设计思想：为了计算这个平均的逗留时间，自然需要知道每个客户到达银行和离开银行这两个时刻，后者减去前者即为每个客户在银行的逗留时间。
所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。
称客户到达银行和离开银行这两个时间发生的事情为“事件”，则整个模拟程序将按事件的先后顺序进行处理。
这样一种程序称做事件驱动模拟。
下面是上述银行客户的离散事件驱动的模拟算法。
void Bank_Simulation( int CloseTime ){ //OpenForDay ( ); //初始化,模拟银行开门时各数据结构的状态。
while(有要处理的事件时) //有事件可处理{EventDrived ; //事件驱动，从事件表中取出事件en；//根据en的类型（客户到达事件或客户离开事件）做相应的处理if(en表示客户到达)CustomerArrived( );// 处理客户到达事件elseCustomerDeparture( ) ;// 处理客户离开事件}//whileCloseForDay( );//计算客户的平均逗留时间}// Bank_Simulation五、数据结构与模块说明下面是模拟程序中需要的数据结构及其操作。
1．模拟算法的主要处理对象是“事件”，事件的主要信息是事件的类型和事件的发生时刻。
算法中处理的事件有两类：一类是客户到达事件；另一类是客户离开事件。
前一类事件发生的时刻随客户的到来自然形成；后一类事件发生的时刻由客户办理业务所需时间和等待时间而定。
由于程序驱动是按事件发生时刻的先后顺序进行的，所以事件表应是有序表，其主要操作是插入和删除事件，用一个单链表表示！！2．模拟程序中需要的另一数据结构是表示客户排队的队列，由于假设银行有4个窗口，因此程序中需要4个队列，队列中有关客户的信息是客户到达的时刻和客户办理业务所需要的时间。
每个队列中的队头客户即为正在窗口办理事务的客户，他办完业务离开队列的时刻就是即将发生的客户离开事件的时刻，这就是说，对每个队头客户都存在一个将要驱动的客户离开事件。
因此在任何时刻即将发生的事伯只有5种可能：1）新的客户到达；2）1号窗口的客户离开；3）2号窗口的客户离开；4）3号窗口的客户离开；5）4号窗口的客户离开；注：为了使编写的程序具有通用性，在编程序时将银行的营业时间、开的窗口数、客户办业业务的最长时间及两个客户到达的时间间隔都设置成程序运行时动态输入，这样可以对程序以及银开设的窗口的合理性进行分析，实现真正的模拟。
从以上分析可知，在模拟程序中只需要两种数据结构：有序链表和队列。
程序中用到的头文件、类型定义及主要的函数原型如下：#include"stdio.h"#include"malloc.h"#include"math.h"#include"stdlib.h"int Cks=4; // 银行办理业务的窗口数,默认值为: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 //定义事件表的结点类型{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;} QNode, *Queue;typedef struct { Queue head; Queue tail;} LinkQueue;LinkQueue q[Qu+1]; // Qu个客户队列void OpenForDay()； //模拟银行开门的动作，即初始化操作void CustomerArrived() // 处理客户到达事件void CustomerDeparture() // 处理客户离开事件六、主要算法的设计与实现void OpenForDay() //模拟银行开门的动作，即初始化操作{int i;InitList(ev); // 初始化事件链表为空en.OccurTime=0; // 设定第一个客户到达事件en.NType=0; // 客户到达事件Insert_EventList(ev, en);//插入事件q=(LinkQueue*)malloc((Qu+1)*sizeof(LinkQueue));//为队列申请Qu+1个队头指针，第0个不用for(i=1;i<Qu+1;++i) // 置空队列InitQueue(q[i]);}void CustomerArrived(){ // 处理客户到达事件QElemType f;int durtime,intertime,i;++CustomerNum;Random(durtime,intertime); // 生成随机数//printf("%d %d\n",durtime,intertime);et.OccurTime=en.OccurTime+intertime; // 下一客户到达时刻et.NType=0; // 队列中只有一个客户到达事件//printf("%d %d\n",et.NType,et.OccurTime);if(et.OccurTime<CloseTime) // 银行尚未关门，插入事件表Insert_EventList(ev,et);i=Minimum(q); // 求长度最短队列的序号,等长为最小的序号f.ArrivalTime=en.OccurTime;f.Duration=durtime;EnQueue(q[i],f);if(QueueLength(q[i])==1){et.OccurTime=en.OccurTime+durtime;et.NType=i;Insert_EventList(ev,et); // 设定第i队列的一个离开事件并插入事件表}}void CustomerDeparture(){ // 处理客户离开事件，en.NTyPe!=0int i;i=en.NType;DelQueue(q[i],customer); // 删除第i队列的排头客户TotalTime+=en.OccurTime-customer.ArrivalTime; // 累计客户逗留时间if(!QueueEmpty(q[i])){ // 设定第i队列的一个离开事件并插入事件表GetHead_q(q[i],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;i<QU+1;i++) output_q(q[i]);//getchar();Gethead(ev,en); //printf("事件%d %d\n ",en.NType,en.OccurTime);if(en.NType==0)CustomerArrived(); // 处理客户到达事件elseCustomerDeparture(); // 处理客户离开事件} // 计算并输出平均逗留时间printf("顾客总数:%d, 所有顾客共耗时:%d分钟, 平均每人耗时: %d分钟\n",CustomerNum,TotalTime,TotalTime/CustomerNum);}七、源程序见电子稿(文件名为:bank.cpp );八、运行结果请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数Cks=4请输入客户办理业务的最长时间Blsj=30请输入两个相邻客户到达银行的时间间隔的最大值Khjg=5顾客总数:154, 所有顾客共耗时:11303分钟, 平均每人耗时: 73分钟Press any key to continue请输入银行营业时间长度(单位:分)CloseTime=480请输入银行办理业务所开窗口数Cks=5请输入客户办理业务的最长时间Blsj=3048请输入两个相邻客户到达银行的时间间隔的最大值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个窗口比较合适！！九、自我评析与总结通过本次实验，提高了自已调试程序的能力。