l7_11.cpp

数据结构课程的源代码

//实现AOV网的拓扑排序
#include<iostream.h>
typedef int elemtype;
const    int  n=5;     //n表示图中顶点数
const    int  e=6;     //e表示图中弧的数目
struct  link
{   
elemtype data;
link *next;
};
struct   node
{   
elemtype    v ;         //顶点信息
int   id ;            //顶点入度
link *next;
}   a[n+1];

void  creatlink3( )   //建立带入度的邻接表
{  
int i,j,k ;
 link   *s ;
for(i=1; i<=n;i++)                   //建立邻接表头结点
{ a[i].v=i ;
  a[i].id=0;                        //入度值为0 
   a[i].next=NULL;
 }
for(k=1; k<=e;k++)
{ 
 cout<<"请输入一条弧:";
 cin>>i>>j ;                      //输入一条弧 <i,j>
 cout<<endl;
 s=new  link;                     //申请一个动态存储单元
s->data=j ;
s->next=a[i].next ;
a[i].next=s ;
a[j].id++;
}
}

void   topsort ( )      //拓扑排序
{int top=0,m=0;
for (int i=1;i<=n;i++)           //入度为0的顶点进栈
if (a[i].id==0) {a[i].id=top; top=i;}
while (top>0)
{i=top;  top=a[top].id,      //出栈
cout<< i<<" ";       //输出入度为0的顶点
m++;                   //输出结点个数增1 
link  *p=a[i].next;
while (p!=NULL)
{int k=p->data;
a[k].id-- ;                 //删除一条边
if  (a[k].id==0)  {  a[k].id=top; top=k;}
p=p->next;
}
}
if (m<n) cout<<"the network has a crcle";
}
void main()
{ 
    creatlink3( ) ;
	cout<<"拓扑排序的结果为"<<endl;
	topsort (  );
	cout<<endl;
}