(14)拓扑排序.cpp

一些数据结构算法的例子

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

int NodeCount;
char Node[20];
char Graph[20][20];
char RuDu[20];
char Checked[20];

char Locate(char Char)
{
	char Temp;
	for(Temp=0;Temp<NodeCount;Temp++)
		if(Node[Temp]==Char)
			break;
	return Temp;
}

void main()
{
	char Temp1,Temp2;
	int Temp3;
	char Condition=1;
	char min,mintemp,mintemp1;
	clrscr();
	for(Temp2=0;Temp2<20;Temp2++)
		for(Temp1=0;Temp1<20;Temp1++)
			Graph[Temp2][Temp1]=0;
	for(Temp1=0;Temp1<20;Temp1++)
		Checked[Temp1]=0;
	cout<<"Input the node count:";
	cin>>NodeCount;
	cout<<"Input the node:";
	for(Temp1=0;Temp1<NodeCount;Temp1++)
		  cin>>Node[Temp1];
	cout<<"Input the link"<<endl;
	Temp1=0;
	while(1)
	{
		cout<<"Input the first node:";
		cin>>Temp1;
		cout<<"Input the second node:";
		cin>>Temp2;
		if(Temp1=='$')
			break;
		Temp1=Locate(Temp1);
		Temp2=Locate(Temp2);
		Graph[Temp1][Temp2]=1;
	}
	for(Temp2=0;Temp2<NodeCount;Temp2++)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			cout<<(int)Graph[Temp2][Temp1]<<" ";
		cout<<endl;
	}
	while(Condition)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			RuDu[Temp1]=0;
		for(Temp2=0;Temp2<NodeCount;Temp2++)
		{
			Temp3=0;
			for(Temp1=0;Temp1<NodeCount;Temp1++)
				if(Graph[Temp1][Temp2])
					Temp3++;
			RuDu[Temp2]=Temp3;
		}
		Condition=0;
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			if((!RuDu[Temp1])&&(!Checked[Temp1]))
			{
				for(Temp2=0;Temp2<NodeCount;Temp2++)
					Graph[Temp1][Temp2]=0;
				Checked[Temp1]=1;
				cout<<Node[Temp1];
				Condition=1;
			}
	}
}