(教学计划编制问题1.docVIP

******************* 实践教学 ******************* 兰州理工大学 2011年春季学期 算法与数据结构课程设计 题 目： 专业班级： 姓 名： 学 号： 指导教师： 成 绩： 摘要 在本设计实验中，采用的是顺序表存储的方式，根据不同科目的先修关系与教学计划的安排，来设计教学计划编制程序。 教学计划编制问题的目的是解决教学计划的要求与课程之间先修关系的冲突。首先定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程AOV网教学计划在编制的过程中，有一个层次的关系。比如说：数值分析必须在高等数学学完之后才可以学习，数据结构必须要在学习了一两门程序设计语言之后才可以学习。也就是说有的课程必须要在学习完了某些课程之后才可以学习。编制教学计划，当然涉及到的课程都要给学完。所以我们可以将所以的课程编制成一张图，然后遍历图。由于课程有前续后继的关系，所以用AOV网是最合适。对AOV网进行拓扑排序即可以得出结果。对AOV网进行拓扑排序有两种情况：广度优先和深度优先。在进行深度优先周游时，我们要考虑到一种情况。例如：高等数学和C语言编程是并列的两门学科，他们之间没有前续后继的关系，可以同时进行学习。高等数学是数值分析和电子电路的基础课程，电子电路又是模拟电子电路的基础课程。C语言编程是数据结构的基础课程，数据结构是算法设计与分析的基础课程。如果按照深度优先周游的话就有可能将上面几门课程排成：C语言程序设计，数据结构，算法设计与分析，高等数学，电子电路，模拟电子电路。这样的教学计划很明显不符合实际教学的需要。因此我们应该进行广度优先周游，将高等数学和C语言程序设计先学，再学其他后继课程。。LocateVex（）CreateGraph（）：构造生成树 Display（）：输出图的邻接矩阵 FindInDegree（）：求顶点的入度 InitStack（）：构造一个空栈 ClearStack（）：清空栈 StackEmpty（）：判断是否为空栈 Pop（）：出栈 Push（）：入栈 TopologicalSort（）：输出G顶点的拓扑排序结果 2.2模块的层次结构及调用关系 2.3模块的主要功能 见“详细设计”－“主要函数流程图” 2.4数据结构和数据库结构 储存的数据为结构体类型数组，以及结构体单链表结点类型。 1）typedef struct ArcNode 弧所指定点位置 指向下一条弧的指针 网的权值指针 int struct InfoType 2）typedef struct 顶点信息 第一个表结点的地址 VertexType ArcNode 三．主要功能的实现 3.1采用C语言定义相关的数据类型。 其中包括字符常量，整型，字符型，字符串型，typedef 定义的类型，结构体型，单链表节点类型，结构体数组。 3.2主要函数的流程图 1.LocateVex（） 图CreateGraph（） 图Display（） 2.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。 3.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。 4.FindInDegree（）：求顶点的入度。 图FindInDegree（） 图InitStack（） 5.InitStack（）：构造一个空栈。 6.ClearStack（）：清空栈。 7.StackEmpty（）：判断栈是否为空。若栈S为空栈，则返回TRUE，否则返回FALSE。 Pop（）：出栈。若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。 Push（）：入栈。插入元素e为新的栈顶元素。 10.TopologicalSort（）：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR。  3.3画出各函数的调用关系图  四、程序调试 4.1测试数据： 准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。 准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。 数据如下：学期总数：6； 学分上限：10； 该专业共开设课数：12 课程号：从C01到C12； 学分顺序：2，3，4，3，2，3，4，4，7，5