ch6_2.c

数据结构讲义合集

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

void bfs(TD g[],int v,int visited[])
{  int qu[M],f=0,r=0;
   JD *p;
   printf("%d  ",v);
   visited[v]=1;
   qu[0]=v;
   while(f<=r)
   {  v=qu[f++];
      p=g[v].firstarc;
      while(p!=NULL)
      {  v=p->adjvex;
	 if(visited[v]==0)
	 {  visited[v]=1;
	    printf("%d  ",v);
            qu[++r]=v;
         }
         p=p->next;
      }
    }
}

void traver(TD g[],int n)
{  int i;
   static int visited[M];
   for(i=1;i<=n;i++)
      visited[i]=0;
   for(i=1;i<=n;i++)
      if(visited[i]==0)
	 bfs(g,i,visited);
}

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 flag and the number of node,arc:");
    scanf("%d,%d,%d",&flag,&n,&e);
    for(i=1;i<=n;i++)
    {  printf("g[%d].vexdata=",i);
       scanf("%d",&g[i].vexdata);
       g[i].firstarc=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);
	if(flag)
	{   p=(JD *)malloc(sizeof(JD));
	    p->adjvex=j;
	    p->next=g[i].firstarc;
	    g[i].firstarc=p;
	}
	else
	{   p=(JD *)malloc(sizeof(JD));
	    p->adjvex=j;
	    p->next=g[i].firstarc;
	    g[i].firstarc=p;
	    p=(JD *)malloc(sizeof(JD));
	    p->adjvex=i;
	    p->next=g[j].firstarc;
	    g[j].firstarc=p;
	}
    }
    return(n);
}

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