开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 电子书籍 > 软件工程 > 查看源码
CH6_20.C
资源名称：数据结构（ C语言版） 讲义.rar　[点击查看]
上传用户：lgb298
上传日期：2013-03-22
资源大小：1025k
文件大小：3k
源码类别：

软件工程

开发平台：

C/C++

CH6_20.C：源码内容
  1. #include <stdio.h>
  2. #include <alloc.h>
  3. #define M 20
  4. #define MAX 100
  5. typedef struct node
  6. {   int vex;
  7.     int length;
  8.     struct node *next;
  9. }JD;
  10. typedef struct tnode
  11. {   int vexdata;
  12.     int in;
  13.     struct node *link;
  14. }TD;
  16. int loc_vertex(TD g[],int vex,int n)
  17. {   int i,j;
  18.     for(i=1;i<=n;i++)
  19.        if(g[i].vexdata==vex)
  20.    return(i);
  21.     return(0);
  22. }
  23. int crt_linklist(TD g[])
  24. {   int n,e,i,j,k,vt,vh,length;
  25.     JD *p;
  26.     printf("Input and the number of node,arc:");
  27.     scanf("%d,%d",&n,&e);
  28.     for(i=1;i<=n;i++)
  29.     {  printf("g[%d].vexdata=",i);
  30.        scanf("%d",&g[i].vexdata);
  31.        g[i].in=0;
  32.        g[i].link=NULL;
  33.     }
  34.     for(k=1;k<=e;k++)
  35.     {   printf("Vt,Vh,length:");
  36. scanf("%d,%d,%d",&vt,&vh,&length);
  37. i=loc_vertex(g,vt,n);
  38. j=loc_vertex(g,vh,n);
  39. p=(JD *)malloc(sizeof(JD));
  40. p->vex=j;
  41. p->length=length;
  42. p->next=g[i].link;
  43. g[i].link=p;
  44.     }
  45.     return(n);
  46. }
  48. void cal_in(TD g[],int n)
  49. {  int i,k;
  50.    JD *p;
  51.    for(i=1;i<=n;i++)
  52.    {  p=g[i].link;
  53.       while(p!=NULL)
  54.       {  k=p->vex;
  55.  g[k].in++;
  56.  p=p->next;
  57.       }
  58.    }
  59. }
  61. int dut(TD g[],int vt,int vh)
  62. {  JD *p;
  63.    p=g[vt].link;
  64.    while(p!=NULL)
  65.    {   if(p->vex==vh)
  66.    return(p->length);
  67.        else
  68.   p=p->next;
  69.    }
  70.    return(MAX);
  71. }
  73. int toporder(TD g[],int n,int ve[],int top2[],int *t2)
  74. {  int top1[M];
  75.    int m,k,j,top;
  76.    JD *p;
  77.    top=0; m=0;
  78.    for(j=1;j<=n;j++)
  79.       ve[j]=0;
  80.    for(j=1;j<=n;j++)
  81.      if(g[j].in==0)
  82.      {  top1[top]=j;
  83. top++;
  84.      }
  85.    while(top>0)
  86.    {  j=top1[--top];
  87.       top2[*t2]=j;
  88.       (*t2)++;
  89.       m++;
  90.       p=g[j].link;
  91.       while(p!=NULL)
  92.       {  k=p->vex;
  93.  g[k].in--;
  94.  if(g[k].in==0)
  95.     top1[top++]=k;
  96.  if(ve[j]+dut(g,j,k)>ve[k])
  97.     ve[k]=ve[j]+dut(g,j,k);
  98.  p=p->next;
  99.       }
  100.    }
  101.    if(m<n)  return(0);
  102.    else     return(1);
  103. }
  105. void critical_path(TD g[],int n)
  106. {   int i,t2=0,j,k,ee,el;
  107.     char tag;
  108.     JD *p;
  109.     int ve[M],vl[M],top2[M];
  110.     i=toporder(g,n,ve,top2,&t2);
  111.     if(!i)
  112.        printf("Has a cycle!");
  113.     else
  114.     {  for(i=1;i<=n;i++)
  115.   vl[i]=MAX;
  116.        vl[n]=ve[n];
  117.        while(t2>0)
  118.        {  j=top2[--t2];
  119.   p=g[j].link;
  120.   while(p!=NULL)
  121.   {  k=p->vex;
  122.      if(vl[k]-dut(g,j,k)<vl[j])
  123.   vl[j]=vl[k]-dut(g,j,k);
  124.      p=p->next;
  125.   }
  126.        }
  127.        for(j=1;j<=n;j++)
  128.        {  p=g[j].link;
  129.   while(p!=NULL)
  130.   {  k=p->vex;
  131.      ee=ve[j];
  132.      el=vl[k]-dut(g,j,k);
  133.      if(ee==el)
  134.  tag='*';
  135.      else
  136.  tag=' ';
  137.      printf("Vt=%d,Vh=%d,Length=%d,ee=%d,el=%d,%cn",j,k,dut(g,j,k),ee,el,tag);
  138.      p=p->next;
  139.   }
  140.        }
  141.     }
  142. }
  144. void main()
  145. {  int n;
  146.    TD g[M];
  147.    n=crt_linklist(g);
  148.    cal_in(g,n);
  149.    critical_path(g,n);
  150. }