數(shù)據(jù)結(jié)構(gòu)(00007

1、 數(shù)據(jù)結(jié)構(gòu)電梯模擬實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 陳東姓名： 070612146 學(xué)號(hào)： 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 2 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 目 錄 一、【實(shí)驗(yàn)?zāi)康摹?. 4 4 . 二、【問題描述】 4 . 】 .三、【基本要求 4 . 實(shí)驗(yàn)環(huán)境四、【】 5 . 】五、【測(cè)試數(shù)據(jù)及其結(jié)果 9 . 六、【實(shí)驗(yàn)源代碼】 . 越班機(jī)計(jì)12范慶安師學(xué)院02算卓 3 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 一、【實(shí)驗(yàn)?zāi)康摹?幫助學(xué)生熟練掌握線性表的基本操作在鏈表結(jié)構(gòu)中的實(shí)現(xiàn)，熟練進(jìn)行各種鏈表的操作和應(yīng)用。 二、【問題描述】 設(shè)計(jì)一個(gè)電梯模擬系統(tǒng)。這是一個(gè)離散的模擬程

2、序，因?yàn)殡娞菹到y(tǒng)是乘客和電梯等“活動(dòng)體”夠成的集合，雖然他們彼此交互作用，但是他們的行為是基本獨(dú)立的。在離散的模擬中，一模擬時(shí)鐘決定每個(gè)活動(dòng)體的動(dòng)作發(fā)生的時(shí)刻和順序，系統(tǒng)在某個(gè)模擬瞬間處理有待完成的各種事情，然后把模擬時(shí)鐘推進(jìn)到某個(gè)動(dòng)作預(yù)定要發(fā)生的下一個(gè)時(shí)刻。 三、【基本要求】 （1）、模擬某校五層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停留。五個(gè)樓層由下至上依次稱為地下層、第一層、第二層、第三層和第四層，其中第一層是大樓的進(jìn)出層，即是電梯的“本壘層”，電梯“空閑”時(shí)，將來該層候命。五個(gè)樓層從下到上的編號(hào)為：0、1、2、3、4。除了地下層外，每一層都有一個(gè)要求向下的按鈕除了第四層外，每一

3、層都有一個(gè)要求向上的按鈕。對(duì)應(yīng)的變量為：CallUp0.3和CallDown1.4。電梯內(nèi)的五個(gè)目標(biāo)層按鈕對(duì)應(yīng)的變量為：CallCar0.4。 （2）、電梯一共有七個(gè)狀態(tài)，即正在開門（Opening）、已開門（Opened）、正在關(guān)門（Closing）、已關(guān)門（Closed）、等待（Waiting）、移動(dòng)（Moving）、減速（Decelerate）。 （3）、 乘客可隨機(jī)地進(jìn)出于任何層。對(duì)每個(gè)人來說，他有一個(gè)能容忍的最長等待 2012計(jì)算機(jī)卓越班 安慶師范學(xué)院 4 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 時(shí)間，一旦等候電梯時(shí)間過長，他將放棄。對(duì)于在樓層內(nèi)等待電梯的乘客，將插入在等候隊(duì)列里

4、，每一層有兩個(gè)等候隊(duì)列，一隊(duì)要求向上，一隊(duì)要求向下，用鏈隊(duì)列來實(shí)現(xiàn)。對(duì)于在電梯內(nèi)的乘客，用五個(gè)乘客棧來實(shí)現(xiàn)，該乘客要去哪一層，就把他放在相應(yīng)編號(hào)的棧中，對(duì)應(yīng)變量為EleStack04。 （4）、模擬時(shí)鐘從0開始，時(shí)間單位為0.1秒。人和電梯的各種動(dòng)作均要耗費(fèi)一定的時(shí)間單位（簡(jiǎn)記為t）： 有人進(jìn)出時(shí)，電梯每隔40t測(cè)試一次，若無人進(jìn)出，則關(guān)門 關(guān)門和開門各需要20t 每個(gè)人進(jìn)出電梯均需要25t 電梯加速需要15t 如果電梯在某層靜止時(shí)間超過300t，則駛回1層候命。 （5）、按時(shí)序顯示系統(tǒng)狀態(tài)的變化過程：發(fā)生的全部人和電梯的動(dòng)作序列。 四、【實(shí)驗(yàn)環(huán)境】 Windows 7, VC+6.0 五、【

