C++數據結構學習：事件驅動模擬

　　我看的兩本教科書（《數據結構（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驅動大全  數據結構專題，或