拓扑排序.cpp

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include <stdio.h>
#include <malloc.h>
#define max 20
typedef struct graph 
{
	int  vexs[max];
	int  arcs[max][max];
	int  n;
	int  e;
}graph;
void creatgraph(graph *g) 
{
	int i,j,k;
	printf("请输入顶点个数和边数（不大于20）\n");
	scanf("%d%d",&(g->n),&(g->e));
	for (i=0;i<(g->n);i++)
	{
		g->vexs[i]=i;   //建立顶点，注意是从0开始！
	}
	for (i=0;i<g->n;i++)
		for(j=0;j<g->n;j++)
			g->arcs[i][j]=0;
	printf("输入边的信息!\n");
    for (k=0;k<g->e;k++)
	{
    	scanf("%d%d",&i,&j);     //输入边的两个顶点，建立的是有向图！
    	g->arcs[i][j]=1;
	}
}
int  stack[max];          //标记同结点的入度数
bool visited[max];      //标记结点是否已被访问！
void find(graph * g,int i)
{    
	int j;
	if(stack[i]==0&&visited[i]==false) //当结点未被访问及入度数为0时打印出来！
	{
			printf("%d  ",i);
			visited[i]=true;
		for (j=0;j<g->n;j++)
			if(g->arcs[i][j]!=0)
			{
				stack[j]=stack[j]-1;
				find(g,j);
			}
	}
}


void Topo(graph *g)  //拓扑排序！
{  
	int i;
	for (i=0;i<g->n;i++)      //各种初始化！
	{
		stack[i]=0;
		visited[i]=false;
	    for (int j=0;j<g->n;j++)
			stack[i]=g->arcs[j][i]+stack[i];
	}
    for (i=0;i<g->n;i++)
			find(g,i);
	for (i=0;i<g->n;i++)
		if (!visited[i])
		{
			printf("存在有向环!\n");
            break;
		}
}

void main() 
{
	    printf("建立图！\n");
		struct graph * G;
		G=(graph *)malloc(sizeof(graph));
		creatgraph(G);
		printf("建立成功！\n");
		Topo(G);
}