5、測(cè)試數(shù)據(jù)及其結(jié)果】 1、 乘客類型 反映乘客的所有屬性。 ADT Client 數(shù)據(jù)對(duì)象：D=ai乘客信息,I=1,2,n,n0 數(shù)據(jù)關(guān)系：R=|ai-1,aiD,i=2,n 基本操作： 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 5 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 PrintClientInfo(Client const &e,ClientStatus) 操作結(jié)果：輸出乘客信息。 CreatClient(Client *&p) 操作結(jié)果：生成新的乘客。 DestoryClient(Client *&p) 操作結(jié)果：該乘客離開系統(tǒng)。 GoAbove(Client const &e) 操作結(jié)果

6、：判斷該乘客是否去往高層。 CInfloor(Client const &e) 操作結(jié)果：返回乘客進(jìn)入的樓層。 CInTime(Client const &e) 操作結(jié)果：返回乘客進(jìn)入時(shí)間。 COutfloor(Client const &e) 操作結(jié)果：返回乘客進(jìn)入時(shí)間。 2、 乘客棧類型 電梯內(nèi)的乘客用乘客棧表示，去不同樓層的乘客放在不同的棧中。 ADT Estack 數(shù)據(jù)對(duì)象：D=ai乘客信息,I=1,2,n,n0 數(shù)據(jù)關(guān)系：R=|ai-1,aiD,i=2,n 基本操作： 略。 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 6 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 3、 等候隊(duì)列類型 在電梯外

7、等待的乘客用等待隊(duì)列表示。每層各有兩個(gè)等待隊(duì)列，分別為上樓隊(duì)列和下樓隊(duì)列。 與一般隊(duì)列不同的是在基本操作中加入了放棄操作CGiveUp(WQueue &Q,int floor)。 4、 電梯類型 表示電梯的各個(gè)屬性和所有動(dòng)作。 ADT Elevator 數(shù)據(jù)對(duì)象：D=ai電梯信息,I=1,2,n,n0 基本操作： InitEle(Elevator &E) 操作結(jié)果：初始化電梯類型。 DestoryEle(Elevator &E) 操作結(jié)果：銷毀電梯類型。 EleDecide(Elevator &E,WQueue wMaxfloor+12) 操作結(jié)果：電梯動(dòng)作決策。 ElevatorRun(El

8、evator &E,WQueue wMaxfloor+12) 操作結(jié)果：電梯狀態(tài)轉(zhuǎn)換。 CountOver(Elevator &E) 操作結(jié)果：判斷電梯計(jì)時(shí)是否完成。 EleFloor(Elevator const &E) 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 7 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 操作結(jié)果：返回電梯所在的層。 EleStatus(Elevator const &E) 操作結(jié)果：返回電梯狀態(tài)。 RequireAbove(Elevator const &E) 操作結(jié)果：判斷是否有高層請(qǐng)求。 RequireBelow(Elevator const &E) 操作結(jié)果：判斷是否有

9、低層請(qǐng)求。 EleAchieved(Elevator &E) 操作結(jié)果：判斷電梯是否要停于當(dāng)前層。 EleOpenDoor(Elevator &E) 操作結(jié)果：判斷電梯是否要開門。 5、 高樓模塊 實(shí)現(xiàn)電梯和乘客之間的互交功能。包括： InOut(Elevator &E,WQueue wMaxfloor+12) 操作結(jié)果：進(jìn)行乘客的進(jìn)出電梯活動(dòng)。 NewClient(Elevator &E,WQueue w52) 操作結(jié)果：進(jìn)入新乘客。 PrintStatus(Elevator &E,WQueue w52) 操作結(jié)果：輸出當(dāng)前狀態(tài)。 Print(Elevator &E,Action a) 操作

