关键路径问题报告

滁州学院课程设计报告课程名称： 数据结构 设计题目： 关键路径问题 院 部： 计算机与信息工程 专 业： 网络工程 组 别： 第六组 起止日期: 2012年4月9日 2012年6月24日 指导教师: 赵玉艳 计算机与信息工程学院二一二年制课程设计题目关键路径问题组长柯焱芳学号班级网工113班院部计算机工程系专业网络工程组员靳梦婷 李鹏飞 陆勇 刘宜雨指导教师赵玉艳课程设计目的1巩固和加深学生对数据结构课程基本知识的理解，综合该课程中所学的理论知识，独立或联合完成一个数据结构应用课题的设计；2根据选题需要，通过查阅手册和文献资料，培养分析和解决实际问题的能力；3熟练掌握图的各种基本数据结构的定义、存储结构和相应的算法，并可熟练利用c语言进行实现；4具有一定的算法设计和分析能力，掌握选用合适的数据结构解决实际问题的方法；5学会撰写课程设计报告，能做出简单答辩；6培养严肃认真的工作作风和严谨求实的科学态度。课程设计所需环境 实验设备：PC机 操作系统：Windows XP 开发环境：Visio C+6.0课程设计任务要求要求学生理解图的特征和性质，掌握各类图的存储结构、相关操作的程序实现以及图的应用，能够利用图的遍历、图的最小生成树、最短路径、关键路径、拓扑排序等原理解决实际问题。课程设计工作进度计划序号起止日期工 作 内 容分工情况14.09-4.16选题与分析课题内容，查找资料柯焱芳：选题与分析课题内容陆勇 靳梦婷 李鹏飞 刘宜雨：查找资料24.17-4.25编写创建图，求最大路径的函数刘宜雨 靳梦婷：创建图李鹏飞 陆勇：求最大路径34.26-5.16编写总代码和主函数（求关键路径）柯焱芳：编写总代码和主函数（求关键路径）45.17-5.25对程序输入改写柯焱芳 靳梦婷：对程序输入改写55.26-6.10对程序进行测试柯焱芳 靳梦婷 刘宜雨 陆勇 李鹏飞66.11-6.24整理文档与总结 柯焱芳 陆勇指导教师签字： 年 月 日院（系）审核意见院长（主任）签字： 年 月 日数据结构课程设计报告目 录1 引言12 需求分析12.1问题描述12.2基本要求12.3目的23 概要设计23.1数据类型23.2 程序流程图24 详细设计34.1文件输入34.2创建图的函数34.3求关键路径45 关键路径测试76 课程设计总结与体会10参考文献11附录12致谢17数据结构课程设计报告1 引言 当一项工程划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理地组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证，这就是关键路径问题。关键路径问题相应的网称为AOE网，其中：顶点表示事件，边表示活动，边上的权表示活动持续的时间。AOE-网可以用来估算工程的完成时间。 它可以使人了解研究某个工程至少需要多少时间?哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径。2 需求分析2.1问题描述 （1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。具体要解决的问题有如下四个：（1）将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列； （2）用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图； （3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差； （4） 找出所有时差为零的活动所组成的路线，即为关键路径； 2.2基本要求 （1）选取建图的一种算法建立图： 选取邻接表的算法来建立图，是一种顺序+ 链式存储结构。用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间参照该工程所化的AOE-网，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长度最大的路径，从而求得关键路径。 2.3目的在该部分，即需求分析中，根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么，以及限制条件是什么。 程序所能达到的功能：通过输入所要构建的图的顶点数，弧数，创建图，并打印出来，对图进行拓扑排序，求得此图的最早发生时间和最迟发生时间，并求得关键活动和关键路径，打印出来。3 概要设计求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期； 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。关键路径：从源点到汇点的路径长度最长的路径叫关键路径。活动开始的最早时间e(i)；活动开始的最晚时间l(i)；定义e(i)=l(i)的活动叫关键活动；事件开始的最早时间ve(i)；事件开始的最晚时间vl(i)。在程序中进行根据课程要求，需要对数据进行文件输入，所以建文件夹，在文件夹里建input文本文档，在文本文档里写入要输入的数，通过对文档的调用，对程序进行数据输入，在文件夹建output文本文档， 程序输出到屏幕和文件 。3.1数据类型typedef struct node/边表结点 int adjvex; /邻接点编号int dut; /弧的信息 struct node *next; /下一条弧指针edgenode; typedef struct /顶点表结点 int projectname;/顶点域 int id;/顶点的入度信息 edgenode *link; /边表头指针 vexnode; 3.2 程序流程图开始文件输入求最大路径，打印关键路径主函数：求关键路径结束 图3-1程序流程图4 详细设计 4.1文件输入 根据课程设计要求需要对程序进行文件输入，对文件输入的才做如下FILE *fp1,*fp2;if(fp2= fopen(ouput.txt,w)=NULL)fprintf(fp2, 打开文件失败);return 0;if(fp1 = fopen(qq2.txt,r)=NULL)fprintf(fp2, 打开文件失败);return 0;4.2创建图的函数 在创建图的过程中begin,end,duttem分别代表弧的前节点，尾节点，活动时间，在用文件对其进行数据输入，并存储到邻接表内.输入e条弧，建立AOE网的存储结构。void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber,FILE *fp1,FILE *fp2) int begin,end,duttem; edgenode *p; for(int i=0;iprojectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(n); printf(请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n); fprintf(fp2,n); fprintf(fp2,请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n); for(int k=0;kadjvex =end-1; p-dut =duttem; Graphicmapend-1.id +; p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; 4.3求关键路径在求关键路径时，用逆拓扑排序来求活动Ai最迟完成开始时间，即从最后一个节点减去最短的时间，求出整个活动的最短完成时间和活动Ai最早完成时间，当最早完成时间和最迟完成时间相减为零时，即可求出关键路径。根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int &totaltime,FILE *fp2) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int); int* vl=(int*)malloc(projectnumber*sizeof(int); int* ve=(int*)malloc(projectnumber*sizeof(int); int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); edgenode *p; totaltime=0; for(i=0;iprojectnumber;i+) vei=0; for(i=0;iadjvex ; Graphicmapk.id -; if(vej+p-dut vek) vek=vej+p-dut ; if(Graphicmapk.id =0) topologystack+rear=k; p=p-next ; if(mprojectnumber) fprintf(fp2,n本程序所建立的图有回路不可计算出关键路径!n); fprintf(fp2,将退出本程序！n); return 0; totaltime=veprojectnumber-1; for(i=0;i=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i=0; printf(n); printf(| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n); fprintf(fp2,n); fprintf(fp2,| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); fprintf(fp2,| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) fprintf(fp2, 关键活动 ,权值%4d,Gjectname +1,Gjectname +1,p-dut); printf( 关键活动 ,权值%2d,Gjectname +1,Gjectname +1,p-dut); fprintf(fp2,n); printf(n); p=p-next ; return 1;5 关键路径测试程序完成后，在输入文件里输入不同的数据，对程序进行调试，不同的输入数据出现不同的结果：当程序通过input文本文档进行输入数据如图5-1，通过程序运行，结果输出在屏幕（图5-2）。图5-1input文件内容图5-2input文件输出的结果当输入的图会出现回路时，即qq1文档显示的数据如图5-3.由于出现回路，无法运行，出现结果如图5-4.图5-3 qq1文件内容图5-4 qq1文件的输出结果.对下图进行程序测试图5-5 活动图将上述图表示的数据输入到文本文档qq2中如图5-6所示，在通过程序实现可得出关键路径输出如图5-7所示。图5-6 qq2文件内容图5-7 qq2文件输出结果6 课程设计总结与体会课程设计的题目是关键路径问题：当一项工程划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理地组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。设计的程序，当你输入一个AOE网，就可以求出这个AOE网的关键活动。程序还是有很多不足，程序输入时只能输入整形数据，而非整形的输入则会导致程序异常停止 ，但是因为整形的输入方式已贯穿整个程序，若要修改只能另外重做整个程序，所以暂不考虑修改，而打算做一个判错系统，判断若非整形的输入则报错。历时两个月数据结构课程设计终于可以落幕了。在整个课程设计过程中，我们学到了好多知识，例如文件输入是去年学的，由于一直没有使用过，所以无从下手，又一次钻到课本与资料里。自己查资料弄出来的程序总是死机，最后找学长帮忙，程序就是那一点点的小错误造成的死机。但最后我们还是学会了，以后再编写程序需要用文件输入是就会小菜一碟。其次，关于课程设计报告方面的编写，老师对我们的要求非常严格，对课程设计报告的要求与毕业设计的格式相当，在学校网站下载了一个模版，因为写过数字逻辑报告，知道报告单复杂度不比编程序简单，有大堆的要求、规定、格式等，完成起来却真的很麻烦也很辛苦。在抱着电脑，奋斗了好今天的幸苦下，终于把报告完成了，通过对报告的编写，对于个是我们学会了很多，以后遇到要编写报告，就不会像初次这样费时费力。我认为这样的课程设计比较有意义，独立完成资料的搜集以及课设的内容，然后独立的做出报告，让这个过程很完整，无论是知识方面、还是报告的书写方面，都学到了更多的东西。还有团队合作，团队的分工合作也很重要。参考文献1 严蔚敏 吴伟民.数据结构（c语言版本）.北京:清华大学出版社,1997.42 何钦铭 颜晖.C语言程序设计.北京：高等教育出版社，2008.13 胡学钢.数据结构（c语言版本）北京：高等教育出版社，2008.10附录#include#includetypedef struct node int adjvex; int dut; struct node *next; edgenode;typedef struct int projectname; int id; edgenode *link; vexnode;void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber,FILE *fp1,FILE *fp2) int begin,end,duttem; edgenode *p; for(int i=0;iprojectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(n); printf(请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n); fprintf(fp2,n); fprintf(fp2,请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n); for(int k=0;kadjvex =end-1; p-dut =duttem; Graphicmapend-1.id +; p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int &totaltime,FILE *fp2) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int); int* vl=(int*)malloc(projectnumber*sizeof(int); int* ve=(int*)malloc(projectnumber*sizeof(int); int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); edgenode *p; totaltime=0; for(i=0;iprojectnumber;i+) vei=0; for(i=0;iadjvex ; Graphicmapk.id -; if(vej+p-dut vek) vek=vej+p-dut ; if(Graphicmapk.id =0) topologystack+rear=k; p=p-next ; if(mprojectnumber) fprintf(fp2,n本程序所建立的图有回路不可计算出关键路径!n); fprintf(fp2,将退出本程序！n); return 0; totaltime=veprojectnumber-1; for(i=0;i=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i=0; printf(n); printf(| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n); fprintf(fp2,n); fprintf(fp2,| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); fprintf(fp2,| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) fprintf(fp2, 关键活动 ,权值%4d,Gjectname +1,Gjectname +1,p-dut); printf( 关键活动 ,权值%2d,Gjectname +1,Gjectname +1,p-dut); fprintf(fp2,n); printf(n); p=p-next ; return 1;int main() FILE *fp1,*fp2;if(fp2= fopen(ouput.txt,w)=NULL)fprintf(fp2, 打开文件失败);return 0;if(fp1 = fopen(qq2.txt,r)=NULL)fprintf(fp2, 打开文件失败);retu