数据结构课程设计报告--电梯模拟.doc

课 程 设 计 课程名称 数据结构 题目名称 2.8电梯模拟(难度5) 学生学院 计算机学院 专业班级 XXXXXXXXXX 学 号 XXXXXXXX 学生姓名 XXX 指导教师 XX 2013年7月4日电梯模拟系统一、 简单介绍1、问题描述设计一个电梯模拟系统，这是一个离散的模拟程序，因为电梯系统是乘客和电梯等“活动体”构成的集合，虽然他们彼此交互作用，但他们的行为是基本独立的，在离散的模拟中，以模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一个时刻。2、基本要求（1）、模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层，第四层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。（2）、乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。（3）、模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。（4）、按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。二、设计目的 当初之所以选择做电梯模拟这个课题，主要是因为觉得当今时代需要，所以觉得想尝试一下，因为为了方便，我们都会选择乘坐电梯，既省时间又省力，粗略看了书本里面的描述，觉得应该不难，只是按照要求输出动作序列即可，后来经过老师的辅导，才发现，原来自己选了个最难的课程设计，也问了同学，很多都是因为太难了才没有选这个题目，因为它远比想象中的复杂的多很多，它实际上是模拟现实中的电梯的运行状况，因此要考虑很多现实中遇到的实际情况，坐过电梯的人都会应该有点印象，现实中的电梯是按照每个人按下按钮的时间顺序进行服务的，但是，并不是将一个人接进来后就直接开往其目的楼层就完事，其实，当电梯将某个人送往其目的楼层的过程中，经过某层时，如果此层的人也要用电梯，虽然其按按钮的时间有可能比先前那个人晚，但是电梯依旧会开门将其接入，然后继续送前一个人去目的地，之后再送这个人去他的目的楼层，如果有多人在电梯中时，也是按照申请时间的先后决定先去哪层的，同理，若在某层，电梯中的某个人，或者某几个人要在该层下，电梯也不能忽略这些，而是要先开门使要下的人出去，之后继续开往先前的楼层，所以设计时，每当电梯上升或下降一层后，都应该检测现在电梯所处的这层有没有人有用电梯的请求，或者电梯中的人有没有要在该层下的情况，若有则电梯要在该层停一下，否则继续上升或下降.此外，当电梯停在某一层时不外乎三种情况：1.此层有个人或有几个人等候要用电梯 2.电梯中的某个人或者某几个人要在该楼层下 3.则是前面两种情况的结合，此时情况相当复杂，因为，题目要求电梯开门和关门都要消耗一定的时间（题目中没有提电梯上升或者下降一层需要多少时间，所以不妨就假定为30t），而且人进电梯和人出电梯时也要消耗一定的时间，这说明了当同一时刻有至少两个以上的人要进行同一种动作的时候（比方说都是要出电梯，或都是在某一层等电梯，电梯来了后都要进去），但是因为每个人进出电梯都要消耗时间，所以不能单纯的同时让这些人同进或同出电梯，而是要有先后顺序的进出，此为其一其二，题目中还提到每个人等候电梯到来时，都有一个容忍时间（每个人不一定相同），所以，万一，在他按下按钮到电梯开到他所在的那层楼的间隔时间大于他的最大容忍时间，他会先行离开，但这一切电梯并不知道啊，所以电梯依旧会按照每个申请使用电梯的时间进行服务，正是因为这样，极有可能发生这样的情况：电梯开到某层后打开电梯门，但是既没有人出去，也没有人进来其三，根据题目中的要求，当电梯停在某层时候，有人进出，电梯每隔40t测试一次，若无人进出，则关门，关门完后，若300t时间内没有人使用，则自动开到第1层等候下次的使用（第1层楼是电梯的本垒层， 电梯“空闲”时，将来到该层候命）等等等等以上各种情况（还有一些情况这里没列举）都是要在做这道题时需要考虑的，否则这题的电梯根本模拟不起来三、设计概要本程序中所有的抽象数据类型的定义及其相应的操作函数的定义如下：电梯的结构体dianti/*此电梯结构体中分别定义了电梯所在楼层，电梯的现有人数（现实中的电梯有个最大栽客量，在此题中不妨规定为最大12人），以及电梯门的状态（0为关，1为开），至于为什么定义电梯门的状态，并不是多此一举，而是我在调试的过程中发现必须加上的，否则，在一些情况下会出现电梯动作的局部重复，从而导致整个程序的失败*/人的结构体 man/*在人的结构体中，分别定义了人的名字（这个有利于区别各个人），最大容忍时间（题目中的要求），所在的楼层，要去的目的楼层，两个标志位，其中一个标志记录该人是否还在电梯里面，另一个标志记录的是该人是否已经使用过电梯*/事件结构体结点SLNode/*在事件的结构体中分别定义了，事件信息，事件发生的时刻，以及指向下一个事件结构结点的指针*/void ListInitiate(SLNode*head) /*初始化链表*/void LinListSort(SLNode *head) /*用按发生时间的顺序给事件链表中的事件排序*/void Destroy(SLNode * *head)/*撤消链表*/void OPEN(SLNode *head,dianti dt,int now)/*电梯开门函数，将电梯开门的事件信息插入到事件链表中去*/void CLOSE(SLNode *head,dianti dt,int now)/*电梯关门函数，将电梯关门的事件信息插入到事件链表中去*/void GET_IN(SLNode *head,dianti dt,int now)/*人进电梯的函数，将人进电梯时候的各种信息插入到事件链表中去*/void GET_OUT(SLNode *head,dianti dt,int now)/*人出电梯的函数，将人出电梯时候的各种信息插入到事件链表中去*/注释：以上四个函数基本是用来完成人和电梯的动作序列int gettime(SLNode *head) /*返回最新事件（即事件涟表最后一个结点）的发生时间，此为该程序中最重要的一个函数之一，并且为调用最频率最高的一个函数*/void print(SLNode *head)/*将事件链表中的事件一一显示出来，即为最后显示电梯和人动作序列的函数*/void Go(SLNode *head,int n,dianti dt,clock_t s1000,man r1000) /*电梯运行函数，本程序中最最重要的函数，可以说这是这道程序中的灵魂函数，根据申请使用电梯的所有人的信息，以及所有事件发生时的时刻，将所有情况的处理都放在在其中，所以此函数的代码相当占了程序代码的百分之七十多了（程序总代码长度超过1200行）*/注释：以上各个函数以及抽象数据结构的定义都放在头文件”elevator.h”中void main()/*该程序的主函数*/程序流程图如下：四、详细设计本程序的所有抽象数据类型的具体实现一机相应的操作函数的伪算法如下：typedef struct int lc;/电梯所在楼层 int rs;/电梯中的人数,规定最大乘坐人数为12 int door;/门的状态 0关1开dianti;typedef struct char name50; /这个人的名字或序号(以示区别)int rrsj;/一个人的容忍时间int lc;/所在楼层int md;/目的楼层int biaozhi; /此标志位记录人使用电梯是否完成或者是否离去,为1表明使用过(离去),否则为0int in; /标志位,为1时表明人在电梯中,否则为0man;typedef struct Nodechar a1000;/事件信息int mytime;/事件所发生的时间struct Node *next;SLNode;/初始化链表 void ListInitiate(SLNode* *head) if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);(*head)-next = NULL;/将事件结点插入到事件链表中的第i个位置中去 int ListInsert(SLNode *head,int i,char a1000,int t)SLNode *p,*q;int j;p=head;j=-1;while(p-next!=NULL & jnext;j+; if(j!=i-1) printf(n 插入位置参数错!n);return 0; if(q=(SLNode *)malloc(sizeof(SLNode) = NULL) exit(1); q-mytime = t; strcpy(q-a,a); q-next =p-next; p-next =q; return 1;/用按发生时间的顺序给事件排序 void LinListSort(SLNode *head) SLNode *curr,*pre,*p,*q; p=head-next; head-next=NULL; while(p!=NULL)curr=head-next;pre=head;while(curr!=NULL & curr-mytimemytime)pre=curr;curr=curr-next; q=p;p=p-next;q-next=pre-next;pre-next=q; /销毁链表 void Destroy(SLNode * *head)SLNode *p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);*head = NULL;/* 电梯动作： 1.开始开门,20t,开门结束; 2.开始关门,20t,关门结束; 3.从n-1层开始移动,30t,到达第n层; 4.开始等待,有人来或者300t,等待结束; 人的动作： 1.开始等待,xnext;pre=head;while(curr!=NULL)pre=curr;curr=curr-next; return pre-mytime;/电梯运行函数 void Go(SLNode *head,int n,dianti dt,clock_t s1000,man r1000) int k=0,i,time,m,flag=0,counter=0; /flag 记录是否有多个人在同一层或去同一层楼for(i=0;in;i+)if(dt.door=0) /初始电梯门状态为关着if(dt.lc=ri.lc&dt.rs12&ri.biaozhi=0&ri.in=0)/人在该楼层,要进去电梯,且电梯人数不超过规定的12人 if(i=0) time=si/100; /记录当时时间else time=gettime(head);if(flag=0&dt.door=0)OPEN(head,dt,time); /开门dt.door=1;if(time-si/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1;printf(n此时有人离开,以下为离开的人的信息:n); printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);time=gettime(head); /获得事件链表最后一个结点的时间(即当前时刻)if(dt.lc=ri+1.lc) flag=1;counter+;continue; /该层的所有人都进入电梯 else if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); /电梯经过40t时间后，若无人进出，则关门 dt.door=0; /置电梯门状态为关 g+; CLOSE(head,dt,time+40); /* 本层人已经全部进入电梯，接下来电梯启动按每个人事件发生的时间顺序将其送往目的楼层*/flag=0;if(dt.lc=ri-counter.md)time=gettime(head);while(dt.lc=ri-counter.md) /开往该层第一个人的目的楼层flag=0;if(dt.lcri-counter.md)dt.lc+;time+=30; for(m=0;mn;m+)if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12)/若该楼层有人等候，使其进入 if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; /电梯开门,并设置其门状态为开 if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1;printf(n此时有人离开,以下为离开的人的信息:n);printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);flag=1;/若该楼层有人要出去，使其出电梯，置其状态为1表示该人已经使用过电梯else if(dt.lc=rm.md&rm.biaozhi=0&rm.in=1) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1;time=gettime(head); GET_OUT(head,dt,time); rm.biaozhi=1;rm.in=0;flag=1;if(dt.lc=ri-counter.md) break;if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); /电梯经过40t时间后，若无人进出，则关门 dt.door=0; /置电梯门状态为关 g+; CLOSE(head,dt,time+40);time=gettime(head);if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40);dt.door=0; g+; CLOSE(head,dt,time+40);else if(dt.lc=ri-counter.md)time=gettime(head);while(dt.lc=ri-counter.md)flag=0;if(dt.lcri-counter.md)dt.lc-; /30t,电梯下降一层time+=30;for(m=0;mn;m+)if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12) /若该楼层有人等候，使其进入if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1; printf(n此时有人离开,以下为离开的人的信息:n);printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);flag=1;/若该楼层有人要出去，使其出电梯，置其状态为1表示该人已经使用过电梯else if(dt.lc=rm.md&rm.biaozhi=0&rm.in=1) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1;time=gettime(head); GET_OUT(head,dt,time); rm.biaozhi=1;rm.in=0;flag=1;if(dt.lc=ri-counter.md) break;if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40); time=gettime(head); if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40);i=i-counter; else if(dt.lc=ri.md&ri.biaozhi=0&ri.in=1) /人在电梯中,在该楼层要出去if(i=0)time=s0/100; else time=gettime(head);for(m=0;mn;m+)if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12) /若该楼层有人等候，使其进入if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1; printf(n此时有人离开,以下为离开的人的信息:n);printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);flag=1;/若该楼层有人要出去，使其出电梯，置其状态为1表示该人已经使用过电梯else if(dt.lc=rm.md&rm.biaozhi=0&rm.in=1) if(flag=0&dt.door=0)OPEN(head,dt,time); dt.door=1;time=gettime(head);GET_OUT(head,dt,time); rm.biaozhi=1;rm.in=0;flag=1;if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40);/1.if(dt.lc=ri.lc&dt.rs12&ri.biaozhi=0&ri.in=0) ,人在该楼层,要进去电梯/2.else if(dt.lc=ri.md&ri.biaozhi=0&ri.in=1),人在电梯中,在该楼层要出去/3.else if(dt.lc!=ri.lc&dt.rs12&ri.biaozhi=0&ri.in=0),人不在该楼层,要进去电梯 /4.else if(dt.lc!=ri.md&ri.biaozhi=0&ri.in=1),人在电梯里,该楼层不是其目的楼层else if(dt.lc!=ri.lc&dt.rs12&ri.biaozhi=0&ri.in=0) /3.人不在该楼层,要进去电梯 flag=0; if(i=0)time=s0/100; /以该事件发生的时间为起始时间else time=gettime(head); /取当前时间 if(dt.lc=ri.lc)while(dt.lc=ri.lc)flag=0;if(dt.lcri.lc)dt.lc+; time+=30; /30t,电梯上升一层for(m=0;mn;m+)/若该楼层有人等候，使其进入if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1; printf(n此时有人离开,以下为离开的人的信息:n); printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);flag=1;/若该楼层有人要出去，使其出电梯，置其状态为1表示该人已经使用过电梯else if(dt.lc=rm.md&rm.biaozhi=0&rm.in=1) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; time=gettime(head); GET_OUT(head,dt,time); rm.biaozhi=1; rm.in=0;flag=1;if(dt.lc=ri.lc) break;if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40); time=gettime(head);if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40);time=gettime(head);else if(dt.lc=ri.lc)while(dt.lc=ri.lc)flag=0;if(dt.lcri.lc)dt.lc-; time+=30;for(m=0;mn;m+)/若该楼层有人等候，使其进入if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1; printf(n此时有人离开,以下为离开的人的信息:n); printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,dt.lc);flag=1;/若该楼层有人要出去，使其出电梯，置其状态为1表示该人已经使用过电梯else if(dt.lc=rm.md&rm.biaozhi=0&rm.in=1) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; time=gettime(head); GET_OUT(head,dt,time); rm.biaozhi=1; rm.in=0;flag=1;if(dt.lc=ri.lc) break;if(dt.door=1)time=gettime(head); ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40); time=gettime(head);if(dt.door=1)time=gettime(head);ListInsert(head,g,该层已无人进出,关门,time+40); dt.door=0; g+; CLOSE(head,dt,time+40);/*接下来将电梯里的人按时间顺序送到各自的目的楼层*/time=gettime(head); if(dt.lc=ri.md&ri.in=1)while(dt.lc=ri.md)flag=0;if(dt.lcri.md)dt.lc+; time+=30;for(m=0;mn;m+)/若该楼层有人等候，使其进入if(dt.lc=rm.lc&rm.biaozhi=0&rm.in=0&dt.rs12) if(flag=0&dt.door=0)OPEN(head,dt,time);dt.door=1; if(time-sm/100)rm.rrsj)&rm.biaozhi=0)rm.biaozhi=1; printf(n此时有人离开,以下为离开的人的信息:n); printf(时间:%d(单位:t) 发生的事件超过用户的容忍时间,第%d层楼的人已经离去n,sm/100+rm.rrsj,