滁州学院课程设计报告课程名称：数据结构设计题目：关键路径问题院部：计算机与信息工程专业：网络工程组别：第六组起止日期:2012年4月9日~2012年6月24日指导教师:赵玉艳计算机与信息工程学院二○一二年制课程设计题目关键路径问题组长柯焱芳学号2011211384 班级网工113班院部计算机工程系专业网络工程组员靳梦婷李鹏飞陆勇刘宜雨指导教师赵玉艳课程设计目的1．巩固和加深学生对数据结构课程基本知识的理解，综合该课程中所学的理论知识，独立或联合完成一个数据结构应用课题的设计；2．根据选题需要，通过查阅手册和文献资料，培养分析和解决实际问题的能力；3．熟练掌握图的各种基本数据结构的定义、存储结构和相应的算法，并可熟练利用c语言进行实现；4．具有一定的算法设计和分析能力，掌握选用合适的数据结构解决实际问题的方法；5．学会撰写课程设计报告，能做出简单答辩；6．培养严肃认真的工作作风和严谨求实的科学态度。
课程设计所需环境⑴实验设备：PC机⑵操作系统：Windows XP ⑶开发环境：VisioC++6.0课程设计任务要求要求学生理解图的特征和性质，掌握各类图的存储结构、相关操作的程序实现以及图的应用，能够利用图的遍历、图的最小生成树、最短路径、关键路径、拓扑排序等原理解决实际问题。
课程设计工作进度计划序号起止日期工作内容分工情况1 4.09-4.16 选题与分析课题内容，查找资料柯焱芳：选题与分析课题内容陆勇靳梦婷李鹏飞刘宜雨：查找资料2 4.17-4.25 编写创建图，求最大路径的函数刘宜雨靳梦婷：创建图李鹏飞陆勇：求最大路径34.26-5.16 编写总代码和主函数（求关键路径）柯焱芳：编写总代码和主函数（求关键路径）4 5.17-5.25 对程序输入改写柯焱芳靳梦婷：对程序输入改写5 5.26-6.10 对程序进行测试柯焱芳靳梦婷刘宜雨陆勇李鹏飞6 6.11-6.24 整理文档与总结柯焱芳陆勇指导教师签字：年月日院（系）审核意见院长（主任）签字：年月日目录1 引言 (1)2 需求分析 (1)2.1问题描述 (1)2.2基本要求 (1)2.3目的 (2)3 概要设计 (2)3.1数据类型 (2)3.2 程序流程图 (2)4 详细设计 (3)4.1文件输入 (3)4.2创建图的函数 (3)4.3求关键路径 (4)5 关键路径测试 (7)6 课程设计总结与体会 (10)参考文献 (11)附录 (12)致谢 (17)当一项工程划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理地组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证，这就是关键路径问题。
关键路径问题相应的网称为AOE网，其中：顶点表示事件，边表示活动，边上的权表示活动持续的时间。
AOE-网可以用来估算工程的完成时间。
它可以使人了解⑴研究某个工程至少需要多少时间?⑵哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。
完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。
因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径。
2 需求分析2.1问题描述（1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。
（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。
对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。
完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。
具体要解决的问题有如下四个：（1）将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；（2）用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；（3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；（4）找出所有时差为零的活动所组成的路线，即为关键路径；2.2基本要求（1）选取建图的一种算法建立图：选取邻接表的算法来建立图，是一种顺序+ 链式存储结构。
用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。
（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间参照该工程所化的AOE-网，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长度最大的路径，从而求得关键路径。
在该部分，即需求分析中，根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么，以及限制条件是什么。
程序所能达到的功能：通过输入所要构建的图的顶点数，弧数，创建图，并打印出来，对图进行拓扑排序，求得此图的最早发生时间和最迟发生时间，并求得关键活动和关键路径，打印出来。
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条弧<j,k>，建立AOE网的存储结构。
void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber,FILE *fp1,FILE *fp2){int begin,end,duttem;edgenode *p;for(int i=0;i<projectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id =0;Graphicmap[i].link =NULL;}printf("\n");printf("请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：\n"); fprintf(fp2,"\n");fprintf(fp2,"请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：\n"); for(int k=0;k<activenumber;k++){fscanf(fp1,"%d%*c%d%*c%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;}}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;i<projectnumber;i++) ve[i]=0;for(i=0;i<projectnumber;i++){if(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link ;while(p){k=p->adjvex ;Graphicmap[k].id --;if(ve[j]+p->dut >ve[k])ve[k]=ve[j]+p->dut ;if(Graphicmap[k].id ==0)topologystack[++rear]=k;p=p->next ;}}if(m<projectnumber){fprintf(fp2,"\n本程序所建立的图有回路不可计算出关键路径!\n");fprintf(fp2,"将退出本程序！\n");return 0;}totaltime=ve[projectnumber-1];for(i=0;i<projectnumber;i++)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");printf("| 起点| 终点| 最早开始时间| 最迟完成时间| 差值| 备注\n"); fprintf(fp2,"\n");fprintf(fp2,"| 起点| 终点| 最早开始时间| 最迟完成时间| 差值| 备注\n"); for(j=0;j<projectnumber;j++){p=Graphicmap[j].link;while(p){k=p->adjvex ;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("| %4d | %4d | %11d | %11d | %3d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);fprintf(fp2,"| %4d | %4d | %11d | %11d | %3d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i]) {fprintf(fp2," 关键活动<%2d,%4d>,权值%4d",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,p->dut);printf(" 关键活动<%2d,%4d>,权值%2d",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,p->dut);}fprintf(fp2,"\n");printf("\n");p=p->next ;}}return 1;}5 关键路径测试程序完成后，在输入文件里输入不同的数据，对程序进行调试，不同的输入数据出现不同的结果：⑴当程序通过input文本文档进行输入数据如图5-1，通过程序运行，结果输出在屏幕（图5-2）。