#include
#include
#define?stack_init_size?100?//存儲空間初始分配量
#define?createstack?10?//存儲空間分配增量
#define?max_vertex_num?20
typedef?int?Status;
typedef?int??SElemType;//棧類型
typedef?struct
{
	SElemType?*base;//棧底指針
	SElemType?*top;//棧頂指針
	int?stacksize;//棧大小
}SqStack;//順序棧
typedef?struct?ArcNode
{
????int?adjvex;//該弧所指向的頂點的位置
	struct?ArcNode?*nextarc;//指向第一條依附該頂點的弧的指針
}ArcNode;//頂點的弧
typedef?struct?VNode//頂點
{
	char?data[10];
	ArcNode?*firstarc;
}AdjList[max_vertex_num];//最大頂點數?頭結點
typedef?struct
{
	AdjList?vertices;
	int?vexnumarcnum;//圖的當前頂點數和弧數
}ALGraph;
int?indegree[20]={0};//存儲圖的入度的全局變量數組
Status?InitStack（SqStack?&S）//將棧分配存儲空間，并對top和base賦值
{???//構造一個空棧S
	S.base=（SElemType?*）malloc（stack_init_size*sizeof（SElemType））;//將malloc函數返回的指針強制轉化成一個ElemType指針
	if（!S.base）
		return?0;//內存分配失敗
	S.top=S.base;
	S.stacksize=stack_init_size;
	return?1;
}
Status?Push（SqStack?&SSElemType?e）
{?????//插入元素e為新的棧頂元素
	?if（S.top-S.base>=S.stacksize）
	?{???//棧滿，追加存儲空間
		?S.base=（SElemType?*）realloc（S.base（S.stacksize+createstack）*sizeof（SElemType））;
		?if（!S.base）
			?return?0;//存儲分配失敗
		?S.top=S.base+S.stacksize;
		?S.stacksize+=createstack;
	?}
	?*S.top++=e;
?????return?1;
}
Status?Pop（SqStack?&SSElemType?&e）
{???//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1，否則返回0
	if（S.top==S.base）
		return?0;
	e=*--S.top;
	return?1;
}
Status?StackEmpty（SqStack?S）
{???//判斷棧是否為空，為空返回1，否則返回0
	if（S.top==S.base）
		return?1;
	else?return?0;
}
Status?CreateALGraph（ALGraph?&G）
{???//建立鄰接表
????int?isemester_numvwvex;
????printf（“請輸入學期數目:“）;
????scanf（“%d“&semester_num）;
????if（semester_num>8）
	{
	?????printf（“請重新輸入學期數目:“）;
	?????scanf（“%d“&semester_num）;
	}
	printf（“請輸入課程數目（課程數必須小于20）:“）;
	scanf（“%d“&vex）;
	if（vex>=20）
	{
		printf（“請重新輸入課程數目（課程數必須小于20）:“）;
		scanf（“%d“&vex）;
	}
	G.vexnum=vex;
????printf（“請輸入課程間的先后關系數（總邊數）:“）;
	scanf（“%d“&G.arcnum）;
????for（i=0;i	{
		printf（“請輸入%d課程的名字（課程名的長度小于等于10個字符）:“i+1）;
		scanf（“%s“&G.vertices[i].data）;
		G.vertices[i].firstarc?=?NULL;
	}
	for（i=0;i	{
		printf（“請輸入課程間兩兩間的先后關系（用整數表示整數與整數之間用逗號隔開）:“）;
		scanf（“%d%d“&v&w）;
		ArcNode?*p=new?ArcNode;//建立結點
		if（!p）?return?0;
		p->adjvex=w-1;
		p->nextarc=G.vertices[v-1].firstarc;//頂點v的鏈表
		G.vertices[v-1].firstarc=p;//添加到最左邊
	}
	return?1;
}
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）;//初始化棧S1
	InitStack（S2）;//初始化棧S2
	for（i=0;i		if（!indegree[i]）
		???Push（S1i）;//把入度為0的壓入棧S1
	count=0;//對輸出頂點計數
	while（!StackEmpty（S1））
	{
		printf（“第%d學期應學的課程:“cou

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

?????文件???????4267??2018-07-12?15:25??排課系統\main.cpp

?????目錄??????????0??2018-12-19?08:35??排課系統

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

?????????????????4267????????????????????2