006.c

用C语言实现数据结构的几种常用结构

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100
#define TRUE 1
#define FALSE 0
#define MAXEDGE 100 
typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
typedef float AdjType;

struct EdgeNode
{ int endvex;             /* 相邻顶点字段 */
  AdjType weight;
  PEdgeNode nextedge;     /* 链字段 */
};                        /* 边表中的结点 */
typedef struct
{ int vertex;
  EdgeList edgelist;      /* 边表头指针 */
} VexNode;

typedef struct
{VexNode vexs[MAXVEX];    /* 顶点表中的结点 */
 int n;                  /* 图的顶点个数 */
}GraphList;

typedef struct
{int vexsno[MAXVEX];     /* 顶点在顶点表中的下标值 */
}Topo;

void findInDegree(GraphList* g, int *inDegree)   /* 求出图中所有顶点的入度 */
{int i;
 PEdgeNode p;
 for(i=0; i<g->n; i++)
   inDegree[i] = 0;
 for(i=0; i<g->n; i++)
 {p = g->vexs[i].edgelist;
   while(p)
    {++inDegree[p->endvex];
      p = p->nextedge;
    }
  }
}

void makeNewAOV(EdgeList p,int* indegree,int* top)
{int k;
 while(p)                               /* 删除以该顶点为起点的边 */
 {k=p->endvex;
   indegree[k]--;
  if(indegree[k]==0)                   /* 将新的入度为零的边入栈 */
  {indegree[k]=*top;
    *top=k;
  }
  p=p->nextedge;
 }
}

int topoSort(GraphList *paov,Topo *ptopo)             /* 拓扑排序算法*/
{EdgeList p;
 int i, j,nodeno=0, top=-1;
 int indegree[MAXVEX];
  findInDegree(paov,indegree);                /* 求出图中所有顶点的入度 */
  for(i=0; i<paov->n; i++)
    if(indegree[i]==0)                        /* 将入度为零的顶点入栈 */
      {indegree[i]=top; top=i; }
        while(top!=-1)
        {j=top;
         top=indegree[top];               /* 取出当前栈顶元素 */
         ptopo->vexsno[nodeno]=paov->vexs[j].vertex; /* 将该元素输出到拓扑序列中 */
          ptopo->vexsno[nodeno++]=j;
        p=paov->vexs[j].edgelist;         /* 取该元素边表中的第一个边结点 */
        makeNewAOV(p,indegree,&top);      /*删除该结点,构造新的AOV网*/
         }
     if(nodeno<paov->n)       /* AOV网中存在回路 */
      {printf("The aov network has a cycle.\n");
       return(FALSE);
       }
      return(TRUE);
}

void insert(GraphList*p,int a,int b,float weight)
{   EdgeList pp;
    PEdgeNode temp;
    temp=(PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex=b;
    temp->nextedge=NULL;
    temp->weight=weight;
    pp=p->vexs[a].edgelist;
    if(pp==NULL)p->vexs[a].edgelist=temp;
    else{
        while(pp->nextedge!=NULL)
            pp=pp->nextedge;
        pp->nextedge=temp;
    }
}
    
GraphList* makeList()            /* 邻接表的构造*/
{ GraphList*p;
  int i;
  int a,b,weight;
  int s;
  p=(GraphList*)malloc(sizeof(GraphList));
  printf("please input the number of the vertex:");
  scanf("%d",&(p->n));
  for(i=0;i<p->n;i++)
    p->vexs[i].edgelist=NULL;
  printf("please input the vertexs and the weight:\n");
  do{printf("from=>");   scanf("%d",&a);
     printf("to=>");    scanf("%d",&b);
     printf("weight=>");   scanf("%d",&weight);
     insert(p,a,b,weight);
     do
     {printf("press 1 to go on input.    press 2  to stop.\n");
      scanf("%d",&s);
      if(s<1||s>2)
       printf("ERROR!input again.\n");
     }while(s<1||s>2);
    }while(s!=2);
    return p;
}

void countee(GraphList*paoe,Topo*ptopo, AdjType*ee)/* 计算数组ee*/
{int  i,j,k;EdgeList p;
 for(i=0; i<paoe->n; i++)  ee[i]=0;
 for(k=0; k<paoe->n; k++)                           /* 求事件vj可能的最早发生时间ee(j) */
 {i=ptopo->vexsno[k]; p=paoe->vexs[i].edgelist;
  while (p!=NULL)
  {j=p->endvex;
    if(ee[i]+p->weight>ee[j])
    ee[j]=ee[i]+p->weight;
   p=p->nextedge;
  }
 }
}

void countle(GraphList *paoe,Topo*ptopo, AdjType*ee, AdjType*le)     /* 计算数组le*/
{int  i,j,k;EdgeList p;
 for(i=0;i<paoe->n; i++)                  /* 求事件vi允许的最迟发生时间le(i) */
  le[i]=ee[paoe->n-1];
 for(k=paoe->n-2; k>=0; k--)
 {i=ptopo->vexsno[k];
  p=paoe->vexs[i].edgelist;
  while(p!=NULL)
  {j=p->endvex;
    if( (le[j]-p->weight)<le[i]) le[i]=le[j]-p->weight;
     p=p->nextedge;
  }
 }
}

void counte_l(GraphList *paoe,Topo *ptopo, AdjType*ee,AdjType*le, AdjType*e, AdjType*l)
{int i,j,k ;EdgeList p; k=0;
  for(i=0;i<paoe->n;i++)    /* 求活动ak的最早开始时间e(k)及最晚开始时间l(k) */
  {p=paoe->vexs[i].edgelist;
   while(p!=NULL)
   {j=p->endvex; e[k]=ee[i];
    l[k]=le[j]-p->weight;
    if(e[k]==l[k])
    printf("<v%2d,v%2d>, ",i,j);
    k++;
    p=p->nextedge;
   }
  }
}

int CriticalPath(GraphList * paoe)    /* 关键路径算法*/
{AdjType ee[MAXVEX], le[MAXVEX], l[MAXEDGE], e[MAXEDGE];
 Topo topo;
  if(topoSort(paoe,&topo)==FALSE)               /* 求AOE网的一个拓扑序列 */
    return(FALSE);
  countee(paoe,&topo, ee);                 /*计算数组ee*/
  countle(paoe,&topo, ee,le);              /*计算数组le*/
  counte_l(paoe,&topo, ee,le, e, l);       /*计算数组e,l并输出结果*/
  printf("\n");
  return(TRUE);
}

gua()
{ GraphList* p;
  Topo topo;
  int i;
  p=makeList();
   if(topoSort(p,&topo)==TRUE)
    if(CriticalPath(p)==FALSE)
        printf("There is no critical path!\n");
    else
    {printf("the critical path is:\n");
      for(i=0;i<p->n;i++)
       printf("%d\t",topo.vexsno[i]);
    }
 getch();
}