sy7_6.c

数据结构实验与学习指导

#include "stdio.h"
#include "conio.h"
#define VERTEX_MAX 30   /*最大顶点数*/
#define VEX_NUM 10
typedef char Vextype[3];  /*顶点类型*/
typedef struct node       /*边结点定义*/
 {
    int  adjvex;          /*邻接点域*/
    struct node  *next; /*指向下一个边结点的指针域*/
  }EdgeNode;
typedef struct vnode   /*表头结点定义*/
 { int indegree;        /*顶点入度域*/
   Vextype  vertex;     /*顶点信息*/
   EdgeNode   *firstedge;
  }VertexNode;
typedef struct                        /*图的邻接表存储*/
 { VertexNode adjlist[VERTEX_MAX];
   int n,e;                            /*顶点数和边数*/
 } ALGraph;
void CreateALGraph(ALGraph *G) /*创建有向图的邻接表*/
{ int i,j,k;
  int vin[VERTEX_MAX]={0};
  EdgeNode * s,*p;
  printf("请输入顶点数和弧数:");    /*输入顶点数n和弧数m*/
  scanf("%d,%d",&(G->n),&(G->e));
  printf("输入顶点信息，如V0,V1等:");
  for (i=0;i<G->n;i++)
     { scanf("%s",&(G->adjlist[i].vertex));
       G->adjlist[i].firstedge=NULL;  
     }
  printf("请输入弧的信息<i,j>\n");
  for (k=0;k<G->e;k++) /*建立边表*/
     { scanf("%d,%d",&i,&j);
       s=(EdgeNode*)malloc(sizeof(EdgeNode));
       s->adjvex=j;
       vin[j]++;  /*统计各顶点的入度*/
       s->next=G->adjlist[i].firstedge;    /*前插方法*/
       G->adjlist[i].firstedge=s;
     }
   for(i=0;i<G->n;i++)
     G->adjlist[i].indegree=vin[i];
   for (i=0;i<G->n;i++)
   { printf("%s ",G->adjlist[i].vertex);
     printf("%d ",G->adjlist[i].indegree);
     p=G->adjlist[i].firstedge;
     while (p)
      {
        printf("->%d",p->adjvex);
        p=p->next;
      }
    printf("\n");
   }
}/*CreateALGraph*/
int topsort( ALGraph *G) /*拓扑排序过程*/
{
   int i,j,k,top;
   EdgeNode   *ptr;
   top=-1;
   for(i=0;i<G->n;i++)    /*将入度为0的顶点入栈*/
   {
     if(G->adjlist[i].indegree==0)
     {
      G->adjlist[i].indegree=top;
      top=i;
     }
   }
  for(i=0;i<G->n;i++)
  {
    if(top==-1) return -1;   /*AOV网中有回路*/
     j=top;
     top=G->adjlist[top].indegree;   /*从栈中退出一个入度为0的顶点并输出*/
     printf("->%s",G->adjlist[j].vertex);
     ptr=G->adjlist[j].firstedge;
     while(ptr!=NULL)
     {
       k=ptr->adjvex;
       G->adjlist[k].indegree--;  /*修改其他顶点的入度*/
       if(G->adjlist[k].indegree==0)   /*为0则入栈*/
        {
          G->adjlist[k].indegree=top;
          top=k;
        }
       ptr=ptr->next;
     }
  }
}
main()
{  int flag;
    ALGraph *g;
    g=(ALGraph *)malloc(sizeof(ALGraph));
    CreateALGraph(g);
    flag=topsort(g);
    if (flag==-1) printf("有回路");
}