电梯模拟系统教学提纲.doc

精品文档
目录
一：问题描述—————————————————————————第2页

二：问题分析—————————————————————————第2页

三：数据结构—————————————————————————第2页

四：算法设计—————————————————————————第4页

五设计与调试分析———————————————————————第6页

六：体会及建议————————————————————————第7页

七：参考文献—————————————————————————第7页

八：原代码——————————————————————————第7页

一：问题描述
设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等“活动体”够成的集合，虽然他们彼此交互作用，但是他们的行为是基本独立的。在离散的模拟中，一模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一个时刻。

二：问题分析
（1）、模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层和第四层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来该层候命。五个楼层从下到上的编号为：0、1、2、3、4。除了地下层外，每一层都有一个要求向下的按钮除了第四层外，每一层都有一个要求向上的按钮。对应的变量为：CallUp[0..3]和CallDown[1..4]。电梯内的五个目标层按钮对应的变量为：CallCar[0..4]。
（2）、电梯一共有七个状态，即正在开门（Opening）、已开门（Opened）、正在关门（Closing）、已关门（Closed）、等待（Waiting）、移动（Moving）、减速（Decelerate）
（3）、 乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。对于在楼层内等待电梯的乘客，将插入在等候队列里，每一层有两个等候队列，一队要求向上，一队要求向下，用链队列来实现。对于在电梯内的乘客，用五个乘客栈来实现，该乘客要去哪一层，就把他放在相应编号的栈中，对应变量为EleStack[0…4]。
（4）、模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位（简记为t）：
有人进出时，电梯每隔40t测试一次，若无人进出，则关门
关门和开门各需要20t
每个人进出电梯均需要25t
电梯加速需要15t
如果电梯在某层静止时间超过300t，则驶回1层候命。
（5）、按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。
三：数据结构
1、 乘客类型
反映乘客的所有属性。
ADT Client
数据对象：D={ai∈乘客信息,I=1,2,…,n,n≥0}
数据关系：R={|ai-1,ai∈D,i=2,…,n}
基本操作：
PrintClientInfo(Client const &e,ClientStatus)
操作结果：输出乘客信息。
CreatClient(Client *&p)
操作结果：生成新的乘客。
DestoryClient(Client *&p)
操作结果：该乘客离开系统。
GoAbove(Client const &e)
操作结果：判断该乘客是否去往高层。
CInfloor(Client const &e)
操作结果：返回乘客进入的楼层。
CInTime(Client const &e)
操作结果：返回乘客进入时间。
COutfloor(Client const &e)
操作结果：返回乘客进入时间。
}
2、 乘客栈类型
电梯内的乘客用乘客栈表示，去不同楼层的乘客放在不同的栈中。
ADT Estack
数据对象：D={ai∈乘客信息,I=1,2,…,n,n≥0}
数据关系：R={|ai-1,ai∈D,i=2,…,n}
基本操作：
略。
}
3、 等候队列类型
在电梯外等待的乘客用等待队列表示。每层各有两个等待队列，分别为上楼队列和下楼队列。
与一般队列不同的是在基本操作中加入了放弃操作CGiveUp(WQueue &Q,int floor)。
4、 电梯类型
表示电梯的各个属性和所有动作。
ADT Elevator
数据对象：D={ai∈电梯信息,I=1,2,…,n,n≥0}
基本操作：
InitEle(Elevator &E)
操作结果：初始化电梯类型。
DestoryEle(Elevator &E)
操作结果：销毁电梯类型。
EleDecide(Elevator &E,WQueue w[Maxfloor+1][2])
操作结果：电梯动作决策。
ElevatorRun(Elevator &E,WQueue w[Maxfloor+1][2]){
操作结果：电梯状态转换。
CountOver(Elevator &E)
操作结果：判断电梯计时是否完成。
EleFloor(Elevator const &E)
操作结果：返回电梯所在的层。
EleStatus(Elevator const &E)
操作结果：返回电梯状态。
RequireAbove(Elevator const E)
操作结果：判断是否有高层请求。
RequireBelow(Elevator const &E)
操作结果：判断是否有低层请求。
EleAchieved(Elevator &E)
操作结果：判断电梯是否要停于当前层。
EleOpenDoor(Elevator &E)
操作结果：判断电梯是否要开门。
}
5、 高楼模块
实现电梯和乘客之间的互交功能。包括：
InOut(Elevator &E,WQueue w[Maxfloor+1][2])
操作结果：进行乘客的进出电梯活动。
NewClient(Elevator &E,WQueue w[5][2])
操作结果：进入新乘客。
PrintStatus(Elevator &E,WQueue w[5][2])
操作结果：输出当前状态。
Print(Elevator &E,Action a)
操作结果：输出电梯动作信息。

