描述：
学校领导在大学生培养计划的制订中，涉及到课程的安排问题，由于课程较多，现在要求编程高手的你帮忙。假定课程之间的先修关系已确定，现在要求你根据先修关系，通过编程确定各门课程的先后关系，并生成一张课程先后安排顺序表，以帮助学校设置各年度课程。
输入：
输入只包括一个测试用例，第一行为一个自然数n，表示课程数量，第二行为n个单词，分别表示n门课程，一个单词表示一门课程，单词全为小写状态，各单词之间用一个空格隔开。
接下来为n*n行0和1构成的矩阵，表示各门课程之间的先修关系。假设i行j列为1，表示第i课程为第j课程的先修课。否则表示不存在先修关系。
输出
要求根据各课程之间的先修关系，用一行输出课程的拓扑排序结果。注意：如果两门课程的访问顺序相同，则根据课程名的字典顺序进行访问。
样例输入
4
db c computer math
0 0 0 0
1 0 1 0
0 0 0 0
0 0 1 0
样例输出：
c db math computer
代码：
#include<iostream>
#include <string>
using namespace std;
#define MAX 1024
#include <string>
using namespace std;
#define MAX 1024
class Stack //自定义栈
{
string str[10000];
int statop; //最顶元素下标加1，我习惯这样做
public:
Stack();
void push(string &); // 进栈
void pop();
int getsize(){return statop;} //得到元素个数
};
Stack::Stack()
{
statop=0;
}
void Stack::pop()
{
if(statop!=0)
{
statop--;
cout<<str[statop];
}
}
void Stack::push(string & te)
{
if(statop!=10000)
{
str[statop]=te;
statop++;
}
}
Stack mystack;
int indegree[MAX]; //外面关联图中的入度
{
string str[10000];
int statop; //最顶元素下标加1，我习惯这样做
public:
Stack();
void push(string &); // 进栈
void pop();
int getsize(){return statop;} //得到元素个数
};
Stack::Stack()
{
statop=0;
}
void Stack::pop()
{
if(statop!=0)
{
statop--;
cout<<str[statop];
}
}
void Stack::push(string & te)
{
if(statop!=10000)
{
str[statop]=te;
statop++;
}
}
Stack mystack;
int indegree[MAX]; //外面关联图中的入度
struct node
{
int adjvex;
string data;
node* first; //前驱个数（入度）
node* next; //后继，用来减少后面顶点的入度
}adj[MAX];
{
int adjvex;
string data;
node* first; //前驱个数（入度）
node* next; //后继，用来减少后面顶点的入度
}adj[MAX];
void Create(node adj[],int n) //建邻接表，n点数
{
int i,j;
for(i=1;i<=n;i++)
{
adj[i].adjvex=i;
cin>>adj[i].data;
adj[i].first=NULL;
adj[i].next=NULL;
}
int u,v,t;
node *p,*pp;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>t;
if(t==1)
{
u=j;
v=i;
pp=new node;
pp->adjvex=u;
pp->data=adj[u].data;
pp->next=adj[v].next;
adj[v].next=pp;
p=new node;
p->adjvex=v;
p->data=adj[v].data;
p->first=adj[u].first;
adj[u].first=p;
}
}
}
{
int i,j;
for(i=1;i<=n;i++)
{
adj[i].adjvex=i;
cin>>adj[i].data;
adj[i].first=NULL;
adj[i].next=NULL;
}
int u,v,t;
node *p,*pp;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>t;
if(t==1)
{
u=j;
v=i;
pp=new node;
pp->adjvex=u;
pp->data=adj[u].data;
pp->next=adj[v].next;
adj[v].next=pp;
p=new node;
p->adjvex=v;
p->data=adj[v].data;
p->first=adj[u].first;
adj[u].first=p;
}
}
}
void print(int n)
{
int i;
node *p;
cout<<"前驱：";
for(i=1;i<=n;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->first;
}
cout<<endl;
}
cout<<"后继：";
for(i=1;i<=n;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->next;
}
cout<<endl;
}
}
for(i=1;i<=n;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->first;
}
cout<<endl;
}
cout<<"后继：";
for(i=1;i<=n;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->next;
}
cout<<endl;
}
}
void topsort(node adj[],int n) //拓扑排序
{
int i,pkm;
node *p,*q;
memset(indegree,0,sizeof(indegree));
for(i=1;i<=n;i++)
{
q=&adj[i];
p=q->first;
while(p!=NULL)
{
indegree[q->adjvex]++;
p=p->first;
}
}
{
int i,pkm;
node *p,*q;
memset(indegree,0,sizeof(indegree));
for(i=1;i<=n;i++)
{
q=&adj[i];
p=q->first;
while(p!=NULL)
{
indegree[q->adjvex]++;
p=p->first;
}
}
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{
mystack.push(adj[i].data);
pkm=adj[i].adjvex;
indegree[i]--;
break;
}
}
int count=0;
{
if(indegree[i]==0)
{
mystack.push(adj[i].data);
pkm=adj[i].adjvex;
indegree[i]--;
break;
}
}
int count=0;
while(mystack.getsize()!=0)
{
mystack.pop();
cout<<' ';
count++;
for(p=adj[pkm].next;p!=NULL;p=p->next)
indegree[p->adjvex]--;
{
mystack.pop();
cout<<' ';
count++;
for(p=adj[pkm].next;p!=NULL;p=p->next)
indegree[p->adjvex]--;
for(i=1;i<=n;i++)
if(indegree[i]==0)
{
mystack.push(adj[i].data);
pkm=adj[i].adjvex;
indegree[i]--;
break;
}
}
cout<<endl;
if(count<n) cout<<"有回路"<<endl;
}
if(indegree[i]==0)
{
mystack.push(adj[i].data);
pkm=adj[i].adjvex;
indegree[i]--;
break;
}
}
cout<<endl;
if(count<n) cout<<"有回路"<<endl;
}
int main()
{
int n;
cin>>n;
Create(adj,n);
// cout<<"输入的邻接表为:"<<endl;
// print(n);
// cout<<"拓扑排序结果为:"<<endl;
topsort(adj,n);
return 0;
}
Create(adj,n);
// cout<<"输入的邻接表为:"<<endl;
// print(n);
// cout<<"拓扑排序结果为:"<<endl;
topsort(adj,n);
return 0;
}
运行结果：
敲了好久才敲好，不过弄懂了就是高兴的，呵呵
里面可能还少了按字典排序一个小问题，改一下就行，大概思路就是这样了。