关键路径的查找实验报告

概要设计—7—中国矿业大学矿业工程学院实验报告课程名称计算机软件设计基础姓名xxxx班级采矿10-8班学号xxxxx日期2012年10月成绩教师xxxx数据结构课程设计报告—8—3．2算法步骤：总结—16—(1)输入e条弧j,k，建立AOE网的存储结构。(2)从源点v1出发，令ve(1)=0,求ve(j)，2=j=n。(3)从汇点vn出发，令vl(n)=ve(n),求vl(i)1=i=n-1。(4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。总结首先，关于程序方面，我发现即使对设计思路有了眉目，知道了所要用到的数据结构、用邻接表来存储AOE-网、建立栈来求拓扑序列、输出的拓扑序列的个数少于节点数则有回路等等，要把这些方法写成函数代码，其实还是一件非常不容易的事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大的工作。在处理程序代码的时候，有两个问题始终解决不了。一是程序输入时只能输入整形数据，而非整形的输入则会导致程序异常停止，但是因为整形的输入方式已贯穿整个程序，若要修改只能另外重做整个程序，所以暂不考虑修改，而打算做一个判错系统，判断若非整形的输入则报错；二是第一种错误的解决方案未能成功实行，于网路上搜索到了几种判断是否为整形数据的程序代码，但将其修改融合到求关键路径的程序中，虽然没有错误可以运行，但是却不能正确的报错。于是，在尝试多种方案却仍不成功的前提下，我只好选择加上提示语，即：printf(请输入某项目的信息，并请用整形数字表示（格式：弧头，数据结构课程设计报告—8—弧尾，数据结构课程设计报告—8—权值）：\n);printf(例如:输入1,2,4即代表结点1与4之间的活动需要4个时间单位。\n);这是这次课程设计中最大的两个遗憾。不过在操作界面的人性化上，我倒尽可能的做得很完善，无论从美观角度还是方便清楚操作，都实行了非常人性化的方式。因为通常清楚程序的人，知道怎么操作以及该输入什么，而不清楚的人却有很大可能在细节方面输入错误导致程序运行失败，或是根本不知道应该怎么输入。所以，尽可能的人性化的设计是非常有必要的，让不懂程序的人也可以正确的操作运行。我认为这样的课程设计比较有意义，独立完成资料的搜集以及课设的内容，然后独立的做出报告，让这个过程很完整，无论是知识方面、还是报告的书写方面，都学到了更多的东西，为毕业设计打下了良好的基础。最后，做再次一下总结。程序方面仍有为解决的问题，希望即便课设之后也可以努力将问题解决掉。然后关键路径的算法中，有些知道怎么做却很难清楚回答出来的问题，希望可以再好好的查找一下相关资料，将知识系统化、理论化、规范化。数据结构课程设计报告—8—三、程序设计步骤1）功能分析说明图：数据结构课程设计报告—8—2）采用主要的数据结构类型。1、数据结构typedefstructnode{intadjvex;intdut;structnode*next;}edgenode;typedefstructmain()函数swith()函数seekkeyroot()函数case:Scase:ESreateGraphic()函数SearchMapPath()函数调用结束ch!='S'&&ch!='E'数据结构课程设计报告—8—{intprojectname;intid;edgenode*link;}vexnode;//vexnodeGraphicmap[PROJECTNUMBER];2、构建AOE-网voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber)//构建AOE-网，for(scanf())逐个对图结点信息（包括两邻接点，权值）输入接收，并与分配存储空间。{intbegin,end,duttem;edgenode*p;for(inti=0;iprojectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id=0;Graphicmap[i].link=NULL;}printf(某项目的开始到结束在图中的节点输入vi,vj,dut\n);printf(如：,4,9回车表示第三节点到第四节点之间的活动用了个单位时间\n);for(intk=0;kactivenumber;k++)数据结构课程设计报告—8—{scanf(%d,%d,%d,&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p-adjvex=end-1;p-dut=duttem;Graphicmap[end-1].id++;p-next=Graphicmap[begin-1].link;Graphicmap[begin-1].link=p;}}3、寻找关键路径intSearchMaxPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,int&totaltime)//寻找关键路径，构建栈用与储存拓扑排序序列，求得每个接点的相应最早发生时间、最迟完成时间，关键事件的求取，并输出关键路径。{inti,j,k,m=0;intfront=-1,rear=-1;int*topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列int*vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间int*ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间数据结构课程设计报告—8—int*l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间int*e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间edgenode*p;totaltime=0;for(i=0;iprojectnumber;i++)ve[i]=0;for(i=0;iprojectnumber;i++){if(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link;数据结构课程设计报告—8—while(p){k=p-adjvex;Graphicmap[k].id--;if(ve[j]+p-dutve[k])ve[k]=ve[j]+p-dut;if(Graphicmap[k].id==0)topologystack[++rear]=k;p=p-next;}}if(mprojectnumber){printf(\n本程序所建立的图有回路不可计算出关键路径\n);printf(将退出本程序\n);return0;}totaltime=ve[projectnumber-1];for(i=0;iprojectnumber;i++)数据结构课程设计报告—8—vl[i]=totaltime;for(i=projectnumber-2;i=0;i--){j=topologystack[i];p=Graphicmap[j].link;while(p){k=p-adjvex;if((vl[k]-p-dut)vl[j])vl[j]=vl[k]-p-dut;p=p-next;}}i=0;printf(|起点|终点|最早开始时间|最迟完成时间|差值|备注|\n);for(j=0;jprojectnumber;j++){p=Graphicmap[j].link;while(p)数据结构课程设计报告—8—{k=p-adjvex;e[++i]=ve[j];l[i]=vl[k]-p-dut;printf(|%4d|%4d|%4d|%4d|%4d|,Graphicmap[j].projectname+1,Graphicmap[k].projectname+1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf(关键活动|);printf(\n);p=p-next;}}return1;}4、数据输入voidseekkeyroot()//先使用库函数system(cls)清屏，scanf()对结点数的接收，分配相应的存储空间，调用CreateGraphic()函数和SearchMapPath()函数。{intprojectnumber,activenumber,totaltime=0;system(cls);printf(请输入这个工程的化成图形的节点数:);数据结构课程设计报告—8—scanf(%d,&projectnumber);printf(请输入这个工程的活动个数:);scanf(%d,&activenumber);vexnode*Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));CreateGraphic(Graphicmap,projectnumber,activenumber);SearchMaxPath(Graphicmap,projectnumber,activenumber,totaltime);printf(整个工程所用的最短时间为：%d个单位时间\n,totaltime);system(pause);}3）各软件模块之间的调用方式该软件各个模块的调用主要是通过声明函数，和定义函数，再通过主函数调用实现的。主函数：intmain()//输出主屏信息，判断进入关键路径的程序条件，switch()对条件进行选择。{charch;for(;;){do{system(cls);数据结构课程设计报告—8—printf(|欢迎进入求关键路径算法程序|\n);for(inti=0;i80;i++)printf(*);printf(%s,(S)tart开始输入工程的节点数据并求出关键路径\n);printf(%s,(E)xit退出\n);printf(%s,请输入选择:);scanf(%c,&ch);ch=toupper(ch);}while(ch!='S'&&ch!='E');switch(ch){case'S':seekkeyroot();break;case'E':return1;}}}数据结构课程设计报告—8—