四：算法设计
1：本程序包含6个模块：
（1） 主程序模块
（2） 乘客模块
（3） 乘客栈模块
（4） 电梯模块
（5） 等待队列模块
（6） 高楼模块：实现电梯和乘客之间的互交。
各模块之间的调用关系如下：
主程序
电梯模块
乘客栈模块
等待队列模块
乘客模块
高楼模块

2：主程序
主程序主要处理两类事件：乘客事件和电梯事件。除此之外，主程序还处理各个模块的初始化和销毁工作，以及电梯状态的输出。乘客事件包括新乘客到达事件，乘客放弃等待事件，乘客进出电梯事件。电梯事件包括电梯运行事件。
3：详细设计
#define NULL 0 //空指针
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define INT_MAX 32767
//Status是函数类型，其值是函数结果状态代码
typedef int Status;

#define Empty 0
//------------------------------------------------------
//电梯状态
enum EleStatus{Opening,Opened,Closing,Closed,Moving,Decelerate,Waiting};
enum Action{DoorOpened,DoorClosed,GoingUp,GoingDown,Achieved,None};
enum EleStage{Up,Down,OpenDoor,Stop};
enum ClientStatus{New,GiveUp,In,Out,Finish};

#define CloseTest 40 //电梯关门测试时间
#define OverTime 300 //电梯停候超时时间
#define DoorTime 20 //开门关门时间
#define InOutTime 25 //进出电梯时间
#define Maxfloor 4 //最高层
#define Minfloor 0 //最低层

long Time=0; //时钟
long MaxTime;//系统运行最长时间
int InOutCount=0;//用于进出计时
int InterTime=0;//下一乘客进入系统的时间
int ID=0; //乘客编号
int GiveUpNumber=0;//乘客放弃的数目
int TotalTime=0;//总共等待时间
部分重要操作的算法：
1、判断运动方向函数EleDecide的算法：
2、统计高层和低层的请求（不包括当前层）。
3、高层和低层均无请求：发出Stop命令。
4、否则，
1）若电梯在上升期：
1. 若有高层请求：上升；
2.若无高层请求：转下降期，下降。
2）若电梯在下降期：
1. 若有低层请求：下降；
2. 若无有低层请求：转上升期，上升。
判断电梯是否要停于当前层函数EleAchieved的算法：
1. 该层的CallCar为1；
2. 该层在上升（下降）期有上升（下降）请求（判断CallUp或CallDown）；
3. 上升（下降）期高（低）层没有请求而该层由下降（上升）请求，要转换运行时期。
判断电梯动作函数ElevatorRun的算法：
1. 若电梯在Opening状态，则转至Opened状态。
2. 若电梯在Opened状态，若无人进出，则转至Closing状态。
3. 若电梯在Closed状态，则根据电梯请求情况转至相应状态。
4. 若电梯在Closing状态，则转至Closed状态。
5. 若电梯在Moving状态，若达到目标层，则转至Decelerate状态。否则，继续移动。
6 若电梯在Decelerate状态，则设定电梯时期，并转至Opening状态。
7. 若电梯在Waiting状态，在判断是否等待超时，若超时则向第一层移动。否则，判断电梯请求情况并转至相应状态。
五： 设计与调试分析
在本程序中如何判断电梯的动作最为关键。此外，合理划分各个模块和处理各个模块之间的联系也非常重要。
在电梯调度方面不能按照预定的想法实现，所以和现实中的电梯有出入。没有显示电梯的运行到哪里，而是用有乘客进入电梯时显示乘客进入到哪层楼来告知电梯运行到几楼。开门，关门时需要精心思考，此处记时及判断是否要开门也是难点，所以这些看似很平常的动作却是最难也是最容易错的地方。此外在指针的使用方面也是难点，很多地方比如乘客进队出队以及放弃乘坐电梯时均涉及指针的使用，也经常在这些地方通不过编译。为了便于控制循环，设计了电梯运行时间，则在时间到达时即可退出系统。由于开始为了简化程序而定义了很多变量，结果发现并不实际，有的变量仅是在某些函数中赋予其值罢了，于是就将这些变量删除，比如开始按照提示设置了D1—表示人们正在进出电梯等等。

