/*//////////////////////////////////////////////////////////
///////////4、實現課程的拓撲排序。（選）（加）
???問題描述：軟件專業的學生要學習一系列課程，其中有些課程必須在其先修課程完成后才能學習，具體關系見下表：
課程編號	課程名稱	先決條件
C1	程序設計基礎	無
C2	離散數學	C1
C3	數據結構	C1，C2
C4	匯編語言	C1
C5	操作系統	C3
假設每門課程的學習時間為一學期，試為該專業的學生設計教學計劃，使他們能在最短的時間內修完這些課程。
?

//////////由小謝編輯，只作學習參考，不能直接復制作為作業
///////////本人已將作品放在www.edugoo.com/guangxi/bbs上供大家學習使用
///////////////////////////////////////////////////////////*/
//拓撲排序topSort.cpp
#include
//#include
#include
typedef?struct
{char?w1w2;
?float?w;
}RCW;
#include?“graph4.h“
typedef?struct
{int?*data;
?int?maxtop;
}Stack;

void?TopSort（Graph?*G）
{int?ijndcount=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??{d=0;
???for（i=0;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=1ww=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<data[i]<
}
if?（S.top+1!=0）
{cout<data[i];//輸出點

}

??count++;//計算曾經輸出的點的個數
?for（j=0;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??cout<<“\nThere?is?a?cycle.“;
?free（D）;
?free（S.data）;
}
void?main（）
{cout<<“經拓撲排序后，結果為:\n“;
?Graph?G;int?n=5e=5;//int?n=6e=8;//n為頂點數e為邊數
?RCW?rcw[5]={{‘a‘‘b‘1}{‘a‘‘c‘1}{‘a‘‘d‘1}{‘b‘‘c‘1}
?????????????{‘c‘‘e‘1}};//1表示兩點之間有聯系
?SetGraph（&Gn）;
?MakeGraph（&Grcwne）;
?TopSort（&G）;
?free（G.data）;//釋放空間
?free（G.visited）;
?for（int?i=0;i?free（G.edge）;
?cin.get（）;//等待函數（可以去掉哦）
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2005-09-15?07:08??課程安排，用拓撲排序實現\
?????目錄???????????0??2005-09-15?07:08??課程安排，用拓撲排序實現\www.cnzz.cn\
?????目錄???????????0??2005-09-06?12:46??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\
?????文件????????1815??2005-09-06?13:09??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\BuildLog.htm
?????文件??????229421??2005-09-06?10:01??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\topSort.exe
?????文件??????264832??2005-09-06?10:01??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\topSort.ilk
?????文件???????50176??2005-09-06?10:02??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\vc60.idb
?????文件???????61440??2005-09-06?10:01??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\vc60.pdb
?????文件???????11264??2005-09-06?13:09??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\vc70.idb
?????文件???????36864??2005-09-06?13:09??課程安排，用拓撲排序實現\www.cnzz.cn\Debug\vc70.pdb
?????文件?????????878??2005-09-06?10:01??課程安排，用拓撲排序實現\www.cnzz.cn\graph4.h
?????文件????????2343??2005-09-06?13:08??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.cpp
?????文件????????3413??2005-09-04?13:48??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.dsp
?????文件?????????520??2005-09-04?13:55??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.dsw
?????文件???????19456??2005-09-06?13:10??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.ncb
?????文件???????48640??2005-09-06?10:02??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.opt
?????文件?????????248??2005-09-06?10:02??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.plg
?????文件?????????903??2005-09-06?13:09??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.sln
?????文件????????3978??2005-09-06?13:09??課程安排，用拓撲排序實現\www.cnzz.cn\topSort.vcproj
?????文件???????50118??2004-11-30?03:27??課程安排，用拓撲排序實現\使用說明.CHM