河南师范大学计算机与信息技术学院实验报告
数 据 结 构 实验报告
学 号 姓 名 年 级 班级 填实际班级 张磊 机号： 学院机房 时 间 指导教师 一、实验题目：银行业务模拟系统的设计与实现 （该实验为综合性实验，共用6个学时） 二、实验要求：
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( );// 处理客户到达事件 else
CustomerDeparture( ) ;// 处理客户离开事件 }//while
CloseForDay( );//计算客户的平均逗留时间 }// Bank_Simulation
环境语言：Windows下的Microsoft VC++ 四、数据结构与模块说明
下面是模拟程序中需要的数据结构及其操作。
河南师范大学计算机与信息技术学院实验报告
1．模拟算法的主要处理对象是“事件”，事件的主要信息是事件的类型和事件的发生时刻。算法中处理的事件有两类：一类是客户到达事件；另一类是客户离开事件。前一类事件发生的时刻随客户的到来自然形成；后一类事件发生的时刻由客户办理业务所需时间和等待时间而定。由于程序驱动是按事件发生时刻的先后顺序进行的，所以事件表应是有序表，其主要操作是插入和删除事件，用一个单链表表示！！
2．模拟程序中需要的另一数据结构是表示客户排队的队列，由于假设银行有4个窗口，因此程序中需要4个队列，队列中有关客户的信息是客户到达的时刻和客户办理业务所需要的时间。每个队列中的队头客户即为正在窗口办理事务的客户，他办完业务离开队列的时刻就是即将发生的客户离开事件的时刻，这就是说，对每个队头客户都存在一个将要驱动的客户离开事件。因此在任何时刻即将发生的事伯只有5种可能：1）新的客户到达；2）1号窗口的客户离开；3）2号窗口的客户离开；4）3号窗口的客户离开；5）4号窗口的客户离开；
注：为了使编写的程序具有通用性，在编程序时将银行的营业时间、开的窗口数、客户办业业务的最长时间及两个客户到达的时间间隔都设置成程序运行时动态输入，这样可以对程序以及银开设的窗口的合理性进行分析，实现真正的模拟。
从以上分析可知，在模拟程序中只需要两种数据结构：有序链表和队列。 程序中用到的头文件、类型定义及主要的函数原型如下： #include\#include\#include\#include\
int Cks=4; // 银行办理业务的窗口数,默认值为:4；最大值不超过20； int Qu ; // 客户队列数Qu=Cks
int Khjg=5; // 两相邻到达客户的时间间隔最大值,默认值为:5 int Blsj=30; // 每个客户办理业务的时间最大值,默认值为:30 typedef 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 void CustomerArrived() { // 处理客户到达事件 QElemType f; int durtime,intertime,i; ++CustomerNum; Random(durtime,intertime); // 生成随机数 //printf(\ %d\\n\ et.OccurTime=en.OccurTime+intertime; // 下一客户到达时刻 et.NType=0; // 队列中只有一个客户到达事件 //printf(\ %d\\n\ if(et.OccurTime 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!=0 int 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 Gethead(ev,en); //printf(\事件%d %d\\n \ if(en.NType==0) CustomerArrived(); // 处理客户到达事件 else CustomerDeparture(); // 处理客户离开事件 } // 计算并输出平均逗留时间 printf(\顾客总数:%d, 所有顾客共耗时:%d分钟, 平均每人耗时: %d分钟\\n\ } 六、源程序 见电子稿(文件名为: .cpp ); //文件名由自己取 七、运行结果 请输入银行营业时间长度(单位:分)CloseTime=480 请输入银行办理业务所开窗口数Cks=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个窗口比较合适！！ 八、自我评析与总结 该实验做得比较成功，例如在编写调试程序时，并不是仅仅把目标局限在编译通过，执行有结果上。除了为了完成任务的模块外，另有测试事件表的函数output_ev和各窗口队列状态的函数output_q；在适当的地方调用它们，运行时可以看到事件表和窗口队列的状态，用来判断编写程序的正确性；当运行通过并符合题中要求后将这一部分代码变成注释即可。 通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应用先写出算法，再写程序，调试时一段一段调试；对于没有实现在操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样错误太难找。 九、参考文献 1．蒋盛益 等编著 《数据结构学习指导与训练》 中国水利水电出版社 2．严蔚敏 吴伟民编著 《数据结构》 （Ｃ语言版） 清华大学出版社 3．严蔚敏 等编著 《数据结构习题集》（Ｃ语言版） 清华大学出版社 十、教师评语：
实验报告银行业务模拟系统的设计与实现(1)
