教学计划编制问题.docVIP

数据结构与算法分析 课程设计(论文) 设计（论文）题目 教学计划编制问题 学院名称 管理科学学院 专业名称 信息与计算科学专业 学生姓名 王进 学生学号 201307020106 任课教师 乐千桤老师 设计（论文）成绩 教务处制 2014 年 12 月 31 日 教学计划编制问题 摘 要 此次课程设计，我们选择了教学计划编制的课题。大学的每个专业都要制订教学计划，一个好的教学计划可以在同学们的时间安排与学习任务安排之间取得平衡。同学们可以按照自己的个性化需求自定义课程学习过程，这样可以提高同学们的学习积极性。我们小组认为各种课程是有先后顺序的，这个可以用数据结构中的有权图来描述，而这个顺序正好可以用拓扑序列描述。于是我们进行程序设计，并制作了一个选课的小程序。因为个人能力以及时间关系，我们的课题相当于只是完成了骨架的设计，还有很多地方都值得进一步修改。 关键词：栈；AOV网；图函数；拓扑排序；main()函数的调用 目录 第1章 问题及要求 1 1.1 问题描述 1 1.2问题要求 1 第2章 问题的要点及要求 2 2.1 问题要点 2 2.2我的分工 2 第3章 函数功能和算法 3 3.1 函数功能 3 3.2 函数名及功能 3 第4章 程序代码 4 4.1 源程序………….………………………………………………………………………………………………………………….…..4 4.2 演示结果 6 第5章 说明 9 第6章 参考文献 10 第1章 问题及要求 1.1问题描述： 大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 1.2问题要求： （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号； （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀(以下简称策略一)；二是使课程尽可能地集中在前几个学期中(策略二)； （3）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中. 第2章 问题的要点及分工 2.1问题要点： 根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。 程序模块及可实现的功能简介： 1)图的邻接表的存储表示，即结构体的定义； 2)利用前插法，建立图的邻接链表； 3)输出图的顶点和边； 4)结合入度并通过栈实现拓扑排序； 5)根据用户选择策略:学分上限决定一种策略;平均学分以及修正值决定另一种策略;其中R[ ]中存储的是经过拓扑排序后的课程先后顺序。 6）输出课程安排到文件。 2.2我的分工： 我负责结合入度并通过栈实现拓扑排序，其他任务详情组员曹昌杰和苗佳佳。 第3章 函数功能与算法 3.1函数功能： 以下是分点详述功能实现： (1)根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体。 (2)创建图函数CreateGraph(G)：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程 (3)输出图函数Display(G)：将图的信息即顶点和弧边输出。 (4)拓扑排序TopologicalOrder (G)：将课程排序后并决定出每学期所学课程。 (5)求顶点入度FindIndegree(G)：拓扑排序的前提，知道顶点的入度。 (6)策略选择Choice(G,R)：进行策略制定。 (7)输出函数print(R)：根据拓扑排序后的序列对课程编号进行适当划分。 (8)输出调用Conversion(str)：把课程编号与课程名称对应起来。 (9)编写main()：实现每个函数的调用。 (10)对栈的分配以及进栈和出栈实现，把栈和拓扑排序相结合完成相应的程序。 3.2函数名及功能： 我所负责的程序的功能如下： TopologicalOrder (G)：拓扑排序依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegree[i]中（i=0…n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++），堆栈是否为空？，n个顶点全输出，依次