数据结构：思想与方法-翁惠玉-27783第四章幻灯片.ppt

* 银行排队系统的模拟系统 设计一个最简单的排队系统模拟器，即只有一个服务台的排队系统，希望通过这个模拟器得到顾客的平均排队时间。 银行中只有一个服务台，顾客到达的时间间隔服从[arrivaLow, arrivalHigh]的均匀分布，服务时间长度服从[serviceTimeLow, serviceTimeHigh]间的均匀分布，一共模拟customNum个顾客。要求统计顾客的平均排队时间。 * 单服务台的排队系统的实现 只要使用一个队列 整个模拟由三个步骤组成： 首先生成所有的顾客到达事件，按到达时间排成一个队列； 服务员一旦有空，就为队头元素服务，在提供服务前先检查该顾客等待了多少时间，记入累计值； 最后，在所有顾客都服务完以后，返回累计值除以顾客数的结果。 * totalWaitTime = 0; 设置顾客开始到达的时间currentTime = 0; for (i=0; icustomNum; ++i) { 生成下一顾客到达的间隔时间； 下一顾客的到达时间currentTime += 下一顾客到达的间隔时间； 将下一顾客的到达时间入队； } 从时刻0开始模拟; while （顾客队列非空） { 取队头顾客； If （到达时间 当前时间） 直接将时钟拨到事件发生的时间； Else 收集该顾客的等待时间； 生成服务时间； 将时钟拨到服务完成的时刻；} 返回 等待时间/顾客数； * 模拟类的定义 设计一个实现单服务台排队系统的工具。 数据成员：到达时间间隔的分布，服务时间的分布，以及想要模拟多少个顾客。 功能：获得本次服务中顾客的平均等待时间是多少。这个类应该有两个公有函数：构造函数接受用户输入的参数，另外一个就是执行模拟并最终给出平均等待时间的函数avgWaitTime。 * class simulator{ int arrivalLow; int arrivalHigh; int serviceTimeLow; int serviceTimeHigh; int customNum; public: simulator(); int avgWaitTime() const; }; * 构造函数 simulator::simulator() { cout 请输入到达时间间隔的上下界：; cin arrivalLow arrivalHigh; cout 请输入服务时间的上下界：; cin serviceTimeLow serviceTimeHigh; cout 请输入模拟的顾客数：; cin customNum; srand(time(NULL)); } * avgWaitTime int simulator::avgWaitTime() const { int currentTime = 0; //当前时间 int totalWaitTime = 0; //总的等待时间 int eventTime; linkQueueint customerQueue; int i; for (i=0; icustomNum; ++i) { currentTime += arrivalLow + (arrivalHigh -arrivalLow +1) * rand() / (RAND_MAX + 1); customerQueue.enQueue(currentTime); } * currentTime = 0; while (!customerQueue.isEmpty()) { eventTime = customerQueue.deQueue(); if (eventTime currentTime) totalWaitTime += currentTime - eventTime; else currentTime = eventTime; currentTime += serviceTimeLow + (serviceTimeHigh -serviceTimeLow +1) * rand() / (RAND_MAX + 1); } return totalWaitTime / customNum; } * simulator类的应用