topsort.cpp

课程安排,用拓扑实现...适合初学者学习

/*//////////////////////////////////////////////////////////
///////////4、实现课程的拓扑排序。(选)（加）
问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：
课程编号	课程名称	   先决条件
C1	       程序设计基础	     无
C2	        离散数学	     C1
C3	        数据结构	   C1，C2
C4	        汇编语言         C1
C5	        操作系统	     C3
假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
 

//////////由赵辉编辑，只作学习参考，不能直接复制作为作业
///////////////////////////////////////////////////////////*/
//拓扑排序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();//等待函数（可以去掉哦）
}