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

《数据结构(拓扑排序).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程名称数据结构课题名称拓扑排序专业班级学号姓名指导教师　　2011年6月16日湖南工程学院课程设计任务书一．设计内容：问题：拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需一定的课时，而各学期的总课时不能超过上限。测试数据学期课时上限数：350各课程所需学时：48课程先、后修关系如图：194212101136578二．设计要求：课程设计报告内容

2、说明1)需求分析程序的功能；输入输出的要求。2)概要设计程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得

3、体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录参考书目；源程序清单（带注释）目录封面………………………………………………………………………1任务书……………………………………………………………………1目录………………………………………………………………………3正文………………………………………………………………………4一、需求分析………………………………………………………41.1程序的功能………………………………………………41.2输入输出

4、的要求…………………………………………4二、概要设计………………………………………………………42.1采用邻接链表作为有向圈的存贮结构…………………42.2基本设计…………………………………………………4三、主要功能的实现………………………………………………53.1设计拓扑排序的步骤……………………………………53.2拓扑排序问题的特征……………………………………63.3算法设计…………………………………………………63.4算法编码实现……………………………………………6四、调试分析以及设计体会…………………

5、……………………64.1调试分析…………………………………………………74.2设计体会…………………………………………………7五、使用说明………………………………………………………8附录Ⅰ……………………………………………………………………9附录Ⅱ…………………………………………………………………9一、需求分析1.1程序的功能排课问题是现在各个学校必须面临的一个问题。而且随着近年来学生规模的扩招,教育机构的复杂化，课程各类的多样化，排课的问题越来越难。尽管目前对排课采用了程序设计的计算机智能排课系统，但是仍然

6、存在着这样或者那样的问题。最为突出的一个问题，比如，有一些排课方案,看上去完美无缺,或者效率比较高,甚至达到了最优解，但是具体地去实施的时候，发现整个课程的设计方案有着大的漏洞，经常出现的问题是，排课的拓扑图出现了一些环，以至于进入了死循环。该课程设计的目的就是针对于如何检测环的存在而避免错误的排课方案。本文采用的算法是基于拓扑序列的拓扑排序算法对特定条件的排课问题提出的一种解决方案，具体的实验结果是展示出一个符合条件的课程拓扑序列，整个算法的设计与实现过程将要用到邻接表,堆栈等数据结构等等。1.2输入输出的

7、要求(1)输入：学期课时，一学期的课时上线，每门课的课程号，直接先修关系的课程号。(2)输出参数：若无解，则报告错误信息；否则输出教学计划。二、概要设计2.1采用邻接链表作为有向圈的存贮结构链表由两部分组成，一部分是表头结点。反映各门课程的编号、该课程的前趋课程数及后继课程的首地址。形式如下：编号入度指针另一部分是表结点，反映各课程的链接关系，形式如下：编号指针2.2基本设计以顶点代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图的邻接表结构并统计得到初始的入度为0的顶点，利用拓扑排序算法来进行课程安

8、排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课程的先决条件是学完它的全部先修课程，如“3”课程就必须在它的两门先修课程“1”和“2”之后，“9”课程则可以在后修课程之前随时安排，因为它是基础课程。通常我们把这种顶点代表活动，边代表活动间先后关系的有向图称作顶点活动网，简称Aov网。—个Aov网应该是—个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动