课程安排，用拓扑排序实现

/*////////////////////////////////////////////////////////// ///////////4、实现课程的拓扑排序。(选)（加） 问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表： 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1，C2 C4 汇编语言 C1 C5 操作系统 C3 假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。 //////////由小谢编辑，只作学习参考，不能直接复制作为作业 ///////////本人已将作品放在www.edugoo.com/guangxi/bbs上供大家学习使用 ///////////////////////////////////////////////////////////*/ //拓扑排序topSort.cpp #include<iostream.h> //#include<iomanip.h> #include<stdlib.h> typedef struct {char w1,w2; float w; }RCW; #include "graph4.h" typedef struct {int *data; int max,top; }Stack; void TopSort(Graph *G) {int i,j,n,d,count=0,*D; Stack S; if(G->size==0) return; n=G->size; S.data=new int[n]; S.max=n;S.top=-1; D=new int[n]; for(j=0;j<n;j++) {d=0; for(i=0;i<n;i++) if(G->edge[i][j]!=0) d++; D[j]=d;//统计入度 if(d==0)//入度为0 {if(S.top==S.max-1) {cout<<"Stack is full!\n";exit(1);} S.top++; S.data[S.top]=j;//记录入度为0的点 } } while(!(S.top==-1))//如果有入度为0的点..... { int w=1,ww=0; if(S.top==-1) {cout<<"Pop an empty stack!\n";exit(1);} S.top--; i=S.data[S.top+1]; if (S.top+1==0) { cout<<G->data[i]<<endl;//输出点 } if (S.top+1!=0) {cout<<G->data[i];//输出点 } count++;//计算曾经输出的点的个数 for(j=0;j<n;j++)//将顶点输出后，对顶点的入度作修改 if(G->edge[i][j]!=0) {D[j]--; if(D[j]==0) {if(S.top==S.max-1) {cout<<"Stack is full!\n";exit(1);} S.top++; S.data[S.top]=j;//修改之后入度为0，入站记录 }}}//while(!(S.top==-1)) if(count<n) cout<<"\nThere is a cycle."; free(D); free(S.data); } void main() {cout<<"经拓扑排序后，结果为:\n"; Graph G;int n=5,e=5;//int n=6,e=8;//n为顶点数,e为边数 RCW rcw[5]={{'a','b',1},{'a','c',1},{'a','d',1},{'b','c',1}, {'c','e',1}};//1表示两点之间有联系 SetGraph(&G,n); MakeGraph(&G,rcw,n,e); TopSort(&G); free(G.data);//释放空间 free(G.visited); for(int i=0;i<G.max;i++) free(G.edge[i]); free(G.edge); cin.get();//等待函数（可以去掉哦） }