邻接表实现拓扑排序_第2关:基于邻接表完成拓扑排序

#include <iostream>
#include <stack>
using namespace std;
 
struct node {
	int index;
	node* next;
	node() { next = NULL; }
	node(int i) { index = i; next = NULL; }
};
 
struct head {
	int in;
	char data;
	node* adj;
	head() { in = 0; }
};
 
head h[100];
int vexnum;
stack<int> s;
void topology() {
	//初始化栈
	for (int i = 1; i <= vexnum; i++) {
		if (h[i].in == 0) {
			s.push(i);//是0，就把节点压入
		}
	}
	while (!s.empty()) {
		int i = s.top();
		s.pop();
		cout << h[i].data << " ";
		node* p = h[i].adj;
		while (p != NULL) {
			int ii = p->index;
			h[ii].in--;
			if (h[ii].in == 0) {
				s.push(ii);
			}
			p = p->next;
		}
	}
 }
 
int findnode(char c) {
	for (int i = 1; i <= vexnum; i++) {
		if (c == h[i].data)
			return i;
	}
	return -1;
}
 
void create() {
	cout << "请输入节点信息" << endl;
	for (int i = 1; i <= vexnum; i++) {
		cin>>h[i].data;
	}
	cout << "请问有几条边" << endl;
	int line;
	cin >> line;
	cout << "请输入拓扑信息" << endl;
	for (int i = 0; i < line; i++) {
		char a, b;
		cin >> a >> b;
		int ai = findnode(a);
		int bi = findnode(b);
		node* p = new node(bi);
		p->next = h[ai].adj;
		h[ai].adj = p;
		h[bi].in++;
	}
}
 
int main() {
	cout << "请问有几个顶点" << endl;
	cin >> vexnum;
	create();
	//打印创建的邻接表
	/*for (int i = 1; i <= vexnum; i++) {
		cout << h[i].data << " "<<h[i].in<<" ";
		node* p = h[i].adj;
		while (p != NULL) {
			cout << p->index << " ";
			p = p->next;
		}
		cout << endl;
	}*/
	topology();
	return 0;
}