分享
 
 
 

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

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

我看的两本教科书(《数据结构(C语言版)》还有这本黄皮书)都是以这个讲解队列应用的,而且都是银行营业模拟(太没新意了)。细比较,这两本书模拟的银行营业的方式还是不同的。

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){}

};

//#definePRINTPROCESS

classSimulation

{

public:

Simulation()

{

cout

couttellerNum;

coutsimuTime;

coutarrivalLow;

coutarrivalHigh;

coutserviceLow;

coutserviceHigh;

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),

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

{

tellers[i].totalCustomerCount=0;

tellers[i].totalServiceTime=0;

tellers[i].finishServiceTime=0;

}

customer.MakeEmpty();

}

voidRun()

{

Initialize();

NextArrived();

#ifdefPRINTPROCESS

cout

cout

for(intk=1;k

cout

#endif

for(curTime=0;curTime

{

if(curTime=nextTime)

{

CustomerArrived();

NextArrived();

}

#ifdefPRINTPROCESS

cout

#endif

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

for(inti=1;i

{

if(tellers[i].finishServiceTime

if(tellers[i].finishServiceTime==curTime&&!customer.IsEmpty())

{

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

cout

cout

}

voidPrintResult()

{

inttSN=0;

longtST=0;

cout

cout

cout

for(inti=1;i

{

cout

cout

cout

cout

if(tellers[i].totalCustomerCount)

cout

elsecout

cout

}

cout

if(tSN)cout

cout

cout

cout

if(tSN)cout

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);

}

voidCustomerDeparture()

{

customerTime+=(long)curTime-(long)customer.DeQueue();

}

};

#endif

几点说明

lRun()的过程是这样的:curTime是时钟,从开始营业计时,自然流逝到停止营业。当顾客到的事件发生时(顾客到时间等于当前时间,小于判定是因为个别时候顾客同时到达——输入arrivalLow=0的情况,而在同一时间,只给一个顾客发号码),给这个顾客发号码(用顾客到时间标示这个顾客,入队,来到顾客数增1)。当柜台服务完毕时(柜台服务完时间等于当前时间),该柜台服务人数增1,服务时间累加,顾客离开事件发生,下一个顾客到该柜台。因为柜台开始都是空闲的,所以实际代码和这个有点出入。最后,停止营业的时候,停止发号码,还在接受服务的顾客继续到服务完,其他还在排队的就散伙了。

l模拟结果分别是:各个柜台的服务人数、服务时间、平均服务时间,总的服务人数、服务时间、平均服务时间,来的顾客总数、没被服务的数目(来的太晚了)、接受服务顾客总等待时间、平均等待时间。

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

l这个算法效率是比较低的,实际上可以不用队列完成这个模拟(用顾客到时间推动当前时钟,柜台直接公告服务完成时间),但这样就和实际情况有很大差别了——出纳员没等看见人就知道什么时候完?虽然结果是一样的,但是理解起来很莫名其妙,尤其是作为教学目的讲解的时候。

当然了,实际中为了提高模拟效率,本文的这个算法是不值得提倡的。

l注释掉的#definePRINTPROCESS,去掉注释符后,在运行模拟的时候,能打印出每个时刻柜台的服务情况(第几个顾客,顾客到达时间,接受服务时间),但只限4个柜台以下,多了的话屏幕就满了(格式就乱了)。

【后记】本来我没打算写这篇,后来,当我开始实现模拟的时候,竟欲罢不能了。这是数据结构这本书中第一个实际应用的例子,而且也有现实意义。你可以看出各个柜台在不同的业务密度下的工作强度(要么给哪个柜台出纳员发奖金,要么轮换柜台),各种情况下顾客的等待时间(人都是轮到自己就不着急了),还有各种情况下设立几个柜台合理(很少的空闲时间,很短的等待时间,几乎为零的未服务人数)。例如这样:

for(inti=1;i

{

Simulationa(i,240,1,4,8,15);

a.Run();

}

你模拟一下就会得出,在不太繁忙的银行,4~5个柜台是合适的——现在的银行大部分都是这样的。

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有