C++数据结构学习:事件驱动模拟

2016-02-19 20:22 7 1 收藏

今天天气好晴朗处处好风光，好天气好开始，图老师又来和大家分享啦。下面给大家推荐C++数据结构学习:事件驱动模拟，希望大家看完后也有个好心情，快快行动吧！

【 tulaoshi.com - 编程语言】

我看的两本教科书（《数据结构（C语言版）》还有这本黄皮书）都是以这个讲解队列应用的，而且都是银行营业模拟（太没新意了）。细比较，这两本书模拟的银行营业的方式还是不同的。 !-- frame contents -- !-- /frame contents -- 1997版的《数据结构（C语言版）》的银行还是老式的营业模式（究竟是1997年的事了），现在的很多地方还是这种营业模式——几个窗口同时排队。
　　
　　　　这种方式其实不太合理，经常会出现先来的还没有后来的先办理业务（经常前面一个人磨磨蹭蹭，别的队越来越短，让你恨不得把前面那人干掉）。1999版的这本黄皮书的银行改成了一种挂牌的营业方式，每个来到的顾客发一个号码，假如哪个柜台空闲了，就叫号码最靠前的顾客来办理业务；假如同时几个柜台空闲，就按照一种法则来决定这几个柜台叫号的顺序（最简单的是按柜台号码顺序）。这样，就能保证顾客按照先来后到的顺序接受服务——因为大家排在一个队里。这样的营业模式我在北京的西直门工商银行见过，应该说这是比较合理的一种营业模式。不过，在本文中最重要的是，这样的营业模式比较好模拟（一个队列总比N个队列好操作）。
　　
　　　　原书的这部分太难看了，我看的晕晕的，我也不知道按照原书的方法能不能做出来，因为我没看懂（旁白：靠，你小子这样还来现眼）。我按照实际情况模拟，实现如下：
　　
　　　　#ifndefSimulation_H
　　
　　　　#defineSimulation_H
　　
　　　　#include
　　
　　　　#include
　　
　　　　#include
　　
　　　　classTeller
　　
　　　　{
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　　public:
　　
　　　　inttotalCustomerCount;
　　
　　　　inttotalServiceTime;
　　
　　　　intfinishServiceTime;
　　
　　　　Teller():totalCustomerCount(0),totalServiceTime(0),
　　
　　　　finishServiceTime(0){}
　　
　　　　};
　　
　　 !-- frame contents -- !-- /frame contents -- 　　//#definePRINTPROCESS
　　
　　　　classSimulation
　　
　　　　{
　　
　　　　public:
　　
　　　　Simulation()
　　
　　　　{
　　
　　　　cout<　　
　　　　cout<<"柜台数量：";cin>>tellerNum;
　　
　　　　cout<<"营业时间：";cin>>simuTime;
　　
　　　　cout<<"两个顾客来到的最小间隔时间：";cin>>arrivalLow;
　　
　　　　cout<<"两个顾客来到的最大间隔时间：";cin>>arrivalHigh;
　　　　
　　　　cout<<"柜台服务最短时间：";cin>>serviceLow;
　　
　　　　cout<<"柜台服务最长时间：";cin>>serviceHigh;
　　
　　　　arrivalRange=arrivalHigh-arrivalLow+1;
　　
　　　　serviceRange=serviceHigh-serviceLow+1;
　　
　　　　srand((unsigned)time(NULL));
　　　　
　　　　}　
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　　Simulation(inttellerNum,intsimuTime,intarrivalLow,intarrivalHigh,intserviceLow,intserviceHigh)
　　
　　
　　　　:tellerNum(tellerNum),simuTime(simuTime),arrivalLow(arrivalLow),arrivalHigh(arrivalHigh),
　　
　　 !-- frame contents -- !-- /frame contents -- 　　serviceLow(serviceLow),serviceHigh(serviceHigh),
　　
　　　　arrivalRange(arrivalHigh-arrivalLow+1),serviceRange(serviceHigh-serviceLow+1)
　　
　　　　{srand((unsigned)time(NULL));}
　　
　　　　voidInitialize()
　　
　　　　{
　　　　
　　　　curTime=nextTime=0;
　　　　
　　　　customerNum=customerTime=0;
　　
　　　　for(inti=1;i<=tellerNum;i++)
　　
　　　　{
　　
　　　　tellers[i].totalCustomerCount=0;
　　　　
　　　　tellers[i].totalServiceTime=0;
　　
　　　　tellers[i].finishServiceTime=0;
　　
　　　　}
　　
　　　　customer.MakeEmpty();
　　
　　　　}
　　
　　　　voidRun()
　　
　　　　{
　　
　　　　Initialize();
　　
　　　　NextArrived();
　　
　　　　#ifdefPRINTPROCESS
　　
　　　　cout<　　
　　　　cout<<"tellerID";
　　
　　　　for(intk=1;k<=tellerNum;k++)cout<<"TELLER"<　　
　　　　cout<　　
　　　　#endif
　　
　　　　for(curTime=0;curTime<=simuTime;curTime++)
　　　　
　　　　{
　　　　
　　　　if(curTime>=nextTime)
　　　　
　　　　{
　　　　
　　　　CustomerArrived();
　　　　
　　　　NextArrived();
　　
　　　　}
　　
　　　　#ifdefPRINTPROCESS
　　
　　　　cout<<"Time:"<　　
　　　　#endif
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　　for(inti=1;i<=tellerNum;i++)
　　
　　　　{
　　
　　　　if(tellers[i].finishServiceTime　　
　　　　if(tellers[i].finishServiceTime==curTime&&!customer.IsEmpty())
　　
　　　　{
　　
　　 !-- frame contents -- !-- /frame contents -- 　　intt=NextService();
　　
　　　　#ifdefPRINTPROCESS
　　　　
　　　　cout<<''<　　
　　　　#endif
　　
　　　　CustomerDeparture();
　　
　　　　tellers[i].totalCustomerCount++;
　　
　　　　tellers[i].totalServiceTime+=t;
　　
　　　　tellers[i].finishServiceTime+=t;
　　　　
　　　　}
　　
　　　　#ifdefPRINTPROCESS
　　
　　　　elsecout<<"";
　　　　
　　　　#endif
　　　　
　　　　}
　　
　　　　#ifdefPRINTPROCESS
　　
　　　　cout<　　
　　　　#endif
　　
　　　　}
　　
　　　　PrintResult();
　　
　　　　}
　　　　voidPtintSimuPara()
　　
　　　　{
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　　cout<　　
　　
　　　　cout<<"柜台数量："<　　
　　　　cout<<"两个顾客来到的最小间隔时间："<
　　　　cout<<"两个顾客来到的最大间隔时间："<
　　 !-- frame contents -- !-- /frame contents -- 　　cout<<"柜台服务最短时间："<　　
　　　　cout<<"柜台服务最长时间："<　　
　　　　}
　　
　　　　voidPrintResult()
　　
　　　　{
　　
　　　　inttSN=0;
　　
　　　　longtST=0;
　　
　　　　cout<　　　　
　　　　cout<<"－－－－模拟结果－－－－－－";
　　
　　　　cout<　　
　　　　for(inti=1;i<=tellerNum;i++)
　　
　　　　{
　　
　　　　cout<<"TELLER"<　　
　　　　cout<<''<　　
　　　　cout<<''<　　
　　　　cout<<'';
　　
　　　　if(tellers[i].totalCustomerCount)
　　
　　　　cout<<(float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
　　
　　　　elsecout<<0;
　　
　　　　cout<<""<　　　　
　　　　}
　　
　　　　cout<<"TOTAL"<　　
　　　　if(tSN)cout<<(float)tST/(float)tSN;elsecout<<0;
　　
　　　　cout<<""<　　
　　　　cout<<"CustomerNumber:"<　　
　　　　cout<<"CustomerWaitTime:"<　　
　　　　if(tSN)cout<<(float)customerTime/(float)tSN;elsecout<<0;
　　　　
　　　　cout<　　　　
　　　　}
　　　　　
　　　　private:
　　　　
　　　　inttellerNum;
　　
　　　　intsimuTime;
　　　　
　　　　intcurTime,nextTime;
　　
　　　　intcustomerNum;
　　
　　　　longcustomerTime;
　　
　　　　intarrivalLow,arrivalHigh,arrivalRange;
　　
　　　　intserviceLow,serviceHigh,serviceRange;
　　
　　　　Tellertellers[21];
　　
　　　　Queuecustomer;
　　
　　　　voidNextArrived()
　　　　
　　　　{
　　
　　　　nextTime+=arrivalLow+rand()%arrivalRange;
　　
　　　　}
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　　intNextService()
　　　　
　　　　{
　　　　
　　　　returnserviceLow+rand()%serviceRange;
　　
　　　　}
　　
　　　　voidCustomerArrived()
　　　　
　　　　{
　　
　　　　customerNum++;
　　
　　　　customer.EnQueue(nextTime);
　　　　
　　　　}
　　 !-- frame contents -- !-- /frame contents -- 　
　　　　voidCustomerDeparture()
　　
　　　　{
　　
　　
　　　　customerTime+=(long)curTime-(long)customer.DeQueue();
　　　　
　　　　}
　　　　
　　　　};
　　　　
　　　　
　　　　
　　　　#endif
　　　　
　　　　几点说明
　　　　lRun()的过程是这样的：curTime是时钟，从开始营业计时，自然流逝到停止营业。当顾客到的事件发生时（顾客到时间等于当前时间，小于判定是因为个别时候顾客同时到达——输入arrivalLow＝0的情况，而在同一时间，只给一个顾客发号码），给这个顾客发号码（用顾客到时间标示这个顾客，入队，来到顾客数增1）。当柜台服务完毕时（柜台服务完时间等于当前时间），该柜台服务人数增1，服务时间累加，顾客离开事件发生，下一个顾客到该柜台。因为柜台开始都是空闲的，所以实际代码和这个有点出入。最后，停止营业的时候，停止发号码，还在接受服务的顾客继续到服务完，其他还在排队的就散伙了。
　　　　
　　　　l模拟结果分别是：各个柜台的服务人数、服务时间、平均服务时间，总的服务人数、服务时间、平均服务时间，来的顾客总数、没被服务的数目（来的太晚了）、接受服务顾客总等待时间、平均等待时间。
　　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或　
　　　　l这个算法效率是比较低的，实际上可以不用队列完成这个模拟（用顾客到时间推动当前时钟，柜台直接公告服务完成时间），但这样就和实际情况有很大差别了——出纳员没等看见人就知道什么时候完？虽然结果是一样的，但是理解起来很莫名其妙，尤其是作为教学目的讲解的时候。 !-- frame contents -- !-- /frame contents -- 当然了，实际中为了提高模拟效率，本文的这个算法是不值得提倡的。
　　　　
　　l注释掉的#definePRINTPROCESS，去掉注释符后，在运行模拟的时候，能打印出每个时刻柜台的服务情况（第几个顾客，顾客到达时间，接受服务时间），但只限4个柜台以下，多了的话屏幕就满了（格式就乱了）。
　　　　
　　　　本来我没打算写这篇，后来，当我开始实现模拟的时候，竟欲罢不能了。这是数据结构这本书中第一个实际应用的例子，而且也有现实意义。你可以看出各个柜台在不同的业务密度下的工作强度（要么给哪个柜台出纳员发奖金，要么轮换柜台），各种情况下顾客的等待时间（人都是轮到自己就不着急了），还有各种情况下设立几个柜台合理（很少的空闲时间，很短的等待时间，几乎为零的未服务人数）。例如这样：
　　　　
　　　　for(inti=1;i<16;i++)
　　　　
　　　　{
　　
　　　　Simulationa(i,240,1,4,8,15);
　　　　
　　　　a.Run();
　　　　
　　　　}
　　
　　　　你模拟一下就会得出，在不太繁忙的银行，4～5个柜台是合适的——现在的银行大部分都是这样的。
　　　　
　　　　
　　

更多内容请看C/C++技术专题 Linux驱动大全数据结构专题，或

来源:http://www.tulaoshi.com/n/20160219/1623499.html

上一篇：用css改变鼠标显示
下一篇： css(div+span)padding的使用

看过《C++数据结构学习:事件驱动模拟》的人还看了以下文章更多>>

C++数据结构学习:二叉树(4)

标签：编程语言网络编程

才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而假如再讲B＋、B－，就不能不提到搜索，假如是胜者树就不能不提到排序。为此，把这部分放到后面。 !-- frame contents -- !-- /frame contents -- 我前面所做的努力，只是让你有个基本概念，什么...

C++数据结构学习:二叉树(2)

标签：编程语言网络编程

线索化二叉树这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。 !-- frame contents -- !-- /frame contents -- 我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不...

C++数据结构学习:二叉树(3)

标签：编程语言网络编程

递归遍历与非递归遍历前面写过一些关于递归的文章，因为那时还没有写到树，因此也举不出更有说服力的例子，只是阐述了“递归是一种思想”，正像网友评价的，“一篇入门的文章”。但只要能能让你建立“递归是一种思想”这个观念，我的努力就没有白费。 !-- frame contents -- !-- /frame contents -- 现在，讲完了二叉...

C++数据结构学习:二叉树(1)

标签：编程语言网络编程

这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。 !-- frame contents -- !-- /frame contents -- 正像我在前...

C++数据结构学习:在链表中链入对象

标签：编程语言网络编程

似乎你也注重到了，不管怎么定义，似乎一个链表中的对象都是同一类型的。而实际上，这也是必须的，否则，返回节点中的数据这样的函数的返回值的类型是什么呢？但是，人的要求是无止境的……（省略本人感慨若干百字）。 !-- frame contents -- !-- /frame contents -- 把不同的对象链在一个链表中的目的是为了方便使用，现在一定记住...

查看更多精彩>>