数据结构课程设计报告
学号:******
班级:******
姓名:******
指导老师:******
日期:2015
题号 题目:电梯模拟
1.需求分析
模拟某校九层教学楼的电梯系统。该楼有一个自动电梯,能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、……第八层,其中第一层是大楼的进出层,即是电梯的“本垒层”,电梯“空闲”时,将来到该层候命。
乘客可随机地进出于任何层。对每个人来说,他有一个能容忍的最长等待时间,一旦等候电梯时间过长,他将放弃。
模拟时钟从0开始计时,时间单位t=0.1秒。人和电梯的各种动作均要消耗一定的时间单位,规定:有人进出时,电梯每隔40t测试一次,若无人进出,则关门;关门和开门各需要20t;每个人进出电梯均需要25t;如果电梯在某层静止时间超过300t,则驶回1层侯命。
电梯调度规则:
l 就近原则:电梯的主要调度策略是首先响应沿当前行进方向上最近端的请求直到满足最远端请求。若该方向上无请求时,就改变移动方向。
l 在就近原则无法满足的情况下,首先满足更高层的请求。
l 电梯的最大承载人数为12人,电梯人数达到12人后,在有人出电梯之前,不接受进入电梯的请求。
l 乘客上下电梯时先出后进。出电梯的时间固定是25t(与人数无关),进电梯时乘客是按队列的顺序依次进入,每次只能进入一人且每个人花费的时间都为25t。
l 电梯在关门期间(电梯离开之前)所在层提出请求的乘客同样允许进入。
l 电梯的运行速度为2t/层。
【基本要求】
根据提供的文本文档(包含随机的乘电梯人数),通过自己编的程序读取文件,获得乘电梯的需求,按时序输出系统状态的变化过程,即发生的全部人和电梯的动作序列。
【选作内容】
电梯模似器具有一个简单的图形用户界面。用动画显示电梯的升降,人进出电梯。设计有下列对象:电梯、人、电梯控制板及其上各种按钮、定时器等。
【实现提示】
每层设置一个队列,用来存储从文件中读取的当前层的乘客信息,并按时间的先后顺序进行排序。
附:测试数据(以txt文档读取)
2.设计
2.1 设计思想
(1)数据与操作的特性
模拟电梯,以实际生活中的电梯为参考,应有两个对象:电梯、乘客。对于人这一对象,应包含乘客自身的信息;对于电梯这一对象,应具备添加乘客、删除乘客、访问乘客信息(获取乘客的去向等)、上升、下降、开关门等基本操作来实现相应的功能。此外,对于等候在电梯外面的乘客队列,应有添加乘客、删除乘客(进入电梯或等待超时离开)、获取乘客信息(如到达时间等)等基本操作以实现相应的功能。
整个系统运行的时间是以电梯的运作为轴,往前推进,知道服务完成,返回本垒层候命,此时程序结束(当然,理论上程序是无期限地执行下去);系统的空间开发与电梯层数、乘客人数成正比,电梯层数确定后,空间开发便与请求服务的乘客数有关,并处于动态开发(“人来人去”,空间的开辟与释放是动态的)。
可见,时空的要求不是特别紧迫,资源的开发不会很大,效率也会有所保证。
(2)数据结构设计
由(1)中的数据与操作的特性分析,应用类与对象、抽象数据类型(ADT)的设计思想,下面详细说明这两点。
电梯与乘客都设计为类,其操作涉及到队列、链表的数据结构。对于乘客,每层设置一个队列,用来存储从文件中读取的当前层的乘客信息,并按先来后到的顺序进行排序。对于电梯里面的乘客,我是用一个链表来存储的。且这些数据结构均采用抽象数据类型,在使用的时候生成需要的实例。
涉及的数据结构:
这两种数据结构大体上是相同的,只是操作上有所!他们的逻辑结构与物理结构图示如下:
电梯类以及相应的功能函数:
乘客类以及相应的功能函数:
(3)算法设计
系统的总体设计思路:
首先,在电梯运作这一模块,“三个已知”才能保证电梯的正常运作,“三个已知”分别是:电梯当前楼层、电梯运作方向(U、D表示,分别为上、下)以及有请求的楼层。因为电梯调度是这样的(以例子来说明):假如当前电梯方向是向上,那么电梯就会在该方向上一直,碰到请求层则服务,服务完继续向上,直到某一层,当且仅当该层以上的楼层没有请求(请求包括上电梯请求和下电梯请求),电梯才会停止(当下面也没有请求时)或者换方向向下运行(下方有请求);向下的情形跟向上是一样的。所以,电梯调度算法的一个重要“已知”就是其运作方向,应一直有所记录。
其次,电梯里面的乘客这一模块,我记录在一个单独的链表里,电梯类的数据成员里只记录该链表的大小(即为梯内人数),而没有乘客这一对象。
此外,等候在每层的乘客,均存储在每层的等待队列之中。
系统的信息交流:
电梯与乘客链表(记录梯内乘客)之间发生的信息交流就是乘客数以及程序去向楼层这些数据;乘客链表与等待队列之间发生的信息交流是有人进电梯时,将该人添加到乘客链表中并从等待队列中删除;电梯与等待队列之间发生的信息交流是电梯当前楼层与相应楼层的等待队列之间的对应关系。它们之间相互联系,以保证系统的正常运转,均不可或缺!
主要算法基本思想:
整个系统以电梯的状态转换来达成目标,我把电梯分为四个状态,分别为:UP、DOWN、WAIT、CLOSED,即为上升、下降、等待、已关门,他们之间的状态变迁以及各自状态下调用相应的函数所做的工作如下图所示:
主程序流程图如下:
2.2 设计表示
(1)函数调用关系图
首先,我的工程的文件结构如下图所示。其中,LinList.h和LinQueue.h是单链表和链式队列的头文件(均是ADT设计),里面包含对链表和队列的相关操作函数;List.h和Man.h是电梯和乘客的头文件,里面有电梯、乘客相关的属性和相应的操作,在前面已经给出他们的类定义,可以清楚地看到这些。Init.h头文件则主要是些支撑电梯系统的正常运作的函数,比如open()、close()、up()、down()等等,Init.h中各自的函数调用关系:主要有五个骨架函数支撑电梯的运作,如下所示。
(2)函数接口规格说明
这上面的五个骨架函数之间联系密切,相互有调用的情形(比如刷新请求的函数,在时间流逝的过程中不断地有调用)。其余的属于类的函数,即链表类、队列类、电梯类、乘客类这些类内的公有成员函数是整个系统的接口函数,各自对相应的对象进行操作,来服务于主程序。其相应的定义及注释在本报告2.1(2)处有详细的说明,此处不再累述。
2.3 详细设计
根据主程序流程示意图,这里我主要说明一下保证电梯正常运作的五个骨架函数。
up()函数:
电梯上行。函数内实现时间的流逝(伴随着刷新请求)、电梯层数加一,最后置电梯状态为WAIT,置方向状态为U。
down()函数:
电梯下行。函数内实现时间的流逝(伴随着刷新请求)、电梯层数加一,最后置电梯状态为WAIT,置方向状态为D。
up()与down()函数是一样的(大同小异),下面是up()函数的实现:
__________________________________________________________________________
void up(){ //电梯上升一层楼(要用2t时间)
int f=list.GetFloor(); //获取电梯当前楼层
cout<<"在"<<NowTime<<"t时刻 "<<"电梯上行(在F"<<f<<" 到 F"<<f+1<<"之间)"<<endl;
NowTime++; //时间一增加
refreshReq(); //就要刷新电梯的请求数组
cout<<"在"<<NowTime<<"t时刻 "<<"电梯上行(在F"<<f<<" 到 F"<<f+1<<"之间)"<<endl;
NowTime++;
refreshReq();
list.SetFloor(f+1); //楼层数加一
list.SetState(WAIT); //上完一层,电梯运行状态转换为WAIT
list.SetDire(U); //方向状态置U
}
__________________________________________________________________________
wait()函数:
每当到达某楼,便调用。其内部工作流程如下:
无
有
wait()函数内部工作流程
closed()函数:
电梯处在某层的时候,该函数做了大量的工作。主要功能是由“三个已知”来决定电梯的运作。下面以流程图的形式进行说明。
有
无
如果为U(D的情形与之是类似的)
有 无
有 无
(超时等待则驳回本垒层,结束程序)closed()函数部工作流程
wait()和closed()的实现类似于上面列出的up()函数那样,依照上面分析的流程,不断地进行判断、处理,很容易写出其代码,在此不再列出它们的代码实现(本册附录有程序代码,里面有相应的代码及解释)。
3.调试分析
这个电梯模拟的工程相对来说还是比较复杂的,我在编写代码的时候,始终有一个习惯,就是每当完成一个小模块儿,就调试一下,有问题就马上处理掉,在不断地“编辑-编译-调试-修改”的循环过程中,始终对程序有整体上的把握,编写起来就比较轻松了。在调试的过程中,问题也是不断地发生,有像掉了“;”、括号不匹配、局部变量重定义等等很简单容易忽视也容易发现的错误,在此就不列出这类错误了。另外有些错误是调试通过,但结果错误的错误,这类“错误”对程序本身而言不是错误,但对编程者来说,是错误,这种错误不易发现,下面列出几点我出现过的这类错误:
(1)void open(){//电梯开门
int f=list.GetFloor(); //获得当前楼层
for(int i=0;i<20;i++){ //开门用时20t
cout<<"在"<<NowTime<<"t时刻 "<<"电梯正在开门(在F"<<f<<")"<<endl;
NowTime++;
}
refreshReq();//开门后,刷新请求数组
}
错误:在20t的开门操作之后,再刷新电梯的请求数组。
修改:在整个系统的运作过程中,时间这个维度一但有变,则就刷新请求。“请求伴随时间的变化而刷新”。应将refreshReq()语句放在for()循环的NowTime++的后面。上述的错误会导致电梯对楼层的乘客请求不能立刻响应。其他任何地方有NowTime++的语句的,必然应有refreshReq()语句与之匹配。
(2)for(int i=0;i<in_list.Size();i++){ //下电梯
if(in_list.GetData(i).GetTo() == f){ //该人去往楼层等于该楼层,则该人下电梯
cout<<"在"<<NowTime<<"t时刻 "<<in_list.GetData(i).GetNum()<<"号乘客出电梯(在F"<<f<<")"<<endl;
in_list.Delete(i); //在电梯内人链表中删除下电梯的人
list.SetMan(list.GetMan()-1); //电梯人数减一
}
}
上面的in_list是一个链表,存放的是电梯里面的乘客,上面的功能是实现“乘客下电梯操作”,链表中的乘客一个一个地判断其去往楼层是否等于电梯所在楼层,若是,则删除该人。但上面的代码在我调试的过程中,出现了该下的乘客却没下的情况。究其原因,跟链表的特性有关,链表在删除第i个元素的时候,如果原先有第i+1的元素,那么删除第i个元素后,第i+1个元素就变成了第i个元素,而程序中的for()循环执行了i++,要么导致第i+1个元素该删没有删,要么会导致参数越界的错误。解决办法是在list.SetMan(list.GetMan()-1)语句后加上i--语句。
此外,break语句在多层循环体中使用,只会结束其所在循环体的结束,外部循环并未结束,这一点也导致我一些错误。
算法的时空复杂度分析:系统的空间开发与电梯层数、乘客人数成正比,电梯层数确定后,空间开发便与请求服务的乘客数有关,并处于动态开发(“人来人去”,空间的开辟与释放是动态的)。可见,时空的要求不是特别紧迫,资源的开发不会很大,效率也会有所保证。
4.用户手册
该系统的使用十分简单,与实际生活中的电梯是类似的。用户只需要在程序指定路径下建立相应的txt文件(也可以自己修改程序指定的路径),文件中的内容按指定格式,放置数据,如:
txt文件中内容的格式
然后直接运行程序即可。运行结果是每一时刻,电梯系统的情况。
5.测试数据及测试结果
用上面的数据作测试,测试结果截图如下(部分截图):
测试数据的程序结果部分截图(一)
测试数据的程序结果部分截图(二)
测试数据的程序结果部分截图(三)
6.源程序清单
下面按有图所示的文件结构,一次列出
程序的源代码:
/*Elevator.cpp*/
#include "Init.h"
int main(){
readFile();//读文件
while(1){
states sta=list.GetState();//获得电梯当前状态
switch(sta){
case CLOSED: closed();break;
case UP: up();break;
case DOWN: down();break;
case WAIT: wait();break;
}
}
return 0;
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*Init.h*/
#include"List.h"//电梯头文件
#include"Man.h"//人头文件
#include"LinQueue.h"//等待队列
#include"LinList.h"//电梯内的人链
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int NowTime=0;//系统的时间
int WaitTime=0;//用于记录无人请求时间;超过300t,电梯驳回本垒层
int TestTime=0; //电梯有人进出时进行检测的计时器
int count=0; //帮助电梯有人进出时进行检测的变量
List list;//电梯(默认初始状态在本垒层等待)
LinList<Man> in_list;//电梯内的人的链表
LinQueue<Man> wait_queue[FLOORS];//FLOORS个空队列(每层一个队列,用于存储当前层的乘客信息)
void readFile(){//读文件,以初始化等待队列
ifstream ifile;
ifile.open("d:\\myfile.txt");
char c;
while(ifile.get(c)){
if(c=='\n') break;//跳过第一行
}
while(1){
Man man;
int a,b,c,d;//分别为人的编号、来自楼层、去往楼层、来到时间
ifile>>a>>b>>c>>d;
man.Assign(a,b,c,d);
int from=man.GetFrom();//得到该人的来自楼层
wait_queue[from].Append(man);//将其填入相应楼层的等待队列
if(ifile.eof() != 0) break;//文件读完,退出
}
ifile.close();
}
void refreshReq()//刷新电梯的请求数组
{
for(int i=0;i<FLOORS;i++){//检测各等待队列是否有请求
//队列非空且队头元素来到时间等于当前时间,则该层发出请求
if(wait_queue[i].NotEmpty()){//非空才有可能有请求
int size=wait_queue[i].Size();
for(int j=0;j<size;j++){
if(wait_queue[i].GetData(j).GetArrival() == NowTime){
cout<<"在"<<NowTime<<"t时刻 "<<wait_queue[i].GetData(j).GetNum()<<"号乘客发出请
求"<<"(F"<<i<<" -> "<<"F"<<wait_queue[i].GetData(j).GetTo()<<")"<<endl;
list.SetReque(i,true);//将电梯的相应楼层的请求数组置true(模拟每来一个人,按一下电梯)
}
}
}
}
for(i=0;i<in_list.Size();i++){//检测电梯内人链表的去往楼层来刷新服务请求
int to=in_list.GetData(i).GetTo();
list.SetReque(to,true);//将电梯的相应楼层的请求数组置true
}
}
void up(){//电梯上升一层楼(要用2t时间)
int f=list.GetFloor();//获取电梯当前楼层
cout<<"在"<<NowTime<<"t时刻 "<<"电梯上行(在F"<<f<<" 到 F"<<f+1<<"之间)"<<endl;
NowTime++;//时间一增加
refreshReq();//就要刷新电梯的请求数组
cout<<"在"<<NowTime<<"t时刻 "<<"电梯上行(在F"<<f<<" 到 F"<<f+1<<"之间)"<<endl;
NowTime++;//电梯的已经上完了一层
list.SetFloor(f+1);//楼层数加一
refreshReq();
list.SetState(WAIT);//上完一层,电梯运行状态转换为WAIT
list.SetDire(U);//方向状态置U
}
void down(){//电梯电梯下降一层楼
int f=list.GetFloor();
cout<<"在"<<NowTime<<"t时刻 "<<"电梯下行(在F"<<f<<" 到 F"<<f-1<<"之间)"<<endl;
NowTime++;
refreshReq();
cout<<"在"<<NowTime<<"t时刻 "<<"电梯下行(在F"<<f<<" 到 F"<<f-1<<"之间)"<<endl;
NowTime++;//电梯的已经上完了一层
list.SetFloor(f-1);//楼层数减一
refreshReq();
list.SetState(WAIT);
list.SetDire(D);//方向状态置D
}
void open(){//电梯开门
int f=list.GetFloor();//获得当前楼层
for(int i=0;i<20;i++){
cout<<"在"<<NowTime<<"t时刻 "<<"电梯正在开门(在F"<<f<<")"<<endl;
NowTime++;
refreshReq();
}
}
void close(){//电梯关门(与开门相反)
int f=list.GetFloor();
for(int i=0;i<20;i++){
cout<<"在"<<NowTime<<"t时刻 "<<"电梯正在关门(在F"<<f<<")"<<endl;
NowTime++;
refreshReq();
}
}
void in(){
int f=list.GetFloor();
count=0;
if(wait_queue[f].NotEmpty()){//该楼等待队列非空,才可能有人上电梯(注意:有可能连续有人上电梯)
while(1){
if(wait_queue[f].NotEmpty()){
int t = wait_queue[f].GetFront().GetArrival();//取队头的到达时间
if(t>NowTime) break;//队头到达时间大于系统当前时间,则无人上电梯,退出
}
else{//等待队列已空,则无人上电梯,退出
break;
}
bool IsIn=false;//记录是否有人进电梯
int t = wait_queue[f].GetFront().GetArrival();//取队头的到达时间
if(NowTime-t > MAX_WAIT_TIME){//等待时间大于最大忍受时间,则该人离开
cout<<"在"<<NowTime<<"t时刻 "<<wait_queue[f].GetFront().GetNum()<<"号乘客由于超
过最大等待时间已离开"<<endl;
wait_queue[f].Delete();//从队列中删除已离开的人
}
else{//等待时间小于等于最大忍受时间,则该人离开队头进入电梯
if(list.GetMan() == LOAD){//超载
cout<<"在"<<NowTime<<"t时刻 "<<"对不起!由于电梯人数已达上限,请稍等!(在
F"<<f<<")"<<endl;
break;
}
else{//没超载,上之
cout<<"在"<<NowTime<<"t时刻 "<<wait_queue[f].GetFront().GetNum()<<"号乘客进电梯
(在F"<<f<<")"<<endl;
count++;
if(count == 1) TestTime=NowTime;//队头人进,启动检测装置
in_list.Add(wait_queue[f].GetFront());//添加到电梯内人链表
list.SetMan(list.GetMan()+1);
wait_queue[f].Delete();//从队列中删除已进入电梯的人
IsIn=true;
}
}
if(IsIn){//有人上电梯,时间流逝25t
for(int i=0;i<25;i++){//进电梯每人用25t时间
NowTime++;
refreshReq();
if((NowTime-TestTime)%40==0){
cout<<"在"<<NowTime<<"t时刻 "<<" 电梯检测(在F"<<f<<"),"<<"不能关
门!"<<endl;
}
cout<<"在"<<NowTime<<"t时刻 "<<" 乘客进电梯(在F"<<f<<")"<<endl;
}
}
}
}//电梯在该层的“进出”服务至此完成
}
void wait(){
int f=list.GetFloor();//获得电梯当前楼层
if(!list.GetReque()[f] ) list.SetState(CLOSED);//若该层无请求,则不理会该层
else{//该层有请求,便开门服务(先下后上)
open();//电梯开门;
/*下电梯*/
bool IsOut=false;//记录是否有人下电梯
for(int i=0;i<in_list.Size();i++){//下电梯
if(in_list.GetData(i).GetTo() == f){//该人去往楼层等于该楼层,则该人下电梯
cout<<"在"<<NowTime<<"t时刻 "<<in_list.GetData(i).GetNum()<<"号乘客出电梯(在
F"<<f<<")"<<endl;
in_list.Delete(i);//在电梯内人链表中删除下电梯的人
list.SetMan(list.GetMan()-1);
i--;//由于链表删除元素,i值应减一,才不会导致链表中有人未检测到
IsOut=true;
}
}
if(IsOut){//下电梯统一用25t时间
for(i=0;i<25;i++){
NowTime++;
refreshReq();
cout<<"在"<<NowTime<<"t时刻 "<<" 乘客出电梯(在F"<<f<<")"<<endl;
}
}
in();//上电梯
list.SetReque(f,false);//该楼层请求取消
while(1){
NowTime++;
refreshReq();
if((NowTime-TestTime)%40==0){
if(!list.GetReque()[f]){
cout<<"在"<<NowTime<<"t时刻 "<<" 电梯检测(在F"<<f<<"),"<<"可以关门!"<<endl;
close();//关门
list.SetState(CLOSED);//状态转换至CLOSED
break;
}
else cout<<"在"<<NowTime<<"t时刻 "<<" 电梯检测(在F"<<f<<")"<<endl;
}
if(list.GetReque()[f]){
in();//上之
}
}
}
}
void closed(){
int f=list.GetFloor();//获得电梯当前楼层
if(list.GetReque()[f]) list.SetState(WAIT);//检测到该层有请求,状态转换至WAIT
else{//该层无请求,测其上、方
direct dir=list.GetDire();//获得电梯方向状态
switch(dir){
case U:{
bool up_req=false;//该层上方是否有请求
for(int i=FLOORS;i>f;i--){
up_req = list.GetReque()[i];
if(up_req) break;//从顶层往下找,一单发现请求,则不再继续检测
}
if(up_req){
list.SetState(UP);//上方有请求,置状态为UP
WaitTime=0;//电梯空等时,一但有请求(即等待未超时)时,要将WaitTime复位
}
else{//上方没请求,开始检测下方,方法一样
bool down_req=false;
for(int i=0;i<f;i++){
down_req=list.GetReque()[i];
if(down_req) break;
}
if(down_req){//如果下方有请求
list.SetState(DOWN);//电梯反向
list.SetDire(D);//反向后的方向置D
WaitTime=0;
}
else{//如果下方也没请求,则电梯转为等候状态
cout<<"在"<<NowTime<<"t时刻 "<<" 电梯在F"<<f<<"等待"<<endl;
NowTime++;//时间流逝一个单位
WaitTime++;
if(WaitTime == 300){
cout<<"在"<<NowTime<<"t时刻 "<<" 等待超时!电梯驳回本垒层等待!"<<endl;
exit(0);
}
refreshReq();
list.SetState(CLOSED);
}
}
break;
}//case U over
case D:{
bool down_req=false;
for(int i=0;i<f;i++){
down_req = list.GetReque()[i];
if(down_req) break;
}
if(down_req){
list.SetState(DOWN);//下方有请求,置状态为DOWN
WaitTime=0;
}
else{////下方没请求,开始检测上方
bool up_req=false;
for(int i=FLOORS;i>f;i--){
up_req=list.GetReque()[i];
if(up_req) break;
}
if(up_req){//如果上方有请求
list.SetState(UP);
list.SetDire(U);
WaitTime=0;
}
else{//上方也没有请求
cout<<"在"<<NowTime<<"t时刻 "<<" 电梯在F"<<f<<"等待"<<endl;
NowTime++;
WaitTime++;
if(WaitTime == 300){//电梯等待时间到了300t,驳回本垒层候命
if(f == 1){//本身就在本垒层
cout<<"在"<<NowTime<<"t时刻 "<<" 等待超时!电梯在本垒层候
命!"<<endl;
}
else{//本身不在本垒层
cout<<"在"<<NowTime<<"t时刻 "<<" 等待超时!电梯驳回本垒层候
命!"<<endl;
}
exit(0);
}
refreshReq();
list.SetState(CLOSED);
}
}
break;
}//case D over
}
}
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*LinQueue.h*/
template <class T> class LinQueue;//前视定义,否则友元无法定义
template <class T>
class QueueNode{
friend class LinQueue<T>;//定义LinQueue<T>为友元
private:
QueueNode<T> *next;//指针
T data;//数据
public:
//构造函数
QueueNode(const T& item,QueueNode<T> *ptrNext=0)
:data(item),next(ptrNext){}
~QueueNode(){};//析构函数
};
template <class T>
class LinQueue{
private:
QueueNode<T> *front;//队头指针
QueueNode<T> *rear;//队尾指针
int count;//计数器
public:
LinQueue(void);
~LinQueue(void);
int Size();
void Append(const T& item);//入队列
T Delete(void);//出队列
T GetFront(void) const;//取队头数据元素
T GetData(int i) const;//取队列第i个元素(为需要而增加的一个函数)
bool NotEmpty(void) const//非空否(非空为1)
{
return count!=0;
};
};
template <class T>
LinQueue<T>::LinQueue(void){//构造函数初始化
front=rear=0;
count=0;
}
template <class T>
LinQueue<T>::~LinQueue(void){//析构函数置初始状态
QueueNode<T> *p,*q;
p=front;
while(p !=0){
q=p;
p=p->next;
delete q;
}
count=0;
front=rear=0;
}
template <class T>
int LinQueue<T>::Size(){
return count;
}
template <class T>
void LinQueue<T>::Append(const T& item){
QueueNode<T> *newNode=new QueueNode<T>(item,0);
if(rear !=0) rear->next=newNode;
rear=newNode;
if(front ==0) front=newNode;
count++;
}
template <class T>
T LinQueue<T>::Delete(void){
if(count==0) exit(0);
QueueNode<T> *p=front->next;
T data=front->data;
delete front;
front=p;
count--;
return data;
}
template <class T>
T LinQueue<T>::GetFront(void) const{
if(count==0) exit(0);
return front->data;
}
template <class T>
T LinQueue<T>::GetData(int i) const{
if(i<0 || i>count-1) exit(0);
QueueNode<T> *p=front;
int j=0;
while(p != 0 && j<i){
p=p->next;
j++;
}
return p->data;
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*LinList.h*/
//链表类的定义与队列类的定义如出一辙,大同小异
template <class T>
class LinList;
template <class T>
class ListNode{
friend class LinList<T>;
private:
ListNode<T> *next;
T data;
public:
ListNode(ListNode<T> *ptrNext=0){
next=ptrNext;
}
ListNode(const T& item,ListNode<T> *ptrNext=0){
data=item;
next=ptrNext;
}
~ListNode(void){}
};
template <class T>
class LinList{
ListNode<T> *head;
int size;
ListNode<T> *Index(int i);
public:
LinList();
~LinList();
int Size() const;
void Add(const T& item);//链首添加
T Delete(int i);
T GetData(int i);
};
template <class T>
LinList<T>::LinList(){
head=new ListNode<T>();
size=0;
}
template <class T>
LinList<T>::~LinList(){
ListNode<T> *p,*q;
p=head;
while(p !=0)
{
q=p;
p=p->next;
delete q;
}
size=0;
head=0;
}
template <class T>
ListNode<T> *LinList<T>::Index(int i){
if(i<-1 || i>size-1)
exit(0);
if(i==-1) return head;
ListNode<T> *p=head->next;
int j=0;
while(p !=0 && j<i){
p=p->next;
j++;
}
return p;
}
template <class T>
int LinList<T>::Size() const{
return size;
}
template <class T>
void LinList<T>::Add(const T& item){
ListNode<T> *newNode=new ListNode<T>(item,0);
newNode->next=head->next;
head->next=newNode;
size++;
}
template <class T>
T LinList<T>::Delete(int i){
if(size == 0 || i<0 || i>size-1)//无元素可删或参数越界
exit(0);
ListNode<T> *s,*p=Index(i-1);
s=p->next;
p->next=p->next->next;
T x=s->data;
delete s;
size--;
return x;
}
template <class T>
T LinList<T>::GetData(int i){
if(i<0 || i>size-1)//参数越界
exit(0);
ListNode<T> *p=Index(i);
return p->data;
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*List.h*/
const int FLOORS=9;//总楼层数(一律从标号0开始,至FLOORS-1层)
const int LOAD=12;//电梯载重(人数)
enum states {UP,DOWN,CLOSED,WAIT};//电梯运作的状态(上升、下降、关门、等待)
enum direct {U,D};//电梯运作的方向U(上),D(下)
class List{
private:
int curr_floor;//电梯当前所在楼层
int curr_man;//电梯内当前总人数
states state;//电梯当前所处状态
direct dire;//电梯运作的方向
bool request[FLOORS];//记录有请求的楼层
public:
List();
int GetFloor();//得到电梯当前楼层
int GetMan();//得到电梯当前人数
states GetState();
direct GetDire();
bool* GetReque();
void SetState(states sta);
void SetDire(direct dir);
void SetFloor(int i);//设置电梯当前的楼层
void SetMan(int i);//设置电梯当前人数
void SetReque(int i,bool b);//设置请求数组的request[i]值为b(bool类型)
};
List::List(){
curr_floor=1;//默认1楼为本垒层
curr_man=0;
state=CLOSED;
dire=U;
for(int i=0;i<FLOORS;i++) request[i]=false;
}
int List::GetFloor(){
return curr_floor;
}
int List::GetMan(){
return curr_man;
}
states List::GetState(){
return state;
}
direct List::GetDire(){
return dire;
}
bool * List::GetReque(){
return request;
}
void List::SetFloor(int i){
curr_floor=i;
}
void List::SetMan(int i){
curr_man=i;
}
void List::SetState(states sta){
state=sta;
}
void List::SetDire(direct dir){
dire=dir;
}
void List::SetReque(int i,bool b){
request[i]=b;
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*Man.h*/
const int MAX_WAIT_TIME=300;//最大等待时间
class Man{
private:
int number;//编号
int from_floor;//来自楼层
int to_floor;//去楼层
int arrival_time;//到达时间
public:
Man(void);
void Assign(int num,int from,int to,int arrival_t);
int GetNum();
int GetFrom();
int GetTo();
int GetArrival();
};
Man::Man(void){//初始化(全置-1,表示无意义)
number=-1;
from_floor=-1;
to_floor=-1;
arrival_time=-1;
}
void Man::Assign(int num,int from,int to,int arrival_t){
number=num;
from_floor=from;
to_floor=to;
arrival_time=arrival_t;
}
int Man::GetNum(){
return number;
}
int Man::GetFrom(){
return from_floor;
}
int Man::GetTo(){
return to_floor;
}
int Man::GetArrival(){
return arrival_time;
}
7.参考文献
《数据结构(C++语言描述)》 朱战立
《C++程序设计(第2版)》 吴乃陵