tuopu01.cpp

严版（c语言）数据结构中拓扑排序的实验

#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <string.h>
typedef struct node{ 
	int adjvex; 
	struct node *next; 
}EdgeNode; 
typedef struct vnode{ 
	int id; 
	EdgeNode *link; 
}vnode,Adjlist[100]; 
typedef Adjlist LGraph; 
typedef struct snode{ 
	int data; 
	struct snode *next; 
}Link_Stack; 
Link_Stack *top,*s; 
void Push(Link_Stack **top,int x){ 
	s=(Link_Stack*)malloc(sizeof(Link_Stack)); 
	s->data=x; 
	s->next=(*top)->next; 
	(*top)->next=s;} 
void GetTop(Link_Stack **top,int *x){ 
	s=(*top)->next; 
	*x=s->data; 
	(*top)->next=s->next; 
	free(s);} 
int CreatGraph(LGraph gl){ 
	int m,n,i=0,c,d; 
	EdgeNode *p; 
	printf("input start.\n"); 
	printf("please input how many vertex there had?\n",i); 
	scanf("\n%d",&c); 
	for(i=0;i<c;i++){ 
		gl[i].link=NULL; 
		gl[i].id=0;} 
	printf("please input EdgeNodes number?"); 
	scanf("%d",&d); 
	for(i=0;i<d;i++){ 
		printf("\nplease input Vi&Vj:="); 
		scanf("\n%d,%d",&m,&n); 
		if((m>=0)&&(m<c)&&(n>=0)&&(n<c)){ 
			p=(EdgeNode*)malloc(sizeof(EdgeNode)); 
			p->adjvex=n; 
			p->next=gl[m].link; 
			gl[m].link=p; 
			gl[n].id++;}} 
	return c;} 
void TopuSort(LGraph G,int n){ 
	int i,j,m=0; 
	EdgeNode *p; 
	top=(Link_Stack*)malloc(sizeof(Link_Stack)); 
	top->next=NULL; 
	for(i=0;i<n;i++) 
		if(G[i].id==0) Push(&top,i); 
		while(top->next!=NULL){ 
			GetTop(&top,&i); 
			printf(" %d ",i); 
			m++; 
			p=G[i].link; 
			while(p){ 
				j=p->adjvex; 
				G[j].id--; 
				if(G[j].id==0) Push(&top,j); 
				p=p->next;}} 
		if(m<n) printf("The Graph has a cycle!!!\n");} 
void main(){ 
	LGraph GL; 
	TopuSort(GL,CreatGraph(GL));}