topologicalsort.cpp

文件夹中包括常用的数据结构的算法

#include <stdio.h>
#include <malloc.h>
#define MAX_VERTEX_NUM	20
#define NULL 0

//邻接表结点：
typedef   struct  Jnode
{    int  vex;   //顶点域
     struct  Jnode  *Nextarc;   //链域
}Jnode;

//表头结点：
typedef  struct  tnode
{
	int data;
	int  in;  //入度域
    Jnode  *firstarc;    //链域
}tnode;

typedef  struct ALGrahp
{
	//int data;
    tnode vertices[MAX_VERTEX_NUM];   //图的表头结点
	int vexnum;                       //图的顶点数
}ALGrahp;



// G采用邻接表。
// G无回路，则输出G的顶点的一个拓扑序列，OK,否则ERROR
void TopologicalSort( ALGrahp &G)
{
   	//	FindInDegree( G, indegree );	// 求个顶点的入度；
	int stack[MAX_VERTEX_NUM];
    int sTop=0;

	for(int j = 0; j < G.vexnum; j++ )
	{
		if( !G.vertices[j].in )
		{
			stack[sTop++] = j;
		}
	}

    int	count = 0;
	while(sTop > 0)    //注意判断条件sTop>0
	{
		int i = stack[--sTop] ;     //Pop( S, i );
		printf("%d,\t", G.vertices[i].data );  //从栈中弹出入度为零的顶点， 打印
		count++;
        Jnode *p = G.vertices[i].firstarc;

		while(p)
		{
		    int	k = p->vex -1;	// 取邻接点的位置，入度减1
			if( !( --G.vertices[k].in ))
			{
				stack[sTop++] = k;	// 若是0，入栈，等待处理
			}
            p=p->Nextarc;
		}


/*		for(Jnode *p = G.vertices[i].firstarc; p; p=p->Nextarc)  //至少执行一次所以当p==NULL时同样执行一次，所以错误
		{
		    int	k = p->vex -1;	// 取邻接点的位置，入度减1
			if( !( --G.vertices[k].in ))
			{
				stack[sTop++] = k;	// 若是0，入栈，等待处理
			}
		}*/
	}

    if( count < G.vexnum ) printf("图中有回路");
}

void main()
{
    ALGrahp G;
	printf("输入顶点数\n");  //读入顶点数
	scanf("%d", &G.vexnum) ;
	for(int i=0; i < G.vexnum; i++ )
	{
	    int nextNum=0;
		G.vertices[i].data = i+1;    //顶点号为脚标 +1
		printf("输入顶点%d的入度\n", i+1);
		scanf("%d", &G.vertices[i].in );
		printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
		scanf("%d", &nextNum);
		if(nextNum >= 0)
		{
			Jnode *p;
			
		    G.vertices[i].firstarc = p = (Jnode *)malloc(sizeof(Jnode));
            p->vex = nextNum;
			p->Nextarc = NULL;
			printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
	     	scanf("%d", &nextNum);
			while(nextNum >= 0)
			{
			    p->Nextarc = (Jnode *)malloc(sizeof(Jnode));
                p = p->Nextarc;
				p->vex = nextNum;
                printf("输入顶点%d的下一个邻接顶点号，如结束输入负数\n", i+1);
	     	    scanf("%d", &nextNum);
			}
            p->Nextarc = NULL;
		}//nextNum > =0
		else
		{
		    G.vertices[i].firstarc = NULL;
		}

	};
	

	TopologicalSort(G);
	printf("\n");

}