习题3-拓扑排序.c

数据结构各章实验源代码； 数据结构实验源代码

#include <stdio.h>
#include <malloc.h>
#include "datastru.h"

ADJGRAPH creat_adjgraph()
{/*建立有向图的邻接链表结构*/
  EDGENODE *p;
  int i,s,d;
  ADJGRAPH adjg;

  adjg.kind = 1;
  printf("\n\n输入顶点数和边数(用逗号隔开) : ");
  scanf("%d,%d", &s,&d);fflush(stdin);
  adjg.vexnum = s;                           /*存放顶点数在adjg.vexnum中 */
  adjg.arcnum = d;                           /*存放边点数在adjg.arcnum中*/
  printf("\n\n");
  for(i = 0; i < adjg.vexnum; i++)           /*邻接链表顶点初始化*/
    {printf("输入顶点 %d 的值 : ", i + 1);
     scanf("%d", &adjg.adjlist[i].vertex);   /*输入顶点的值*/
     fflush(stdin);
     adjg.adjlist[i].link = NULL;
     adjg.adjlist[i].id = 0;}
     printf("\n\n");
  for(i = 0; i < adjg.arcnum; i++)
	{printf("输入第 %d 条有向弧的起始顶点和终止顶点(用逗号隔开): ", i + 1);
	 scanf("%d,%d",&s,&d);                   /*输入弧的起始顶点和终止顶点*/
	 fflush(stdin);
     while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum)
	   {printf("输入错，重新输入: ");
	    scanf("%d,%d", &s,&d);}
	 s --;
	 d --;
	 p = malloc(sizeof(EDGENODE));           /*每条弧对应生成一个结点*/
	 p->adjvex = d;
	 p->next = adjg.adjlist[s].link;         /*结点插入对应的单链表上*/
	 adjg.adjlist[s].link = p;
	 adjg.adjlist[d].id++;}                  /*弧的终端顶点入度加1*/
return adjg;
}

void topsort(ADJGRAPH ag)
{	int i, j, k, m, n, top;
	EDGENODE *p;

	n = ag.vexnum;
	top = -1;                               /*拓扑排序中用到的栈初始化*/
	for(i = 0; i < n; i++)
	   if(ag.adjlist[i].id == 0)            /*入度为0的结点压入一链栈，top指向栈顶结点*/
	     { ag.adjlist[i].id = top;
	       top = i;}
	m = 0;
	printf("\n\n有向图拓扑排序结果 : ");
    while(top != -1)                        /*栈不空，进行拓扑排序*/
	  {j = top;                             /*取栈顶元素*/
	   top = ag.adjlist[top].id;            /*删除一个栈顶元素*/
	   printf("  %d", ag.adjlist[j].vertex);/*输出一个拓扑排序结点即栈顶元素*/
	   m++;                                 /*拓扑排序结点计数加1*/
	   p = ag.adjlist[j].link;
	   while(p != NULL)                     /*如果拓扑排序结点有出度*/
	     {k = p->adjvex;
	      ag.adjlist[k].id--;               /*删除相关的弧，即弧终点结点的入度减1*/
	      if(ag.adjlist[k].id == 0)         /*出现新的入度为0的顶点，将其入栈*/
		  {ag.adjlist[k].id = top;
		   top = k;}
	      p = p->next;}}
	if(m < n)
	   printf("\n\n有向图中有环路 !\n\n");  /*拓扑排序过程中输出的顶点数<有向图的顶点数*/
}

main()
{ ADJGRAPH ag;

  printf("\n有向图的拓扑排序\n");
  ag = creat_adjgraph();          /*建立有向图的邻接链表结构*/
  topsort(ag);                    /*进行拓扑排序*/
  printf("\n\n");
}