六：体会及建议

我们应重视编程思想的培养，语言很重要，但究竟只是工具，思想才是精髓。通过阅读书中的各种数据结构及相应算法的代码来吸收书中的思想。我们可以利用各种途径来学习认识一种功能的实现，但是最终的串联编写还是应该靠自己的思路去不断完善，在这段时间中我们有充分的时间去了解我们完成任务所需的知识内容，而我们也应该去认真完成。

在这阶段的设计过程中，编写时总是出现原来未曾遇到过的各种错误，很难解决，常常受到很长时间的困扰，虽然这属于纯粹的个人能力体现，属于自学运用，但老师并不能在有问题时及时给与有效建议。而我们的所学有限，考虑问题不是很全面，解决问题也总是难以有高效的解决方案只能通过不断的实践去比较结果。
七：参考文献
1：严蔚敏等 数据机构（C语言版） 清华大学出版社
2：谭浩强 C语言程序设计 清华大学出版社
八：原代码
#include
#include stream.h>
#include
#include
#include
#include
#include

//所有常量，全局变量和类型定义
#define NULL 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define INT_MAX 32767
//Status是函数类型，其值是函数结果状态代码
typedef int Status;

#define Empty 0
//电梯状态
enum EleStatus{Opening,Opened,Closing,Closed,Moving,Decelerate,Waiting};
enum Action{DoorOpened,DoorClosed,GoingUp,GoingDown,Achieved,None};
enum EleStage{Up,Down,OpenDoor,Stop};
enum ClientStatus{New,GiveUp,In,Out,Finish};

#define CloseTest 40 //电梯关门测试时间
#define OverTime 300 //电梯停候超时时间
#define DoorTime 20 //开门关门时间
#define InOutTime 25 //进出电梯时间
#define Maxfloor 4 //最高层
#define Minfloor 0 //最低层

long Time=0; //时钟
long MaxTime;//系统运行最长时间
int InOutCount=0;//用于进出计时
int InterTime=0;//下一乘客进入系统的时间
int ID=0; //乘客编号
int GiveUpNumber=0;//乘客放弃的数目
int TotalTime=0;//总共等待时间
//乘客类型
typedef struct {
int ClinetID; //乘客编号
int Outfloor; //去哪层
int InTime; //该乘客进入时间
int GivepuTime; //所能容忍的等待时间
int Infloor;//乘客进入的楼层
}Client;
//乘客类型基本操作
void PrintClientInfo(Client const &e,ClientStatus s)
{
switch(s) {
case New: printf("\t%d号乘客进入第%d层.\n",e.ClinetID,e.Infloor);break;
case GiveUp: printf("\t%d号乘客放弃等待.\n",e.ClinetID);break;
case Out: printf("\t%d号乘客走出电梯.\n",e.ClinetID);break;
case In:printf("\t%d号乘客走进电梯，要去第%d层.\n",e.ClinetID,e.Outfloor);break;
default:break;
};
}

