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

山东理工大学计算机学院

课 程 设 计

（数据结构）

班 级

姓 名

学 号

指导教师

2013年 1月 15日

课程设计任务书及成绩评定

课题名称
电梯模拟

Ⅰ、题目的目的和要求：

巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

Ⅱ、设计进度及完成情况

日 期
内 容
2013-1-7
选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。
2013-1-10
创建相关数据结构,录入源程序。
2013-1-13
调试程序并记录调试中的问题，初步完成课程设计报告。
2013-1-15
上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。
2013-1-16
考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。

Ⅲ、主要参考文献及资料
[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强 C语言程序设计 清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料

Ⅳ、成绩评定：

设计成绩： （教师填写）

指导老师： （签字）

二 年 月 日
目 录

第一章 概述……………………………………………………………1
第二章 系统分析………………………………………………………2
第三章 概要设计………………………………………………………4
第四章 详细设计………………………………………………………7
第五章 运行与测试……………………………………………………25
第六章 总结与心得……………………………………………………28

参考文献 ………………………………………………………………28
第一章 概述

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是图书管理。传统的人工图书管理，基本业务活动有对一本书的采编入库、清除库存、借阅和归还等等，但是人工统计操作起来效率相对来说要低，也容易出错。但是现在这些业务借助计算机系统完成后，效率可以得到提高，也可以减少出错的几率。可以使图书管理的日常业务更加的方便迅捷、减少很多劳动量。
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

第二章 系统分析

任务
根据教材《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。
设计题目从《数据结构题集》“第二篇 实习篇”中选取，每班每题不得超过2人。
另选题：
学生自选课题
学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在17周前报课程设计指导教师批准方可生效。

要求：
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。
2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;
4、每位同学需提交可独立运行的程序；
5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。
（1）、模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层和第四层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来该层候命。五个楼层从下到上的编号为：0、1、2、3、4。除了地下层外，每一层都有一个要求向下的按钮除了第四层外，每一层都有一个要求向上的按钮。对应的变量为：CallUp[0..3]和CallDown[1..4]。电梯内的五个目标层按钮对应的变量为：CallCar[0..4]。
（2）、电梯一共有七个状态，即正在开门（Opening）、已开门（Opened）、正在关门（Closing）、已关门（Closed）、等待（Waiting）。
（3）、 乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。对于在楼层内等待电梯的乘客，将插入在等候队列里，每一层有两个等候队列，一队要求向上，一队要求向下，用链队列来实现。对于在电梯内的乘客，用五个乘客栈来实现，该乘客要去哪一层，就把他放在相应编号的栈中，对应变量为k[0…4]。
（4）、模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位（简记为t）：
有人进出时，电梯每隔40t测试一次，若无人进出，则关门
关门和开门各需要20t
每个人进出电梯均需要25t
如果电梯在某层静止时间超过300t，则驶回1层候命。
（5）、按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。

第三章 概要设计

乘客类型

反映乘客的所有属性。
Man
数据对象：D={ai∈乘客信息,I=1,2,…,n,n≥0}
数据关系：R={|ai-1,ai∈D,i=2,…,n}
基本操作：
void inel();
该乘客进入电梯时 发生的数据转换 及基本的输出
void onwait();
该乘客进入某层等待队列时 发生的数据变动 及基本的输出
long giveup();
void getout();
该乘客出电梯时所发生的数据变动，及基本的状态输出

电梯栈类型

电梯内的乘客用乘客栈表示，去不同楼层的乘客放在不同的栈中。
ADT Estack
数据对象：D={ai∈乘客信息,I=1,2,…,n,n≥0}
数据关系：R={|ai-1,ai∈D,i=2,…,n}
基本操作：
本设计中运用了一个链栈的模板，可以自己定义栈的数据类型
共用到了五个栈，分别表示电梯内到往某楼的乘客，为了方便设计，用一个栈的数组来表示这五个栈，数组的下标表示楼层。

等候队列类型

在电梯外等待的乘客用等待队列表示。每层各有一个等待队列，表示在该层楼排队的乘客。为了方便程序设计，用一个队列的数组来表示这五个队列，数组的下标表示楼层。

同上，本次设计也用了一个链队列的模板，

电梯相关的动作

表示电梯的各个属性和所有动作。
Void e1()
表示电梯开门 时所发生的动作
Void e2()
在本层出电梯的乘客从本层的栈中弹出
调用乘客走出楼梯事件
Void e3()
电梯外的队列入电梯栈
Void e4()
电梯状态的转换
Void e5()
电梯关门时基本状态的输出 及一些数据变换
Void e6()
电梯上升时基本状态的输出 及数据的变动
Void e7)
电梯下降时基本状态的输出，及数据的变动
Void e8()
电梯处于静止状态时状态的输出，及数据的变动

控制模块

Void control（）
与电梯控制有关的函数集合，用于判断电梯门的开关，及电梯状态转换控制

