数据结构课程设计-电梯模拟.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语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 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。除了地下层外，每一层都有一个要求向下的按钮除了第四层外，每一层都有一个要求向上的按钮。对应的变量为：CallUp0.3和CallDown1.4。电梯内的五个目标层按钮对应的变量为：CallCar0.4。（2）、电梯一共有七个状态，即正在开门（Opening）、已开门（Opened）、正在关门（Closing）、已关门（Closed）、等待（Waiting）。（3）、乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。对于在楼层内等待电梯的乘客，将插入在等候队列里，每一层有两个等候队列，一队要求向上，一队要求向下，用链队列来实现。对于在电梯内的乘客，用五个乘客栈来实现，该乘客要去哪一层，就把他放在相应编号的栈中，对应变量为k04。（4）、模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位（简记为t）：有人进出时，电梯每隔40t测试一次，若无人进出，则关门关门和开门各需要20t每个人进出电梯均需要25t如果电梯在某层静止时间超过300t，则驶回1层候命。（5）、按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。第三章 概要设计乘客类型反映乘客的所有属性。Man数据对象：D=ai乘客信息,I=1,2,n,n0数据关系：R=|ai-1,aiD,i=2,n基本操作：void inel();该乘客进入电梯时 发生的数据转换 及基本的输出void onwait(); 该乘客进入某层等待队列时 发生的数据变动 及基本的输出long giveup();void getout();该乘客出电梯时所发生的数据变动，及基本的状态输出电梯栈类型电梯内的乘客用乘客栈表示，去不同楼层的乘客放在不同的栈中。ADT Estack数据对象：D=ai乘客信息,I=1,2,n,n0数据关系：R=|ai-1,aiD,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 100using 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 callup5;int calldown5;int callcar5;long timesum;/延时函数用到的变量long delay;long sum=1;long nexttime;/下一个乘客出现的时刻int tf;/时间恢复标志，用在输入函数递归调用中/int flag;/事件结束的标识long jingzhi;/静止开始时间、用于判断楼梯是否在某一层等待超过300tint f;/电梯动作标志配合jingzhi协同int lt;/下一个人出现的时间间隔int renshu; /电梯内的人数LinkStack biaozhi;/用于时间保存函数递归调用过程中对时间的保存void chushihua()int i=5;while(i)callupi=0;calldowni=0;callcari=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)/重载流输出用于栈和队列的遍历outputc.number ;return output;man m;/中间变量man n;/等待队列LinkQueue s5;/电梯栈LinkStack k5;void man:inel()if(ime+m.giveuptime*TIME)clock()-delay)coutclock()/TIME-delay/TIME,nexttime/TIME:number号乘客等待超时，已自动离开！endl;elsekoutfloor.Push(*this);/wait(25);coutclock()/TIME-delay/TIME,nexttime/TIME:number号乘客从infloor楼进入电梯。endl;callcaroutfloor=1;void man:onwait()sinfloor.EnQueue(*this);/wait(25);coutclock()/TIME-delay/TIME,nexttime/TIME:number号乘客进入infloor楼的等待队列。endl;long man:giveup()coutclock()/TIME-delay/TIME,nexttime/TIME:number号乘客放弃等待endl;return 0;void man:getout()coutclock()/TIME-delay/TIME,nexttime/TIME:number号乘客出电梯endl;/-时间函数定义-int shuru();int wait(long tt)/延时控制函数/coutclock()/TIME-delay/TIME,nexttime/TIME:wait 计时开始endl;clock_t end;/end=clock()+tt*TIME;end=clock()-delay;while(clock()=nexttime)/当 当前时刻 大于等于下一个人到来的时刻时，调用输入函数shuru();/coutclock()/TIME-delay/TIME,nexttime/TIME:wait 计时结束endl;return 0;void times()/保存时间biaozhi.Push(clock();timesum=clock();/couttimesum/TIMEendl;void timer()/恢复时间delay+=clock()-biaozhi.Pop();/coutdelay/TIMEendl;/-电梯相关的活动-int e1 ()/开门wait(20);coutclock()/TIME-delay/TIME,nexttime/TIME:电梯开门。endl;return 0;int e2()/在本层出电梯的人出栈while(!knowfloor.StackEmpty()n=knowfloor.Pop();wait(25);n.getout();renshu-;return 0;int e3()/楼梯外的队列入栈while(!snowfloor.QueueEmpty()&renshuMAXMAN)n=snowfloor.DeQueue();wait(25);n.inel();renshu+;return 0;int e6()/电梯上升coutclock()/TIME-delay/TIME,nexttime/TIME:电梯正在上升中endl;wait(30);callcarnowfloor=0;nowfloor+;callupnowfloor-1=0;coutclock()/TIME-delay/TIME,nexttime/TIME:电梯上升到了第nowfloor层endl;callcarnowfloor=0;f=1;return 0;int e7()/电梯下降coutclock()/TIME-delay/TIME,nexttime/TIME:电梯正在下降中endl;wait(30);callcarnowfloor=0;nowfloor-;calldownnowfloor+1=0;coutclock()/TIME-delay/TIME,nexttime/TIME:电梯下降到了第nowfloor层endl;f=1;callcarnowfloor=0;return 0;int e8()/静止coutclock()/TIME-delay/TIME,nexttime/TIME:电梯静止,现在的楼层是：nowfloorendl;if(f!=0)jingzhi=clock();f=0;return 0;int e4()/电梯状态的转换int diantizhuangtai();system(cls);diantizhuangtai();int c,d,j;/c为电梯是否应该向上走的标志，d是向下的标志j=nowfloor;if(callupj=1)c=1;elsefor(c=0,j=nowfloor+1;j=0;j-)if(callcarj=1|callupj=1|calldownj=1|(kj.StackEmpty()=0)|sj.QueueEmpty()=0)d=1;break;if(nowstate=goingup)if(nowfloor=4|(c=0&d=1)/电梯由向上转到向下的条件if(nowfloor=4&d=0)e8();/静止elsenowstate=goingdown;e7();/下降/callcarnowfloor=0;else/state=goingdown;if(d=0&c=0)e8();/电梯静止nowstate=idle;elsee6();/电梯上升elseif(nowstate=goingdown)/判断过程基本和上一级的if语句相同if(nowfloor=0|(d=0&c=1)if(nowfloor=0&c=0)e8();/静止elsenowstate=goingup;e6();/电梯上升elseif(c=0&d=0)e8();/电梯静止nowstate=idle;elsee7();/电梯下降elseif(c=0&d=0)/以下是由静止转向其他动作过程nowstate=idle;e8();/return 0;elseif(c=1)nowstate=goingup;e6();/电梯上升elsenowstate=goingdown;e7();/电梯下降/flag=0;return 0;int e5()/关门wait(20);coutclock()/TIME-delay/TIME,nexttime/TIME:电梯关门endl;return 0;/-输入输出函数的定义-int diantizhuangtai()/输出电梯状态cout -下边是电梯现在的状态信息：-endlendl;cout 现在的楼层是：nowfloorendl=0;i-)if(i=nowfloor)cout ;elsecout ;cout电梯中前往第i层的乘客:;ki.StackTranverse();/cout 第i层电梯外边的等待队列：;/si.QueueTranverse();cout=0;i-)if(i=nowfloor)cout ;elsecout ;/cout 前往第i层的乘客:;/ki.StackTranverse();cout第i层电梯外边的等待乘客队列：;si.QueueTranverse();coutendl;coutnow,next-endl;return 0;int subsr()/输入函数的子函数coutm.infloorm.outfloorm.giveuptimelt)if(m.infloor=0&m.outfloor=0&m.giveuptime=0<=0)int nowdelay;nowdelay=delay;cout=5|m.outfloor=5|m.infloor=m.outfloor)coutclock()/TIME-delay/TIME,nexttime/TIME:输入楼层错误！请重新输入clock()-delay)/下一个人到来的时间nexttime=nexttime+lt*TIME;elsenexttime=clock()-delay+lt*TIME;ime =clock()-delay;if (m.infloorm.outfloor)calldownm.infloor=1;else callupm.infloor=1;m.onwait ();return 0;/-电梯控制函数-int control()/system(cls);if(clock()-delay)=nexttime)/当当前时刻大于等于下一个人到来的时刻时，调用输入函数shuru();return 0;if(callcarnowfloor!=0)|callupnowfloor!=0|calldownnowfloor!=0|(knowfloor.StackEmpty()=0)|snowfloor.QueueEmpty()=0)/电梯开门的条件if(renshu=MAXMAN&knowfloor.StackEmpty()=1)e4();elsee1();/电梯开门e2();/在本层出电梯的人出栈e3();/楼梯外的队列入电梯栈e5();/关门e4();/电梯状态变换elsee4();/电梯状态改变if(f=0)callcarnowfloor=0;if(clock()-jingzhi)300*TIME)/电梯等待时间超过300t时回到一楼if(nowfloor!=1)callcar1=1;if(knowfloor.StackEmpty()=1)|snowfloor.QueueEmpty()=1)callupnowfloor=0;calldownnowfloor=0;return 0;/-主函数-int _tmain(int argc, _TCHAR* argv)system(color 1a);/把命令提示符窗口的背景色设为蓝色，前景色设为淡绿色timesum=clock();chushihua();/初始化/-欢迎界面-coutendlendlendlendlendlendl;cout -endl;cout 欢迎使用电梯模拟系统endl;cout -endlendl;system(pause);/暂停while(1)/flag=1;system(cls);/清屏diantizhuangtai();/输出电梯状态while(clock()-delay)10)wait(10);control();shuru();/输入乘客信息return 0;-以下是程序所涉及的头文件-栈模板头文件：-/链栈类的定义templatestruct NodeT data;Node *next;/此处T可以省略;templateclass 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;*/;/链栈类的实现templateLinkStack:LinkStack()/析构函数，销毁栈Node *q;while(top)/从栈顶开始释放栈链的每一个结点的存储空间q=top;/暂存被释放结点top=top-next;/头指针后移指向下一个被释放结点delete q;templatevoid LinkStack:Push(T x)/入栈Node *s;s=new Node;s-data=x;/创建一新结点，数据域为x的结点ss-next=top;top=s;/新结点链入表首，为栈顶templateT LinkStack:Pop()/出栈T x; Node *p;if(top=NULL) throw下溢;x=top-data;/暂存栈顶元素p=top;top=top-next;/栈顶后移delete p;/删除原栈顶结点return x;template T LinkStack:GetTop()/获取栈顶元素if(top=NULL) throw 栈空，栈顶无元素;return top-data;template void LinkStack:ClearStack()/清空栈while(top)/从栈顶开始释放栈链的每一个结点的存储空间Node *q;q=top;/暂存被释放结点top=top-next;/头指针后移指向下一个被释放结点delete q;template int LinkStack:StackEmpty()/测栈空if(top=NULL) return 1;elsereturn 0;template void LinkStack:StackTranverse()/从栈顶起，遍历输出栈元素 Node *p; p=top; while(p) coutdata; p=p-next; coutendl; -队列模版头文件-/链队类的定义templatestruct NodesT data;Nodes *next;/此处T可以省略;templateclass LinkQueueprivate:Nodes *front;/队头指针，链表头为队头Nodes *rear;/队尾指针，链表尾为了队尾public:LinkQueue();/构造空队列LinkQueue();/ 析构函数，释放链队各结点的存储空间void EnQueue(T x);/ 元素x入队T DeQueue();/ 队顶元素出队T GetHead();/ 取队头元素T GetLast();/取队尾元素int QueueEmpty(); / 判断队是否为空void ClearQueue();/void QueueTranverse();/*friend ostream &operator(ostream &stream,T asd)streamasd.number;return stream;*/;/链队类的实现templateLinkQueue:LinkQueue()/构建函数，创建一空队front=new Nodes;/创建队头结点front-next=NULL;rear=front;/空队templateLinkQueue:LinkQueue()/析构函数，销毁队Nodes *p;while(front!=NULL)/从队头开始逐个删除队列中的结点p=front;/暂存被释放结点front=front-next;/头指针后移指向下一个被释放结点delete p;templatevoid LinkQueue:EnQueue(T x)/入队Nodes *s;s=new Nodes; s-data=x; /申请一数据域为x的结点ss-next=rear-next;rear-next=s; /新结点插在链队尾rear=s; /修改尾指针if(front-next=NULL)/如果创建的是首元结点，front-next指向它front-next=s;templateT LinkQueue:DeQueue()/出队T x; Nodes *p;if(rear=front) throw下溢;/队空，则下溢p=front-next;x=p-data;/暂存队头元素front-next=p-next;/将队头结点从链表中摘除if(p-next=NULL) rear=front;/如果出队后为空队，修改队尾指针delete p;return x;template T LinkQueue:GetHead()/获取队头元素Nodes *p;if(front=rear) throw 队空，无队头元素;/p=front-next;return p-data;template T LinkQueue:GetLast()/获取队尾元素if(front=rear) throw 队空，无队尾元素;return rear-data;template void LinkQueue:ClearQueue()/清空队Nodes *p;p=front-next;while(p)/从队头开始逐个删除队列中的结点front-next=p-next;/暂存被释放结点delete p; p=front-next;rear=front;template int LinkQueue:QueueEmpt