|
描述：
学校领导在大学生培养计划的制订中，涉及到课程的安排问题，由于课程较多，现在要求编程高手的你帮忙。假定课程之间的先修关系已确定，现在要求你根据先修关系，通过编程确定各门课程的先后关系，并生成一张课程先后安排顺序表，以帮助学校设置各年度课程。 输入： 输入只包括一个测试用例，第一行为一个自然数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; } 运行结果： 敲了好久才敲好，不过弄懂了就是高兴的，呵呵 里面可能还少了按字典排序一个小问题，改一下就行，大概思路就是这样了。 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/pukuimin1226/archive/2010/12/07/6061696.aspx |
|
|