10、結(jié)果：輸出電梯動(dòng)作信息。 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 8 / 21 越機(jī)計(jì)12學(xué)師安慶范院02算卓班 9 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 六、【實(shí)驗(yàn)源代碼】 #include #include #include #include #include #include #include /所有常量，全局變量和類型定義 #define NULL 0 1 #define TRUE 0 #define FALSE 1 #define OK 0 #define ERROR #define INFEASIBLE -1 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 #define OVERFLOW -2

11、 #define INT_MAX 32767 typedef int Status; /Status是函數(shù)類型，其值是函數(shù)結(jié)果狀態(tài)代碼 #define Empty 0 /電梯狀態(tài)EleStatusOpening,Opened,Closing,Closed,Moving,Decelerate,Waiting; enum ActionDoorOpened,DoorClosed,GoingUp,GoingDown,Achieved,None; enum EleStageUp,Down,OpenDoor,Stop; enum ClientStatusNew,GiveUp,In,Out,Finish;

12、enum 電梯關(guān)門測(cè)試時(shí)間#define CloseTest 40 / 電梯停候超時(shí)時(shí)間#define OverTime 300 / 開門關(guān)門時(shí)間#define DoorTime 20 / 進(jìn)出電梯時(shí)間#define InOutTime 25 / /#define Maxfloor 4 最高層 /最低層#define Minfloor 0 /時(shí)鐘 long Time=0; / 系統(tǒng)運(yùn)行最長時(shí)間long MaxTime; int InOutCount=0; /用于進(jìn)出計(jì)時(shí) int InterTime=0; 下一乘客進(jìn)入系統(tǒng)的時(shí)間 /int ID=0; 乘客編號(hào) / int GiveUpNumbe

13、r=0; /乘客放棄的數(shù)目 int TotalTime=0; /總共等待時(shí)間 /乘客類型typedef struct int ClinetID; / 乘客編號(hào) int Outfloor; / 去哪層 int InTime; / 該乘客進(jìn)入時(shí)間 int GivepuTime; /所能容忍的等待時(shí)間 int Infloor;/乘客進(jìn)入的樓層 Client; /乘客類型基本操作void PrintClientInfo(Client const &e,ClientStatus s) switch(s) case New: printf(%d號(hào)乘客進(jìn)入第%d層 .n,e.ClinetID,e.Inflo

14、or);break; case GiveUp: printf(%d 號(hào)乘客放棄等待.n,e.ClinetID);break; .n,e.ClinetID);break; 號(hào)乘客走出電梯case Out: printf(%dcase In:printf(%d號(hào)乘客走進(jìn)電梯，要去第 %d層.n,e.ClinetID,e.Outfloor);break; 2012計(jì)算機(jī)卓學(xué)師安慶范院越班 10 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 default:break; ; Status CreatClient(Client *&p) int d; p=new Client; if(!p) return

15、 OVERFLOW; p-ClinetID=+ID; :,ID); printf(%d 所能容忍的等待時(shí)間scanf(%d,&d); p-GivepuTime=d; p-InTime=Time; :); 牰湩晴尨下一乘客要到達(dá)的時(shí)間 scanf(%d,&d); InterTime=d; :); 牰湩晴尨 所要到達(dá)的樓層 scanf(%d,&d); p-Outfloor=d; while(p-Infloor=rand()%(Maxfloor+1)=p-Outfloor); PrintClientInfo(*p,New); return OK; Status DestoryClient(Clien

16、t *&p) delete p; p=NULL; return OK; Status GoAbove(Client const &e) if(e.Outfloore.Infloor) return TRUE; else return FALSE; Status CInfloor(Client const &e) return e.Infloor; Status CInTime(Client const &e) return e.InTime; 102院范師慶安學(xué)越卓機(jī)算2計(jì)班 11 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 Status COutfloor(Client const &e)