时间模块
Void Wait(long tt)
本函数用于时间模拟中延时tt个单位的时间
Void times()
本函数用于现在时间状态的保存，用于输入新的 乘客时去处输入所用的时间
Void timer（）
本函数用于时间状态的恢复

输入输出模块
diantizhuangtai()
输出电梯现在的状态
subsr()
输入函数的子函数用于处理数据输入并记录用于输入数据所耽误的时间以维持系统时间的准确性。
Void shuru()
输人下一个乘客的信息，及相关的判断
本函数用于现在时间状态的恢复，用于输入新的 乘客时去处输入所用的时间
主程序
主程序主要处理两类事件：显示欢迎界面，输入事件和电梯状态转换事件。
输入事件是输入乘客的信息和下一个乘客到来的时间
状态转换事件是处理在当前状态下电梯的动作

本程序包含6个模块：
（1）主程序模块
（2）乘客模块
（3）电梯模块
（4）时间模块
（5）控制模块
（6）输入输出模块

各模块之间的调用关系如下：
电梯控制模块
主程序
输入输出模块
时间模块
电梯模块
乘客模块

第四章 详细设计

// 电梯模拟.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"//此头文件在详细设计的结尾
#define MAXMAN 5
#define TIME 100
using namespace std;

//--------------------------------------变量定义----------------

enum states {goingup,goingdown,idle};
states state=idle;
states nowstate=idle;//控制楼梯的上下
int nowfloor=1;//电梯当前的楼层
//int d1=0;未用到
//int d2=0;
//int d3=0;
int callup[5];
int calldown[5];
int callcar[5];
long timesum;//延时函数用到的变量
long delay;
long sum=1;
long nexttime;//下一个乘客出现的时刻
int tf;//时间恢复标志，用在输入函数递归调用中
//int flag;//事件结束的标识
long jingzhi;//静止开始时间、、用于判断楼梯是否在某一层等待超过300t
int f;//电梯动作标志配合jingzhi协同
int lt;//下一个人出现的时间间隔
int renshu; //电梯内的人数
LinkStack biaozhi;//用于时间保存函数递归调用过程中对时间的保存

void chushihua()
{
int i=5;
while(i)
{
callup[i]=0;
calldown[i]=0;
callcar[i]=0;
i--;
}
}

