银行模拟系统的设计与实现计算机与信息技术学院综合性、设计性实验报告专业：计算机科学与技术年级/班级：计科二班2011—2012学年第一学期课程名称数据结构指导教师王岁花本组成员学号姓名成员姓名：彭涛学号：1008114150实验地点215机房实验时间7,8,9周下午5-6节项目名称银行模拟系统的设计与实现实验类型综合性/设计性一、实验目的1）通过实验掌握对离散事件模拟的认识；2）进一步理解队列的实现与应用；3）对链表的操作有更深层次的理解；该实验涉及到线性表的建立、插入、删除等操作，涉及到了队列的建立、插入、删除，涉及到了离散事件的应用思想，还涉及到了排序的概念。
完成这个实验对线性表、队列及C语言编程等多方面的知识将是一个很好的利用，对离散事件也将有一个初步的认识。
二、实验仪器或设备装有Visual C++ 6.0的计算机一台三、总体设计（设计原理、设计方案及流程等）实验问题描述：假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。
由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。
现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
设计原理：根据前几章所学习的与链表、队列等相关的知识，了解到链表与队列的特点，联系实际，对题目思考可知：①动态链表可以进行动态分配与存储，还可以在链表中适合的位置进行删除和插入操作；②多个相同类型的数据类型可将其放在一个数组中；③结构体类型的数据可以有多个域，存放不同的数据信息；④队列是一种先进后出的线性表，只允许在表的一端进行插入而在另一端进行删除，和日常生活中的排队是一样的；⑤在一天的营业过程中，银行的工作流程，包含开门事件、客户到达对客户业务进行办理、关门时间到的时候关门事件；而对顾客来说，办理业务需要排队等候（如果银行里办理业务的人比较多的话）、办理业务、办理完之后离开；⑥时间是贯穿所有动作发生的线索，动作只有两种：到达和离开；由此想到可以建立一个以时间先后顺序来连接动作的事件链表，将各个事件发生的时间及类型（到达或离开）作为链表结点中的数据内容。
设计方案：①对银行的业务办理流程进行深入了解，思考程序的基本框架；②根据生活实际，先将主函数编写出来，主函数中应包含银行开门事件，顾客到达事件和离开事件；③编写出各个事件的算法；④用初始化的事件链表将各个事件联系起来；⑤对编号的算法进行程序化；⑥然后上机对程序进行编译、调试，直到程序可以正确运行。
设计流程仔细分析课题，得出解决该课题的基本思路：1：链表是解决该事件的关键，从对链表的建立到链表中元素的删除并分析，就完成了问题的解决。
银行开门后，对各项数据进行初始化，向链表中插入第一个数据元素，接着进行对客户到达事件和离开事件的处理（客户到达时，客户计数器增加，窗口队列插入，相应数据插入事件链表；客户离开时，计时计数器增加，窗口队列的删除，相应的数据插入事件链表）。
其中，客户的离开与到达的处理先后顺序是有链表中的元素决定，即先删除链表的第一个元素，然后分析属于到达事件则执行到达事件相应操作，若为离开事件则执行离开事件相应操作2：对编写该程序所需的队列数组和事件链表（链表中的元素应以时间的先后顺序链接）的基本结构进行定义，设计出基本的程序框架，使程序在自己的脑子中有一个清晰的轮廓3：编写出主函数，是银行的各种操作（开门事件、办理业务事件）及客户的各种操作（到达事件和离开事件）都能在主函数中得以体现；需要注意的是主函数中还应包含程序中所需的相关数据的输入操作4：将主函数中的各个子函数的算法进行程序化，然后再对函数进行细节方面的处理（程序的声明等）。
对完成的程序进行调试，若出现错误则进行修改，若无错则输入多组数据进行执行，验证程序的完整性与健壮四、实验步骤（包括主要步骤、代码分析等）主要步骤：（1）打开Visual C++ 6.0，新建一个C++ Source File，文件名为“银行模拟系统”，保存在G：\数据结构\数据结构实验文件夹中。
（2）输入该程序所需的代码。
（3）编译、链接，出现错误。
（4）对错误进行修改，再次编译、链接，无错误后，执行，得出，如下图所示的执行结果：代码分析：1：首先分析主函数前面的程序，头文件的声明，各种变量的定义；#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个客户队列EventList ev; // 事件表Event en; // 事件Event et; // 临时变量QElemType customer; // 客户记录int TotalTime=0,CustomerNum=0; // 累计客户逗留时间,客户数(初值为0)int CloseTime; // 银行营业时间(单位是分)2：再分析主函数，主函数中包含了程序所需的数据的输入，接着是随机种子的接受（为了后面的程序中随机数的产生），紧接着是开门事件函数，然后是对事件链表中的元素进行删除，然后对所删除结点中的数据进行分析，若该结点的信息属于客户到达事件则处理到达事件，反之则处理离开事件；最后是函数结果的输出；void main(){printf("请输入银行营业时间长度(单位:分)CloseTime=");scanf("%d",&CloseTime);printf("请输入银行办理业务所开窗口数Cks=");scanf("%d",&Cks);printf("请输入客户办理业务的最长时间Blsj=");scanf("%d",&Blsj);printf("请输入两个相邻客户到达银行的时间间隔的最大值Khjg="); scanf("%d",&Khjg);Qu=Cks; //给Qu赋值为窗口数CksBank_Simulation(); //模拟银行业务}3：接下来，是程序中的子函数：cmp比较函数，将事件（到达或离开）的发生时间进行比较，不同结果返回不同的返回值，用于对链表中事件的插入；int cmp(Event a, Event b){// 依事件a的发生时刻<、=或>事件b的发生时刻分别返回-1、0或1if(a.OccurTime==b.OccurTime)return 0;elsereturn(a.OccurTime-b.OccurTime)/abs(a.OccurTime-b.OccurTime);}4：OpenForDay银行开门事件的函数，设置计数器与计时器，初始化时间表与队列数组，将第一个客户的相关信息结点插入链表中；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]);}5：CustomerArrived客户到达事件函数，客户数加一，产生随机数（办理业务时间，下一个客户到达时间），由随机数可得到下一个客户的到达事件，插入时间表（到达时间小于关门时间），并将该结点插入最小队列中，若该队列中只有一个客户（即办理业务不需要等候），将该客户的离开事件也插入链表中；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队列的一个离开事件并插入事件表}}6：CustomerDeparture客户离开事件函数，将该客户所在队列的第一个元素（该客户）删掉，计时器增加，然后分析该队列，若队列不为空，则下一个客户要开始业务办理，由由下一个客户的元素信息可得出该客户的离去事件，将该事件插入事件链表中；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);}}7:接下来的一些函数是一些比较简单的子函数，如判断一个队列、链表是否为空，求队列的长度，求长度最小的队列，链表、队列的初始化等，在此不做详细分析；8:最后再分析一下OrderInsert事件链表的插入函数，先将一个指针指向链表头结点，接着将你所要插入事件的发生时间和链表中的事件的时间依次比较，直至找到合适位置。