#include?
using?namespace?std;

//函數結果狀態代碼?
#?define?ERROR?0?
#?define?INFEASIBLE?-1?
#?define?OVERFLOW?-2
#?define?MAX_VERTEX_NUM?40

int?*temp;??//用于儲存VERTEX_NUM次回歸后得到的序列

//用于拓撲排序的圖的鄰接表的定義
typedef?int?Status;
typedef?struct?ArcNode{????//弧結點
	int?adjvex;
	bool?deleteed;?????????//標志是否被刪除
	struct?ArcNode?*nextarc;
}ArcNode;
typedef?struct?VNode{?????//頂結點
	char?data;????????????//頂點名稱
	int?indegree;
	bool?deleteed;????????//標志是否被刪除
	ArcNode?*firstarc;
}VNodeAdjList[MAX_VERTEX_NUM];
typedef?struct{?????//圖
	AdjList?vertices;
	int?vexnumarcnum;
}ALGraph;

//int型的隊列
class?linkQueue
{
private:
	struct?QNode
	{
		int?date;
		QNode?*next;
	};
	QNode?*front;
	QNode?*rear;
public:
	linkQueue（）
	{
		front=rear=（QNode*）malloc（sizeof（QNode））;
		if?（!front）?exit（OVERFLOW）;
		front->next=NULL;
	}
	void?Destroy（）
	{
		while（front）
		{
			rear=front->next;
			free（front）;
			front=rear;
		}
		front=rear=（QNode*）malloc（sizeof（QNode））;
		if?（!front）?exit（OVERFLOW）;
		front->next=NULL;
	}
	void?EnQueue（int?e）
	{
		QNode?*p=new?QNode;
		if?（!p）?exit（OVERFLOW）;
		p->date=e;p->next=NULL;
		rear->next=p;
		rear=p;
	}
	int?Size（）
	{	
		int?count=0;
		if?（front==rear）?return?count;
		QNode?*p=front->next;
		while（p）
		{
			++count;
			p=p->next;
		}
		return?count;
	}
	int?DeQueue（）?????//輸出單個元素
	{
		int?a;
		if?（front==rear）?{cout<<“隊列空！“<		QNode?*p=front->next;
		a=p->date;
		front->next=p->next;
		if?（rear==p）?rear=front;
		free（p）;
		return?a;
	}
	void?PrintQueue（ALGraph?G）??//用于輸出全部隊列元素
	{
		QNode?*p=front->next;
		while（p）
		{
			cout<date].data;
			p=p->next;
		}
		cout<	}
};

//建立鄰接表
//定位頂點的函數
int?LocateVex（ALGraph?Gchar?u）
{
	int?i;
	for?（i=0;i		if（G.vertices[i].data==u）?return?i;
	if?（i==G.vexnum）?{cout<<“錯誤的頂點名!“;exit（1）;}
	return?-1;
}
//建立有向圖的鄰接表的函數
void?CreateALGraph_adjlist（ALGraph?&G）
{
	int?ijk;??
	char?v1v2;
	ArcNode?*p;
	cout<<“請輸入頂點數和弧數:“;
	cin>>G.vexnum>>G.arcnum;
	cout<<“開始構造鄰接表:“<	for?（i=0;i	{
		cout<<“輸入第“<		cin>>G.vertices[i].data;
		G.vertices[i].deleteed=false;
		G.vertices[i].firstarc=NULL;
		G.vertices[i].indegree=0;
	}
	for?（k=0;k	{
		cout<<“請輸入第“<		cin>>v1>>v2;
		i=LocateVex（Gv1）;
		j=LocateVex（Gv2）;
		p=（ArcNode*）malloc（sizeof（ArcNode））;
		p->adjvex=j;	
		p->deleteed=false;
		p->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p;
		G.vertices[j].indegree++;
	}
	return;
}
int?*InDegree（ALGraph?Gint?&numint?n）??//返回一個int型數組的指針，內含圖中0度頂點的序號num返回其0度頂點數n是初始的頂點個數
{
	int?*a=（int?*）malloc（sizeof（int））;
	a[0]=-1;??????//a[0]=-1時無0度頂點
	num=0;
	for（int?i=0j=0;i	{
		if?（G.vertices[i].deleteed==true）??//如果已經刪除
			continue;
		if?（G.vertices[i].indegree==0）
		{
			if?（a[0]==-1）
			{
				a[0]=i;
				++j;
				++num;
		

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????4793??2009-07-02?13:43??拓撲排序\chuopu.cpp

?????文件???????4284??2009-07-01?17:13??拓撲排序\ChuoPu.dsp

?????文件????????537??2009-07-01?15:39??拓撲排序\ChuoPu.dsw

?????文件??????41984??2009-07-02?14:44??拓撲排序\ChuoPu.ncb

?????文件??????53760??2009-07-02?14:44??拓撲排序\ChuoPu.opt

?????文件???????1267??2009-07-02?13:43??拓撲排序\ChuoPu.plg

?????文件?????532534??2009-07-02?13:43??拓撲排序\Debug\ChuoPu.exe

?????文件?????263005??2009-07-02?13:43??拓撲排序\Debug\chuopu.obj

?????文件????1090560??2009-07-02?13:43??拓撲排序\Debug\ChuoPu.pdb

?????文件?????110592??2009-07-02?13:43??拓撲排序\Debug\vc60.pdb

?????文件?????417792??2009-07-02?16:33??拓撲排序\數據結構課程設計-拓撲排序.doc

?????目錄??????????0??2009-10-25?09:28??拓撲排序\Debug

?????目錄??????????0??2009-11-11?17:23??拓撲排序

-----------?---------??----------?-----??----

??????????????2521108????????????????????13