复件 7_3.txt

来自「数据结构及算法经典 讲述数据结构的经典算法c源程序」· 文本 代码 · 共 100 行

#include<stdio.h>
typedef struct node{
  int data;
  struct node *next;
 }Node;
typedef struct adjnode{
  char ch[10];
  Node *firstarc;
 }Adjnode;
locate(Adjnode *adj,int n,char *s)
 {
  int i;
  for(i=0;i<n;i++)
   if(strcmp(adj[i].ch,s)==0)return i;
  return -1;
 }
createadj(Adjnode **adj,int n,int e)
 {char *s,*t; int i,j,k;
  Node *p,*q;
  printf("Please input the numbers of vertex:\n");
  for(i=0;i<n;i++)
   { gets(s);
    strcpy((*adj)[i].ch,s);
    (*adj)[i].firstarc=NULL;
   }
    printf("Please input the edges:\n");  /*如v1回车v2回车表明有v1到v2的边*/
   for(i=1;i<=e;i++)
   {
    gets(s);
    gets(t);
    j=locate(*adj,n,s);
    k=locate(*adj,n,t);   
    if(k>=0 && j>=0){
     p=(Node *)malloc(sizeof(Node));
     p->data=k;p->next=NULL;
     q=(Node *)malloc(sizeof(Node));
     q->data=j;q->next=NULL;
     p->next=(*adj)[j].firstarc;
     (*adj)[j].firstarc=p;
     q->next=(*adj)[k].firstarc;
     (*adj)[k].firstarc=q;
     }
     else
     printf("The vertexs are wrong!\n");
   }
 }
 createinvadj(Adjnode *adj,Adjnode **invadj,int n,int e)
 {
  Node *p,*q;int i,j;
  for(i=0;i<n;i++)                    /*逆邻接表初始化*/
   {
    strcpy((*invadj)[i].ch,adj[i].ch);
    (*invadj)[i].firstarc=NULL;
    }
    for(i=0;i<n;i++)                  /*建立逆邻接表*/
   {
    p=adj[i].firstarc;
    while(p){
     q=(Node *)malloc(sizeof(Node));
     j=p->data;
     q->data=i;
     q->next=(*invadj)[j].firstarc;
     (*invadj)[j].firstarc=q;
     p=p->next;
    }
   }
 }
printadj(Adjnode *adj,int n)
 {
  Node *p;int i;
   for(i=0;i<n;i++)                  
    {
    p=adj[i].firstarc;
    while(p){
     printf("%s->%s\n",adj[i].ch,adj[p->data].ch);
     p=p->next;
     }
     } 
  }

main()
{
 int n,e,i;
 Adjnode *adj,*invadj;
 printf("Please input the numbers of vertexs and edges:\n");
 do
 scanf("%d%d",&n,&e);
 while(n<=0 || e<=0);
 getchar();
 adj=(Adjnode *)malloc(sizeof(Adjnode)*n);
 invadj=(Adjnode *)malloc(sizeof(Adjnode)*n);
 createadj(&adj,n,e);
 createinvadj(adj,&invadj,n,e);
printadj(adj,n);
 /*for(i=0;i<n;i++)
  printf("%s\n",adj[i].ch);*/

printadj(invadj,n);
 }