数据结构(拓扑排序).doc

课程设计报告课程名称数据结构课题名称拓扑排序专业班级学号姓名指导教师 :问题:拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的,而有的则有先修后修的限定。试设计相应的课程设置程序,实现对某专业各学期的课程的排布,其中每门课需一定的课时,而各学期的总课时不能超过上限。测试数据学期课时上限数:350各课程所需学时:48课程先、后修关系如图:1942**********:课程设计报告内容说明1)需求分析程序的功能;输入输出的要求。2)概要设计程序的模块构成以及模块之间的层次结构、各模块的调用关系;每个模块的功能;课题涉及的数据结构和数据库结构;即要存储什么数据,这些数据是什么样的结构,它们之间有什么关系等。3)详细设计采用C语言定义相关的数据类型;写出各模块的类C码算法;画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会测试数据:准备典型的测试数据和测试方案,包括正确的输入及输出结果和含有错误的输入及输出结果;程序调试中遇到的问题以及解决问题的方法;课程设计过程经验教训、心得体会。5)使用说明用户使用手册:说明如何使用你编写的程序,详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录参考书目;源程序清单(带注释)目录封面………………………………………………………………………1任务书……………………………………………………………………1目录………………………………………………………………………3正文………………………………………………………………………4一、需求分析…………………………………………………………………………………………………………………………………………………4二、概要设计……………………………………………………………………………………………………………………………4三、主要功能的实现…………………………………………………………………………………………………………………………………………………………………………………………………………………………6四、调试分析以及设计体会……………………………………………………………………………………………………………………………………………7五、使用说明………………………………………………………8附录Ⅰ……………………………………………………………………9附录Ⅱ…………………………………………………………………9一、。而且随着近年来学生规模的扩招,教育机构的复杂化,课程各类的多样化,排课的问题越来越难。尽管目前对排课采用了程序设计的计算机智能排课系统,但是仍然存在着这样或者那样的问题。最为突出的一个问题,比如,有一些排课方案,看上去完美无缺,或者效率比较高,甚至达到了最优解,但是具体地去实施的时候,发现整个课程的设计方案有着大的漏洞,经常出现的问题是,排课的拓扑图出现了一些环,以至于进入了死循环。该课程设计的目的就是针对于如何检测环的存在而避免错误的排课方案。本文采用的算法是基于拓扑序列的拓扑排序算法对特定条件的排课问题提出的一种解决方案,具体的实验结果是展示出一个符合条件的课程拓扑序列,整个算法的设计与实现过程将要用到邻接表,堆栈等数据结构等等。(1)输入:学期课时,一学期的课时上线,每门课的课程号,直接先修关系的课程号。(2)输出参数:若无解,则报告错误信息;否则输出教学计划。二、,一部分是表头结点。反映各门课程的编号、该课程的前趋课程数及后继课程的首地址。形式如下:编号入度指针另一部分是表结点,反映各课程的链接关系,形式如下:,弧代表课程的先后修关系,按表中条件建立有向无环图的邻接表结构并统计得到初始的入度为0的顶点,利用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里,课程代表活动,学****每门课程的先决条件是学完它的全部先修课程,如“3”课程就必须在它的两门先修课程“1”和“2”之后,“9”课程则可以在后修课程之前随时安排,因为它是基础课程。通常我们把这种顶点代表活动,边代表活动间先后关系的有向图称作顶点活动网,简称Aov网。—个Aov网应该是—个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都