5.2.c

自己写的数据结构课程程序

#include<stdio.h>
#define MAX_VERTEX_NUM 20
#define NULL 0
struct ArcNode
{int adjvex;
 struct ArcNode* nextarc;
};
struct VNode
{char data[50];
 struct ArcNode* firstarc;
};
struct ALGraph
{struct VNode vertices[MAX_VERTEX_NUM+1];
 int vexnum,arcnum;
 int kind;
};
struct Node
{int vex;
 struct Node* next;
};
struct Stack
{struct Node* base;
 struct Node* top;
 int stacksize;
};
struct Stack S;
struct ALGraph G;
int *indegree;
void CreatALGraph()
{int i,v;
 struct ArcNode *p,**q;
 printf("please input the number of vertexs:\n");
 scanf("%d",&G.vexnum);
 getchar();
 for(i=1;i<=G.vexnum;i++)
   G.vertices[i].firstarc=NULL;
 printf("please input the data of every vertex first:\n");
 for(i=1;i<=G.vexnum;i++)
   {scanf("%s",G.vertices[i].data);
    printf("continue.\n");
   }
 getchar();
 printf("now input the neighbors:\n");
 for(i=1;i<=G.vexnum;i++)
   {printf("please input the neighbors of %d\n",i);
    q=&G.vertices[i].firstarc;
    while(1)
      {scanf("%d",&v);
       if(v==0)
         break;
       else
         {p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
          p->adjvex=v;
          p->nextarc=NULL;
          *q=p;
          q=&p->nextarc;
         }
      }

   }
 printf("success!\n");
}
void FindInDegree()
{int i;
 struct ArcNode *p;
 indegree=(int *)malloc(G.vexnum*sizeof(int));
 for(i=1;i<=G.vexnum;i++)
   indegree[i]=0;
 for(i=1;i<=G.vexnum;i++)
   {p=G.vertices[i].firstarc;
    while(p)
      {indegree[p->adjvex]++;
       p=p->nextarc;
      }
   }
}
void InitStack()
{S.base=NULL;
 S.top=(struct Node*)malloc(sizeof(struct Node));
 S.top->next=NULL;
}
void Push(int i)
{struct Node *p;
 S.top->vex=i;
 p=(struct Node*)malloc(sizeof(struct Node));
 p->next=S.top;
 S.top=p;
}
int StackEmpty()
{if(S.top==S.base)
   return 1;
 else
   return 0;
}
void Pop(int *p)
{S.top=S.top->next;
 *p=S.top->vex;
}
void TopologicalSort()
{int i,k,count;
 struct ArcNode *p;
 FindInDegree();
 InitStack();
 for(i=1;i<=G.vexnum;++i)
   if(!indegree[i])
     Push(i);
 count=0;
 printf("the sequence is:\n");
 while(!StackEmpty())
  {Pop(&i);
   printf("%s ",G.vertices[i].data);
   ++count;
   for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     {k=p->adjvex;
      if(!(--indegree[k]))
        Push(k);
     }
  }
 printf("\n");
 if(count<G.vexnum)
   printf("print error!\n");
 else
   printf("print ok!\n");
}
void main(void)
{CreatALGraph();
 TopologicalSort();
 getchar();
 getchar();
}