中南大学数据结构课程设计报告详解.doc

数据结构与算法课程设计 课题名称： 课程管理系统编制 学 院： 班 级： 学 号： 学生姓名： 指导老师： 完成日期： 2014年7月11日 目录 一、需求分析 3 1.1实验内容及要求 3 1.2问题分析 3 二、概要设计 4 2.1程序的模块组成 4 2.2模块的层次结构及调用关系 4 2.3主要函数的流程图 5 三、详细设计 9 3.1头文件 9 3.2全局变量的exten声明和子函数的声明 9 3.3各个结构体定义 10 3.4主函数和全局变量的定义 11 3.5图的建立 12 3.6栈操作 13 3.7入度统计 14 3.8拓扑排序的两种输出方式 15 四、调试分析 19 4.1测试数据内容 19 4.2用户使用说明 20 4.3调试时存在的问题及改进 22 五、课设总结 23 5.1问题及解决办法 23 5.2心得体会 23 六、附录 24 6.1参考书籍 24 一、需求分析 1.1实验内容及要求 [问题描述] 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 [基本要求] （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 （3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 1.2问题分析 编制教学计划，需要满足涉及到的课程都要给学完。由于课程有基础知识和深入知识的关系，所以课程间的学习有前后关系，用AOV网是最合适的。根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，利用先修关系将课程排序，再根据两种要求的课程编排策略输出，同时生成含有课程排序的.txt文件，最终解决问题。 对AOV网进行拓扑排序即可以得出结果。而对AOV网进行拓扑排序有两种情况：广度优先和深度优先。在进行深度优先遍历时，我们要考虑到一种情况。例如：高等数学和程序设计基础是并列的两门学科，他们之间没有前续后继的关系，可以同时进行学习。高等数学是离散数学和数据结构的基础课程，数据结构又是操作系统的基础课程。程序设计基础也是是数据结构的基础课程，数据结构又是语言的设计和分析的基础课程。如果按照深度优先遍历的话就有可能将上面几门课程排成：程序设计基础，数据结构，操作系统，语言的设计和分析，高等数学，离散数学。这样的教学计划很明显不符合实际教学的需要。因此我在本次课设中选择广度优先遍历，将高等数学和程序设计基础先学，再学其他后继课程。 对于两种编排策略，一个是课程尽可能集中在前几个学期，也就是说在不超过学期额定学分的情况下，尽可能的多排课程。另一个是使学生各学期学习负担尽量均匀，则要在第一个条件的前提下，再加上一个条件，在一个学期中排的课程总数，不超过每学期的课程均值（总课程数÷总学期数）。 二、概要设计 2.1程序的模块组成 LocateVex（）：图的邻接表存储的基本操作 CreateGraph（）：图的建立 FindInDegree（）：求顶点的入度 InitStack（）：构造一个空栈 ClearStack（）：清空栈 StackEmpty（）：判断是否为空栈 Pop（）：出栈 Push（）：入栈 TopologicalSort（）：输出G顶点的拓扑排序结果 2.2模块的层次结构及调用关系 （1）本程序包括2个模块：主程序模块和拓扑排序模块。 （2）调用关系 2.3主要函数的流程图 （1）LocateVex（）：图的邻接表存储的基本操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 （2）CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。 （1） （2） （3）FindInDegree（）：求顶点的入度。