ch6_4.c

数据结构的一些小算法

#include <stdio.h>
#include <alloc.h>
#define M 10
typedef struct node
{   int vex;
    struct node *next;
}JD;
typedef struct tnode
{   int vexdata;
    int in;
    struct node *link;
}TD;

void toposort(TD g[],int n)
{  int top,m,k,j;
   JD *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)
     {  g[j].in=top; 
        top=j;
     }
   while(top>0)
   {  j=top;
      top=g[top].in;
      printf("%d  ",j);
      m++;
      p=g[j].link;
      while(p!=NULL)
      {  k=p->vex;
	 g[k].in--;
	 if(g[k].in==0)
	 {   g[k].in=top;
	     top=k;
	 }
	 p=p->next;
      }
   }
   printf("\nm=%d\n",m);
   if(m<n)  printf("The network has a cycle\n");
}

int loc_vertex(TD g[],int vex,int n)
{   int i,j;
    for(i=1;i<=n;i++)
       if(g[i].vexdata==vex)
	   return(i);
    return(0);
}
int crt_linklist(TD g[])
{   int n,e,i,j,k,vt,vh,flag;
    JD *p;
    printf("Input and the number of node,arc:");
    scanf("%d,%d",&n,&e);
    for(i=1;i<=n;i++)
    {  printf("g[%d].vexdata=",i);
       scanf("%d",&g[i].vexdata);
       g[i].in=0;
       g[i].link=NULL;
    }
    for(k=1;k<=e;k++)
    {   printf("Vt,Vh:");
	scanf("%d,%d",&vt,&vh);
	i=loc_vertex(g,vt,n);
	j=loc_vertex(g,vh,n);
	p=(JD *)malloc(sizeof(JD));
	p->vex=j;
	p->next=g[i].link;
	g[i].link=p;
    }
    return(n);
}

void cal_in(TD g[],int n)
{  int i,k;
   JD *p;
   for(i=1;i<=n;i++)
   {  p=g[i].link;
      while(p!=NULL)
      {  k=p->vex;
	 g[k].in++;
	 p=p->next;
      }
   }
}

void main()
{  int n;
   TD g[M];
   n=crt_linklist(g);
   cal_in(g,n);
   toposort(g,n);
}