-

数据结构里的拓扑排序和非拓扑排序算法

#include <iostream.h>

const int nmax=100;

typedef struct
{
	int data[nmax+1];    
    int adjmat[nmax+1][nmax+1];   
    int n,e;             
}mat_graph;

typedef struct node * pointer;

struct node 
{                 
	int no;                     
	pointer next;
	int data;
};

typedef struct 
{
	int data;
	int out;
	pointer first;
}headtype;                        

typedef struct
{
	headtype adjlist[nmax+1];            
	int n,e;                       
}lk_graph;


typedef struct {
   pointer top;
} lkstack;		
			                    

int Distopsort(lk_graph gl);
void init_lkstack(lkstack *S);
int empty_lkstack(lkstack *S);
int push_lkstack(lkstack *S,int i);
int pop_lkstack(lkstack *S,int v); 
void main()
{
	int i,j;
	mat_graph ga;
    ga.n=4;
	ga.e=4;
	ga.adjmat[1][2]=1;
	ga.adjmat[2][3]=1;
	ga.adjmat[3][1]=1;
	ga.adjmat[1][4]=1;
	lk_graph gl;
	pointer p;
	gl.n=ga.n;
	gl.e=ga.e;
	for(i=1;i<=gl.n;i++) gl.adjlist[i].first=NULL;
	for(i=1;i<=ga.n;i++)
		for(j=ga.n;j>=i;j--)
		{
			if(ga.adjmat[i][j]==0) continue;
			p=new node;                       
			p->no=i;                          
			p->next=gl.adjlist[j].first;
			gl.adjlist[j].first=p;
		}
    Distopsort(gl);
}
int Distopsort(lk_graph gl) 
{
	lkstack S;                  
	pointer p;
	int m,i,v;
	init_lkstack (&S);
	for(i=1;i<=gl.n;i++)
		if(gl.adjlist[i].out==0) push_lkstack(&S,i);
		m=0;
		while(!empty_lkstack(&S)) 
		{
			pop_lkstack (&S,v);cout<<v<<" ";
			m++;
			p=gl.adjlist[v].first;
			while(p!=NULL) 
			{         
				gl.adjlist[p->no].out--;
				if(gl.adjlist[p->no].out==0)  push_lkstack(&S,p->no);
				p=p->next;
			}
		}
		if (m<gl.n) {cout<<"图中有环，不能逆拓扑排序！"<<endl;}
		else return 1;
		cout<<"distopsort completed"<<endl;
}

void init_lkstack(lkstack *S) 
{
  S->top=NULL;
}
int empty_lkstack(lkstack *S) 
{
   if(S->top==NULL) return 1;
   else return 0;
}
int push_lkstack(lkstack *S,int i) 
{
	pointer p;
    p=new node;		
	p->data=i;		
	p->next=S->top;	
	S->top=p;		
	return 1;
}
int pop_lkstack(lkstack *S,int v) 
{
  pointer p;
  if(S->top==NULL)
    {cout<<"栈空，不能退栈!"<<endl; return 0;}//下溢
  else
    {p=S->top; v=p->data; S->top=p->next;
     delete p; return 1;}

}