tp.cpp

该程序设计是本人数据结构实践项目的拓扑结构的源代码

#include "iostream.h"
#include "string.h"
#define N 50  //N为最大
struct node 
{int p;          // 指向顶点的位置的弧
	node *next; 
};	
struct node1 
{int aa;      //顶点
	node *head; //指向第一条依附该顶点的弧
};
class tp    //建立拓扑排序的类，命名为tp
{public:
     node1 date[N];
	int v;     // 图的当前顶点数 
	int a;     // 图的当前弧数
	tp ()    //建立空图
	{for(int i=0;i<N;i++)
			date[i].aa='#';
	v=0;
		a=0;
	};
	void createtp();
	int lj(int v); //连接
	void TPpx();   //实现拓扑排序
};
void tp::createtp()
{
	int v1;
	int v2;
	int j;
	int k;
	node *p;
	cout<<"1.输入顶点的个数："<<endl;
	cin>>v;
	cout<<"2.输入弧的个数："<<endl;
	cin>>a;
	for(int i=0;i<v;i++)
	{
		cout<<"输入关于第i个顶点的信息："<<endl;
		cin>>date[i].aa;
		date[i].aa=NULL;
	}
	cout<<"输入每条弧的始点和终点："<<endl;
	for(i=0;i<10;i++)
	{
		cin>>v1>>v2;
		j=lj (v1);
		k=lj(v2);
		p=new node ;
		p->p=k;
		p->next=date[j].head;
		date[j].head=p;
	}
}
int tp::lj (int v)
{
	for(int i=0;i<N;i++)
	{
		if(v==date[i].aa)
		break;
	}
			return i;
}


void tp::TPpx()
{
	node *q;
	int in[N];       //记录该顶点的入度
	int out[N];       //出度
	for(int i=0;i<v;i++)
	{
		in[i]=0;
		out[i]=0;
	}
	for(i=0;i<v;i++)    //判断每个元素的入度与出度
	{
		q=date[i].head;
		while(q!=NULL)
		{
			in[q->p]++;
			q=q->next;
		}
	}
	for(i=0;i<v;i++)
	if(in [i]==0&&out [i]==0)
	{
		cout<<date[i].aa<<"  "<<endl;
		out[i]=1;
		q=date[i].head;
		while(q)
		{
			in[q->p]--;
			q=q->next;
		}
		i=-1;
	}
//	cout<<"拓扑排序的结果是："<<endl;
}
void main()
{  cout<<"第11题 "<<endl;
   cout<<"/*任务：编写函数实现图的拓扑排序*/"<<endl;
   cout<<"下面按步骤进行实现："<<endl;
  tp t;
	t.createtp();
	//cout<<"1.输入顶点的个数："<<endl;
	cout<<"拓扑排序的结果是："<<endl;
	t.TPpx();
}