topology.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include<iostream.h>

struct EdgeNode {
	int adj;       
	EdgeNode *next;  
};  //边表结点类型

struct VertexNode {
	int vertex;
	EdgeNode *firstedge;
	int tag;
};  //顶点结点类型

struct AdjGraph {
	VertexNode vexlist[30];
	int n, e;
} graph;  //图的结点型

//建立图函数
void CREATGRAGH(void) {   
	int i;
	int head, tail;
	EdgeNode *p;
lable0:	
	cout<<"功能描述：根据课程间（不超过30门）的先修关系，本程序可以实现教学计划的制定，给出课程的学习次序。"<<endl;
	cout<<"将课程及课程间的先修关系用AOV网表示，顶点代表课程，有向边代表先修关系。"<<endl;
	cout<<"请输入顶点总数，即课程总数：";
	cin>>graph.n;
	if(graph.n > 30 || graph.n < 1) {
		cout<<"顶点总数不在程序允许范围内，请重新输入。"<<endl;
		goto lable0;
	}
	cout<<"请输入AOV网中有向边总数：";
	cin>>graph.e;
	
	//为课程编号
	cout<<"程序已自动为课程编号，从1到"<<graph.n<<"。"<<endl;
	for(i = 1;i <= graph.n;i++) {
		graph.vexlist[i-1].vertex = i;
		graph.vexlist[i-1].tag = 0;
		graph.vexlist[i-1].firstedge = NULL;
	}
	
	//输入课程先修关系
	cout<<"请根据AOV网输入各条有向边，即课程间的先修关系。"<<endl;
	for(i = 1;i <= graph.e;i++) {   
		cout<<"输入第"<<i<<"条边的起点编号：";
		cin>>head;
		cout<<"输入第"<<i<<"条边的终点编号：";
		cin>>tail;

		head = head - 1;
		tail = tail - 1;
		
		p = new EdgeNode;
		p->adj = tail;
		p->next = graph.vexlist[head].firstedge;
		graph.vexlist[head].firstedge = p;
	}
}

//判断结点入度是否为零
int IsZero(int i) {
	int j = 0;
	EdgeNode *p;
	
	if(graph.vexlist[i].tag == 1)
		return 0;
	while(j < graph.n) {
		if(graph.vexlist[j].firstedge != NULL) {
			p = graph.vexlist[j].firstedge;
			while(p != NULL) {
				if(p->adj == i)
					return 0;
				p = p->next;
			}
		}
		j++;
	}
	return 1;
}
//拓扑分类函数
void Topology(void) {
	int a[30], i=0, j = 1;
	int v, k, nodes;
	
	//初始化
	while(i < 30) {
		a[i] = -1;
		i++;
	}
	i = 0;
	nodes = 0;
	
	while(j != -1 && nodes != graph.n) {
		for(v = 0;v < graph.n;++v)
			if(IsZero(v)) {	
				a[i] = v;
				i++;
			}
		i = i-1;
		j = i;
		while(i != -1) {
			k = a[i];
			i--;
			nodes++;
			cout<<graph.vexlist[k].vertex<<"-->";
			graph.vexlist[k].tag = 1;
			graph.vexlist[k].firstedge = NULL;	
		}
		i = 0;
	}
	if(nodes < graph.n)
		cout<<"AOV网中有环路！"<<endl;
}

void main() {
	char yn;
label:
	CREATGRAGH();
	Topology();
	cout<<"END";

	cout<<endl<<"是否继续使用本程序？继续请按Y，退出请按N：";
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto label;
}