数据结构大型实验报告银行模拟系统.doc
数据结构大型实验报告目录一：采用的模型和类的设计1.1模型 1.2类的设计 1.2.1 time24类1.2.2 event类 1.2.3 pqueue类1.2.4 simulation类二：整个系统的框架设计三：本离散事件描述四：实现模拟的过程框图五：完整的系统源代码六：本系统运行结果七：实验中遇到的问题及解决方法一：采用的模型和类的设计1.1模型：本系统采取事件驱动模型来设计。通过程序动态模拟银行顾客在一家有n>=2个窗口的银行的到达和离开的情况。通过计算每位顾客的平均等待时间及每一窗口处于“繁忙”状态的百分比，来计算银行的服务效率。实现中，可以顾客的到达事件，离开事件代表银行活动的对象，用事件驱动来模拟这些活动，并以概率（随机数发生器）来描述预期的客户到达率和银行职员为一个顾客服务所需的时间。在实验中，可改变参数，如银行营业时间范围，银行窗口数、客户的到达率、服务时间，顾客的最大耐性等待时间，VIP顾客的到达率等，测试银行的服务效率。银行模拟的关键部分为客户时间，包括到达，中途离开和办完业务离开事件，刚达到的顾客通过随机数产生下一个顾客的到达，已到达的顾客通过随机数产生服务时间，选择最早空闲的窗口后，可生成离开事件；所有事件都被加上时间戳，放到优先队列中，队列中优先级最高的事件就是时间戳最早的事件。其中每一到达事件均可估计出自己的等待时间，若等待时间超出一开始设定的最大耐性等待时间，则顾客选择中途离开，生成中途离开事件。到达的事件中，又分为普通顾客到达事件和VIP顾客到达事件。VIP到达时，可选择普通窗口和贵宾窗口来办理业务。但是普通顾客到达只能选择普通窗口来办理业务。1.2类的设计：1.2.1 time24类Time24类对24小时时间制的加，减，等于，小于，输入，输出进行了运算符的重载。class time24;time24 operator+ (const time24& lhs, const time24& rhs);time24 operator+ (const time24& lhs, int min);time24 operator+ (int min,const time24& rhs);time24 operator- (const time24& lhs, const time24& rhs);bool operator= (const time24& lhs, const time24& rhs);bool operator< (const time24& lhs, const time24& rhs);istream& operator>> (istream& istr, time24 &r);ostream& operator<< (ostream& ostr, const time24& r);1.2.2 event类Event类首先枚举了事件类型：到达事件，中途离开事件还是正常办完业务的离开事件。其中每个事件还包括了属性（普通事件还是贵宾事件）。具体成员变量及函数如下:#ifndef EVENT_CLASS#define EVENT_CLASS#include "time24.h"enum EventTypearrival,departure,dep2;class Eventprivate:int time;/到达时间EventType etype;/事件类型int customerID;/顾客号int tellerID;/窗口号int waitTime;/等待时间int serviceTime;/服务时间int vip;/贵宾级public:Event()int getTime()Event(int t,EventType et,int cID,int tID,int wt,int st,int v);int GetTime()const;EventType GetEventType() const;int GetCustomerID()const;int GetTellerID()const;int GetWaitTime()const;void setWaitTime(int t);int GetServiceTime()const;int GetVip()const;#endif1.2.3 pqueue类该优先级队列是以链表来实现的。由于每个事件都被插上了时间戳，所以以事件发生的先后顺序来排定优先级。时间早的事件，优先级高。同一时间，离开事件的优先级大于到达事件。template <class T>struct nodeT value;int priority;node<T> * next;template <class T>class PQueueprivate:int count;/队伍中的人数node<T> *front,*back;/首尾指针node<T> * NewNode(T & value,int & priority,node<T>* next);/插入的新的结点（事件类型的）public:PQueue();PQueue();T PQFirst();void PQInsert(T item,int priority);/插入函数void PQDelete();/删除函数void ClearPQ();/清除函数bool PQEmpty()const;/判断是否为空bool PQFull()const;/判断是否已满int PQLength()const;/判断队伍长度;1.2.4 simulation 类 具体的模拟过程实现。#ifndef SIMULATION_CLASS#define SIMULATION_CLASS#include<string>#include"Event.h"#include"PQueue.h"#include "time24.h"struct WindowStateint finishServiceTime;int totalCustomerCount;int totalCustomerWait;int totalService;int MAX_Wait;class Simulationprivate:time24 begin,end;/营业开始和结束时间int SimulationTimeLength;int TellersCount;int nextCustomerID;int arrivalLow,arrivalHigh;/最小最大到达时间间隔（分钟）int serviceLow,serviceHigh;/最小最大服务时间间隔（分钟）int MaxBearWait;/最大耐心等待时间int VipRate;/贵宾到达概率int totalCustomerAway;/中途离开的顾客数目WindowState tstat11;WindowState Vtstat;/贵宾窗口PQueue<Event> pq;int flag;int NextArrivaltime();int GetServiceTime();int NextAvailableTeller();public:Simulation();void initialization();/各窗口的数据初始化void ArrivalEvent(Event e);/到达事件void DepartureEvent(Event e);/办完业务离开事件void DepartureEvent2(Event e);/中途离开事件void RunSimulation();void PrintSimulation();二：整个系统的设计框架 首先，根据银行服务的流程设计好系统的整个模拟运作的框图。由框图，划分好程序所需的几个类，确定好相应的功能。用VC6.0实现基本功能，分调各内容，排除bug，再联调。实现了系统的基本功能后，再加上顾客的最大耐心等待时间，VIP窗口等功能，进行调试。调试的时候，原代码保留输出语句，用来检验是否符合逻辑。 本系统关键在于处理各类事件，包括了到达事件，中途离开事件，办完业务离开事件。由于系统运用事件驱动来模拟，故插入到优先级的是各事件。各事件再根据它们的时间，来排定优先级。故重新设计了一个优先级队列。三：本离散事件的描述本离散时间采用的比较简单类型的随机离散。模拟过程中，通过输入最大，最短服务时间，来确定一个顾客的的服务时间，如：serviceLow+rand()%(serviceHigh-serviceLow+1)；同样，采用输入一个顾客到达的时间间隔范围来随机取得一个顾客的到达时间，如：arrivalLow+rand()%(arrivalHigh-arrivalLow+1)。模拟过程中产生每个顾客的到达和离开事件，所有事件都加上时间戳，然后放到优先级队列中，队列中优先级最高的就是到达或离开最早的事件。由于接受服务的时间的长短不同，故先到达的顾客不一定可以先离开。根据服务窗口的当前情况，取一个时间最短的窗口分配给该顾客。接着用服务时间随机变量产生新的服务时间，由顾客的到达时间，等待时间和服务时间就可以确定该顾客的离开时间，再将顾客离开事件插入到队列。作为优先级队列的队列成员为事件对象，到达事件和离开事件均为Event类的数据成员。对每个弹出到达事件，先读入它是何时到达的，并于各窗口的finishServiceTime作比较，如果值大于顾客的到达时间，则需要等待，不然，发生无需等待这种情况。同时产生下一个顾客的到达时间。调用NextAvailableTeller（）来获得等待时间最小的窗口号，其中服务窗口的数量可由系统界面选定；再调用GetServiceTime（）来取得随机的服务时间，其中服务时间范围可由系统界面设定。修改windows的窗口信息，产生离开事件。四：实现模拟的过程框图产生顾客到达事件随机获得下一个到达事件下一到达事件是否超出营业时间结束下一个由窗口状态决定顾客的服务窗口号和等待时间服务时间随机变量采样该顾客接受服务的时间顾客离开事件到达和离开事件的优先级队列（时间戳）开始营业 入队列入队 列图1 产生顾客到达和离开事件队列逻辑顾客到达事件获取服务窗口号（等待时间最短）随机变量采样（所需服务时间）更改该窗口信息1. 完成服务时间2. 累计顾客数3. 累计等待时间4. 累计服务时间图2 服务窗口状态跟踪产生第一个事件判断事件类型计算下次到达时间到达事件该时间< 终止时间？Y为下一个顾客产生到达事件计算事件服务窗口窗口空闲？Y窗口完成时间= 事件发生时间等待时间= 窗口完成时间-事件发生时间等待时间超时或模拟时间完Y修改窗口属性数据：窗口完成时间+= 顾客服务时间窗口服务顾客总数+总顾客等待时间+= 等待时间总服务时间+= 服务时间顾客离开生成离开事件，加入队列设置窗口是否空闲获取下一个事件结束离开事件NNN失败成功图3 整个模拟流程五：完整的系统代码5.1 Event.h5.2 d_except.h5.3 time24.h5.4 pqueue.h5.5 simulation.h5.6 main.cpp六：本系统运行结果6.1 输入银行营业时间范围6.2 输入各参数6.3 具体执行结果6.4 最后执行结果七：实验中遇到的问题及解决方法试验中，遇到了不少问题，主要有如下：1、 对各种数据输入异常的处理。本实验中需要输入不少int类型的数据。故在编代码的时候，需要处理输入错误数据的处理。比如时间，一开始只考虑到输入的8点之类单个字符的数据的，所以使用char来读入，并使用isdigit()来判断，这使得我后来测试的时候，输入10：00，11：00之类的数据时，系统会出现异常。同样的错误还出现在对其他数据的处理上，如：服务时间，到达时间范围等，刚开始是都用char来读取，后来换成了string来读取，解决了这个问题。2、 对优先级队列的编写。在优先级队列的重写过程中，有一个插入的函数。刚开始编写的时候，忘了考虑到在空的队列中插入的情形。这使得我在运行程序的时候，会报错。后来通过在函数在使用输出语句的形式，来检查到达时哪一步出错了。最后，发现当优先级队列为空时，插入出错。最后，添加上空队列插入元素的情形即可。3、 运行程序时还碰到死循环的情况。通过插入输出语句发现，是事件的插入和弹出一直进行，即队列无法实现空的情况。仔细考虑模拟过程后，发现缺少了到了营业结束时间时，不插入新的到达事件的条件。最后，通过在弹出到达事件时，判断它新生成的事件的到达时间，如果超出模拟时间范围，则不插入，反之，插入。
