数据结构课程设计报告(完整版)[1]

第二题：电梯模拟1、需求分析：模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、……第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。而题目的最终要求输出时：按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。2、设计2．1设计思想：（1）数据结构设计本题中的电梯的变化，是一个动态变化的过程，要在动态过程中实现正常跳转，首先要确定各种跳转的状态，因而这里我使用枚举类型来表示电梯的各种状态的：enum{up,down,stop,home}State(home);同时初始化最初状态为电梯在本垒层。而在电梯的运行过程中对于乘客来说，显然有一个进入电梯与出电梯的队列，因而在这里我是用的链表来实现这个过程的，同时用结构体来保存该乘客的信息：typedefstructpassage{intnow;//乘客当前所在的位置intdis;//乘客的目地地intwait;//最长的等待的时间intwaitnow;//已经等待的时间structpassage*next;}Passage;虽然电梯中的状态是由枚举类型来实现的，但是在整个程序的运行过程中，我还是为电梯设置了一个结构体类型，以便保存更多的信息：typedefstructlift{intcount_C;//计数电梯已到达的层数intcount_A;//系统的总时间计数器记得必须初始化为0intflag_in[High];//九个楼层有无请求的标志哪个楼层如果有请求该标志置1intnum;//等待队列中的人数记得要进行初始化为0intpeople;//电梯中人数intflag_out[High];}Lift;（2）算法设计顾名思义本程序在运行的过程中用到的算法便是—“电梯算法”，电梯算法借鉴了磁盘寻道C-LOOK算法，即电梯向一个方向运行，直到这个方向上没有服务为止。2.2设计表示（1）、函数调用关系图及其说明如下:(2)函数接口说明：函数中的参数均是使用的全局变量的传递，因而在函数间进行传递的过程中比较简单，下面就将主要函数及他们之间的参数的关系列出如下：intOutOrIn(Lift&L,Passage*Queue,Passage*LiftQ);//进和出电梯的总函数intUpdate(Lift&L,Passage*Queue,Passage*LiftQ);//刷新的函数intRun(Lift&L,Passage*Queue,Passage*LiftQ);//整个电梯各种状态转换的函数intOpenTheDoor(Lift&L);//开门主要是用于解决其中的时间问题intCloseTheDoor(Lift&L);//关门intIn(Lift&L);//进入主要是解决每个人进入电梯的时间问题intOut(Lift&L);//出去intTest(Lift&L,Passage*Queue,Passage*LiftQ);//电梯测试关门还是开门的函数intRequest(Lift&L,Passage*Queue);2.3详细设计3、调试分析该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。4、用户手册点击运行程序，在弹出的窗口中，会提示要输入的信息：1、提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧的标志：”按要求输入即可，本题即输入911va2、提示信息为“请完成该邻接表的输入”：由于邻接表的输入信息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心3、在完成上面两步的输入后按enter键便能得到程序的运行结果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动5测试数据及测试结果测试数据如下：911va13161242353214143141541526526977786174971821081841190程序运行结果如下：6、原程序清单如下：/*关键路径问题2010年07月31日晚上08：36开始动工*/#includeiostreamusingnamespacestd;constintMAX_V_NUM=20;//最大存储顶点的数目constintSTACK_INIT_SIZE=20;//栈的存储空间分配量////数据存储部分/*一下是图的邻接表的存储表示，由于第一次用用的比较的生疏……*/typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指下一条弧的指针intinfo;//该弧相关信息即权值intname;//弧的名字}ArcNode;typedefstructVNode{intdata;//顶点的信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}AdjList[MAX_V_NUM];typedefstruct{AdjListvertices;intvnum,arcnum;//图中当前顶点数和弧数charkind,kind1;//图中的各类标志顶点和弧}ALGraph;typedefstruct{int*base;int*top;intstacksize;}Stack;intve[MAX_V_NUM];StackT;//函数体描述部分intInitStack(Stack&S);intPush(Stack&S,int&e);intPop(Stack&S,int&e);intCriticalPath(ALGraph&G);intToPoOrder(ALGraph&G,Stack&T);intFindInDegree(ALGraph&G,int(&indegree)[MAX_V_NUM]);/*下面是函数的具体实现部分*///构造一个空栈intInitStack(Stack&S){S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)return0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;//可以用于当栈的存储空间不够的情况下进行扩充return1;};//元素进栈intPush(Stack&S,int&e){*S.top++=e;return1;};//元素出栈intPop(Stack&S,int&e){if(S.top==S.base)return0;e=*--S.top;return1;};//判断栈是否为空intStackEmpty(Stack&S){if(S.top==S.base)return1;elsereturn0;};//找出每个顶点的入度intFindInDegree(ALGraph&G,int(&indegree)[MAX_V_NUM]){ArcNode*p;inti;for(i=0;iMAX_V_NUM;i++)indegree[i]=0;for(i=0;iG.vnum;i++){for(p=G.vertices[i].firstarc;p;p=p-nextarc)indegree[p-adjvex]++;}return0;}//拓扑排序同时求出各活动的最早发生时间intToPoOrder(ALGraph&G,Stack&T){intcount=0;inti,j,k;StackS1;ArcNode*p;intindegree[MAX_V_NUM];InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i++)if(indegree[i]==0)Push(S1,i);//建立0入度顶点栈Sfor(i=0;iG.vnum;i++)ve[i]=0;while(!StackEmpty(S1)){Pop(S1,j);Push(T,j);count++;for(p=G.vertices[j].firstarc;p;p=p-nextarc){k=p-adjvex;if(--indegree[k]==0)Push(S1,k);if(ve[j]+(p-info)ve[k])ve[k]=ve[j]+(p-info);}}//for(i=0;iG.vnum;i++)//coutve[i]endl;if(countG.vnum)return0;elsereturn1;}//计算各顶点的最迟发生时间及进行输出intCriticalPath(ALGraph&G){intvl[MAX_V_NUM];intdut;inti,j,k,ee,el;ArcNode*p;//chartag;if(!ToPoOrder(G,T))return0;cout完成整项工程至少需要的时间是：ve[G.vnum-1]endl;for(i=0;iG.vnum;i++)vl[i]=ve[G.vnum-1];while(!StackEmpty(T)){for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p-nextarc){k=p-adjvex;dut=(p-info);if(vl[k]-dutvl[j])vl[j]=vl[k]-dut;}}//for(i=0;iG.vnum;i++)//coutvl[i]endl;cout影响工程进度的关键活动是:endl;for(j=0;jG.vnum;j++)for(p=G.vertices[j].firstarc;p;p=p-nextarc){k=p-adjvex;dut=(p-info);ee=ve[j];el=vl[k]-dut;//coutj=jK=kdut=dutee=eeel=elendl;if(ee==el)//tag=(ee=el)?'*':'';coutG.kind1p-nameendl;}return1;}intmain(){ALGraphG;inti,j,Hnum;ArcNode*p,*q;//intindegree[MAX_V_NUM];//ALGraphG;cout请输入图中的顶点数和弧数以及图的标志和弧的标志：endl;cinG.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout请完成该邻接表的输入：endl;for(i=0;iG.vnum;i++){cout请输入该顶点的信息endl;cinG.vertices[i].data;cout请输入与G.kindG.vertices[i].data号顶点相邻的弧的数目:endl;cinHnum;if(Hnum==0){G.vertices[i].firstarc=0;}else{cout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）endl;p=(ArcNode*)malloc(sizeof(ArcNode));G.vertices[i].firstarc=p;p-nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j++){cout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）endl;q=(ArcNode*)malloc(sizeof(ArcNode));cin