拓扑排序 C++实现

描述：

学校领导在大学生培养计划的制订中，涉及到课程的安排问题，由于课程较多，现在要求编程高手的你帮忙。假定课程之间的先修关系已确定，现在要求你根据先修关系，通过编程确定各门课程的先后关系，并生成一张课程先后安排顺序表，以帮助学校设置各年度课程。

输入：

输入只包括一个测试用例，第一行为一个自然数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

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];   //外面关联图中的入度

struct node
{
    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;
           
   }
  }
}

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;
    }
 
}

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;
        }
    }

    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;

    while(mystack.getsize()!=0)
    {
        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;
}

int main()
{
    int n;

    cin>>n;
    Create(adj,n);
// cout<<"输入的邻接表为:"<<endl;
// print(n);
 // cout<<"拓扑排序结果为:"<<endl;
    topsort(adj,n);
    return 0;
}

运行结果：

敲了好久才敲好，不过弄懂了就是高兴的，呵呵

里面可能还少了按字典排序一个小问题，改一下就行，大概思路就是这样了。