實(shí)驗(yàn)報(bào)告銀行業(yè)務(wù)模擬系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).doc

數(shù) 據(jù) 結(jié) 構(gòu) 實(shí)驗(yàn)報(bào)告學(xué) 號(hào)姓 名年 級(jí)班級(jí)填實(shí)際班級(jí)機(jī)號(hào)：學(xué)院機(jī)房時(shí) 間指導(dǎo)教師張磊一、實(shí)驗(yàn)題目：銀行業(yè)務(wù)模擬系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) （該實(shí)驗(yàn)為綜合性實(shí)驗(yàn)，共用6個(gè)學(xué)時(shí)）二、實(shí)驗(yàn)要求：1 問(wèn)題描述：假設(shè)某銀行有四個(gè)窗口對(duì)外接待客戶，從早晨銀行開(kāi)門起不斷有客戶進(jìn)入銀行。由于每個(gè)窗口在某個(gè)時(shí)刻只能接待一個(gè)客戶，因此在客戶人數(shù)眾多時(shí)需在每個(gè)窗口前順次排隊(duì)，對(duì)于剛進(jìn)入銀行的客戶，如果某個(gè)窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)，反之，若四個(gè)窗口均有客戶所占，他便會(huì)排在人數(shù)最少的隊(duì)伍后面?，F(xiàn)在需要編制程序以模擬銀行的這種業(yè)務(wù)活動(dòng)并計(jì)算一天中客戶在銀行逗留的平均時(shí)間。2一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：1）初始化（OpenForDay），模擬銀行開(kāi)門時(shí)各數(shù)據(jù)結(jié)構(gòu)的狀態(tài)。2） 事件驅(qū)動(dòng)（EventDrived）, 對(duì)客戶到達(dá)和離開(kāi)事件做相應(yīng)處理。3） 下班處理（CloseForDay）, 模擬銀行關(guān)門時(shí)的動(dòng)作，統(tǒng)計(jì)客戶平均逗留時(shí)間 。備注：假設(shè)銀行開(kāi)門的時(shí)刻（間）設(shè)為0 , 銀行每天營(yíng)業(yè)的時(shí)間在程序運(yùn)行時(shí)輸入（例如480分鐘）。每個(gè)客戶辦理業(yè)務(wù)的時(shí)間不超過(guò)30分鐘，兩個(gè)相鄰客戶到達(dá)銀行的時(shí)間間隔不超過(guò)5分鐘要求程序執(zhí)行時(shí)，只要給出銀行每天的營(yíng)業(yè)時(shí)間即可輸出客戶平均逗留的時(shí)間。三、總的設(shè)計(jì)思想、環(huán)境語(yǔ)言、工具等總的設(shè)計(jì)思想：為了計(jì)算這個(gè)平均的逗留時(shí)間，自然需要知道每個(gè)客戶到達(dá)銀行和離開(kāi)銀行這兩個(gè)時(shí)刻，后者減去前者即為每個(gè)客戶在銀行的逗留時(shí)間。所有客戶逗留時(shí)間的總和被一天內(nèi)進(jìn)入銀行的客戶數(shù)除便是所求的平均時(shí)間。稱客戶到達(dá)銀行和離開(kāi)銀行這兩個(gè)時(shí)間發(fā)生的事情為“事件”，則整個(gè)模擬程序?qū)词录南群箜樞蜻M(jìn)行處理。這樣一種程序稱做事件驅(qū)動(dòng)模擬。下面是上述銀行客戶的離散事件驅(qū)動(dòng)的模擬算法。 void Bank_Simulation( int CloseTime ) / OpenForDay ( ); /初始化,模擬銀行開(kāi)門時(shí)各數(shù)據(jù)結(jié)構(gòu)的狀態(tài)。 while(有要處理的事件時(shí)) /有事件可處理 EventDrived ; /事件驅(qū)動(dòng)，從事件表中取出事件en；/根據(jù)en的類型（客戶到達(dá)事件或客戶離開(kāi)事件）做相應(yīng)的處理 if(en表示客戶到達(dá)) CustomerArrived( );/ 處理客戶到達(dá)事件 else CustomerDeparture( ) ;/ 處理客戶離開(kāi)事件 /while CloseForDay( );/計(jì)算客戶的平均逗留時(shí)間/ Bank_Simulation 環(huán)境語(yǔ)言：Windows下的Microsoft VC+四、數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明下面是模擬程序中需要的數(shù)據(jù)結(jié)構(gòu)及其操作。1模擬算法的主要處理對(duì)象是“事件”，事件的主要信息是事件的類型和事件的發(fā)生時(shí)刻。算法中處理的事件有兩類：一類是客戶到達(dá)事件；另一類是客戶離開(kāi)事件。前一類事件發(fā)生的時(shí)刻隨客戶的到來(lái)自然形成；后一類事件發(fā)生的時(shí)刻由客戶辦理業(yè)務(wù)所需時(shí)間和等待時(shí)間而定。由于程序驅(qū)動(dòng)是按事件發(fā)生時(shí)刻的先后順序進(jìn)行的，所以事件表應(yīng)是有序表，其主要操作是插入和刪除事件，用一個(gè)單鏈表表示！2模擬程序中需要的另一數(shù)據(jù)結(jié)構(gòu)是表示客戶排隊(duì)的隊(duì)列，由于假設(shè)銀行有4個(gè)窗口，因此程序中需要4個(gè)隊(duì)列，隊(duì)列中有關(guān)客戶的信息是客戶到達(dá)的時(shí)刻和客戶辦理業(yè)務(wù)所需要的時(shí)間。每個(gè)隊(duì)列中的隊(duì)頭客戶即為正在窗口辦理事務(wù)的客戶，他辦完業(yè)務(wù)離開(kāi)隊(duì)列的時(shí)刻就是即將發(fā)生的客戶離開(kāi)事件的時(shí)刻，這就是說(shuō)，對(duì)每個(gè)隊(duì)頭客戶都存在一個(gè)將要驅(qū)動(dòng)的客戶離開(kāi)事件。因此在任何時(shí)刻即將發(fā)生的事伯只有5種可能：1）新的客戶到達(dá)；2）1號(hào)窗口的客戶離開(kāi)；3）2號(hào)窗口的客戶離開(kāi)；4）3號(hào)窗口的客戶離開(kāi)；5）4號(hào)窗口的客戶離開(kāi)；注：為了使編寫的程序具有通用性，在編程序時(shí)將銀行的營(yíng)業(yè)時(shí)間、開(kāi)的窗口數(shù)、客戶辦業(yè)業(yè)務(wù)的最長(zhǎng)時(shí)間及兩個(gè)客戶到達(dá)的時(shí)間間隔都設(shè)置成程序運(yùn)行時(shí)動(dòng)態(tài)輸入，這樣可以對(duì)程序以及銀開(kāi)設(shè)的窗口的合理性進(jìn)行分析，實(shí)現(xiàn)真正的模擬。從以上分析可知，在模擬程序中只需要兩種數(shù)據(jù)結(jié)構(gòu)：有序鏈表和隊(duì)列。程序中用到的頭文件、類型定義及主要的函數(shù)原型如下：#includestdio.h#includemalloc.h#includemath.h#includestdlib.hint Cks=4; / 銀行辦理業(yè)務(wù)的窗口數(shù),默認(rèn)值為:4；最大值不超過(guò)20；int Qu ; / 客戶隊(duì)列數(shù)Qu=Cksint Khjg=5; / 兩相鄰到達(dá)客戶的時(shí)間間隔最大值,默認(rèn)值為:5int Blsj=30; / 每個(gè)客戶辦理業(yè)務(wù)的時(shí)間最大值,默認(rèn)值為:30typedef struct / 定義事件的元素類型ElemType為結(jié)構(gòu)體類型 int OccurTime; / 事件發(fā)生時(shí)刻 int NType; / 事件類型，Qu表示到達(dá)事件,0至Qu-1表示Qu個(gè)窗口的離開(kāi)事件 Event,ElemType; / 事件類型，有序鏈表LinkList的數(shù)據(jù)元素類型typedef struct LNode /定義事件表的結(jié)點(diǎn)類型 ElemType data ;struct LNode *next; LNode, *LinkList; typedef LinkList EventList; / 事件鏈表類型，定義為有序鏈表typedef struct /定義客戶隊(duì)列的元素類型 int ArrivalTime; / 到達(dá)時(shí)刻 int Duration; / 辦理事務(wù)所需時(shí)間 QElemType; / 定義QElemType(隊(duì)列的數(shù)據(jù)元素類型)為結(jié)構(gòu)體類型;typedef struct QNode /定義客戶隊(duì)列的結(jié)點(diǎn)類型 QElemType data ;struct QNode *next; QNode, *Queue; typedef struct Queue head; Queue tail; LinkQueue;LinkQueue qQu+1; / Qu個(gè)客戶隊(duì)列void OpenForDay()； /模擬銀行開(kāi)門的動(dòng)作，即初始化操作 void CustomerArrived() / 處理客戶到達(dá)事件void CustomerDeparture() / 處理客戶離開(kāi)事件五、主要算法的設(shè)計(jì)與實(shí)現(xiàn)void OpenForDay() /模擬銀行開(kāi)門的動(dòng)作，即初始化操作 int i; InitList(ev); / 初始化事件鏈表為空 en.OccurTime=0; / 設(shè)定第一個(gè)客戶到達(dá)事件 en.NType=0; / 客戶到達(dá)事件 Insert_EventList(ev, en);/插入事件 q=(LinkQueue*)malloc(Qu+1)*sizeof(LinkQueue);/為隊(duì)列申請(qǐng)Qu+1個(gè)隊(duì)頭指針，第0個(gè)不用 for(i=1;iQu+1;+i) / 置空隊(duì)列 InitQueue(qi); void CustomerArrived() / 處理客戶到達(dá)事件 QElemType f; int durtime,intertime,i; +CustomerNum; Random(durtime,intertime); / 生成隨機(jī)數(shù) /printf(%d %dn,durtime,intertime); et.OccurTime=en.OccurTime+intertime; / 下一客戶到達(dá)時(shí)刻 et.NType=0; / 隊(duì)列中只有一個(gè)客戶到達(dá)事件 /printf(%d %dn,et.NType,et.OccurTime); if(et.OccurTimeCloseTime) / 銀行尚未關(guān)門，插入事件表 Insert_EventList(ev,et); i=Minimum(q); / 求長(zhǎng)度最短隊(duì)列的序號(hào),等長(zhǎng)為最小的序號(hào) f.ArrivalTime=en.OccurTime; f.Duration=durtime; EnQueue(qi,f); if(QueueLength(qi)=1) et.OccurTime=en.OccurTime+durtime; et.NType=i; Insert_EventList(ev,et); / 設(shè)定第i隊(duì)列的一個(gè)離開(kāi)事件并插入事件表 void CustomerDeparture() / 處理客戶離開(kāi)事件，en.NTyPe!=0 int i; i=en.NType; DelQueue(qi,customer); / 刪除第i隊(duì)列的排頭客戶 TotalTime+=en.OccurTime-customer.ArrivalTime; / 累計(jì)客戶逗留時(shí)間 if(!QueueEmpty(qi) / 設(shè)定第i隊(duì)列的一個(gè)離開(kāi)事件并插入事件表 GetHead_q(qi,customer); et.OccurTime=en.OccurTime+customer.Duration; et.NType=i; Insert_EventList(ev,et); void Bank_Simulation() int i; OpenForDay( ); / 初始化 while(!ListEmpty(ev) /output_ev(ev); /for(i=1;iQU+1;i+) output_q(qi); /getchar();/為觀察執(zhí)行結(jié)果用 Gethead(ev,en); /printf(事件%d %dn ,en.NType,en.OccurTime); if(en.NType=0) CustomerArrived(); / 處理客戶到達(dá)事件 else CustomerDeparture(); / 處理客戶離開(kāi)事件 / 計(jì)算并輸出平均逗留時(shí)間 printf(顧客總數(shù):%d, 所有顧客共耗時(shí):%d分鐘, 平均每人耗時(shí): %d分鐘n,CustomerNum,TotalTime,TotalTime/CustomerNum); 六、源程序 見(jiàn)電子稿(文件名為: .cpp ); /文件名由自己取七、運(yùn)行結(jié)果請(qǐng)輸入銀行營(yíng)業(yè)時(shí)間長(zhǎng)度(單位:分)CloseTime=480請(qǐng)輸入銀行辦理業(yè)務(wù)所開(kāi)窗口數(shù)Cks=4請(qǐng)輸入客戶辦理業(yè)務(wù)的最長(zhǎng)時(shí)間Blsj=30請(qǐng)輸入兩個(gè)相鄰客戶到達(dá)銀行的時(shí)間間隔的最大值Khjg=5顧客總數(shù):154, 所有顧客共耗時(shí):11303分鐘, 平均每人耗時(shí): 73分鐘Press any key to continue請(qǐng)輸入銀行營(yíng)業(yè)時(shí)間長(zhǎng)度(單位:分)CloseTime=480請(qǐng)輸入銀行辦理業(yè)務(wù)所開(kāi)窗口數(shù)Cks=5請(qǐng)輸入客戶辦理業(yè)務(wù)的最長(zhǎng)時(shí)間Blsj=30請(qǐng)輸入兩個(gè)相鄰客戶到達(dá)銀行的時(shí)間間隔的最大值Khjg=5顧客總數(shù):154, 所有顧客共耗時(shí):3854分鐘, 平均每人耗時(shí): 25分鐘Press any key to continue請(qǐng)輸入銀行營(yíng)業(yè)時(shí)間長(zhǎng)度(單位:分)CloseTime=480請(qǐng)輸入銀行辦理業(yè)務(wù)所開(kāi)窗口數(shù)Cks=6請(qǐng)輸入客戶辦理業(yè)務(wù)的最長(zhǎng)時(shí)間Blsj=30請(qǐng)輸入兩個(gè)相鄰客戶到達(dá)銀行的時(shí)間間隔的最大值Khjg=5顧客總數(shù):154, 所有顧客共耗時(shí):2705分鐘, 平均每人耗時(shí): 17分鐘請(qǐng)輸入銀行營(yíng)業(yè)時(shí)間長(zhǎng)度(單位:分)CloseTime=480請(qǐng)輸入銀行辦理業(yè)務(wù)所開(kāi)窗口數(shù)Cks=4請(qǐng)輸入客戶辦理業(yè)務(wù)的最長(zhǎng)時(shí)間Blsj=15請(qǐng)輸入兩個(gè)相鄰客戶到達(dá)銀行的時(shí)間間隔的最大值Khjg=5顧客總數(shù):154, 所有顧客共耗時(shí):1181分鐘, 平均每人耗時(shí): 7分鐘 從運(yùn)行結(jié)果看，銀行設(shè)置6個(gè)窗口比較合適！八、自我評(píng)析與總結(jié)該實(shí)驗(yàn)做得比較成功，例如在編寫調(diào)試程序時(shí)，并不是僅僅把目標(biāo)局限在編譯通過(guò)，執(zhí)行有結(jié)果上。除了為了完成任務(wù)的模塊外，另有測(cè)試事件表的函數(shù)output_ev和各窗口隊(duì)列狀態(tài)的函數(shù)output_q；在適當(dāng)?shù)牡胤秸{(diào)用它們，運(yùn)行時(shí)可以看到事件表和窗口隊(duì)列的狀態(tài)，用來(lái)判斷編寫程序的正確性；當(dāng)運(yùn)