#include?“stdafx.h“
#include“malloc.h“
#include“stdio.h“
#define?OK?1
#define?ERROR?0
#define?TRUE?1
#define?FALSE?0
#define?STACK_INIT_SIZE?100?//存儲空間初始分配量
#define?STACKINCREMENT?10?//存儲空間分配增量
#define?MAX_VERTEX_NUM?20
typedef?int?Status;
typedef?int??SElemType;
typedef?struct?{
	SElemType?*base;?//在棧構造之前和銷毀之后base的值為NULL
	SElemType?*top;?//棧頂指針
	int?stacksize;?//當前已分配的存儲空間以元素為單位
}SqStack;

typedef?struct?ArcNode{
	int?adjvex;//該弧所指向的頂點的位置
	struct?ArcNode?*nextarc;//指向第一條依附該頂點的弧的指針
}ArcNode;
typedef?struct?VNode{
	char?data[10];
	ArcNode?*firstarc;
}VNodeAdjList[MAX_VERTEX_NUM];
typedef?struct{
	AdjList?vertices;
	int?vexnumarcnum;//圖的當前頂點數和弧數
}ALGraph;
int?indegree[20]={0};??//存儲圖的入度的全局變量數組

Status?InitStack（SqStack?&S）
{
	//構造一個空棧S
	S.base=（SElemType?*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
	if（!S.base）
		return?ERROR;//內存分配失敗
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return?OK;
}//InitStack

Status?Push（SqStack?&SSElemType?e）
{
	//插入元素e為新的棧頂元素
	?if（S.top-S.base>=S.stacksize）
	?{//棧滿追加存儲空間
		?S.base=（SElemType?*）realloc（S.base（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
		?if（!S.base）
			?return?ERROR;//存儲分配失敗
		?S.top=S.base+S.stacksize;
		?S.stacksize+=STACKINCREMENT;
	?}
	?*S.top++=e;
?????return?OK;
}//Push?
Status?Pop（SqStack?&SSElemType?&e）
{
	//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR
	if（S.top==S.base）
		return?ERROR;
	e=*--S.top;
	return?OK;
}//Pop
Status?StackEmpty（SqStack?S）
{//判斷棧是否為空為空返回TRUE否則返回FALSE
	if（S.top==S.base）
		return?TRUE;
	else?return?FALSE;
}

Status?CreateDG（ALGraph?&G）{//建立鄰接表
	int?ivwvex;
	printf（“請輸入課程數目（課程數必須小于20）：“）;
	scanf（“%d“&vex）;
	if（vex>=20）
	{
		printf（“請重新輸入課程數目（課程數必須小于20）：“）;
		scanf（“%d“&vex）;
	}
????G.vexnum=vex;

	printf（“請輸入課程間的先后關系數：“）;
	scanf（“%d“&G.arcnum）;

	printf（“請輸入課程的代表值（課程名的長度小于等于10個字符）:“）;
	for（i=0;i	{
		scanf（“%s“&G.vertices[i].data）;
		G.vertices[i].firstarc?=?NULL;
	}//輸入頂點信息
	printf（“請輸入課程間兩兩間的先后關系：“）;
	for（i=0;i		scanf（“%d%d“&v?&w）;//形式2
		ArcNode?*p=?new?ArcNode;//建立結點
		if（!p）?return?ERROR;
		p->adjvex=w-1;
		p->nextarc=G.vertices[v-1].firstarc;//頂點v的鏈表
		G.vertices[v-1].firstarc=p;//添加到最左邊
	}
	return?OK;
}	?
void?FindInDegree（ALGraph?G）
{//求圖的入度
	ArcNode*?p;
	for（int?i=0;i	{
		p=G.vertices[i].firstarc;
		while（p）
		{?
			for（int?j=0;j				if（p->adjvex==j）
					indegree[j]++;
			p=p->nextarc;
		}
	}
}

Status?TopologicalSort（ALGraph?G）
{?//拓撲排序
??//有向圖G采用鄰接表存儲結構
????SqStack?S1S2;
	ArcNode*?p;
	int?icountk;
	FindInDegree（G）;
	InitStack（S1）;
	InitStack（S2）;
	for（i=0;i		if（!indegree[i]）
		???Push（S1i）;??//把入度為0的壓入棧S1
	count=0;????????????//對輸出頂點計數
	while（!StackEmpty（S1））
	{
		printf（“第%d學期應學的課程:“count+1）;
		while（!StackEmpty（S1））
		{
			Pop（S1i）;
			printf（“%s?“G.vertices[i].data）;//輸出i號頂點
	????????Push（S2i）;?????//把i號頂點壓入棧S2
		}

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

?????文件???????3852??2008-07-11?04:19??教學計劃安排檢驗程序（拓撲排序）.cpp

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

?????????????????3852????????????????????1