Status CreatClient(Client p)
{
int d;
p=new Client;
if(!p) return OVERFLOW;
p->ClinetID=++ID;
printf("%d所能容忍的等待时间:",ID);
scanf("%d",&d);
p->GivepuTime=d;
p->InTime=Time;
printf("下一乘客要到达的时间:");
scanf("%d",&d);
InterTime=d;
printf("所要到达的楼层:");
scanf("%d",&d);
p->Outfloor=d;
while((p->Infloor=rand()%(Maxfloor+1))==p->Outfloor);
PrintClientInfo(*p,New);
return OK;
}

Status DestoryClient(Client *&p)
{
delete p;
p=NULL;
return OK;
}
Status GoAbove(Client const &e)
{
if(e.Outfloor>e.Infloor) return TRUE;
else return FALSE;
}
Status CInfloor(Client const &e)
{
return e.Infloor;
}
Status CInTime(Client const &e)
{
return e.InTime;
}
Status COutfloor(Client const &e)
{
return e.Outfloor;
}
#define STACK_INIT_SIZE 10 //存储空间初始分配量
#define STACKINCREMENT 5 //存储空间分配增量
//乘客栈
typedef Client *SElemType;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}ClientStack;

Status InitStack(ClientStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.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;pelse return FALSE;
}
Status StackLength(ClientStack S)
{
return S.top-S.base;
}
Status GetTop(ClientStack S,SElemType &e)
{
if(!S.base) return ERROR;
e=*(S.top-1);
return OK;
}
Status Push(ClientStack &S,SElemType e)
{
if(!S.base) return ERROR;
if(S.top-S.base>=S.stacksize) {
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return OVERFLOW;
S.top=S.base+S.stacksize;
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(iClinetID<<' ';
}
//电梯类型
typedef struct {
int floor; //电梯所在层
int ClientNumber;//电梯内人数
EleStatus status; //电梯当前状态
EleStage Stage; //电梯运行时期
int Count;//用于电梯计时
int CallUp[Maxfloor+1];//每层的Up按钮
int CallDown[Maxfloor+1];//每层的Down按钮
int CallCar[Maxfloor+1];//电梯内的目标层按钮
ClientStack S[Maxfloor+1];//乘客栈,要去不同楼层的人放在不同的栈中
}Elevator;
//电梯类型基本操作
void InitEle(Elevator &E)
{
int i;
E.floor=1;
E.status=Waiting;E.Count=OverTime;
E.Stage=Down;
E.ClientNumber=0;
for(i=0;i<=Maxfloor;i++)
{
E.CallUp[i]=0;E.CallDown[i]=0;E.CallCar[i]=0;
}
for(i=0;i<=Maxfloor;i++) InitStack(E.S[i]);
}
Status CountOver(Elevator &E)
{
if(E.Count) {
E.Count--;return FALSE;
}
return TRUE;
}
void DestoryEle(Elevator &E)
{
int i;
for(i=0;i<=Maxfloor;i++) DestroyStack(E.S[i]);
}
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<=Maxfloor;i++)
if(E.CallCar[i]||E.CallDown[i]||E.CallUp[i]) return TRUE;
return FALSE;
}
Status RequireBelow(Elevator const &E)
{
for(int i=E.floor-1;i>=Minfloor;i--)
if(E.CallCar[i]||E.CallDown[i]||E.CallUp[i]) return TRUE;
return FALSE;
}
Status EleAchieved(Elevator &E)
{
if(E.CallCar[E.floor]) return TRUE;
if(E.Stage==Up&&E.CallUp[E.floor]||E.Stage==Down&&E.CallDown[E.floor])
return TRUE;
if(E.Stage==Up&&E.CallDown[E.floor]&&!RequireAbove(E))
{
E.Stage=Down;return TRUE;
}
if(E.Stage==Down&&E.CallUp[E.floor]&&!RequireBelow(E))
{
E.Stage=Up;return TRUE;
}
return FALSE;
}
Status EleOpenDoor(Elevator &E)
{
if(E.CallCar[E.floor]||E.CallDown[E.floor]&&E.Stage==Down||E.CallUp[E.floor]&&E.Stage==Up)
return TRUE;
if(E.status==Waiting) {
if(E.CallDown[E.floor]) {E.Stage=Down;return TRUE;}
if(E.CallUp[E.floor]) {E.Stage=Up;return TRUE;}
}
return FALSE;
}
EleStage EleDecide(Elevator &E)
{

int Above,Below;
Above=RequireAbove(E);
Below=RequireBelow(E);
if(Above==0&&Below==0) return Stop;
else {
if(E.Stage==Up) {
if(Above!=0) return Up;
else {
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 Opening:
E.status=Opened;E.Count=CloseTest;
return DoorOpened;
case Opened:
if(E.Stage==Down&&!E.CallCar[E.floor]&&!E.CallDown[E.floor]||
E.Stage==Up&&!E.CallCar[E.floor]&&!E.CallUp[E.floor])
{ E.status=Closing;E.Count=DoorTime;} break;
case Closing:
E.status=Closed;
return DoorClosed;
case Waiting:
if(E.Count==0) {
if(E.floor!=1) E.CallCar[1]=1;
}
else E.Count--;
if(EleOpenDoor(E)) {
E.status=Opening;E.Count=DoorTime;break;
}
case Closed:
break;
case Moving:
//完成移动
if(E.Stage==Up) E.floor++;
else E.floor--;
return Achieved;
E.status=Opening;E.Count=DoorTime;
break;
};
return None;
}
//单链队列——队列的链式存储结构
typedef Client *QElemType;
//等候队列
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}WQueue;
//等待队列的基本操作
Status InitQueue(WQueue &Q)
{
Q.front=Q.rear=new QNode;
if(!Q.front) return OVERFLOW;
Q.front->next=NULL;
Q.front->data=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.rearp;
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;

else 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==0&&floor!=p->next->data->Infloor)
{
PrintClientInfo(*(p->next->data),GiveUp);
TotalTime+=Time-CInTime(*(p->next->data));
QDelNode(Q,p);
GiveUpNumber++;
}
else p->next->data->GivepuTime--;
return OK;
}

