使用C 实现的教学计划安排检验程序（拓扑排序）.

教学计划安排检验程序（拓扑排序），按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程

#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