AutoCAD 3DMAX C语言 Pro/E UG JAVA编程 PHP编程 Maya动画 Matlab应用 Android
Photoshop Word Excel flash VB编程 VC编程 Coreldraw SolidWorks A Designer Unity3D
 首页 > VC编程

数据结构中关键路径算法的实现与应用

51自学网 2015-08-30 http://www.wanshiok.com

 

    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)

    {

       printf("/n本程序所建立的图有回路不可计算出关键路径/n");

       printf("将退出本程序/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");

    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 |    %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 ;

       }

    }

    return 1;

}

void seekkeyroot()

{

    int projectnumber,activenumber,totaltime=0;

    system("cls");

    printf("请输入这个工程的化成图形的节点数:");

    scanf("%d",&projectnumber);

  printf("请输入这个工程的活动个数:");

  scanf("%d",&activenumber);

  vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));

  CreateGraphic(Graphicmap,projectnumber,activenumber);

  SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);

  printf("整个工程所用的最短时间为:%d个单位时间/n",totaltime);

  system("pause");

}

int main()

{



    char ch;

    for(;;)

    {

       do

       {

           system("cls");

           printf("|             欢迎进入求关键路径算法程序              |");

      for(int i=0;i<80;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':

           return 1;

     }

    }

}

4: 总结: 

至此,全部的设计过程完毕,上面所有代码已经在VC6.0+Win2000平台下调试成功。从上面的分析可以看出 ,设计结果与预测的相符合.

关键路径在具体的工程中有着重要的作用,当一个AOE网络中的关键路径只有一条时,加速关键路径上的任一关键活动,能够加速整个工程的完成。但当一个AOE网络中的关键路径不止一条时,加速任一关键活动不一定能够加速整个工程的完成。

如方案1与方案2在改变关键路径时整个工程的进度没有改变。

参 考 资 料

[1]谭浩强编著. C程序设计(第二版).北京:清华大学出版社,2000

[2]严蔚敏,吴伟民编著.数据结构.北京:清华大学出版社,2001

[3]刘正林编著.面向对象程序设计.武汉:华东科技大学出版社,2002

[4]宜 晨编著.Visual C++5.0实用培训教程.北京:电子工业出版社,1998

 
 
说明
:本教程来源互联网或网友上传或出版商,仅为学习研究或媒体推广,wanshiok.com不保证资料的完整性。

上一篇:vc6.0工具使用的几个技巧  下一篇:用MFC对话框做无闪烁图片重绘