17、return e.Outfloor; /存儲(chǔ)空間初始分配量#define STACK_INIT_SIZE 100 50 /存儲(chǔ)空間分配增量#define STACKINCREMENT 乘客棧/ *SElemType; typedef Client typedef struct SElemType *base; *top; SElemType stacksize; int ClientStack; Status InitStack(ClientStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S

18、.base) return OVERFLOW; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; Status DestroyStack(ClientStack &S) SElemType *p; if(S.base) for(p=S.base;p=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) return OVERFLOW; S.top=S.base+S.stacks

19、ize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; Status Pop(ClientStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*(-S.top); return OK; void PrintStack(ClientStack &S) SElemType *i; i=S.base; while(iS.top) coutClinetID ; /電梯類型typedef struct 電梯所在層int floor; / 電梯內(nèi)人數(shù) int ClientNumber;/ 電

20、梯當(dāng)前狀態(tài)/EleStatus status; EleStage Stage; / 電梯運(yùn)行時(shí)期 計(jì)202院學(xué)范慶安師1班越卓算機(jī) 13 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 int Count;/用于電梯計(jì)時(shí) int CallUpMaxfloor+1;/每層的Up按鈕 int CallDownMaxfloor+1;/每層的 Down按鈕 int CallCarMaxfloor+1;/ 電梯內(nèi)的目標(biāo)層按鈕 ClientStack SMaxfloor+1;/乘客棧, 要去不同樓層的人放在不同的棧中 Elevator; /電梯類型基本操作 void InitEle(Elevator &E)

21、int i; E.floor=1; E.status=Waiting;E.Count=OverTime; E.Stage=Down; E.ClientNumber=0; for(i=0;i=Maxfloor;i+) E.CallUpi=0;E.CallDowni=0;E.CallCari=0; for(i=0;i=Maxfloor;i+) InitStack(E.Si); Status CountOver(Elevator &E) if(E.Count) E.Count-;return FALSE; return TRUE; void DestoryEle(Elevator &E) int i

22、; for(i=0;i=Maxfloor;i+) DestroyStack(E.Si); Status EleFloor(Elevator const &E) return E.floor; EleStatus EleStatus(Elevator const &E) return E.status; Status RequireAbove(Elevator const &E) for(int i=E.floor+1;i=Minfloor;i-) if(E.CallCari|E.CallDowni|E.CallUpi) return TRUE; return FALSE; Status Ele

23、Achieved(Elevator &E) if(E.CallCarE.floor) return TRUE; if(E.Stage=Up&E.CallUpE.floor|E.Stage=Down&E.CallDownE.floor) return TRUE; if(E.Stage=Up&E.CallDownE.floor&!RequireAbove(E) E.Stage=Down;return TRUE; if(E.Stage=Down&E.CallUpE.floor&!RequireBelow(E) E.Stage=Up;return TRUE; return FALSE; Status

24、EleOpenDoor(Elevator &E) if(E.CallCarE.floor|E.CallDownE.floor&E.Stage=Down|E.CallUpE.floor&E.Stage=Up) return TRUE; if(E.status=Waiting) if(E.CallDownE.floor) E.Stage=Down;return TRUE; if(E.CallUpE.floor) E.Stage=Up;return TRUE; return FALSE; EleStage EleDecide(Elevator &E) int Above,Below; Above=R

25、equireAbove(E); Below=RequireBelow(E); if(Above=0&Below=0) return Stop; else if(E.Stage=Up) if(Above!=0) return Up; else 202院學(xué)范慶安師1越卓機(jī)算計(jì)班 15 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 E.Stage=Down;return Down; else if(Below!=0) return Down; else E.Stage=Up;return Up; Action ElevatorRun(Elevator &E) switch(E.status) case

26、 Opening: E.status=Opened;E.Count=CloseTest; return DoorOpened; case Opened: if(E.Stage=Down&!E.CallCarE.floor&!E.CallDownE.floor| E.Stage=Up&!E.CallCarE.floor&!E.CallUpE.floor) reak; b E.status=Closing;E.Count=DoorTime; case Closing: E.status=Closed; return DoorClosed; case Waiting: if(E.Count=0) i

27、f(E.floor!=1) E.CallCar1=1; else E.Count-; if(EleOpenDoor(E) E.status=Opening;E.Count=DoorTime;break; case Closed: break; case Moving: 完成移動(dòng) /if(E.Stage=Up) E.floor+; E.floor-; else return Achieved; E.status=Opening;E.Count=DoorTime; break; ; return None; 安計(jì)2102院學(xué)范師慶班卓機(jī)算越 16 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 /單鏈

28、隊(duì)列-隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) typedef Client *QElemType; /等候隊(duì)列 typedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; WQueue; 等待隊(duì)列的基本操作/Status InitQueue(WQueue &Q) Q.front=Q.rear=new QNode; if(!Q.front) return OVERFLOW; Q.front-next=NULL; Q.front-data=

29、NULL; return OK; Status DestroyQueue(WQueue &Q) while(Q.front) Q.rear=Q.front-next; if(Q.front-data) DestoryClient(Q.front-data); else Q.front; Q.front=Q.rear; return OK; Status EnQueue(WQueue &Q,QElemType e) QueuePtr p; p=new QNode; if(!p) return OVERFLOW; p-data=e;p-next=NULL; Q.rear-next=p; Q.rea

30、r=p; 算計(jì)202院學(xué)范慶安師1機(jī)班越卓 17 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 return OK; Status DeQueue(WQueue &Q,QElemType &e) QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; Status QueueEmpty(WQueue Q) if(Q.front=Q.rear) return TRUE; el

31、se return FALSE; Status QDelNode(WQueue &Q,QueuePtr p) QueuePtr q; if(p=NULL|p-next=NULL) return ERROR; q=p-next; p-next=q-next; if(p-next=NULL) Q.rear=p; DestoryClient(q-data); free(p); return OK; Status CGiveUp(WQueue &Q,int floor) QueuePtr p; p=Q.front; if(p-next!=NULL) if(p-next-data-GivepuTime=

32、0&floor!=p-next-data-Infloor) PrintClientInfo(*(p-next-data),GiveUp); TotalTime+=Time-CInTime(*(p-next-data); QDelNode(Q,p); GiveUpNumber+; 算2102院范師慶安學(xué)計(jì)班越卓機(jī) 18 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 else p-next-data-GivepuTime-; return OK; void PrintQueue(WQueue Q) QueuePtr q; int count=0; if(Q.front-next=NULL) goto

33、 end; q=Q.front-next; while(q!=NULL) coutsetw(3)data-ClinetIDnext; count+; end: while(count+=4) cout ; void InOut(Elevator &E,WQueue wMaxfloor+12) Client *p; if(E.CallCarE.floor) if(StackEmpty(E.SE.floor) E.CallCarE.floor=0; else Pop(E.SE.floor,p);E.ClientNumber-; InOutCount=InOutTime; PrintClientIn

34、fo(*p,Out); TotalTime+=Time-CInTime(*p); DestoryClient(p); if(E.CallCarE.floor=0) if(!QueueEmpty(wE.floorE.Stage) DeQueue(wE.floorE.Stage,p); Push(E.SCOutfloor(*p),p); if(E.CallCarCOutfloor(*p)!=1) E.CallCarCOutfloor(*p)=1; E.ClientNumber+; 算計(jì)102院學(xué)師慶安范2班越卓機(jī) 19 / 21 實(shí)驗(yàn)三 棧和隊(duì)列及其應(yīng)用電梯模擬 InOutCount=InOutTime; PrintClientInfo(*p,In); else if(E.Stage=Down) E.CallDownE.floor=0; else E.CallUpE.floor=0; void NewClient(Elevator &E,WQueue w52) Client *p; CreatClient(p); if(GoAbove(*p) EnQueue(w