银行业务模拟系统的实现
程序设计与算法综合训练》设计报告3
学号:E11514064 姓名:汪泓章 年级: 大一 专 业:计科
项目名称:银行业务模拟系统的设计与实现完成日期:2016年7月1日
1.需求分析
(1)问题描述:假设某银行有四个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务,反之,若四个窗口均有客户所占,他便会排在人数最少的队伍后面。现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
(2)基本要求
1)初始化(OpenForDay ),模拟银行开门时各数据结构的状态。
2)事件驱动(EventDrived ), 对客户到达和离开事件做相应处理。
3)下班处理(CloseForDay ),模拟银行关门时的动作,统计客户平均逗留时间。
4)按照题意要求独立进行设计,设计结束后按要求写出设计报告。
①输入的形式和输入值的范围:规定银行一天的营业时间为480分钟。
②输出的形式:所有顾客业务办理的总时间;办理业务的总顾客数;平均每人办理时间
③程序所能达到的功能:通过队列的知识完成离散时间模拟,即已知窗口数和一天的营业时间可以求得平均每人办理的时间。
2.概要设计
总体设计思想:为了计算这个平均的逗留时间,自然需要知道每个客户到达银行和离开银行这两个时刻,后者减去前者即为每个客户在银行的逗留时间。所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。称客户到达银行和离开银行这两个时间发生的事情为“事件”,则整个模拟程序将按事件的先后顺序进行处理。这样一种程序称做事件驱动模拟。下面是上述银行客户的离散事件驱动的模拟算法
(1) 数据结构和程序模块:
下面是模拟程序中需要的数据结构及其操作。
a .模拟算法的主要处理对象是“事件”,事件的主要信息是事件的类型和事件的发生时刻。算法中处理的事件有两类:一类是客户到达事件;另一类是客户离开事件。前一类事件发生的时刻随客户的到来自然形成;后一类事件发生的时刻由客户办理业务所需时间和等待
时间而定。由于程序驱动是按事件发生时刻的先后顺序进行的,所以事件表应是有序表,其主要操作是插入和删除事件,用一个单链表表示。
b .模拟程序中需要的另一数据结构是表示客户排队的队列,由于假设银行有4个窗口,因此程序中需要4个队列,队列中有关客户的信息是客户到达的时刻和客户办理业务所需要的时间。每个队列中的队头客户即为正在窗口办理事务的客户,他办完业务离开队列的时刻就是即将发生的客户离开事件的时刻,这就是说,对每个队头客户都存在一个将要驱动的客户离开事件。因此在任何时刻即将发生的事伯只有5种可能:1)新的客户到达;2)1号窗口的客户离开;3)2号窗口的客户离开;4)3号窗口的客户离开;5)4号窗口的客户离开;
从以上分析可知,在模拟程序中只需要两种数据结构:有序链表和队列。 程序中用到的头文件、类型定义及主要的函数原型如下:
#include"stdio.h"
#include"malloc.h"
#include"time.h"
#include"stdlib.h"
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() // 处理客户离开事件
(2)各模块之间的调用与设计
a 主程序模块:
void main()
{
输出主界面:
选择操作:进入银行模拟系统/退出程序;
While(进入银行业务模拟窗口)
{
OpenForDay();进入初始化操作;
输出格式控制;
{银行业务模拟:
While(有要处理的时间时)
{
DeQueuel();
If(客户到达)
CustomerArrived();
Else
CustomerDeparture();
}
计算出客户的平均逗留时间并输出
}
b 函数调用关系图
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 %d\n",durtime,intertime);
et.OccurTime=en.OccurTime+intertime; // 下一客户到达时刻
et.NType=0; // 队列中只有一个客户到达事件 //printf("%d %d\n",et.NType,et.OccurTime);
if(et.OccurTime
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()
{
// 处理客户离开事件,
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 ",en.NType,en.OccurTime);
if(en.NType==0)
CustomerArrived(); // 处理客户到达事件
else
CustomerDeparture(); // 处理客户离开事件
} // 计算并输出平均逗留时间
printf("顾客总数:%d, 所有顾客共耗时:%d分钟, 平均每人耗时: %d分钟\n",CustomerNum,TotalTime,TotalTime/CustomerNum);
}
4. 测试与分析
利用随机产生的种子进行事件的模拟,即到达时间和办理业务的时间都是随机产生。如果事件尚未到达下班时间,则将其插入到空队列或者是人数(元素)最少的队列,通过检验,算出在不同的服务窗口数下的等待时间以及服务时间,基本上实现了银行事件的模拟。
5. 总结
该实验涉及到线性表的建立、插入、删除等操作,涉及到了队列的建立、插入、删除, 涉及到了离散事件的应用思想,还涉及到了排序的概念。完成这个实验对线性表、队列及C 语言编程等多方面的知识将是一个很好的利用,对离散事件也将有一个初步的认识。通过本次实验,提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。
6. 附录
源程序清单:
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedefint Status;
//-----------------银行排队模拟
//事件和事件表
typedefstructQCuEvent
{
intOccurTime;
intNType;
structQCuEvent *next;
}QCuEvent, *EventList;
//窗口前队列元素
typedefstructQCuElem
{
intArrivalTime;
int Duration;
structQCuElem *next;
}QCuElem,*QEptr;
//窗口指针
typedefstruct {
QEptr front;
QEptr rear;
}QCustomerp,*QCupp;
//主要操作函数
Status OpenForDay(EventList&ev, QCuEvent en, QCupp&q);//开门
Status CustomerArrived(EventList&ev, QCupp&q, QCuEvent en);//顾客到达 Status CustomerDeparture(EventList&ev, QCupp&q, QCuEvent en);//顾客离开 voidCloseForDay();
//基本操作函数
Status OrderInser(EventList&ev, QCuEvent en);//按时间顺序插入事件到事件表 intQLength(QCustomerpqn);//求窗口队列长度
intMinCuQueue(QCupp q);//求队最短的窗口
Status DelFirstEvent(EventList&ev);//删除事件表中的第一个事件
Status InitCuQueue(QCustomerp&qn);//初始化窗口队列
Status EnCuQueue(QCustomerp&qn,QEptr Q);//进入队列
Status DeCuQueue(QCustomerp&qn,QCuElem&Q);//删除队列中的元素 Status GetQHead(QCustomerpqn,QCuElem&Q);//获得队列中的第一个元素 Status DestoryQueue(QCustomerpqn);//销毁队列
void Ptint_QStatus(QCustomerpQCu[]);//打印队列长度
voidBank_SimulationFunc();
void test(char str[]);
#include
#include
#include
inti=0,e=0,counter=0;
intTotalTime=0,CustomerNum=0; //累计客户逗留时间, 客户数
intCloseTime; //关门时间
intwindowsnum = 0;
//主函数
void main() {
EventListev; // 事件表
QCuEvent en;
QCuppQCu = NULL;
OpenForDay(ev, en, QCu);
while (ev->next)
{
en.NType = ev->next->NType; en.OccurTime = ev->next->OccurTime;
} DelFirstEvent(ev); if (en.NType == 0) else CustomerDeparture(ev, QCu, en); CustomerArrived(ev, QCu, en); Ptint_QStatus(QCu);
CloseForDay();
}
//主要功能子函数
Status OpenForDay(EventList&ev, QCuEvent en, QCupp&q) {
int temp = 0;
printf("请输入随机数种子(或输入0使用随机种子):"); scanf("%d",&temp);
if (temp==0) srand((unsigned)time(NULL));
elsesrand(temp);
printf("请输入营业时间(单位:分钟):");
scanf("%d",&temp);
CloseTime = temp;
TotalTime = 0;
CustomerNum = 0;
en.OccurTime = 0;
en.NType = 0;
en.next = NULL;
ev = (EventList) malloc(sizeof(QCuEvent));
ev->next = NULL;
OrderInser(ev, en);
printf("请输入办理业务的窗口数(至少1个):");
scanf("%d",&windowsnum);
q = (QCustomerp *) malloc((windowsnum+1)*sizeof(QCustomerp)); for (inti=1;i
{
}
return OK;
}
Status CustomerArrived(EventList&ev, QCupp&q, QCuEvent en) {
test("顾客到达处理
CustomerNum ++;
// 产生随机数
//srand(54);
intdurtime = rand()%30+1;
intintertime = rand()%5+1;
// 插入到达事件表
QCuEventenTemp;
int t = en.OccurTime + intertime;
enTemp.OccurTime = t;
enTemp.NType = 0;
enTemp.next = NULL;
if (t
printf("时间%d\n",t);
// 插入最短队
QEptr Q;
Q = (QEptr) malloc(sizeof(QCuElem));
Q->ArrivalTime = en.OccurTime;
Q->Duration = durtime;
Q->next = NULL;
inti = MinCuQueue(q);
EnCuQueue(q[i],Q);
// 插入离开事件
enTemp.OccurTime = en.OccurTime + durtime; InitCuQueue(q[i]);
enTemp.NType = i;
enTemp.next = NULL;
if(QLength(q[i]) == 1) OrderInser(ev, enTemp);
return OK;
}
Status CustomerDeparture(EventList&ev, QCupp&q, QCuEvent en) {
test(">>>>>>>>顾客离开处理");
inti = en.NType;
printf("离开时间%d\n",en.OccurTime);
if(en.OccurTime>CloseTime)
{
}
else{
}
return OK;
}
voidCloseForDay() QCuElem customer; DeCuQueue(q[i],customer); // 客户逗留时间 TotalTime += en.OccurTime - customer.ArrivalTime; printf("总时间为%d\n",TotalTime); if (q[i].front->next) { } GetQHead(q[i],customer); QCuEventenTemp; enTemp.OccurTime = en.OccurTime + customer.Duration; enTemp.NType = i; OrderInser(ev, enTemp); DestoryQueue(q[i]);
{
printf("***************************************\n");
printf("*\n");
printf("* 所有顾客业务办理总时间:%d分钟\n", TotalTime);
printf("* 业务办理顾客数:%d\n", CustomerNum);
printf("* 平均每人办理时间:%f\n",(float)TotalTime/(float)CustomerNum); printf("*\n");
printf("***************************************\n");
}
//功能实现子函数
Status OrderInser(EventList&ev, QCuEvent en)
{
EventListentemp,qtemp;
entemp = (EventList) malloc(sizeof(QCuEvent));
entemp->OccurTime = en.OccurTime;
entemp->NType = en.NType;
entemp->next = NULL;
if (!ev->next)
{
}
qtemp = ev;
while(qtemp->next&&qtemp->next->OccurTime
}
entemp->next = qtemp->next;
qtemp->next = entemp;
return OK;
}
intQLength(QCustomerpqn) qtemp = qtemp->next; ev->next = entemp; return OK;
{
QEptrqtemp;
inti=0;
qtemp = qn.front->next;
while(qtemp)
{
}
returni;
}
intMinCuQueue(QCupp q)
{
inti,min;
for (i=1,min=1;i
{
}
return min;
}
Status DelFirstEvent(EventList&ev)
{
EventList p;
p = ev->next;
ev->next = p->next;
free(p);
return OK;
}
Status InitCuQueue(QCustomerp&qn)
{
qn.front = (QEptr) malloc(sizeof(QCuElem)); min = QLength(q[min])next; i++;
qn.rear = qn.front;
return OK;
}
Status EnCuQueue(QCustomerp&qn,QEptr Q) {
qn.rear->next = Q;
qn.rear = Q;
return OK;
}
Status DeCuQueue(QCustomerp&qn,QCuElem&Q) {
QEptrqtemp;
qtemp = qn.front->next;
Q.ArrivalTime = qtemp->ArrivalTime;
Q.Duration = qtemp->Duration;
qn.front->next = qtemp->next;
if(qn.rear == qtemp) qn.rear = qn.front;
free(qtemp);
return OK;
}
Status GetQHead(QCustomerpqn,QCuElem&Q) {
Q.ArrivalTime = qn.front->next->ArrivalTime; Q.Duration = qn.front->next->Duration; return OK;
}
Status DestoryQueue(QCustomerpqn)
{
QEptr p;
{
}
qn.front->next =NULL;
qn.rear = qn.front;
return OK;
}
voidPtint_QStatus(QCustomerpQCu[]) {
int l;
for(inti=1;i
}
}
void test(char str[])
{
printf("--%s--\n",str);
}
l = QLength(QCu[i]); printf("队列%d:长%d:",i,l); for (int n=1;nnext; qn.front->next = p->next; free(p);