//------------------------------------自定义乘客类------------------------------------
class man
{
public:
int number;
int infloor;
int outfloor;
long intime;
long giveuptime;

void inel();
void onwait();
long giveup();
void getout();

friend ostream&operator << (ostream& output,man& c)//重载流输出用于栈和队列的遍历
{
output< s[5];

//电梯栈
LinkStack k[5];

void man::inel()
{

if((m.intime+m.giveuptime*TIME)out< s[infloor].EnQueue(*this);
//wait(25);
cout<ut<nd;
//end=clock()+tt*TIME;
end=clock()-delay;
while(clock()=nexttime)//当 当前时刻 大于等于下一个人到来的时刻时，调用输入函数
{

shuru();

}

}
//cout<
}
void times()//保存时间
{
biaozhi.Push(clock());
timesum=clock();
//cout<门
{
wait(20);
cout<nowfloor].QueueEmpty()&&renshucout<1]=0;
cout<}
int e4()//电梯状态的转换
{
int diantizhuangtai();
system("cls");
diantizhuangtai();
int c,d,j;//c为电梯是否应该向上走的标志，d是向下的标志
j=nowfloor;
if(callup[j]==1)
{
c=1;

}
else
{
for(c=0,j=nowfloor+1;j<=4;j++)
{

if(callcar[j]==1||callup[j]==1||calldown[j]==1||(k[j].StackEmpty()==0)||s[j].QueueEmpty()==0)
{
c=1;
break;
}
}
}
j=nowfloor;
if(calldown[j]==1)
{
d=1;

}
else
{

for(d=0,j=nowfloor-1;j>=0;j--)
{

if(callcar[j]==1||callup[j]==1||calldown[j]==1||(k[j].StackEmpty()==0)||s[j].QueueEmpty()==0)
{
d=1;
break;
}
}
}

if(nowstate==goingup)
{
if(nowfloor==4||(c==0&&d==1))//电梯由向上转到向下的条件
{
if(nowfloor==4&&d==0)
e8();//静止
else
{
nowstate=goingdown;
e7();//下降
}
//callcar[nowfloor]=0;
}
else
{
//state=goingdown;
if(d==0&&c==0)
{
e8();//电梯静止
nowstate=idle;
}
else
{
e6();//电梯上升
}
}
}
else
{
if(nowstate==goingdown)//判断过程基本和上一级的if语句相同
{
if(nowfloor==0||(d==0&&c==1))
{
if(nowfloor==0&&c==0)
e8();//静止
else
{
nowstate=goingup;
e6();//电梯上升
}

}
else
{
if(c==0&&d==0)
{
e8();//电梯静止
nowstate=idle;
}
else
{
e7();//电梯下降
}
}
}
else
{
if(c==0&&d==0)//以下是由静止转向其他动作过程
{
nowstate=idle;

e8();
//return 0;

}
else
if(c==1)
{
nowstate=goingup;
e6();//电梯上升
}
else
{
nowstate=goingdown;
e7();//电梯下降
}
}

}
//flag=0;
return 0;
}

int e5()//关门
{
wait(20);
cout<0;
}

//--------------------------------输入输出函数的定义---------------------------------
int diantizhuangtai()//输出电梯状态
{
cout<<" ------------下边是电梯现在的状态信息：-----------"<=0;i--)
{
if(i==nowfloor)
cout<<" ▲▲";
else
cout<<" ";
cout<<"电梯中前往第"<=0;i--)
{
if(i==nowfloor)
cout<<" ▲▲";
else
cout<<" ";
//cout<<" 前往第"</输入函数的子函数
{
cout<<"请输入乘客进入了哪层，要去哪层，容忍等待的最大时间，下一乘客到来的时间间隔：\n";
if(tf==0)
times();//保存时间状态
tf=1;
while(cin>>m.infloor>>m.outfloor>>m.giveuptime>>lt)
{
if(m.infloor==0&&m.outfloor==0&&m.giveuptime==0&<==0)
{

int nowdelay;

nowdelay=delay;

cout<<""< diantizhuangtai();
subsr();

}
if(m.infloor>=5||m.outfloor>=5||m.infloor==m.outfloor)
{

cout<int shuru()//输入函数
{

m.number=sum;

sum++;
subsr();

if(nexttime>clock()-delay)//下一个人到来的时间
nexttime=nexttime+lt*TIME;
else
nexttime=clock()-delay+lt*TIME;
m.intime =clock()-delay;

if (m.infloor>m.outfloor)
calldown[m.infloor]=1;
else
callup[m.infloor]=1;

monwait ();

return 0;
}

//-----------------------------------电梯控制函数-------------------------------------
int control()
{
//system("cls");
if((clock()-delay)>=nexttime)//当当前时刻大于等于下一个人到来的时刻时，调用输入函数
{
shuru();
return 0;
}
if((callcar[nowfloor]!=0)||callup[nowfloor]!=0||calldown[nowfloor]!=0||(k[nowfloor].StackEmpty()==0)||s[nowfloor].QueueEmpty()==0)//电梯开门的条件
{
if((renshu==MAXMAN&&k[nowfloor].StackEmpty()==1))
e4();
else
{
e1();//电梯开门
e2();//在本层出电梯的人出栈
e3();//楼梯外的队列入电梯栈
e5();//关门
e4();//电梯状态变换
}
}
else
{

e4();//电梯状态改变
}
if(f==0)
{
callcar[nowfloor]=0;
if((clock()-jingzhi)>300*TIME)//电梯等待时间超过300t时回到一楼
{
if(nowfloor!=1)
callcar[1]=1;
}
}
if((k[nowfloor].StackEmpty()==1)||s[nowfloor].QueueEmpty()==1)
{
callup[nowfloor]=0;
calldown[nowfloor]=0;
}
return 0;

}

//----主函数---------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
system("color 1a");//把命令提示符窗口的背景色设为蓝色，前景色设为淡绿色
timesum=clock();
chushihua();//初始化
//----------------------欢迎界面------------------------
cout<<izhuangtai();//输出电梯状态
while((clock()-delay)10)
wait(10);

control();
}
shuru();//输入乘客信息
}
return 0;
}

---------------------------------以下是程序所涉及的头文件-----------------------------

---------------------------------栈模板头文件：---------------------
//链栈类的定义
template
struct Node
{
T data;
Node *next;//此处T可以省略
};

template
class LinkStack
{//构建函数，创建一空栈
private:
Node *top;//// 链表首为栈顶
public:
LinkStack(){top=NULL;}//构造函数，置空链栈
~LinkStack();// 析构函数，释放链栈中各结点的存储空间
void Push(T x);// 元素x入栈

T Pop();// 栈顶元素出栈
T GetTop();// 取栈顶元素
int StackEmpty(); // 判断栈是否为空
void ClearStack();//清空栈
void StackTranverse();//遍历输出栈中元素
/*friend ostream &operator << (ostream &stream, T asd)
{
stream << asd.number;
return stream;
}*/
};
//链栈类的实现
template
LinkStack~LinkStack()
{//析构函数，销毁栈
Node *q;
while(top)//从栈顶开始释放栈链的每一个结点的存储空间
{
q=top;//暂存被释放结点
top=top->next;//头指针后移指向下一个被释放结点
delete q;
}
}

template
void LinkStack::Push(T x)
{//入栈
Node *s;
s=new Node;s->data=x;//创建一新结点，数据域为x的结点s
s->next=top;top=s;//新结点链入表