graph.cpp

这是我在复习备考软件设计师时,写的一个程序,拓朴排序在很多方面都会very important,so i think it will be useful many new hands,so i dec

#include "Queue.h"
#include <stdio.h>
#define MAX_VERTEX_NUM 10
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;
typedef struct VNode{
	char data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertics;
	int indegree[MAX_VERTEX_NUM];
	int vexnum,arcnum;
}ALGraph;
typedef struct WNode{
	int weight;
}WNode;
WNode SavWei[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int Get_data(ALGraph &G)
{
	int a1,a2,a3,i,j;
	
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&G.vexnum,&G.arcnum);	
	for(i=0;i<G.vexnum;i++)
//		for(j=0;j<2;j++)
		fscanf(fp," %c",&G.vertics[i].data);
	for(i=0;i<G.vexnum;i++)
		fscanf(fp,"%d",&G.indegree[i]);

	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			SavWei[i][j].weight=0;
		for(i=0;i<G.arcnum;i++)
		{
			fscanf(fp,"%d %d %d",&a1,&a2,&a3);
			SavWei[a1][a2].weight=a3;
		}
		return 1;
}
void Creat(ALGraph &G,VNode VN[10])
{
	int i,j,k,n,a[10];
	//a=G.vexnum;
	
	ArcNode *p1,*p2;
	for(i=0;i<G.vexnum;i++)
	{
//		VN[i]=new VNode;
		VN[i].data=G.vertics[i].data;
		VN[i].firstarc=new ArcNode;
		k=0;
		j=0;
		for(int l=0;l<G.vexnum;l++)
		{
			a[l]=0;
		}
		while(j<G.vexnum)
		{
			if(SavWei[i][j].weight>0)
			{
				a[k]=j;k++;
			}
			j++;
		}
		if(a[0])
		{
			j=a[0];
			VN[i].firstarc->adjvex=j;//G.vertics[j].data;
			VN[i].firstarc->info=SavWei[i][j].weight;		
			p1=p2=VN[i].firstarc;
		
//		j++;
			for(n=1;n<k;n++)
			{
				j=a[n];
				p2=new ArcNode;
				p2->adjvex=j;//G.vertics[j];
				p2->info=SavWei[i][j].weight;
				p1->nextarc=p2;
				p1=p2;
			}
			p1->nextarc=0;
		}
		else 
			VN[i].firstarc=0;
	}
}
void Output(VNode VN[])
{
	int i,j;
	for(i=0;i<9;i++)
	{
		cout<<VN[i].data;
		while(VN[i].firstarc)
		{
			j=VN[i].firstarc->adjvex;
			cout<<VN[j].data;
			VN[i].firstarc=VN[i].firstarc->nextarc;
		}
		cout<<endl;
	}
}
int Search(VNode VN[],ALGraph G)
{
	Queue *Q;
	int i,j,c;
	TYPE e;
	InitQueue(Q);
	for(i=0;i<G.vexnum;i++)
	{
		j=0;
		while(j<G.vexnum)
		{
			if(G.vertics[j].data!='#'&&!G.indegree[j])
			{
//				k=0;
//				cout<<G.vertics[j].data;
				if(VN[j].firstarc)
				{
					while(VN[j].firstarc->nextarc)
					{	
						c=VN[j].firstarc->adjvex;
						G.indegree[c]--;
//					delete VN[j].firstarc;
//					if()
						VN[j].firstarc=VN[j].firstarc->nextarc;
					}
					c=VN[j].firstarc->adjvex;
					G.indegree[c]--;
				}
				EnQueue(Q,G.vertics[j].data);
				G.vertics[j].data='#';
			}
			else
			j++;
		}
	}
//	for(i=0;i<G.vexnum;i++)
//	{
		DeQueue(Q,e);
//		cout<<e;
//	}
	return 1;
}
//int search(VNode VN[],ALGraph G)

void main()
{
	ALGraph G;
	VNode VN[9];
	Get_data(G);
	Creat(G,VN);
	
//	for(int i=0;i<G.vexnum;i++)
//	Search(VN,G);
	cout<<endl;
    Output(VN);
}