graph.cpp

这是一个教学安排管理程序,包括源代码,报告文档,是计算机专业的课程设计

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "graph.h"
#include "queue.h"


Status CreateGraph(Graph &G,int len){
	//通过输入建立一长度为len的有向图
	//若成功建立一有向图返回OK
	//若输入的先修课程代号不在所要学的课程的范围则返回ERROR
	int i,j,k,l;
	char *str;
	G.vertices=(VNode *)malloc(len*sizeof(VNode));
    if(!G.vertices) exit(OVERFLOW);
	G.vexnum=len;
    for(i=0;i<G.vexnum;i++){  //通过给有向图的表结点数组的各表结点的data域赋值，而且v.firstarc=v.tailarc=NULL
		InputVertex(G.vertices[i].data);
	    G.vertices[i].firstarc=G.vertices[i].tailarc=NULL;     
	}
    for(i=0;i<G.vexnum;i++){     //根据preCode插入弧结点
		l=strlen(G.vertices[i].data.preCode);
		if(l==1)
			continue;
		str=G.vertices[i].data.preCode;
		for(k=0;k<l;k+=4){
			for(j=0;j<G.vexnum;j++){    //寻找与先修课程所在顶点的位置
                if(!strncmp(str,G.vertices[j].data.code,3))
					break;
                if(j==G.vexnum-1)
					return ERROR;      //若输入的先修课程代号不在所要学的课程的范围则返回ERROR
			}
			InsertGraph(G,j,i);           //插入弧结点
			str+=4;
		}	
	}
	return OK;
}
Status InsertGraph(Graph &G,int i,int j){
	//成生一弧结点，并链接到在有向图位置为i的顶点所链接的弧结点的末尾
	//该弧的弧头顶点的位置为j,指向NULL
	ArcPtr p;
	MakeArcNode(p,j);
	if(G.vertices[i].firstarc==NULL)
		G.vertices[i].firstarc=G.vertices[i].tailarc=p;
	else{
		G.vertices[i].tailarc->nextarc=p;
	    G.vertices[i].tailarc=p;
	}
	return OK;
}
Status DestroyGraph(Graph &G){
	//销毁有向图G,G不再存在
	int i;
	ArcNode *p,*q;
	for(i=0;i<G.vexnum;i++){     //销毁各顶点所指向的弧结点
		p=G.vertices[i].firstarc;
		for(;p!=NULL;){
			q=p;
            p=p->nextarc;
			FreeArcNode(q);
		}
	}
    free(G.vertices);     //销毁有向图G
	G.vertices=NULL;
	return OK;
}
Status InDegreeGraph(Graph G,int *indegree){ 
	//对各顶点求入度，结果放在indegree为基地址的空间
	//indegree为基地址的空间长为G.vexnum
    int i;
	ArcPtr p;
	for(i=0;i<G.vexnum;i++)      //初始化indegree数组元素为0
		indegree[i]=0;
	for(i=0;i<G.vexnum;i++)      //遍历整个邻接表，求各顶点的入度
		for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
			indegree[p->adjvex]++;
    return OK;
}
Status TopologicalSortGraph(Graph G,VertexType *v){
	//有向图G采用邻接表存储结构
	//对有向图G的顶点进行拓扑排序
    //若拓扑排序成功，则按拓扑排序的顺序将对应的顶点信息放在v为基地址的空间，从0位置开始保存(v为基地址的空间长度为G.vexnum），并返回OK
    //若拓扑排序失败，即有向图中含有环，则返回ERROR
    int i,j=0,k,count;
	ArcPtr p;
	Queue Q;
	int *indegree=(int *)malloc(G.vexnum*sizeof(int));   
	if(!indegree) exit(OVERFLOW);
	InDegreeGraph(G,indegree);   //对各顶点求入度indegree[0...vernum-1]
	InitialQueue(Q);           //建零入度顶点队列
    for(i=0;i<G.vexnum;i++) //从顶点数组的头开始找    
		if(!indegree[i])
			EnQueue(Q,i);      //入度为0者进队列
	count=0;                   //对保存顶点计数
	while(!QueueEmpty(Q)){
		DeQueue(Q,i);
		v[j++]=G.vertices[i].data;   //保存i号到数组v
		++count;     //计数加1
		for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc){  //从顶点的第一个弧结点开始找
			                                                 //对i号顶点的每个邻接点的入度减1
			k=p->adjvex;       
			if(!(--indegree[k]))
				EnQueue(Q,k);            //若入度减为0，则进队列
		}
	}
	if(count<G.vexnum){
		free(indegree);
		DestroyQueue(Q);
		return ERROR;
	}
	free(indegree);
	DestroyQueue(Q);
	return OK;
}