void PrintQueue(WQueue Q)
{
QueuePtr q;
int count=0;
if(Q.front->next==NULL) goto end;
q=Q.front->next;
while(q!=NULL)
{
cout<data->ClinetID<<' ';
q=q->next;
count++;
}
end:
while(count++<=4) cout<<" ";
}

void InOut(Elevator &E,WQueue w[Maxfloor+1][2])
{
Client *p;
if(E.CallCar[E.floor])
if(StackEmpty(E.S[E.floor])) E.CallCar[E.floor]=0;
else
{
Pop(E.S[E.floor],p);E.ClientNumber--;
InOutCount=InOutTime;
PrintClientInfo(*p,Out);
TotalTime+=Time-CInTime(*p);
DestoryClient(p);
}
if(E.CallCar[E.floor]==0)
if(!QueueEmpty(w[E.floor][E.Stage]))
{
DeQueue(w[E.floor][E.Stage],p);
Push(E.S[COutfloor(*p)],p);
if(E.CallCar[COutfloor(*p)]!=1)
{
E.CallCar[COutfloor(*p)]=1;
}
E.ClientNumber++;
InOutCount=InOutTime;
PrintClientInfo(*p,In);
}
else
{
if(EStage==Down) E.CallDown[E.floor]=0;
else E.CallUp[E.floor]=0;
}
}

void NewClient(Elevator &E,WQueue w[5][2])
{
Client *p;
CreatClient(p);
if(GoAbove(*p))
{
EnQueue(w[CInfloor(*p)][Up],p);E.CallUp[CInfloor(*p)]=1;
}
else
{
EnQueue(w[CInfloor(*p)][Down],p);E.CallDow