关键路径算法课程设计

参考文献参考文献[1]严蔚敏编.数据结构（C语言版）.北京:清华大学出版社，1997.2[2]谭浩强著.C语言程序设计（第二版）.北京:清华大出版社，2001.3[3]夏克俭编著.数据结构.北京:国防工业出版社，2000.7[4]彭勃.数据结构.北京:电子工业出版社，2007.6[5]宜晨编著.VisualC++5.0实用培训教程.北京：电子工业出版社，1998.5[6]崔武子.C语言程序设计实践教程.北京:清华大出版社,2006.1[7]庞振平.计算机程序设计基础.广州:华南理工出版社，2002.9沈阳航空工业学院课程设计报告附录附录（程序清单）#include<stdio.h>#include<stdlib.h>typedefstructnode{intadjvex;intw;structnode*nextedge;}edgenode;typedefstruct{chardata;intid;edgenode*firstedge;}vexnode;voidCreateGraph(vexnode*Graph,intvexnumber,intarcnumber){intbegin,end,duttem; charch;edgenode*p;for(inti=0;i<vexnumber;i++){Graph[i].id=0;Graph[i].firstedge=NULL; } printf("请输入这个图中的各个顶点的值:\n");for(i=0;i<vexnumber;i++){scanf("%s",&ch); Graph[i].data=ch; }printf("请输入图中弧的起始点及权值:其格式为<起点,终点,权值>\n");for(intk=0;k<arcnumber;k++){scanf("%d,%d,%d",&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p->adjvex=end-1;p->w=duttem;Graph[end-1].id++;p->nextedge=Graph[begin-1].firstedge;Graph[begin-1].firstedge=p; }}intSearchMapPath(vexnode*Graph,intvexnumber,intarcnumber){ inttotaltime=0; intm=0; inti,j,k,t; charsv[100];intfront,rear; int*topology_queue,*vl,*ve,*el,*ee; front=rear=-1;t=0;topology_queue=(int*)malloc(vexnumber*sizeof(int));vl=(int*)malloc(vexnumber*sizeof(int));ve=(int*)malloc(vexnumber*sizeof(int));el=(int*)malloc(arcnumber*sizeof(int));ee=(int*)malloc(arcnumber*sizeof(int));edgenode*p;for(i=0;i<vexnumber;i++)ve[i]=0;for(i=0;i<vexnumber;i++){if(Graph[i].id==0) topology_queue[++rear]=i; m++; }while(front!=rear){front++;j=topology_queue[front]; m++;p=Graph[j].firstedge;while(p){k=p->adjvex;Graph[k].id--;if(ve[j]+p->w>ve[k])ve[k]=ve[j]+p->w;if(Graph[k].id==0)topology_queue[++rear]=k;p=p->nextedge; } } if(m<vexnumber){printf("\n本程序所建立的图有回路不可计算出关键路径\n");printf("将退出本程序\n");return0;}totaltime=ve[vexnumber-1];for(i=0;i<vexnumber;i++)vl[i]=totaltime;for(i=vexnumber-2;i>=0;i--){j=topology_queue[i];p=Graph[j].firstedge;while(p){k=p->adjvex;if((vl[k]-p->w)<vl[j])vl[j]=vl[k]-p->w;p=p->nextedge; } }printf("|起点|终点|最早开始时间|最迟开始时间|差值|是否为关键路径\n"); i=0;for(j=0;j<vexnumber;j++) {p=Graph[j].firstedge;while(p){k=p->adjvex;ee[++i]=ve[j];el[i]=vl[k]-p->w;printf("|%4c|%4c|%12d|%12d|%4d|",Graph[j].data,Graph[k].data,ee[i],el[i],el[i]-ee[i]);if(el[i]==ee[i]){printf("此弧为关键活动"); sv[t]=Graph[j].data;t++; }printf("\n");p=p->nextedge; } } printf("关键路径节点为："); sv[t]=Graph[vexnumber-1].data; for(i=0;i<=t;i++){ printf("%c",sv[i]); if(sv[i]!=Graph[vexnumber-1].data) printf(">"); } printf("\n"); printf("关键路径长度为：%d个单位时间\n",totaltime);return1;}voidmain(){intvexnumber,arcnumber,totaltime=0;printf("请输入这个图中的节点数:");scanf("%d",&vexnumber);printf("请输入这个图中的弧数:");scanf("%d",&arcnumber);vexnode*Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode)); CreateGraph(Graph,vexnumber,arcnumber);SearchMapPath(Graph,vexnumber,arcnumber);}沈阳航空工业学院课程设计报告

课程设计总结：从这次给我的课程设计任务中我深刻地体会到了。任何事情并不是想我们想的那样简单和容易。只有扎扎时时的学习知识才能解决实际生活中的实际问题。从这次课设