教学计划安排检验程序拓扑排序报告书.docx
《教学计划安排检验程序拓扑排序报告书.docx》由会员分享,可在线阅读,更多相关《教学计划安排检验程序拓扑排序报告书.docx(16页珍藏版)》请在冰点文库上搜索。
教学计划安排检验程序拓扑排序报告书
设计题目:
示例数据:
输入:
学期数:
5,课程数:
12,课程间的先后关系数:
16,课程的代表值:
v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。
课程间两两间的先后关系:
v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6
输出:
第1学期应学的课程:
v1v9
第2学期应学的课程:
v2v4v10v11
第3学期应学的课程:
v3v6v12
第4学期应学的课程:
v5v8
第5学期应学的课程:
v7
一需求分析
1.1引言
通常,这样的线性序列称为满足拓扑次序(TopologicalOrder)的序列,简称拓扑序列。
简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
离散数学中关于偏序和全序的定义:
若集合X上的关系是R,且R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。
设R是集合X上的偏序(PartialOrder),如果对每个x,y属于X必有xRy或yRx,则称R是集合X上的全序关系。
比较简单的理解:
偏序是指集合中只有部分成员可以比较,全序是指集合中所有的成员之间均可以比较。
一般应用:
拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。
例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。
为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。
1.2拓扑排序的了解
.问题的描述
在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序。
拓扑排序可以应用于教学计划的安排,根据课程之间的依赖关系,制定课程安排计划。
按照用户输入的课程数,课程间的先后关系数目以及课程间两两间的先后关系,程序执行后会给出符合拓扑排序的课程安排计划
.拓扑排序进行教学计划安排检验理论基础
为实现对无权值有向图进行拓扑排序,输出拓扑序列,先考虑如何存储这个有向图。
拓扑排序的过程中要求找到入度为0的顶点,所以要采用邻接表来存储有向图,而要得到邻接表,则先要定义有向图的邻接矩阵结构,再把邻接矩阵转化成邻接表。
在具体实现拓扑排序的函数中,根据规则,当某个顶点的入度为0(没有前驱顶点)时,就将此顶点输出,同时将该顶点的所有后继顶点的入度减1,为了避免重复检测入度为0的顶点,设立一个栈St,以存放入度为0的顶点。
.拓扑排序算法voidTopologicalSort(ALGraphG),大体思想为:
1)遍历有向图各顶点的入度,将所有入度为零的顶点入队列;
2)队列非空时,输出一个顶点,并对输出的顶点数计数;
3)该顶点的所有邻接点入度减一,若减一后入度为零则入队列;
4)重复2)、3),直到队列为空,若输出的顶点数与图的顶点数相等则该图可拓扑排序,否则图中有环。
1.3查阅相关资料,完成程序的实现
二总体设计
拓扑排序:
三详细设计
3.1算法设计分析
拓扑排序时有向图的一种重要运算。
在课表排序中,每门课都有多种关系:
、
(一)先后关系,即必须在一门课学完后,才能开始学习另一门课;
(二)在一类课之间没有次序要求,即两门课可以同时学习,互不影响。
将AOV网络中的各个顶点排列成一个线性有序序列,使得所有的要求的前趋、后趋关系都能得到满足。
在AOV网络进行拓扑排序的方法:
(一)从中选择一个没有前趋的顶点,并把它输出;
(二)从网络中删去该顶点和从该顶点出发的所有有向边;
重复执行上述两步,直到网中所有的顶点都被输出
3.2源代码
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineSTACKINCREMENT10
#defineMAX_VERTEX_NUM20
#defineSTACK_INIT_SIZE100
typedefintStatus;
typedefintSElemType;
intindegree[20]={0};
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
typedefstructArcNode{
intadjvex;
structArcNode*nextarc;
}ArcNode;
typedefstructVNode{
chardata[10];
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
StatusInitStack(SqStack&S)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!
S.base)
returnERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush(SqStack&S,SElemTypee)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!
S.base)
returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPop(SqStack&S,SElemType&e)
{
if(S.top==S.base)
returnERROR;
e=*--S.top;
returnOK;
}
StatusStackEmpty(SqStackS)
{
if(S.top==S.base)
returnTRUE;
elsereturnFALSE;
}
StatusCreateDG(ALGraph&G)
{
inti,l,v,w,vex;
printf("\t请输入学期数目(小于等于8):
\t");
scanf("%d",&l);
if(l>8)
{
printf("\tWarning!
\n\t学期数目必须小于等于8!
请重新输入:
");
scanf("%d",&l);
}
printf("\t请输入课程数目(小于20):
");
scanf("%d",&vex);
if(vex>=20)
{
printf("\tWarning!
\n\t课程数目必须小于20!
请重新输入:
");
scanf("%d",&vex);
}
G.vexnum=vex;
printf("\t请输入课程间的先后关系数:
");
scanf("%d",&G.arcnum);
printf("请输入课程的代表值(课程名的长度小于等于10个字符):
");
for(i=0;i{
scanf("%s",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("请注意v1=1,v2=2,v3=3,v4=4,c5=5,v6=6,v7=7,v8=8,v9=9,v10=10,v11=11,v12=12\n");
printf("请输入课程间两两间的先后关系:
");
for(i=0;iscanf("%d%d,",&v,&w);
ArcNode*p=newArcNode;
if(!
p)returnERROR;
p->adjvex=w-1;
p->nextarc=G.vertices[v-1].firstarc;
G.vertices[v-1].firstarc=p;
}
returnOK;
}
voidFindInDegree(ALGraphG)
{
ArcNode*p;
for(inti=0;i{
p=G.vertices[i].firstarc;
while(p)
{
for(intj=0;jif(p->adjvex==j)
indegree[j]++;
p=p->nextarc;
}
}
}
StatusTopologicalSort(ALGraphG)
{
SqStackS1,S2;
ArcNode*p;
inti,count,k;
FindInDegree(G);
InitStack(S1);
InitStack(S2);
for(i=0;iif(!
indegree[i])
Push(S1,i);
count=0;
while(!
StackEmpty(S1))
{
printf("第%d学期应学的课程:
",count+1);
while(!
StackEmpty(S1))
{
Pop(S1,i);
printf("%s",G.vertices[i].data);
Push(S2,i);
}
printf("\n");
count++;
while(!
StackEmpty(S2))
{
Pop(S2,i);
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!
(--indegree[k]))
Push(S1,k);
}
}
}
if(countreturnERROR;
elsereturnOK;
}
intmain()
{
printf("***********************************************************************\n");
printf("教学计划检验程序(拓扑排序)\n\n");
printf("v1程序设计基础v2离散数学v3数据结构\n");
printf("v4汇编语言v5语言设计与分析v6计算机原理\n");
printf("v7编译原理v8操作系统v9高等数学\n");
printf("v10线性代数v11普通物理v12数值分析\n\n");
printf("***********************************************************************\n");
ALGraphT;
CreateDG(T);
TopologicalSort(T);
return0;
}
3.3调试与分析
1.运行程序打开界面如下图,并根据提示,输入学期数目:
2.输入出错时显示如下:
3.输入正确则继续,根据界面提示输入课程的代表值:
4.根据界面提示输入课程间两两间的先后关系:
5输入课程间两两间的先后关系后,则输出每学期应学的课程:
6完美运行结果:
四总结
经过近三个星期的不断的学习与努力,有收获,有挫折,终于完成了《教学计划安排检验程序(拓扑排序)》的数据结构课程设计。
从最开始确定程序设计题目到算法基本完成,从运行程序中逐步完善再到设计报告说明书的结束,每一步都是一种新的挑战,也是进步的重要历程。
这次课程设计的完成,我意识到自己掌握的知识还是远远不够的,在接下来的学习期间,我会尽最大的可能去拓宽自己在计算机编程方面知识,并在不断地实践中运用自己的理论,使得理论与实践结合,提高自己的技术与能力。
通过去图书馆查看相关的资料和书籍以及在网上与他人探讨,通过自己独立的思考,使程序设计一步步完善起来。
我也切实认识到做程序设计必然会遇到许许多多不曾遇到过的难题,比如此次程序设计中,要查阅相关资料,明白拓扑排序的定义以及实现拓扑排序的代码,认真细致的分析题目,根据题目得到拓扑排序的排列序列,在多种思路中寻找到时间复杂度最小的方法,实现程序的最优化……通过这次课程设计我受益匪浅,从中明白了一个道理:
计算机程序设计只要认认真真的用心去做,其中遇到任何的问题都可以一一解决。
在这次课程设计中,收获的不仅仅是技术,本次程序设计使我不仅深化理解了教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,并且在总体分析、总体结构设计、算法设计、课程设计、上机操作及程序调试等基本技能方面受到了综合训练,使我在今后的编程读写中更加的得心应手。
在今后的不断学习中,不断锤炼自己的技能,使得自己更加适应现在这个信息化高速发展的时代,在未来的舞台更好的展现自己。
总的来说,在程序设计过程中,每一次的小成功都会有一份喜悦,程序的完成都是自己努力的结晶。
最后,感谢指导老师不厌其烦的教导,学哥学姐的建议,网上热心人得帮助。
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版).北京:
清华大学出版社,2013.
[2]谭浩强编著.C程序设计(第二版).北京:
清华大学出版社,1999.
[3]温秀梅,丁学钧编著.VisualC++面向对象程序设计教程与实验(第二版).北京:
清华大学出版社,2013
[4]机械工业出版社.拓扑学[M].